src/libswift/bin.h

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