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 ***************************************************************************/
21 // Implementation of the Dynamic Bit Vector with Indels problem
22 // space: O(n) time: O(log(n))
23 // papers: V. Maekinen, G. Navarro. Dynamic Entropy-Compressed Sequences and Full-Text
24 // Indexes. CPM 2006, Chapter 3.4 Dynamic Structures for Bit Vectors
25 // also: W.-L. Chan, W.-K. Hon, and T.-W. Lam. Compressed index for a dynamic collection
26 // of texts. In Proc. CPM04, LNCS 3109, pages 445-456, 2004
45 #define uchar unsigned char
48 #define ulong unsigned long
53 const int logn = (W * 2);
55 //upperBound = 2 * logn;
56 //lowerBound = logn / 2;
62 void callUpdateCounters(RBNode *n, RBTree *T);
63 void callUpdateCountersOnPathToRoot(RBNode *n, RBTree *T);
65 class BVNode : public RBNode
68 ulong myPositions; // 4*4 bytes = 16 bytes
70 ulong subTreePositions; //number of positions stored in the subtree rooted at this node
71 ulong subTreeRank; //number of bits set in the subtree rooted at this node
73 std::bitset<2*logn> *block; // 4 words
77 : RBNode(this), myPositions(0), myRank(0), subTreePositions(0), subTreeRank(0), block(0) {
82 : RBNode(n), myPositions(0), myRank(0), subTreePositions(0), subTreeRank(0), block(0) {
92 return ((BVNode*) ((RBNode*) this)->parent);
96 return ((BVNode*) ((RBNode*) this)->left);
100 return ((BVNode*) ((RBNode*) this)->right);
103 void setParent(BVNode* n){
104 ((RBNode*) this)->parent=(RBNode*)n;
107 void setLeft(BVNode* n){
108 ((RBNode*) this)->left=(RBNode*)n;
111 void setRight(BVNode* n){
112 ((RBNode*) this)->right=(RBNode*)n;
118 class BVTree : public RBTree{
124 setNil(new BVNode());
129 tempbit = new std::bitset<2*logn>;
135 bool operator[](ulong);
138 // inserts bit at position i, countings begins with 1:
139 void appendBit(bool bit);
140 void insertBit(bool bit, ulong i);
141 void deleteBit(ulong i);
143 ulong rank0(ulong i);
144 ulong rank1(ulong i);
145 ulong rank(bool b, ulong i){return b?rank1(i):rank0(i);}
147 ulong select0(ulong i);
148 ulong select1(ulong i);
149 ulong select(bool b, ulong i){return b?select1(i):select0(i);}
151 void setRoot(BVNode* n){
152 ((RBTree*) this)->root=(RBNode*)n;
156 return ((BVNode*) ((RBTree*) this)->root);
159 void setNil(BVNode* n){
161 ((RBTree*) this)->nil=(RBNode*)n;
169 // write bits back into a stream:
171 void writeTree(char *writefile);
172 void writeTree(std::ostream& stream); //e.g. stream = cout
174 int getTreeMaxDepth();
175 int getTreeMinDepth();
176 ulong getPositions();
180 bool iterateGetBit();
182 ulong iterateGetRank(bool bit);
184 bool getLastBitDeleted(){return lastBitDeleted;}
185 ulong getLastRank(){return lastRank;}
187 void checkSubTree(BVNode *n);
189 void updateCounters(BVNode *n);
190 void updateCountersOnPathToRoot(BVNode *walk);
193 void printNode(ulong i);
208 std::bitset<2*logn> *tempbit;
210 // content of BVNode, for debugging:
211 void printNode(BVNode *n);
214 ulong getLocalRank(BVNode* n, ulong position);
215 ulong getLocalSelect0(BVNode* n, ulong query);
216 ulong getLocalSelect1(BVNode* n, ulong query);
218 void deleteNode(BVNode *n);
219 void deleteLeaf(BVNode *leaf);