5 * Created by Victor Grishchenko on 10/10/09.
6 * Reimplemented by Alexander G. Pronchenkov on 05/05/10
8 * Copyright 2010 Delft University of Technology. All rights reserved.
19 * Numbering for (aligned) logarithmic bins.
21 * Each number stands for an interval
22 * [layer_offset * 2^layer, (layer_offset + 1) * 2^layer).
24 * The following value is called as base_offset:
25 * layer_offset * 2^layer -- is called
27 * Bin numbers in the tail111 encoding: meaningless bits in
28 * the tail are set to 0111...11, while the head denotes the offset.
29 * bin = 2 ^ (layer + 1) * layer_offset + 2 ^ layer - 1
31 * Thus, 1101 is the bin at layer 1, offset 3 (i.e. fourth).
36 * +-----------------00111-----------------+
38 * +-------00011-------+ +-------01011-------+
40 * +--00001--+ +--00101--+ +--01001--+ +--01101--+
42 * 00000 00010 00100 00110 01000 01010 01100 1110
54 * Once we have peak hashes, this structure is more natural than bin-v1
63 typedef unsigned long long uint_t;
69 static const bin_t NONE;
70 static const bin_t ALL;
82 explicit bin_t(uint_t val);
88 bin_t(int layer, uint_t layer_offset);
94 uint_t toUInt(void) const;
100 bool operator == (const bin_t& bin) const;
106 bool operator != (const bin_t& bin) const;
112 bool operator < (const bin_t& bin) const;
116 * Operator greater than
118 bool operator > (const bin_t& bin) const;
122 * Operator less than or equal
124 bool operator <= (const bin_t& bin) const;
128 * Operator greater than or equal
130 bool operator >= (const bin_t& bin) const;
135 void decompose(int* layer, uint_t* layer_offset) const;
139 * Gets the beginning of the bin(ary interval)
141 uint_t base_offset(void) const;
145 * Gets the length of the bin interval
147 uint_t base_length(void) const;
151 * Gets the bin's layer, i.e. log2(base_length)
153 int layer(void) const;
157 * Gets the bin layer bits
159 uint_t layer_bits(void) const;
163 * Gets the bin layer offset
165 uint_t layer_offset(void) const;
169 * Whether the bin is none
171 bool is_none(void) const;
175 * Whether the bin is all
177 bool is_all(void) const;
181 * Whether the bin is base (layer == 0)
183 bool is_base(void) const;
187 * Checks whether is bin is a left child
189 bool is_left(void) const;
193 * Checks whether is bin is a left child
195 bool is_right(void) const;
199 * Sets this object to the parent
201 bin_t& to_parent(void);
205 * Sets this object to the left child
207 bin_t& to_left(void);
211 * Sets this object to the right child
213 bin_t& to_right(void);
217 * Sets this object to the sibling
219 bin_t& to_sibling(void);
223 * Sets this object to the leftmost base sub-bin
225 bin_t& to_base_left(void);
229 * Sets this object to the rightmost base sub-bin
231 bin_t& to_base_right(void);
235 * Sets this object to the permutated state
237 bin_t& to_twisted(uint_t mask);
241 * Sets this object to a layer shifted state
243 bin_t& to_layer_shifted(int zlayer);
247 * Gets the parent bin
249 bin_t parent(void) const;
253 * Gets the left child
255 bin_t left(void) const;
259 * Gets the right child
261 bin_t right(void) const;
265 * Gets the sibling bin
267 bin_t sibling(void) const;
271 * Gets the leftmost base sub-bin
273 bin_t base_left(void) const;
277 * Gets the rightmost base sub-bin
279 bin_t base_right(void) const;
283 * Performs a permutation
285 bin_t twisted(uint_t mask) const;
289 * Gets the bin after a layer shifting
291 bin_t layer_shifted(int zlayer) const;
295 * Checks for contains
297 bool contains(const bin_t& bin) const;
301 * Get the standard-form of this bin, e.g. "(2,1)".
302 * (buffer should have enough of space)
304 const char* str(char* buf) const;
317 std::ostream & operator << (std::ostream & ostream, const bin_t & bin);
323 inline bin_t::bin_t(void)
330 inline bin_t::bin_t(uint_t val)
338 inline bin_t::bin_t(int layer, uint_t offset)
340 if (static_cast<unsigned int>(layer) < 8 * sizeof(uint_t)) {
341 v_ = ((2 * offset + 1) << layer) - 1;
343 v_ = static_cast<uint_t>(-1); // Definition of the NONE bin
351 inline bin_t::uint_t bin_t::toUInt(void) const
360 inline bool bin_t::operator == (const bin_t& bin) const
369 inline bool bin_t::operator != (const bin_t& bin) const
378 inline bool bin_t::operator < (const bin_t& bin) const
385 * Operator great than
387 inline bool bin_t::operator > (const bin_t& bin) const
394 * Operator less than or equal
396 inline bool bin_t::operator <= (const bin_t& bin) const
403 * Operator great than or equal
405 inline bool bin_t::operator >= (const bin_t& bin) const
414 inline void bin_t::decompose(int* layer, uint_t* layer_offset) const
416 const int l = this->layer();
421 *layer_offset = v_ >> (l + 1);
427 * Gets a beginning of the bin interval
429 inline bin_t::uint_t bin_t::base_offset(void) const
431 return (v_ & (v_ + 1)) >> 1;
436 * Gets the length of the bin interval
438 inline bin_t::uint_t bin_t::base_length(void) const
441 #pragma warning (push)
442 #pragma warning (disable:4146)
444 const uint_t t = v_ + 1;
447 #pragma warning (pop)
453 * Gets the layer bits
455 inline bin_t::uint_t bin_t::layer_bits(void) const
457 return v_ ^ (v_ + 1);
462 * Gets the offset value of a bin
464 inline bin_t::uint_t bin_t::layer_offset(void) const
466 return v_ >> (layer() + 1);
471 * Does the bin is none
473 inline bool bin_t::is_none(void) const
475 return *this == NONE;
480 * Does the bin is all
482 inline bool bin_t::is_all(void) const
489 * Checks is bin is base (layer == 0)
491 inline bool bin_t::is_base(void) const
498 * Checks is bin is a left child
500 inline bool bin_t::is_left(void) const
502 return !(v_ & (layer_bits() + 1));
507 * Checks whether is bin is a left child
509 inline bool bin_t::is_right(void) const
516 * Sets this object to the parent
518 inline bin_t& bin_t::to_parent(void)
520 const uint_t lbs = layer_bits();
521 const uint_t nlbs = -2 - lbs; /* ~(lbs + 1) */
523 v_ = (v_ | lbs) & nlbs;
530 * Sets this object to the left child
532 inline bin_t& bin_t::to_left(void)
537 #pragma warning (push)
538 #pragma warning (disable:4146)
544 #pragma warning (pop)
558 * Sets this object to the right child
560 inline bin_t& bin_t::to_right(void)
565 #pragma warning (push)
566 #pragma warning (disable:4146)
572 #pragma warning (pop)
586 * Sets this object to the sibling
588 inline bin_t& bin_t::to_sibling(void)
590 v_ ^= (v_ ^ (v_ + 1)) + 1;
597 * Sets this object to the leftmost base sub-bin
599 inline bin_t& bin_t::to_base_left(void)
610 * Sets this object to the rightmost base sub-bin
612 inline bin_t& bin_t::to_base_right(void)
615 v_ = (v_ | (v_ + 1)) - 1;
623 * Performs a permutation
625 inline bin_t& bin_t::to_twisted(uint_t mask)
627 v_ ^= ((mask << 1) & ~layer_bits());
634 * Sets this object to a layer shifted state
636 inline bin_t& bin_t::to_layer_shifted(int zlayer)
638 if (layer_bits() >> zlayer) {
641 v_ = (v_ >> zlayer) & ~static_cast<uint_t>(1);
649 * Gets the parent bin
651 inline bin_t bin_t::parent(void) const
653 const uint_t lbs = layer_bits();
654 const uint_t nlbs = -2 - lbs; /* ~(lbs + 1) */
656 return bin_t((v_ | lbs) & nlbs);
661 * Gets the left child
663 inline bin_t bin_t::left(void) const
668 #pragma warning (push)
669 #pragma warning (disable:4146)
675 #pragma warning (pop)
682 return bin_t(v_ ^ t);
687 * Gets the right child
689 inline bin_t bin_t::right(void) const
694 #pragma warning (push)
695 #pragma warning (disable:4146)
701 #pragma warning (pop)
708 return bin_t(v_ + t);
713 * Gets the sibling bin
715 inline bin_t bin_t::sibling(void) const
717 return bin_t(v_ ^ (layer_bits() + 1));
722 * Gets the leftmost base sub-bin
724 inline bin_t bin_t::base_left(void) const
730 return bin_t(v_ & (v_ + 1));
735 * Gets the rightmost base sub-bin
737 inline bin_t bin_t::base_right(void) const
743 return bin_t((v_ | (v_ + 1)) - 1);
748 * Performs a permutation
750 inline bin_t bin_t::twisted(uint_t mask) const
752 return bin_t( v_ ^ ((mask << 1) & ~layer_bits()) );
757 * Gets the bin after a layer shifting
759 inline bin_t bin_t::layer_shifted(int zlayer) const
761 if (layer_bits() >> zlayer) {
762 return bin_t( v_ >> zlayer );
764 return bin_t( (v_ >> zlayer) & ~static_cast<uint_t>(1) );
770 * Checks for contains
772 inline bool bin_t::contains(const bin_t& bin) const
778 return (v_ & (v_ + 1)) <= bin.v_ && bin.v_ < (v_ | (v_ + 1));