1 /*
2 * bin.h
3 * swift
4 *
5 * Created by Victor Grishchenko on 10/10/09.
6 * Reimplemented by Alexander G. Pronchenkov on 05/05/10
7 *
8 * Copyright 2010 Delft University of Technology. All rights reserved.
9 *
10 */
11
12 #ifndef __bin_h__
13 #define __bin_h__
14
15 #include <iosfwd>
16 #include <string>
17
18
19 /**
20 * Numbering for (aligned) logarithmic bins.
21 *
22 * Each number stands for an interval
23 * [layer_offset * 2^layer, (layer_offset + 1) * 2^layer).
24 *
25 * The following value is called as base_offset:
26 * layer_offset * 2^layer -- is called
27 *
28 * Bin numbers in the tail111 encoding: meaningless bits in
29 * the tail are set to 0111...11, while the head denotes the offset.
30 * bin = 2 ^ (layer + 1) * layer_offset + 2 ^ layer - 1
31 *
32 * Thus, 1101 is the bin at layer 1, offset 3 (i.e. fourth).
33 */
34
35 /**
36 *
37 * +-----------------00111-----------------+
38 * | |
39 * +-------00011-------+ +-------01011-------+
40 * | | | |
41 * +--00001--+ +--00101--+ +--01001--+ +--01101--+
42 * | | | | | | | |
43 * 00000 00010 00100 00110 01000 01010 01100 1110
44 *
45 *
46 *
47 * 7
48 * / \
49 * 3 11
50 * / \ / \
51 * 1 5 9 13
52 * / \ / \ / \ / \
53 * 0 2 4 6 8 10 12 14
54 *
55 * Once we have peak hashes, this structure is more natural than bin-v1
56 *
57 */
58
59 class bin_t
60 {
61 public:
62 /**
63 * Basic integer type
64 */
65 typedef unsigned long long uint_t;
66
67
68 /**
69 * Constants
70 */
71 static const bin_t NONE;
72 static const bin_t ALL;
73
74
75 /**
76 * Constructor
77 */
78 bin_t(void);
79
80
81 /**
82 * Constructor
83 */
84 explicit bin_t(uint_t val);
85
86
87 /**
88 * Constructor
89 */
90 bin_t(int layer, uint_t layer_offset);
91
92
93 /**
94 * Gets the bin value
95 */
96 uint_t toUInt(void) const;
97
98
99 /**
100 * Operator equal
101 */
102 bool operator == (const bin_t& bin) const;
103
104
105 /**
106 * Operator non-equal
107 */
108 bool operator != (const bin_t& bin) const;
109
110
111 /**
112 * Operator less than
113 */
114 bool operator < (const bin_t& bin) const;
115
116
117 /**
118 * Operator greater than
119 */
120 bool operator > (const bin_t& bin) const;
121
122
123 /**
124 * Operator less than or equal
125 */
126 bool operator <= (const bin_t& bin) const;
127
128
129 /**
130 * Operator greater than or equal
131 */
132 bool operator >= (const bin_t& bin) const;
133
134 /**
135 * Decompose the bin
136 */
137 void decompose(int* layer, uint_t* layer_offset) const;
138
139
140 /**
141 * Gets the beginning of the bin(ary interval)
142 */
143 uint_t base_offset(void) const;
144
145
146 /**
147 * Gets the length of the bin interval
148 */
149 uint_t base_length(void) const;
150
151
152 /**
153 * Gets the bin's layer, i.e. log2(base_length)
154 */
155 int layer(void) const;
156
157
158 /**
159 * Gets the bin layer bits
160 */
161 uint_t layer_bits(void) const;
162
163
164 /**
165 * Gets the bin layer offset
166 */
167 uint_t layer_offset(void) const;
168
169
170 /**
171 * Whether the bin is none
172 */
173 bool is_none(void) const;
174
175
176 /**
177 * Whether the bin is all
178 */
179 bool is_all(void) const;
180
181
182 /**
183 * Whether the bin is base (layer == 0)
184 */
185 bool is_base(void) const;
186
187
188 /**
189 * Checks whether is bin is a left child
190 */
191 bool is_left(void) const;
192
193
194 /**
195 * Checks whether is bin is a left child
196 */
197 bool is_right(void) const;
198
199
200 /**
201 * Sets this object to the parent
202 */
203 bin_t& to_parent(void);
204
205
206 /**
207 * Sets this object to the left child
208 */
209 bin_t& to_left(void);
210
211
212 /**
213 * Sets this object to the right child. WARNING: does NOT calculate next-in-layer when at base!
214 */
215 bin_t& to_right(void);
216
217
218 /**
219 * Sets this object to the sibling
220 */
221 bin_t& to_sibling(void);
222
223
224 /**
225 * Sets this object to the leftmost base sub-bin
226 */
227 bin_t& to_base_left(void);
228
229
230 /**
231 * Sets this object to the rightmost base sub-bin
232 */
233 bin_t& to_base_right(void);
234
235
236 /**
237 * Sets this object to the permutated state
238 */
239 bin_t& to_twisted(uint_t mask);
240
241
242 /**
243 * Sets this object to a layer shifted state
244 */
245 bin_t& to_layer_shifted(int zlayer);
246
247
248 /**
249 * Gets the parent bin
250 */
251 bin_t parent(void) const;
252
253
254 /**
255 * Gets the left child
256 */
257 bin_t left(void) const;
258
259
260 /**
261 * Gets the right child. WARNING: does NOT calculate next-in-layer when at base!
262 */
263 bin_t right(void) const;
264
265
266 /**
267 * Gets the sibling bin
268 */
269 bin_t sibling(void) const;
270
271
272 /**
273 * Gets the leftmost base sub-bin
274 */
275 bin_t base_left(void) const;
276
277
278 /**
279 * Gets the rightmost base sub-bin
280 */
281 bin_t base_right(void) const;
282
283
284 /**
285 * Performs a permutation
286 */
287 bin_t twisted(uint_t mask) const;
288
289
290 /**
291 * Gets the bin after a layer shifting
292 */
293 bin_t layer_shifted(int zlayer) const;
294
295
296 /**
297 * Checks for contains
298 */
299 bool contains(const bin_t& bin) const;
300
301
302 /**
303 * Get the standard-form of this bin, e.g. "(2,1)".
304 */
305 std::string str() const;
306
307
308 private:
309
310 /** Bin value */
311 uint_t v_;
312 };
313
314
315 /**
316 * Output operator
317 */
318 std::ostream & operator << (std::ostream & ostream, const bin_t & bin);
319
320
321 /**
322 * Constructor
323 */
bin_t(void)324 inline bin_t::bin_t(void)
325 { }
326
327
328 /**
329 * Constructor
330 */
bin_t(uint_t val)331 inline bin_t::bin_t(uint_t val)
332 : v_(val)
333 { }
334
335
336 /**
337 * Constructor
338 */
bin_t(int layer,uint_t offset)339 inline bin_t::bin_t(int layer, uint_t offset)
340 {
341 if (static_cast<unsigned int>(layer) < 8 * sizeof(uint_t)) {
342 v_ = ((2 * offset + 1) << layer) - 1;
343 } else {
344 v_ = static_cast<uint_t>(-1); // Definition of the NONE bin
345 }
346 }
347
348
349 /**
350 * Gets the bin value
351 */
toUInt(void)352 inline bin_t::uint_t bin_t::toUInt(void) const
353 {
354 return v_;
355 }
356
357
358 /**
359 * Operator equal
360 */
361 inline bool bin_t::operator == (const bin_t& bin) const
362 {
363 return v_ == bin.v_;
364 }
365
366
367 /**
368 * Operator non-equal
369 */
370 inline bool bin_t::operator != (const bin_t& bin) const
371 {
372 return v_ != bin.v_;
373 }
374
375
376 /**
377 * Operator less than
378 */
379 inline bool bin_t::operator < (const bin_t& bin) const
380 {
381 return v_ < bin.v_;
382 }
383
384
385 /**
386 * Operator great than
387 */
388 inline bool bin_t::operator > (const bin_t& bin) const
389 {
390 return v_ > bin.v_;
391 }
392
393
394 /**
395 * Operator less than or equal
396 */
397 inline bool bin_t::operator <= (const bin_t& bin) const
398 {
399 return v_ <= bin.v_;
400 }
401
402
403 /**
404 * Operator great than or equal
405 */
406 inline bool bin_t::operator >= (const bin_t& bin) const
407 {
408 return v_ >= bin.v_;
409 }
410
411
412 /**
413 * Decompose the bin
414 */
decompose(int * layer,uint_t * layer_offset)415 inline void bin_t::decompose(int* layer, uint_t* layer_offset) const
416 {
417 const int l = this->layer();
418 if (layer) {
419 *layer = l;
420 }
421 if (layer_offset) {
422 *layer_offset = v_ >> (l + 1);
423 }
424 }
425
426
427 /**
428 * Gets a beginning of the bin interval
429 */
base_offset(void)430 inline bin_t::uint_t bin_t::base_offset(void) const
431 {
432 return (v_ & (v_ + 1)) >> 1;
433 }
434
435
436 /**
437 * Gets the length of the bin interval
438 */
base_length(void)439 inline bin_t::uint_t bin_t::base_length(void) const
440 {
441 #ifdef _MSC_VER
442 #pragma warning (push)
443 #pragma warning (disable:4146)
444 #endif
445 const uint_t t = v_ + 1;
446 return t & -t;
447 #ifdef _MSC_VER
448 #pragma warning (pop)
449 #endif
450 }
451
452
453 /**
454 * Gets the layer bits
455 */
layer_bits(void)456 inline bin_t::uint_t bin_t::layer_bits(void) const
457 {
458 return v_ ^ (v_ + 1);
459 }
460
461
462 /**
463 * Gets the offset value of a bin
464 */
layer_offset(void)465 inline bin_t::uint_t bin_t::layer_offset(void) const
466 {
467 return v_ >> (layer() + 1);
468 }
469
470
471 /**
472 * Does the bin is none
473 */
is_none(void)474 inline bool bin_t::is_none(void) const
475 {
476 return *this == NONE;
477 }
478
479
480 /**
481 * Does the bin is all
482 */
is_all(void)483 inline bool bin_t::is_all(void) const
484 {
485 return *this == ALL;
486 }
487
488
489 /**
490 * Checks is bin is base (layer == 0)
491 */
is_base(void)492 inline bool bin_t::is_base(void) const
493 {
494 return !(v_ & 1);
495 }
496
497
498 /**
499 * Checks is bin is a left child
500 */
is_left(void)501 inline bool bin_t::is_left(void) const
502 {
503 return !(v_ & (layer_bits() + 1));
504 }
505
506
507 /**
508 * Checks whether is bin is a left child
509 */
is_right(void)510 inline bool bin_t::is_right(void) const
511 {
512 return !is_left();
513 }
514
515
516 /**
517 * Sets this object to the parent
518 */
to_parent(void)519 inline bin_t& bin_t::to_parent(void)
520 {
521 const uint_t lbs = layer_bits();
522 const uint_t nlbs = -2 - lbs; /* ~(lbs + 1) */
523
524 v_ = (v_ | lbs) & nlbs;
525
526 return *this;
527 }
528
529
530 /**
531 * Sets this object to the left child
532 */
to_left(void)533 inline bin_t& bin_t::to_left(void)
534 {
535 register uint_t t;
536
537 #ifdef _MSC_VER
538 #pragma warning (push)
539 #pragma warning (disable:4146)
540 #endif
541 t = v_ + 1;
542 t &= -t;
543 t >>= 1;
544 #ifdef _MSC_VER
545 #pragma warning (pop)
546 #endif
547
548 // if (t == 0) {
549 // return NONE;
550 // }
551
552 v_ ^= t;
553
554 return *this;
555 }
556
557
558 /**
559 * Sets this object to the right child
560 */
to_right(void)561 inline bin_t& bin_t::to_right(void)
562 {
563 register uint_t t;
564
565 #ifdef _MSC_VER
566 #pragma warning (push)
567 #pragma warning (disable:4146)
568 #endif
569 t = v_ + 1;
570 t &= -t;
571 t >>= 1;
572 #ifdef _MSC_VER
573 #pragma warning (pop)
574 #endif
575
576 // if (t == 0) {
577 // return NONE;
578 // }
579
580 v_ += t;
581
582 return *this;
583 }
584
585
586 /**
587 * Sets this object to the sibling
588 */
to_sibling(void)589 inline bin_t& bin_t::to_sibling(void)
590 {
591 v_ ^= (v_ ^ (v_ + 1)) + 1;
592
593 return *this;
594 }
595
596
597 /**
598 * Sets this object to the leftmost base sub-bin
599 */
to_base_left(void)600 inline bin_t& bin_t::to_base_left(void)
601 {
602 if (!is_none()) {
603 v_ &= (v_ + 1);
604 }
605
606 return *this;
607 }
608
609
610 /**
611 * Sets this object to the rightmost base sub-bin
612 */
to_base_right(void)613 inline bin_t& bin_t::to_base_right(void)
614 {
615 if (!is_none()) {
616 v_ = (v_ | (v_ + 1)) - 1;
617 }
618
619 return *this;
620 }
621
622
623 /**
624 * Performs a permutation
625 */
to_twisted(uint_t mask)626 inline bin_t& bin_t::to_twisted(uint_t mask)
627 {
628 v_ ^= ((mask << 1) & ~layer_bits());
629
630 return *this;
631 }
632
633
634 /**
635 * Sets this object to a layer shifted state
636 */
to_layer_shifted(int zlayer)637 inline bin_t& bin_t::to_layer_shifted(int zlayer)
638 {
639 if (layer_bits() >> zlayer) {
640 v_ >>= zlayer;
641 } else {
642 v_ = (v_ >> zlayer) & ~static_cast<uint_t>(1);
643 }
644
645 return *this;
646 }
647
648
649 /**
650 * Gets the parent bin
651 */
parent(void)652 inline bin_t bin_t::parent(void) const
653 {
654 const uint_t lbs = layer_bits();
655 const uint_t nlbs = -2 - lbs; /* ~(lbs + 1) */
656
657 return bin_t((v_ | lbs) & nlbs);
658 }
659
660
661 /**
662 * Gets the left child
663 */
left(void)664 inline bin_t bin_t::left(void) const
665 {
666 register uint_t t;
667
668 #ifdef _MSC_VER
669 #pragma warning (push)
670 #pragma warning (disable:4146)
671 #endif
672 t = v_ + 1;
673 t &= -t;
674 t >>= 1;
675 #ifdef _MSC_VER
676 #pragma warning (pop)
677 #endif
678
679 // if (t == 0) {
680 // return NONE;
681 // }
682
683 return bin_t(v_ ^ t);
684 }
685
686
687 /**
688 * Gets the right child
689 */
right(void)690 inline bin_t bin_t::right(void) const
691 {
692 register uint_t t;
693
694 #ifdef _MSC_VER
695 #pragma warning (push)
696 #pragma warning (disable:4146)
697 #endif
698 t = v_ + 1;
699 t &= -t;
700 t >>= 1;
701 #ifdef _MSC_VER
702 #pragma warning (pop)
703 #endif
704
705 // if (t == 0) {
706 // return NONE;
707 // }
708
709 return bin_t(v_ + t);
710 }
711
712
713 /**
714 * Gets the sibling bin
715 */
sibling(void)716 inline bin_t bin_t::sibling(void) const
717 {
718 return bin_t(v_ ^ (layer_bits() + 1));
719 }
720
721
722 /**
723 * Gets the leftmost base sub-bin
724 */
base_left(void)725 inline bin_t bin_t::base_left(void) const
726 {
727 if (is_none()) {
728 return NONE;
729 }
730
731 return bin_t(v_ & (v_ + 1));
732 }
733
734
735 /**
736 * Gets the rightmost base sub-bin
737 */
base_right(void)738 inline bin_t bin_t::base_right(void) const
739 {
740 if (is_none()) {
741 return NONE;
742 }
743
744 return bin_t((v_ | (v_ + 1)) - 1);
745 }
746
747
748 /**
749 * Performs a permutation
750 */
twisted(uint_t mask)751 inline bin_t bin_t::twisted(uint_t mask) const
752 {
753 return bin_t(v_ ^ ((mask << 1) & ~layer_bits()));
754 }
755
756
757 /**
758 * Gets the bin after a layer shifting
759 */
layer_shifted(int zlayer)760 inline bin_t bin_t::layer_shifted(int zlayer) const
761 {
762 if (layer_bits() >> zlayer) {
763 return bin_t(v_ >> zlayer);
764 } else {
765 return bin_t((v_ >> zlayer) & ~static_cast<uint_t>(1));
766 }
767 }
768
769
770 /**
771 * Checks for contains
772 */
contains(const bin_t & bin)773 inline bool bin_t::contains(const bin_t& bin) const
774 {
775 if (is_none()) {
776 return false;
777 }
778
779 return (v_ & (v_ + 1)) <= bin.v_ && bin.v_ < (v_ | (v_ + 1));
780 }
781
782 // Arno, 2013-03-06: Define here as livehashtree.h needs it.
783 #include <vector>
784 typedef std::vector<bin_t> binvector;
785
786
787 bool bin_sort_on_layer_cmp(bin_t i, bin_t j);
788
789 #endif /*_bin_h__*/
790