bittree.cpp

   1 /***************************************************************************
   2  *   Copyright (C) 2006 by Wolfgang Gerlach   *
   3  *   No object matches key 'wgerlach'.   *
   4  *                                                                         *
   5  *   This program is free software; you can redistribute it and/or modify  *
   6  *   it under the terms of the GNU General Public License as published by  *
   7  *   the Free Software Foundation; either version 2 of the License, or     *
   8  *   (at your option) any later version.                                   *
   9  *                                                                         *
  10  *   This program is distributed in the hope that it will be useful,       *
  11  *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
  12  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
  13  *   GNU General Public License for more details.                          *
  14  *                                                                         *
  15  *   You should have received a copy of the GNU General Public License     *
  16  *   along with this program; if not, write to the                         *
  17  *   Free Software Foundation, Inc.,                                       *
  18  *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
  19  ***************************************************************************/
  20
  21
  22 #include "bittree.h"
  23
  24
  25 using std::cout;
  26 using std::endl;
  27 using std::cerr;
  28 using std::bitset;
  29 using std::ostream;
  30
  31 //std::ostream& operator<<(std::ostream& os, node& n) { ... }
  32
  33
  34   BVTree::~BVTree(){
  35       delete tempbit;
  36       tempbit = 0;
  37   }
  38
  39
  40
  41 /**
  42 BVTree::BVTree(char *readfile){
  43
  44   std::ifstream file(readfile);
  45   if (!file)
  46   {
  47           cout << "error reading file "<< readfile <<" !\n";
  48           exit(EXIT_FAILURE);
  49   }
  50
  51
  52   tempnil = (BVNode*) ((RBTree*) this)->nil;
  53   tempbit = new bitset<2*logn>;
  54
  55
  56   char c;
  57   bitset<8> bs;
  58
  59   while (file.get(c))
  60   {
  61           bs = c;
  62
  63           for (int i=7; i>=0; i--)
  64                   appendBit(bs[i]);
  65   }
  66
  67 }
  68 **/
  69
  70
  71
  72
  73 void BVTree::iterateReset(){
  74         iterate=1;
  75         iterateLocal=0;
  76         if (root!=nil) {
  77                 iterateNode = (BVNode*) treeMinimum(root);
  78                 iterateRank = ((*iterateNode->block)[0])?1:0;
  79         } else {
  80                 iterateNode=getNil();
  81                 iterateRank = 0;
  82                 }
  83 }
  84
  85 bool BVTree::iterateGetBit(){
  86         return ((*iterateNode->block)[iterateLocal]);
  87 }
  88
  89 ulong BVTree::iterateGetRank(bool bit){
  90         if (bit) return iterateRank;
  91         else return (iterate - iterateRank);
  92 }
  93
  94 bool BVTree::iterateNext(){
  95         iterate++;
  96
  97         if (iterate > getPositions()) return false;
  98
  99
 100         if (iterateLocal < iterateNode->myPositions-1) {
 101                 iterateLocal++;
 102         } else {
 103                 // jump to next leaf;
 104                 iterateNode = (BVNode*) treeSuccessor(iterateNode);
 105                 #ifndef NDEBUG
 106                 if (iterateNode==getNil()) {
 107                         cout << "iterateNode==getNil()" << endl;
 108                         return false;
 109                 }
 110                 #endif
 111                 iterateLocal=0;
 112         }
 113         if  ((*iterateNode->block)[iterateLocal]) iterateRank++;
 114
 115         return true;
 116 }
 117
 118 ulong BVTree::getPositions(){
 119
 120         if (getRoot() == getNil()) return 0;
 121         return getRoot()->subTreePositions;
 122 }
 123
 124 ulong BVTree::getRank(){
 125
 126         if (getRoot() == getNil()) return 0;
 127         return getRoot()->subTreeRank;
 128 }
 129
 130
 131 void BVTree::printNode(BVNode *n){
 132         int commas=(2*logn)/10;
 133         int commashift = -1;
 134
 135
 136         cout << "address: " << n << endl;
 137
 138         if (n->block != 0 && (n!=getNil()))
 139         {
 140                 int size = 2*logn + 1 +commas;
 141
 142                 char *myblock = (char *) new char[size];
 143                 if (myblock == 0) {
 144                         cerr << "error: printNode: myblock == 0" << endl;
 145                         exit(0);
 146                 }
 147
 148                 //read: i, write: i+commashift
 149                 for (int i=0; i<(int)(n->myPositions); i++){
 150                         if (i%10 == 0) commashift++;
 151                         myblock[i+commashift]='0' + (*n->block)[i];
 152                         if (i+commashift >= size-1) {
 153                                 cerr << "X) printNode: array wrong index" << endl;
 154                                 exit(0);
 155                         }
 156
 157                 }
 158
 159                 cout << "size=" << size << endl;
 160                 cout << "n->myPositions=" << n->myPositions << endl;
 161                 for (int i=n->myPositions; i<(2*logn); i++){
 162                         if ((i%10) == 0) commashift++;
 163
 164                         myblock[i+commashift]='-';
 165                         if (i+commashift > size-2) {
 166                                 cerr << "A) printNode: array wrong index" << endl;
 167                                 exit(0);
 168                         }
 169                 }
 170
 171                 commashift = 0;
 172                 for (int i=10; i < 2*logn; i++){
 173                         if (i%10 == 0)
 174                         {
 175                                 if (i+commashift >= size-2) {
 176                                         cerr << "B) printNode: array wrong index" << endl;
 177                                         exit(0);
 178                                 }
 179
 180                                 myblock[i+commashift]=',';
 181                                 commashift++;
 182                         }
 183
 184                 }
 185
 186                 myblock[size - 1]='\0';
 187
 188                 cout << "block: \"" << myblock << "\"" << endl;
 189                 delete myblock;
 190
 191         }
 192         else
 193                 cout << "block: none" << endl;
 194
 195
 196         cout << "myPositions: " << n->myPositions << endl;
 197         cout << "myRank: " << n->myRank << endl;
 198         cout << "subTreePositions: " << n->subTreePositions << endl;
 199         cout << "subTreeRank: " << n->subTreeRank << endl;
 200         cout << "color: " << ((n->color==RED)?"RED":"BLACK") << endl;
 201         cout << "parent: " << n->getParent() << endl;
 202         cout << "left: " << n->getLeft() << endl;
 203         cout << "right:" << n->getRight() << endl << endl;
 204
 205 }
 206
 207
 208 int BVTree::getTreeMaxDepth(){
 209         return getNodeMaxDepth(root);
 210 }
 211
 212 int BVTree::getTreeMinDepth(){
 213         return getNodeMinDepth(root);
 214 }
 215
 216
 217 void BVTree::updateCounters(BVNode *n){
 218
 219         if (n == getNil()) return;
 220
 221         ulong lR = 0;
 222         ulong lP = 0;
 223         ulong rR = 0;
 224         ulong rP = 0;
 225
 226         if (n->getLeft() != getNil()) {
 227                 lR = n->getLeft()->subTreeRank;
 228                 lP = n->getLeft()->subTreePositions;
 229         }
 230
 231         if (n->getRight() != getNil()) {
 232                 rR = n->getRight()->subTreeRank;
 233                 rP = n->getRight()->subTreePositions;
 234         }
 235
 236         n->subTreeRank     =lR + rR + n->myRank;
 237         n->subTreePositions=lP + rP + n->myPositions;
 238
 239 }
 240
 241 ulong BVTree::getLocalRank(BVNode* n, ulong position){
 242
 243         #ifndef NDEBUG
 244         if (position > n->myPositions) {
 245                 cerr << "error: getLocalRank: invalid position in block.\n";
 246                 exit(EXIT_FAILURE);
 247         }
 248         #endif
 249
 250         *tempbit =*(n->block)<<((2*logn)-position);
 251         return tempbit->count();
 252
 253         // old version:
 254         //rank = 0;
 255         //for (ulong i = 0; i < position; i++) {
 256         //      if ((*n->block)[i]) rank++;
 257         //}
 258 }
 259
 260 ulong BVTree::getLocalSelect1(BVNode* n, ulong query){
 261         ulong select =0;
 262         #ifndef NDEBUG
 263         if (query > n->myPositions) {
 264                 cerr << "error: getLocalSelect1: invalid position in block.\n";
 265                 exit(EXIT_FAILURE);
 266         }
 267         #endif
 268         ulong i;
 269         for (i = 0; select < query; i++) { // TODO is there a faster solution similar to rank ?
 270                 if ((*n->block)[i]) select++;
 271         }
 272
 273         return i;
 274 }
 275
 276 ulong BVTree::getLocalSelect0(BVNode* n, ulong query){
 277         ulong select =0;
 278         #ifndef NDEBUG
 279         if (query > n->myPositions) {
 280                 cerr << "error: getLocalSelect0: invalid position in block.\n";
 281                 exit(EXIT_FAILURE);
 282         }
 283         #endif
 284         ulong i;
 285         for (i = 0; select < query; i++) {
 286                 if (!(*n->block)[i]) select++;
 287         }
 288
 289         return i;
 290 }
 291
 292
 293 void BVTree::printNode(ulong i){
 294         BVNode* x = getRoot();
 295
 296         #ifndef NDEBUG
 297         if (x == getNil()) {
 298                 cerr << "error: printNode(int i): root=NULL.\n";
 299                 exit(EXIT_FAILURE);
 300
 301         }
 302
 303         if (i > x->myPositions) {
 304                 cerr << "error: printNode(int i): invalid position in block.\n";
 305                 exit(EXIT_FAILURE);
 306         }
 307         #endif
 308
 309         ulong lP=0;
 310         bool search = true;
 311         //find the corresponding block:
 312         while (search)
 313         {
 314
 315                 lP = x->getLeft()->subTreePositions;
 316
 317
 318                 if (lP >= i)
 319                 {
 320                         x=x->getLeft();
 321                 }
 322                 else if (lP+x->myPositions >= i){
 323                         i-=lP;
 324                         search = false;
 325                 }
 326                 else{
 327                         i-=(lP+x->myPositions);
 328                         x=x->getRight();
 329                 }
 330         }
 331
 332
 333         cout << "i=" << i << endl;
 334         printNode(x);
 335 }
 336
 337
 338 bool BVTree::operator[](ulong i){
 339
 340         BVNode* x = getRoot();
 341         ulong lsP=0;
 342         bool search = true;
 343         //find the corresponding block:
 344         while (search)
 345         {
 346
 347                 lsP = x->getLeft()->subTreePositions;
 348
 349                 if (lsP >= i)
 350                 {
 351                         #ifndef NDEBUG
 352                         if (x->getLeft()==getNil()) {
 353                                 cout << "lsP: " << lsP << endl;
 354                                 printNode(x);
 355                                 cout << "ihhh" << endl;
 356                                 checkTree();
 357                                 exit(EXIT_FAILURE);
 358                         }
 359                         #endif
 360                         x=x->getLeft();
 361                 }
 362                 else if (lsP+x->myPositions >= i){
 363                         i-=lsP;
 364                         search = false;
 365                 }
 366                 else{
 367                         i-=(lsP+x->myPositions);
 368                         #ifndef NDEBUG
 369                         if (x->getRight()==getNil()) {
 370                                 cout << "i: " << i << endl;
 371                                 cout << "lsP: " << lsP << endl;
 372                                 cout << "x->myPositions: " << x->myPositions << endl;
 373                                 printNode(x);
 374                                 cout << "ihhh" << endl;
 375                                 checkTree();
 376                                 exit(EXIT_FAILURE);
 377                                 }
 378                         #endif
 379                         x=x->getRight();
 380                 }
 381         }
 382
 383         return (*x->block)[i-1];
 384 }
 385
 386
 387 ulong BVTree::rank1(ulong i){
 388         BVNode* x = getRoot();
 389
 390         if (i == this->getPositions() + 1) i--;
 391         #ifndef NDEBUG
 392         if (i > this->getPositions() ) {
 393                 cerr << "error: rank1(0): invalid position in bittree: " << i << endl;
 394                 cerr << "error: rank1(0): this->getPositions(): " <<  this->getPositions()<< endl;
 395                 exit(EXIT_FAILURE);
 396         }
 397         #endif
 398
 399
 400         ulong lsP=0;
 401         ulong lsR=0;
 402         ulong rank=0;
 403         bool search = true;
 404         //find the corresponding block:
 405         while (search)
 406         {
 407
 408                 lsP = x->getLeft()->subTreePositions;
 409                 lsR = x->getLeft()->subTreeRank;
 410
 411                 if (lsP >= i)
 412                 {// cout << "L" << endl;
 413                         x=x->getLeft();
 414                 }
 415                 else if (lsP+x->myPositions >= i){
 416                         i-=lsP;
 417                         rank+=lsR;
 418                         search = false;
 419                 }
 420                 else{//cout << "R" << endl;
 421                         i-=(lsP+x->myPositions);
 422                         rank+=(lsR+x->myRank);
 423                         x=x->getRight();
 424                 }
 425         }
 426
 427         rank+=getLocalRank(x, i);
 428         return rank;
 429 }
 430
 431 ulong BVTree::rank0(ulong i){
 432         if (this->getPositions() == 0) return 0;
 433         return (i-rank1(i));
 434 }
 435
 436 ulong BVTree::select1(ulong i){
 437         BVNode* x = getRoot();
 438         ulong select=0;
 439         #ifndef NDEBUG
 440         if (i > x->subTreeRank ) {
 441                 cerr << "error: select1: invalid position in bittree: " << i << endl;
 442                 exit(EXIT_FAILURE);
 443         }
 444         #endif
 445
 446         ulong lsP=0;
 447         ulong lsR=0;
 448         bool search = true;
 449         //find the corresponding block:
 450         while (search)
 451         {
 452                 // update subTree-counters
 453
 454
 455                 lsP = x->getLeft()->subTreePositions;
 456                 lsR = x->getLeft()->subTreeRank;
 457
 458                 if (lsR >= i) {
 459                         x=x->getLeft();
 460                 }
 461                 else if (lsR+x->myRank >= i) {
 462                         i-=lsR;
 463                         select+=lsP;
 464                         search = false;
 465                 }
 466                 else {
 467                         i-=(lsR+x->myRank);
 468                         select+=(lsP+x->myPositions);
 469                         x=x->getRight();
 470                 }
 471         }
 472         select+=getLocalSelect1(x, i);
 473
 474
 475
 476         return select;
 477 }
 478
 479 ulong BVTree::select0(ulong i){
 480         BVNode* x = getRoot();
 481         ulong select=0;
 482
 483         #ifndef NDEBUG
 484         if (i > (x->subTreePositions - x->subTreeRank) || i < 0) {
 485                 cerr << "error: select1: invalid position in bittree: " << i << endl;
 486                 exit(EXIT_FAILURE);
 487         }
 488         #endif
 489
 490
 491         ulong lsP=0;
 492         ulong lsR=0;
 493         ulong lmR=0;
 494         ulong lmP=0;
 495         bool search = true;
 496         //find the corresponding block:
 497         while (search)
 498         {
 499                 // update subTree-counters
 500
 501
 502                 lsP = x->getLeft()->subTreePositions;
 503                 lsR = x->getLeft()->subTreeRank;
 504                 lmR = x->getLeft()->myRank;
 505                 lmP = x->getLeft()->myPositions;
 506
 507                 if (lsP-lsR >= i)
 508                 {
 509                         x=x->getLeft();
 510                 }
 511                 else if ((lsP-lsR)+(x->myPositions-x->myRank) >= i){
 512                         i-=lsP-lsR;
 513                         select+=lsP;
 514                         search = false;
 515                 }
 516                 else{
 517                         i-=((lsP-lsR)+(x->myPositions-x->myRank));
 518                         select+=(lsP+x->myPositions);
 519                         x=x->getRight();
 520                 }
 521         }
 522
 523         select+=getLocalSelect0(x, i);
 524
 525         return select;
 526 }
 527
 528
 529 void BVTree::updateCountersOnPathToRoot(BVNode *walk){
 530
 531         while (walk != getNil()) {
 532                 updateCounters(walk);
 533                 walk=walk->getParent();
 534         }
 535 }
 536
 537 //deletes the BVNode and all its children, destroys reb-black-tree property!
 538 void BVTree::deleteNode(BVNode *n){
 539         if (n==getNil() || n == 0) return;
 540
 541         if (n->getLeft() != getNil() && n->getLeft()) deleteNode(n->getLeft());
 542         if (n->getRight() != getNil() && n->getRight()) deleteNode(n->getRight());
 543
 544         delete n;
 545 }
 546
 547
 548
 549
 550 // TODO improve by returning bitvalue
 551
 552 void BVTree::deleteBit(ulong i){
 553         ulong old_i = i;
 554         BVNode* x = getRoot();
 555         bool bit;
 556         ulong rank=0;
 557
 558         #ifndef NDEBUG
 559         if (x == getNil()) {
 560                 cerr << "error: deleteBit, root is empty\n"; //shouldn't happen
 561                 exit(EXIT_FAILURE);
 562         }
 563
 564         if (i > x->subTreePositions || i < 1)
 565         {
 566                 cerr << "error: A, position " << i <<" in block not available, only " << x->myPositions <<" positions.\n"; //shouldn't happen
 567                 exit(EXIT_FAILURE);
 568         }
 569         #endif
 570
 571         ulong lsP=0;
 572         ulong lsR=0;
 573
 574         bool search = true;
 575         //find the corresponding block:
 576         while (search)
 577         {
 578                 // update of pointers is not yet possible: call updateCountersOnPathToRoot
 579
 580                 lsP = x->getLeft()->subTreePositions;
 581                 lsR = x->getLeft()->subTreeRank;
 582
 583
 584                 if (lsP >= i)
 585                 {
 586                         #ifndef NDEBUG
 587                         if (x->getLeft()==getNil()) exit(EXIT_FAILURE);
 588                         #endif
 589                         x=x->getLeft();
 590                 }
 591                 else if (lsP+x->myPositions >= i){
 592                         i-=lsP;
 593                         rank+=lsR;
 594                         search = false;
 595                 }
 596                 else{
 597                         i-=(lsP+x->myPositions);
 598                         rank+=(lsR+x->myRank); // for speedup!
 599                         #ifndef NDEBUG
 600                         if (x->getRight()==getNil()) exit(EXIT_FAILURE);
 601                         #endif
 602                         x=x->getRight();
 603                 }
 604         }
 605
 606
 607
 608         // now delete the bit from the block x:
 609         bit =(*x->block)[i-1];
 610
 611         // store bit and rank information for speedup
 612         lastBitDeleted=bit;
 613         rank+=getLocalRank(x, i);
 614         lastRank=(bit?rank:old_i-rank);
 615
 616         #ifndef NDEBUG
 617         if (i > x->myPositions) {
 618                 cerr << "error: B, position " << i <<" in block not available, only " << x->myPositions <<" positions.\n"; //shouldn't happen
 619                 exit(EXIT_FAILURE);
 620         }
 621         #endif
 622         bitset<2*logn> mask;
 623
 624
 625         if ( i > 1 )
 626         {
 627                 mask.set();
 628                 mask>>=(2*logn - i + 1);
 629                 mask &= *(x->block);
 630                 (*(x->block)>>=i)<<=i-1;  // shift bits by one
 631                 (*x->block)|=mask;        // restore bits in front of deleted bit
 632         } else {
 633                 *(x->block)>>=1;  // shift bits by one
 634         }
 635
 636         x->myPositions--;
 637         if (bit) x->myRank--;
 638
 639         updateCountersOnPathToRoot(x);
 640
 641
 642         if (x->myPositions == 0){ // if merging was not possible:
 643
 644                 rbDelete(x, callUpdateCountersOnPathToRoot);
 645                 delete x;
 646
 647         } else if (x->myPositions <= logn/2) // merge (and rotate), if necessary:
 648         {
 649
 650                 BVNode *sibling = (BVNode*) treeSuccessor(x);
 651                 //cout << "try to merge -----------------------------------------" << endl;
 652                 if (sibling != getNil())
 653                 {
 654                         if (x->myPositions + sibling->myPositions < 2*logn) //merge !
 655                         {
 656                         //cout << "merge with right sibling -----------------------------------------" << endl;
 657                                 // move bits from sibling to x:
 658
 659                                 (*sibling->block)<<=x->myPositions;
 660                                 (*x->block)|=(*sibling->block);
 661
 662                                 x->myPositions+=sibling->myPositions;
 663                                 x->myRank+=sibling->myRank;
 664                                 updateCountersOnPathToRoot(x);
 665                                 rbDelete(sibling, callUpdateCountersOnPathToRoot);
 666                                 delete sibling;
 667                         }
 668                         else sibling = getNil(); //to try the left sibling!
 669                 }
 670                 else if ((sibling= (BVNode*) treePredecessor(x)) != getNil())
 671                 {
 672                         if (x->myPositions + sibling->myPositions < 2*logn) //merge !
 673                         {
 674                                 // move bits from sibling to x: (more complicated, needs shift!)
 675                                 //cout << "merge with left sibling -----------------------------------------" << endl;
 676                                 (*x->block)<<=sibling->myPositions;
 677                                 x->myPositions+=sibling->myPositions;
 678
 679                                 (*x->block)|=(*sibling->block);
 680
 681                                 x->myRank+=sibling->myRank;
 682                                 updateCountersOnPathToRoot(x);
 683                                 rbDelete(sibling, callUpdateCountersOnPathToRoot);
 684                                 delete sibling;
 685                         }
 686
 687
 688
 689                 } // end else if
 690         } // end else if
 691
 692
 693
 694 }
 695
 696 void BVTree::writeTree(char *writefile){
 697         std::ofstream write(writefile);
 698         if (!write)
 699         {
 700                 cerr << "error: Error writing file: " << writefile<< "." << endl;
 701                 exit(EXIT_FAILURE);
 702         }
 703         writeTree(write);
 704 }
 705
 706
 707 ulong* BVTree::getBits(){
 708         BVNode *n = getRoot();
 709         ulong blockCounter=0;
 710         ulong len = getPositions();
 711
 712 //      int W = sizeof(ulong)*8;
 713
 714
 715         ulong bitsLength = len/W + ((len%W==0)?0:1);
 716
 717         ulong *bits = new ulong[bitsLength];
 718
 719         ulong i=0; //0 .. bitsLength-1
 720         int j=0; //0 .. W-1
 721
 722         ulong mask_LeftBitSet = 1;
 723
 724         mask_LeftBitSet <<= W-1;
 725
 726         n=(BVNode*) treeMinimum(root);
 727         while (n != getNil()) {
 728                 #ifndef NDEBUG
 729                 if (n->block == 0) {
 730                         cerr << "getBits(): block not found !!!" << endl;
 731                         exit(EXIT_FAILURE);
 732                 }
 733                 #endif
 734                 for (blockCounter=0; blockCounter < n->myPositions; blockCounter++) {
 735                         if (j == W) {
 736                                 i++;
 737                                 j=0;
 738                         }
 739                         bits[i] >>= 1; // set 0
 740
 741                         if ((*n->block)[blockCounter]) bits[i] |= mask_LeftBitSet; // set 1
 742                         j++;
 743                 }
 744                 n=(BVNode*) treeSuccessor(n);
 745         }
 746
 747         if (i != bitsLength-1) {
 748                 cout << "last index is wrong" << endl;
 749                 exit(EXIT_FAILURE);
 750         }
 751         while (j < W) {
 752                 bits[i] >>= 1;
 753                 j++;
 754         }
 755
 756         return bits;
 757 }
 758
 759 void BVTree::writeTree(ostream& stream){
 760         BVNode *x;
 761         char c=0;
 762         ulong cCounter=0;
 763         ulong blockCounter=0;
 764
 765         x = (BVNode*) treeMinimum(getRoot());
 766
 767         while (x != getNil()){
 768                 blockCounter=x->myPositions;
 769                 while (blockCounter > 0)
 770                 {
 771                         while (blockCounter > 0 && cCounter < 8 )
 772                         {
 773                                 c<<=1;
 774                                 if ((*x->block)[x->myPositions - blockCounter]) c++;
 775                                 cCounter++;
 776                                 blockCounter--;
 777                         }
 778                         if (cCounter == 8)
 779                         {
 780                                 stream << c;
 781                                 cCounter = 0;
 782                         }
 783                 }
 784
 785
 786                 x = (BVNode*) treeSuccessor(x);
 787         }
 788
 789         if (cCounter != 0) {
 790                 while (cCounter < 8 )
 791                 {
 792                         c<<=1; // fill with zeros.
 793                         cCounter++;
 794                 }
 795                 stream << c;
 796         }
 797 }
 798
 799
 800 void BVTree::appendBit(bool bit){
 801         ulong pos = 1;
 802         if (root != getNil()) pos= getRoot()->subTreePositions + 1;
 803
 804         insertBit(bit, pos);
 805 }
 806
 807 void BVTree::insertBit(bool bit, ulong i){
 808         if (getRoot() == getNil())
 809         {
 810                 BVNode *newNode;
 811                 newNode = new BVNode(getNil());
 812                 newNode->color=BLACK;
 813                 bitset<2*logn> *newBlock;
 814                 newBlock=new bitset<2*logn>;
 815                 newNode->block = newBlock;
 816                 setRoot(newNode);
 817
 818         }
 819
 820         BVNode* x = getRoot();
 821
 822         #ifndef NDEBUG
 823         if (i > x->subTreePositions+1)
 824         {
 825                 printNode(x);
 826                 cerr << "error: insertBit: position " << i <<" in block not available, only " << x->myPositions <<" positions.\n"; //shouldn't happen
 827                 exit(EXIT_FAILURE);
 828         }
 829         if (i < 1)
 830         {
 831                 cerr << "error: insertBit: position " << i <<" is not valid.\n"; //shouldn't happen
 832                 exit(EXIT_FAILURE);
 833         }
 834         #endif
 835
 836         ulong lsP=0;
 837
 838
 839         while (true)
 840         {
 841                 // update subTree-counters
 842                 (x->subTreePositions)++;
 843                 if (bit) (x->subTreeRank)++;
 844
 845                 lsP = x->getLeft()->subTreePositions;
 846
 847                 if (lsP >= i)
 848                 {//     cout << "A" << endl;
 849                         x=x->getLeft();
 850                 }
 851                 else if (lsP+x->myPositions >= i-1){ //-1 to append to last position in current node
 852                         i-=lsP;
 853                         break;
 854                 }
 855                 else{
 856                         i-=(lsP+x->myPositions);
 857                         x=x->getRight();
 858                 }
 859         }
 860
 861         // now put the bit into the block x:
 862         bitset<2*logn> mask;
 863
 864         if (x->myPositions > 0)
 865         {
 866                 if (i != 1)
 867                 {
 868                         mask.set();
 869                         mask>>=2*logn - i +1; // make 1's at all positions < i
 870                         mask &= *(x->block);      // store bits in front of new bit
 871                         (*(x->block)>>=i-1)<<=i;  // shift bits by one
 872                         (*x->block)|=mask;        // restore bits in front of new bit
 873                 }
 874                 else
 875                   (*x->block)<<=1;
 876         }
 877
 878         (*x->block)[i-1]=bit;     // set new bit
 879
 880         // update local pointers
 881         (x->myPositions)++;      //update p (leaf)
 882         if (bit) (x->myRank)++;  //update r (leaf)
 883
 884         #ifndef NDEBUG
 885         if ((int)x->myPositions > 2*logn)
 886         {
 887                 cerr << "error: positions in block already too many.\n"; //shouldn't happen
 888                 exit(EXIT_FAILURE);
 889         }
 890         #endif
 891
 892         // split and rotate, if necessary
 893         if ((int)x->myPositions == 2*logn)
 894         {
 895                 //cout << "split !-------------" << endl;
 896
 897                 // new node:
 898                 BVNode *newNode;
 899                 newNode = new BVNode(getNil());
 900
 901                 //find place for new node:
 902                 BVNode *y;// some parent of new node
 903                 if (x->getRight() != getNil()) {
 904                         y = (BVNode*) this->treeMinimum(x->getRight());
 905                         y->setLeft(newNode);
 906                 } else {
 907                         y=x;
 908                         y->setRight(newNode);
 909                 }
 910                 newNode->setParent(y);
 911
 912                 //new block:
 913                 bitset<2*logn> *newBlock;
 914                 newBlock=new bitset<2*logn>;
 915                 *newBlock=*x->block>>logn; //copy of bits into the new block
 916
 917                 mask.set();
 918                 mask>>=logn;
 919                 *x->block &= mask; //delete bits that already have been copied to the new block
 920
 921                 newNode->block=newBlock;
 922                 newNode->myRank=(*newNode->block).count();
 923                 newNode->myPositions=logn;
 924                 newNode->color=RED;
 925
 926                 //update old node x:
 927                 x->myRank-=newNode->myRank;     //=(*x->block).count();
 928                 x->myPositions=logn;
 929
 930                 updateCountersOnPathToRoot(newNode);  // meets x
 931                 rbInsertFixup(newNode, callUpdateCounters);
 932
 933         } // end if
 934
 935
 936 }
 937
 938 void BVTree::checkSubTree(BVNode *n){
 939         ulong lP = 0;
 940         ulong lR = 0;
 941         ulong rP = 0;
 942         ulong rR = 0;
 943
 944         if (n->getLeft()!=getNil()) {
 945                 lP = n->getLeft()->subTreePositions;
 946                 lR = n->getLeft()->subTreeRank;
 947                 if (n->getLeft()->getParent() != n) {
 948                         cout << "au"<< endl;
 949                         exit(1);
 950                 }
 951
 952         }
 953
 954         if (n->getRight()!=getNil()) {
 955                 rP = n->getRight()->subTreePositions;
 956                 rR = n->getRight()->subTreeRank;
 957                 if (n->getRight()->getParent() != n) {
 958                         cout << "au"<< endl;
 959                         exit(1);
 960                 }
 961         }
 962
 963         if  ( (n->subTreePositions != (n->myPositions + lP + rP)) ||
 964               (n->subTreeRank != (n->myRank + lR + rR)) ){
 965                 cout << "checkSubTree: error" <<endl;
 966                 cout << "lP: " << lP << endl;
 967                 cout << "lR: " << lR << endl;
 968                 cout << "rP: " << rP << endl;
 969                 cout << "rR: " << rR << endl;
 970                 cout << "n->myPositions + lP + rP: " << n->myPositions + lP + rP << endl;
 971                 cout << "n->myRank + lR + rR: " << n->myRank + lR + rR << endl;
 972                 printNode(n);
 973                 printNode(n->getLeft());
 974                 printNode(n->getRight());
 975                 exit(1);
 976         }
 977
 978         if (n->getLeft()!=getNil()) checkSubTree(n->getLeft());
 979         if (n->getRight()!=getNil()) checkSubTree(n->getRight());
 980 }
 981
 982 void callUpdateCounters(RBNode *n, RBTree *T){
 983         ((BVTree*)T)->updateCounters((BVNode*) n);
 984 }
 985
 986 void callUpdateCountersOnPathToRoot(RBNode *n, RBTree *T){
 987         ((BVTree*)T)->updateCountersOnPathToRoot((BVNode*) n);
 988 }
 989