OpenASIP 2.2
Loading...
Searching...
No Matches
BitTrie.icc
Go to the documentation of this file.
1/*
2 Copyright (c) 2002-2016 Tampere University.
3
4 This file is part of TTA-Based Codesign Environment (TCE).
5
6 Permission is hereby granted, free of charge, to any person obtaining a
7 copy of this software and associated documentation files (the "Software"),
8 to deal in the Software without restriction, including without limitation
9 the rights to use, copy, modify, merge, publish, distribute, sublicense,
10 and/or sell copies of the Software, and to permit persons to whom the
11 Software is furnished to do so, subject to the following conditions:
12
13 The above copyright notice and this permission notice shall be included in
14 all copies or substantial portions of the Software.
15
16 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
19 THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21 FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
22 DEALINGS IN THE SOFTWARE.
23 */
24/*
25 * @file BitTrie.icc
26 *
27 * Implementation of BitTrie class.
28 *
29 * Created on: 2.2.2016
30 * @author Henry Linjamäki 2016 (henry.linjamaki-no.spam-tut.fi)
31 * @note rating: red
32 */
33
34#include "BitTrie.hh"
35
36#include <cassert>
37#include <list>
38
39#include "MathTools.hh"
40#include "Conversion.hh"
41
42/**
43 * Constructs an empty bit trie where patterns to be stored are read starting
44 * from LSB.
45 */
46template<class DataType, class ValueType>
47inline
48BitTrie<DataType, ValueType>::BitTrie() {
49}
50
51
52/**
53 * Constructs an empty bit trie where patterns to be stored are read in order
54 * of choice.
55 *
56 * @param bitReadLeftToRight If true, patterns are read MSB first. Otherwise,
57 * they are read LSB first.
58 */
59template<class DataType, class ValueType>
60inline
61BitTrie<DataType, ValueType>::BitTrie(bool bitReadLeftToRight)
62 : bitReadLeftToRight_(bitReadLeftToRight) {
63}
64
65
66/**
67 * Private constructor.
68 */
69template<class DataType, class ValueType>
70inline
71BitTrie<DataType, ValueType>::BitTrie(
72 bool bitReadLeftToRight,
73 BitTrie& parent)
74 : bitReadLeftToRight_(bitReadLeftToRight), parent_(&parent) {
75
76
77}
78
79
80/**
81 * Desctructor.
82 */
83template<class DataType, class ValueType>
84inline
85BitTrie<DataType, ValueType>::~BitTrie() {
86 for (auto& node : node_) {
87 delete node;
88 node = nullptr;
89 }
90 delete data_;
91 data_ = nullptr;
92}
93
94
95/**
96 * Returns count where the given pattern overlaps with the patterns stored.
97 *
98 * @param bits The pattern.
99 * @return The count.
100 */
101template<class DataType, class ValueType>
102inline
103unsigned
104BitTrie<DataType, ValueType>::frequency(
105 const BitTrie<DataType, ValueType>::BitVector& bits) const {
106
107 if (width(bits) == 0) {
108 return frequency_;
109 }
110 BitTrie* nextNode = node_[nextBit(bits)];
111 if (nextNode) {
112 return nextNode->frequency(stripBit(bits));
113 } else {
114 return 0;
115 }
116}
117
118
119/**
120 * Return true if the trie has the exact bit pattern.
121 */
122template<class DataType, class ValueType>
123inline
124bool
125BitTrie<DataType, ValueType>::check(
126 const BitTrie<DataType, ValueType>::BitVector& bits) const {
127
128 const BitTrie* found = findNode(bits);
129
130 if (found == nullptr) {
131 return false;
132 }
133 if (isRootNode(*found)) {
134 return false;
135 }
136
137 return nodeTerminatesPattern(*found);
138}
139
140
141/**
142 * Inserts new pattern into the trie with default constructed data.
143 *
144 * @param bits The bit pattern to add
145 * @return True, if the pattern is added to the trie. Otherwise, returns false
146 * and the pattern pattern is not added.
147 */
148template<class DataType, class ValueType>
149inline
150bool
151BitTrie<DataType, ValueType>::insert(
152 BitTrie<DataType, ValueType>::BitVector bits) {
153
154 return insert(bits, DataType());
155}
156
157
158/**
159 * Inserts new pattern into the trie and attaches the given data to it.
160 *
161 * @param bits The bit pattern to add
162 * @return True, if the pattern is added to the trie. Otherwise, returns false
163 * and the pattern pattern is not added.
164 */
165template<class DataType, class ValueType>
166inline
167bool
168BitTrie<DataType, ValueType>::insert(
169 BitTrie<DataType, ValueType>::BitVector bits,
170 const DataType& data) {
171
172 if (isRootNode(*this) && check(bits)) {
173 return false;
174 }
175 if (width(bits) == 0 && isRootNode(*this)) {
176 return false;
177 }
178
179 if (width(bits) == 0) {
180 frequency_++;
181 assert(nodeTerminatesPattern(*this));
182 if (data_ == nullptr) {
183 data_ = new DataType(data);
184 } else {
185 *data_ = data;
186 }
187 return true;
188 }
189
190 BitTrie*& node = node_[nextBit(bits)];
191 if (node == nullptr) {
192 node = new BitTrie(bitReadLeftToRight_, *this);
193 }
194 assert(node_[nextBit(bits)] != nullptr);
195 assert(node_[nextBit(bits)]->parent_ == this);
196 assert(node_[nextBit(bits)] != this);
197 frequency_++;
198 return node->insert(stripBit(bits), data);
199}
200
201
202/**
203 * Erases the given exact pattern from the trie.
204 *
205 * Data associated to the pattern is deleted.
206 *
207 * @return Returns true if the given pattern was erased from the trie.
208 * Otherwise, returns false (i.e. trie does not have the pattern).
209 *
210 */
211template<class DataType, class ValueType>
212inline
213bool
214BitTrie<DataType, ValueType>::erase(
215 BitTrie<DataType, ValueType>::BitVector bits) {
216
217 if (parent_ == nullptr && !check(bits)) {
218 return false;
219 }
220
221 if (width(bits) == 0) {
222 if (parent_ == nullptr) {
223 return false;
224 }
225 if (frequency_) frequency_--;
226 return true;
227 }
228
229 BitTrie*& node = node_[nextBit(bits)];
230 if (node) {
231 if (node->erase(stripBit(bits))) {
232 frequency_--;
233 if (node->frequency_ == 0) {
234 delete node;
235 node = nullptr;
236 }
237 }
238 return true;
239 } else {
240 return false;
241 }
242}
243
244
245/**
246 * Returns shortest unambiguous pattern in the trie.
247 *
248 * In a case where there is multiple patterns of same length, the smallest in
249 * the binary value is returned.
250 */
251template<class DataType, class ValueType>
252inline
253typename BitTrie<DataType, ValueType>::BitVector
254BitTrie<DataType, ValueType>::uniqueUnusedPrefix() const {
255
256 return uniqueUnusedPrefixImpl(*this);
257}
258
259
260/**
261 * Returns data associated with the bit pattern.
262 *
263 * @param bits The pattern as key to the data
264 * @return The data stored with one of the insert() methods.
265 * @exception KeyNotFound If the trie does not have the given pattern (bits).
266 */
267template <class DataType, class ValueType>
268inline DataType&
269BitTrie<DataType, ValueType>::at(BitTrie<DataType, ValueType>::BitVector bits) {
270 BitTrie* found = findNode(bits);
271 if (found == nullptr) {
272 THROW_EXCEPTION(KeyNotFound, "BitTrie does not have pattern of 0b"
273 + Conversion::toBinary(value(bits), width(bits)) + ".");
274 } else {
275 if (found->data_ == nullptr) {
276 found->data_ = new DataType();
277 }
278 return *found->data_;
279 }
280}
281
282/**
283 * Returns width of the BitVector as reference.
284 */
285template<class DataType, class ValueType>
286inline
287typename BitTrie<DataType, ValueType>::WidthType&
288BitTrie<DataType, ValueType>::width(
289 BitVector& bitVector) {
290
291 return std::get<1>(bitVector);
292}
293
294
295/**
296 * Returns width of the BitVector as constant reference.
297 */
298template<class DataType, class ValueType>
299inline
300const typename BitTrie<DataType, ValueType>::WidthType&
301BitTrie<DataType, ValueType>::width(
302 const BitVector& bitVector) {
303
304 return std::get<1>(bitVector);
305}
306
307
308/**
309 * Returns value of the BitVector as reference.
310 */
311template<class DataType, class ValueType>
312inline
313ValueType&
314BitTrie<DataType, ValueType>::value(
315 BitVector& bitVector) {
316
317 return std::get<0>(bitVector);
318}
319
320
321/**
322 * Returns value of the BitVector as constant reference.
323 */
324template<class DataType, class ValueType>
325inline
326const ValueType&
327BitTrie<DataType, ValueType>::value(
328 const BitVector& bitVector) {
329
330 return std::get<0>(bitVector);
331}
332
333
334/**
335 * Returns next bit in the read order set in the trie.
336 */
337template<class DataType, class ValueType>
338inline
339bool
340BitTrie<DataType, ValueType>::nextBit(
341 const BitVector& bits) const {
342
343 assert(width(bits) > 0);
344 return MathTools::bit(value(bits), bitReadLeftToRight_?(width(bits)-1):0);
345}
346
347
348/**
349 * Returns BitVector with one bit removed from it in the read order set in the
350 * trie.
351 *
352 * The bit to removed is same that would be returned by nextBit() method.
353 */
354template<class DataType, class ValueType>
355inline
356typename BitTrie<DataType, ValueType>::BitVector
357BitTrie<DataType, ValueType>::stripBit(BitVector bits) const {
358
359 assert(width(bits) > 0);
360 width(bits)--;
361 if (!bitReadLeftToRight_) {
362 value(bits) = value(bits) >> 1;
363 }
364 return bits;
365}
366
367
368/**
369 * Looks for trie node by the pattern.
370 *
371 * @param bits The Pattern.
372 * @return Returns pointer to the found node. If not found, return nullptr.
373 */
374template<class DataType, class ValueType>
375inline
376BitTrie<DataType, ValueType>*
377BitTrie<DataType, ValueType>::findNode(const BitVector& bits) {
378 if (width(bits) == 0) {
379 return this;
380 }
381
382 BitTrie* nextNode = node_[nextBit(bits)];
383 if (nextNode == nullptr) {
384 return nullptr;
385 } else {
386 return nextNode->findNode(stripBit(bits));
387 }
388}
389
390
391/**
392 * Const version of findNode() method.
393 */
394template<class DataType, class ValueType>
395inline
396const BitTrie<DataType, ValueType>*
397BitTrie<DataType, ValueType>::findNode(const BitVector& bits) const {
398 if (width(bits) == 0) {
399 return this;
400 }
401
402 const BitTrie* nextNode = node_[nextBit(bits)];
403 if (nextNode == nullptr) {
404 return nullptr;
405 } else {
406 return nextNode->findNode(stripBit(bits));
407 }
408}
409
410
411/**
412 * The implementation of uniqueUnusedPrefix() method.
413 */
414template<class DataType, class ValueType>
415inline
416typename BitTrie<DataType, ValueType>::BitVector
417BitTrie<DataType, ValueType>::uniqueUnusedPrefixImpl(const BitTrie& bitTrie) {
418
419 std::list<const BitTrie*> queue;
420 queue.push_back(&bitTrie);
421 const BitTrie* current = nullptr;
422 bool availableBit = false;
423 while(!queue.empty()) {
424 current = queue.front();
425 queue.pop_front();
426 for (unsigned i = 0; i < 2; i++) {
427 if (current->node_[i]) {
428 assert(current->node_[i]->parent_ == current);
429 queue.push_back(current->node_[i]);
430 } else {
431 availableBit = i;
432 queue.clear(); // break from while clause
433 break;
434 }
435 }
436 }
437
438 BitVector result;
439 value(result) = availableBit;
440 width(result) = 1;
441 assert(current != nullptr);
442
443 while (current->parent_ != nullptr) {
444 for (unsigned i = 0; i < 2; i++) {
445 if (current->parent_->node_[i] == current) {
446 if (current->bitReadLeftToRight_) {
447 value(result) = MathTools::concatenateBits(
448 i, 1, value(result), width(result));
449 } else {
450 value(result) = MathTools::concatenateBits(
451 value(result), width(result), i, 1);
452 }
453 width(result)++;
454 break;
455 }
456 }
457 current = current->parent_;
458 }
459
460 return result;
461}
462
463
464/**
465 * Clears all patterns stored to the trie and deletes any data associated to
466 * them.
467 */
468template<class DataType, class ValueType>
469inline
470void
471BitTrie<DataType, ValueType>::clear() {
472 for (int i = 0; i < 2; i++) {
473 if (node_[i]) {
474 node_[i]->clear();
475 delete node_[i];
476 node_[i] = nullptr;
477 }
478 }
479 frequency_ = 0;
480}
481
482
483/**
484 * Returns the count of stored patterns.
485 */
486template<class DataType, class ValueType>
487inline
488unsigned
489BitTrie<DataType, ValueType>::size() const {
490 assert(parent_ == nullptr && "size(): Valid call only for root node.");
491 return frequency_;
492}
493
494
495/**
496 * Returns longest pattern in the trie that as whole acts as prefix to the
497 * given pattern.
498 */
499template<class DataType, class ValueType>
500inline
501typename BitTrie<DataType, ValueType>::BitVector
502BitTrie<DataType, ValueType>::longestCompletePattern(
503 const BitVector& bits) const {
504
505 // Traverse bit trie until bits or nodes are run out. //
506 if (width(bits) > 0) {
507 const BitTrie* nextNode = node_[nextBit(bits)];
508 if (nextNode) {
509 return nextNode->longestCompletePattern(stripBit(bits));
510 }
511 }
512
513 // Traverse towards root to find a node that terminates a bit pattern. //
514 const BitTrie* node = this;
515 do {
516 if (nodeTerminatesPattern(*node)) {
517 // Found complete pattern.
518 return patternAtNode(*node);
519 }
520 } while((node = node->parent_));
521
522 // No pattern found. //
523 return BitVector{0, 0};
524}
525
526
527/**
528 * Debug method.
529 */
530template<class DataType, class ValueType>
531inline
532void
533BitTrie<DataType, ValueType>::dump(std::ostream& out) const {
534 out << this << ", " << depth(*this) << ", "
535 << value(patternAtNode(*this)) << ", "
536 << width(patternAtNode(*this)) << ", "
537 << frequency_ << std::endl;
538 if (node_[0]) node_[0]->dump(out);
539 if (node_[1]) node_[1]->dump(out);
540}
541
542
543/**
544 * Returns true id some bit pattern is terminated at the node.
545 */
546template<class DataType, class ValueType>
547inline
548bool
549BitTrie<DataType, ValueType>::nodeTerminatesPattern(const BitTrie& node) {
550 WidthType subFreq = 0;
551 for (const BitTrie* subTrie : node.node_) {
552 subFreq += subTrie?subTrie->frequency_:0;
553 }
554 assert(node.frequency_ >= subFreq);
555 assert((node.frequency_ - subFreq) < 2);
556 if ((node.frequency_ - subFreq) == 1) {
557 return true;
558 } else {
559 return false;
560 }
561}
562
563
564/**
565 * Returns the BitVector that the node describes.
566 */
567template<class DataType, class ValueType>
568inline
569typename BitTrie<DataType, ValueType>::BitVector
570BitTrie<DataType, ValueType>::patternAtNode(const BitTrie& node) {
571 if (isRootNode(node)) {
572 return BitVector{0, 0};
573 }
574 BitVector result{0, depth(node)};
575
576 const BitTrie* currentNode = &node;
577 for (unsigned i = 0; i < width(result); i++) {
578 if (currentNode->bitReadLeftToRight_) {
579 MathTools::setBit(value(result), i, nodeBitValue(*currentNode));
580 } else {
581 MathTools::setBit(
582 value(result), width(result)-1-i, nodeBitValue(*currentNode));
583 }
584 currentNode = currentNode->parent_;
585 }
586 return result;
587}
588
589
590/**
591 * Returns the bit value of the node.
592 *
593 */
594template<class DataType, class ValueType>
595inline
596bool
597BitTrie<DataType, ValueType>::nodeBitValue(const BitTrie& node) {
598 assert(node.parent_ != nullptr
599 && "Illegal call for root node.");
600 assert((node.parent_->node_[1] == &node || node.parent_->node_[0] == &node)
601 && "Not registered to parent.");
602 return (node.parent_->node_[1] == &node);
603}
604
605
606/**
607 * Returns true if the node is root node of the trie. Otherwise returns false.
608 */
609template<class DataType, class ValueType>
610inline
611bool
612BitTrie<DataType, ValueType>::isRootNode(const BitTrie& node) {
613 return (node.parent_ == nullptr);
614}
615
616
617/**
618 * Returns the depth of the node and also number of bits it describes.
619 */
620template<class DataType, class ValueType>
621inline
622unsigned
623BitTrie<DataType, ValueType>::depth(const BitTrie& node) {
624 unsigned count = 0;
625 const BitTrie* parent = node.parent_;
626 while (parent) {
627 count++;
628 parent = parent->parent_;
629 }
630 return count;
631}
Generated by doxygen 1.9.8