1 /***************************************************************************
2 * Copyright (C) 2006 by Wolfgang Gerlach *
3 * No object matches key 'wgerlach'. *
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. *
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. *
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 ***************************************************************************/
31 //std::ostream& operator<<(std::ostream& os, node& n) { ... }
42 BVTree::BVTree(char *readfile){
44 std::ifstream file(readfile);
47 cout << "error reading file "<< readfile <<" !\n";
52 tempnil = (BVNode*) ((RBTree*) this)->nil;
53 tempbit = new bitset<2*logn>;
63 for (int i=7; i>=0; i--)
73 void BVTree::iterateReset(){
77 iterateNode = (BVNode*) treeMinimum(root);
78 iterateRank = ((*iterateNode->block)[0])?1:0;
85 bool BVTree::iterateGetBit(){
86 return ((*iterateNode->block)[iterateLocal]);
89 ulong BVTree::iterateGetRank(bool bit){
90 if (bit) return iterateRank;
91 else return (iterate - iterateRank);
94 bool BVTree::iterateNext(){
97 if (iterate > getPositions()) return false;
100 if (iterateLocal < iterateNode->myPositions-1) {
103 // jump to next leaf;
104 iterateNode = (BVNode*) treeSuccessor(iterateNode);
106 if (iterateNode==getNil()) {
107 cout << "iterateNode==getNil()" << endl;
113 if ((*iterateNode->block)[iterateLocal]) iterateRank++;
118 ulong BVTree::getPositions(){
120 if (getRoot() == getNil()) return 0;
121 return getRoot()->subTreePositions;
124 ulong BVTree::getRank(){
126 if (getRoot() == getNil()) return 0;
127 return getRoot()->subTreeRank;
131 void BVTree::printNode(BVNode *n){
132 int commas=(2*logn)/10;
136 cout << "address: " << n << endl;
138 if (n->block != 0 && (n!=getNil()))
140 int size = 2*logn + 1 +commas;
142 char *myblock = (char *) new char[size];
144 cerr << "error: printNode: myblock == 0" << endl;
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;
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++;
164 myblock[i+commashift]='-';
165 if (i+commashift > size-2) {
166 cerr << "A) printNode: array wrong index" << endl;
172 for (int i=10; i < 2*logn; i++){
175 if (i+commashift >= size-2) {
176 cerr << "B) printNode: array wrong index" << endl;
180 myblock[i+commashift]=',';
186 myblock[size - 1]='\0';
188 cout << "block: \"" << myblock << "\"" << endl;
193 cout << "block: none" << endl;
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;
208 int BVTree::getTreeMaxDepth(){
209 return getNodeMaxDepth(root);
212 int BVTree::getTreeMinDepth(){
213 return getNodeMinDepth(root);
217 void BVTree::updateCounters(BVNode *n){
219 if (n == getNil()) return;
226 if (n->getLeft() != getNil()) {
227 lR = n->getLeft()->subTreeRank;
228 lP = n->getLeft()->subTreePositions;
231 if (n->getRight() != getNil()) {
232 rR = n->getRight()->subTreeRank;
233 rP = n->getRight()->subTreePositions;
236 n->subTreeRank =lR + rR + n->myRank;
237 n->subTreePositions=lP + rP + n->myPositions;
241 ulong BVTree::getLocalRank(BVNode* n, ulong position){
244 if (position > n->myPositions) {
245 cerr << "error: getLocalRank: invalid position in block.\n";
250 *tempbit =*(n->block)<<((2*logn)-position);
251 return tempbit->count();
255 //for (ulong i = 0; i < position; i++) {
256 // if ((*n->block)[i]) rank++;
260 ulong BVTree::getLocalSelect1(BVNode* n, ulong query){
263 if (query > n->myPositions) {
264 cerr << "error: getLocalSelect1: invalid position in block.\n";
269 for (i = 0; select < query; i++) { // TODO is there a faster solution similar to rank ?
270 if ((*n->block)[i]) select++;
276 ulong BVTree::getLocalSelect0(BVNode* n, ulong query){
279 if (query > n->myPositions) {
280 cerr << "error: getLocalSelect0: invalid position in block.\n";
285 for (i = 0; select < query; i++) {
286 if (!(*n->block)[i]) select++;
293 void BVTree::printNode(ulong i){
294 BVNode* x = getRoot();
298 cerr << "error: printNode(int i): root=NULL.\n";
303 if (i > x->myPositions) {
304 cerr << "error: printNode(int i): invalid position in block.\n";
311 //find the corresponding block:
315 lP = x->getLeft()->subTreePositions;
322 else if (lP+x->myPositions >= i){
327 i-=(lP+x->myPositions);
333 cout << "i=" << i << endl;
338 bool BVTree::operator[](ulong i){
340 BVNode* x = getRoot();
343 //find the corresponding block:
347 lsP = x->getLeft()->subTreePositions;
352 if (x->getLeft()==getNil()) {
353 cout << "lsP: " << lsP << endl;
355 cout << "ihhh" << endl;
362 else if (lsP+x->myPositions >= i){
367 i-=(lsP+x->myPositions);
369 if (x->getRight()==getNil()) {
370 cout << "i: " << i << endl;
371 cout << "lsP: " << lsP << endl;
372 cout << "x->myPositions: " << x->myPositions << endl;
374 cout << "ihhh" << endl;
383 return (*x->block)[i-1];
387 ulong BVTree::rank1(ulong i){
388 BVNode* x = getRoot();
390 if (i == this->getPositions() + 1) i--;
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;
404 //find the corresponding block:
408 lsP = x->getLeft()->subTreePositions;
409 lsR = x->getLeft()->subTreeRank;
412 {// cout << "L" << endl;
415 else if (lsP+x->myPositions >= i){
420 else{//cout << "R" << endl;
421 i-=(lsP+x->myPositions);
422 rank+=(lsR+x->myRank);
427 rank+=getLocalRank(x, i);
431 ulong BVTree::rank0(ulong i){
432 if (this->getPositions() == 0) return 0;
436 ulong BVTree::select1(ulong i){
437 BVNode* x = getRoot();
440 if (i > x->subTreeRank ) {
441 cerr << "error: select1: invalid position in bittree: " << i << endl;
449 //find the corresponding block:
452 // update subTree-counters
455 lsP = x->getLeft()->subTreePositions;
456 lsR = x->getLeft()->subTreeRank;
461 else if (lsR+x->myRank >= i) {
468 select+=(lsP+x->myPositions);
472 select+=getLocalSelect1(x, i);
479 ulong BVTree::select0(ulong i){
480 BVNode* x = getRoot();
484 if (i > (x->subTreePositions - x->subTreeRank) || i < 0) {
485 cerr << "error: select1: invalid position in bittree: " << i << endl;
496 //find the corresponding block:
499 // update subTree-counters
502 lsP = x->getLeft()->subTreePositions;
503 lsR = x->getLeft()->subTreeRank;
504 lmR = x->getLeft()->myRank;
505 lmP = x->getLeft()->myPositions;
511 else if ((lsP-lsR)+(x->myPositions-x->myRank) >= i){
517 i-=((lsP-lsR)+(x->myPositions-x->myRank));
518 select+=(lsP+x->myPositions);
523 select+=getLocalSelect0(x, i);
529 void BVTree::updateCountersOnPathToRoot(BVNode *walk){
531 while (walk != getNil()) {
532 updateCounters(walk);
533 walk=walk->getParent();
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;
541 if (n->getLeft() != getNil() && n->getLeft()) deleteNode(n->getLeft());
542 if (n->getRight() != getNil() && n->getRight()) deleteNode(n->getRight());
550 // TODO improve by returning bitvalue
552 void BVTree::deleteBit(ulong i){
554 BVNode* x = getRoot();
560 cerr << "error: deleteBit, root is empty\n"; //shouldn't happen
564 if (i > x->subTreePositions || i < 1)
566 cerr << "error: A, position " << i <<" in block not available, only " << x->myPositions <<" positions.\n"; //shouldn't happen
575 //find the corresponding block:
578 // update of pointers is not yet possible: call updateCountersOnPathToRoot
580 lsP = x->getLeft()->subTreePositions;
581 lsR = x->getLeft()->subTreeRank;
587 if (x->getLeft()==getNil()) exit(EXIT_FAILURE);
591 else if (lsP+x->myPositions >= i){
597 i-=(lsP+x->myPositions);
598 rank+=(lsR+x->myRank); // for speedup!
600 if (x->getRight()==getNil()) exit(EXIT_FAILURE);
608 // now delete the bit from the block x:
609 bit =(*x->block)[i-1];
611 // store bit and rank information for speedup
613 rank+=getLocalRank(x, i);
614 lastRank=(bit?rank:old_i-rank);
617 if (i > x->myPositions) {
618 cerr << "error: B, position " << i <<" in block not available, only " << x->myPositions <<" positions.\n"; //shouldn't happen
628 mask>>=(2*logn - i + 1);
630 (*(x->block)>>=i)<<=i-1; // shift bits by one
631 (*x->block)|=mask; // restore bits in front of deleted bit
633 *(x->block)>>=1; // shift bits by one
637 if (bit) x->myRank--;
639 updateCountersOnPathToRoot(x);
642 if (x->myPositions == 0){ // if merging was not possible:
644 rbDelete(x, callUpdateCountersOnPathToRoot);
647 } else if (x->myPositions <= logn/2) // merge (and rotate), if necessary:
650 BVNode *sibling = (BVNode*) treeSuccessor(x);
651 //cout << "try to merge -----------------------------------------" << endl;
652 if (sibling != getNil())
654 if (x->myPositions + sibling->myPositions < 2*logn) //merge !
656 //cout << "merge with right sibling -----------------------------------------" << endl;
657 // move bits from sibling to x:
659 (*sibling->block)<<=x->myPositions;
660 (*x->block)|=(*sibling->block);
662 x->myPositions+=sibling->myPositions;
663 x->myRank+=sibling->myRank;
664 updateCountersOnPathToRoot(x);
665 rbDelete(sibling, callUpdateCountersOnPathToRoot);
668 else sibling = getNil(); //to try the left sibling!
670 else if ((sibling= (BVNode*) treePredecessor(x)) != getNil())
672 if (x->myPositions + sibling->myPositions < 2*logn) //merge !
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;
679 (*x->block)|=(*sibling->block);
681 x->myRank+=sibling->myRank;
682 updateCountersOnPathToRoot(x);
683 rbDelete(sibling, callUpdateCountersOnPathToRoot);
696 void BVTree::writeTree(char *writefile){
697 std::ofstream write(writefile);
700 cerr << "error: Error writing file: " << writefile<< "." << endl;
707 ulong* BVTree::getBits(){
708 BVNode *n = getRoot();
709 ulong blockCounter=0;
710 ulong len = getPositions();
712 int W = sizeof(ulong)*8;
715 ulong bitsLength = len/W + ((len%W==0)?0:1);
717 ulong *bits = new ulong[bitsLength];
719 ulong i=0; //0 .. bitsLength-1
722 ulong mask_LeftBitSet = 1;
724 mask_LeftBitSet <<= W-1;
726 n=(BVNode*) treeMinimum(root);
727 while (n != getNil()) {
730 cerr << "getBits(): block not found !!!" << endl;
734 for (blockCounter=0; blockCounter < n->myPositions; blockCounter++) {
739 bits[i] >>= 1; // set 0
741 if ((*n->block)[blockCounter]) bits[i] |= mask_LeftBitSet; // set 1
744 n=(BVNode*) treeSuccessor(n);
747 if (i != bitsLength-1) {
748 cout << "last index is wrong" << endl;
759 void BVTree::writeTree(ostream& stream){
763 ulong blockCounter=0;
765 x = (BVNode*) treeMinimum(getRoot());
767 while (x != getNil()){
768 blockCounter=x->myPositions;
769 while (blockCounter > 0)
771 while (blockCounter > 0 && cCounter < 8 )
774 if ((*x->block)[x->myPositions - blockCounter]) c++;
786 x = (BVNode*) treeSuccessor(x);
790 while (cCounter < 8 )
792 c<<=1; // fill with zeros.
800 void BVTree::appendBit(bool bit){
802 if (root != getNil()) pos= getRoot()->subTreePositions + 1;
807 void BVTree::insertBit(bool bit, ulong i){
808 if (getRoot() == getNil())
811 newNode = new BVNode(getNil());
812 newNode->color=BLACK;
813 bitset<2*logn> *newBlock;
814 newBlock=new bitset<2*logn>;
815 newNode->block = newBlock;
820 BVNode* x = getRoot();
823 if (i > x->subTreePositions+1)
826 cerr << "error: insertBit: position " << i <<" in block not available, only " << x->myPositions <<" positions.\n"; //shouldn't happen
831 cerr << "error: insertBit: position " << i <<" is not valid.\n"; //shouldn't happen
841 // update subTree-counters
842 (x->subTreePositions)++;
843 if (bit) (x->subTreeRank)++;
845 lsP = x->getLeft()->subTreePositions;
848 {// cout << "A" << endl;
851 else if (lsP+x->myPositions >= i-1){ //-1 to append to last position in current node
856 i-=(lsP+x->myPositions);
861 // now put the bit into the block x:
864 if (x->myPositions > 0)
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
878 (*x->block)[i-1]=bit; // set new bit
880 // update local pointers
881 (x->myPositions)++; //update p (leaf)
882 if (bit) (x->myRank)++; //update r (leaf)
885 if ((int)x->myPositions > 2*logn)
887 cerr << "error: positions in block already too many.\n"; //shouldn't happen
892 // split and rotate, if necessary
893 if ((int)x->myPositions == 2*logn)
895 //cout << "split !-------------" << endl;
899 newNode = new BVNode(getNil());
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());
908 y->setRight(newNode);
910 newNode->setParent(y);
913 bitset<2*logn> *newBlock;
914 newBlock=new bitset<2*logn>;
915 *newBlock=*x->block>>logn; //copy of bits into the new block
919 *x->block &= mask; //delete bits that already have been copied to the new block
921 newNode->block=newBlock;
922 newNode->myRank=(*newNode->block).count();
923 newNode->myPositions=logn;
927 x->myRank-=newNode->myRank; //=(*x->block).count();
930 updateCountersOnPathToRoot(newNode); // meets x
931 rbInsertFixup(newNode, callUpdateCounters);
938 void BVTree::checkSubTree(BVNode *n){
944 if (n->getLeft()!=getNil()) {
945 lP = n->getLeft()->subTreePositions;
946 lR = n->getLeft()->subTreeRank;
947 if (n->getLeft()->getParent() != n) {
954 if (n->getRight()!=getNil()) {
955 rP = n->getRight()->subTreePositions;
956 rR = n->getRight()->subTreeRank;
957 if (n->getRight()->getParent() != n) {
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;
973 printNode(n->getLeft());
974 printNode(n->getRight());
978 if (n->getLeft()!=getNil()) checkSubTree(n->getLeft());
979 if (n->getRight()!=getNil()) checkSubTree(n->getRight());
982 void callUpdateCounters(RBNode *n, RBTree *T){
983 ((BVTree*)T)->updateCounters((BVNode*) n);
986 void callUpdateCountersOnPathToRoot(RBNode *n, RBTree *T){
987 ((BVTree*)T)->updateCountersOnPathToRoot((BVNode*) n);