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
56 const int logn = LOGN;
58 //upperBound = 2 * logn;
59 //lowerBound = logn / 2;
65 void callUpdateCounters(RBNode *n, RBTree *T);
66 void callUpdateCountersOnPathToRoot(RBNode *n, RBTree *T);
68 class BVNode : public RBNode
71 ulong myPositions; // 4*4 bytes = 16 bytes
73 ulong subTreePositions; //number of positions stored in the subtree rooted at this node
74 ulong subTreeRank; //number of bits set in the subtree rooted at this node
76 std::bitset<2*logn> *block; // 4 bytes
80 : RBNode(this), myPositions(0), myRank(0), subTreePositions(0), subTreeRank(0), block(0) {
85 : RBNode(n), myPositions(0), myRank(0), subTreePositions(0), subTreeRank(0), block(0) {
95 return ((BVNode*) ((RBNode*) this)->parent);
99 return ((BVNode*) ((RBNode*) this)->left);
103 return ((BVNode*) ((RBNode*) this)->right);
106 void setParent(BVNode* n){
107 ((RBNode*) this)->parent=(RBNode*)n;
110 void setLeft(BVNode* n){
111 ((RBNode*) this)->left=(RBNode*)n;
114 void setRight(BVNode* n){
115 ((RBNode*) this)->right=(RBNode*)n;
121 class BVTree : public RBTree{
127 setNil(new BVNode());
132 tempbit = new std::bitset<2*logn>;
138 bool operator[](ulong);
141 // inserts bit at position i, countings begins with 1:
142 void appendBit(bool bit);
143 void insertBit(bool bit, ulong i);
144 void deleteBit(ulong i);
146 ulong rank0(ulong i);
147 ulong rank1(ulong i);
148 ulong rank(bool b, ulong i){return b?rank1(i):rank0(i);}
150 ulong select0(ulong i);
151 ulong select1(ulong i);
152 ulong select(bool b, ulong i){return b?select1(i):select0(i);}
154 void setRoot(BVNode* n){
155 ((RBTree*) this)->root=(RBNode*)n;
159 return ((BVNode*) ((RBTree*) this)->root);
162 void setNil(BVNode* n){
164 ((RBTree*) this)->nil=(RBNode*)n;
172 // write bits back into a stream:
174 void writeTree(char *writefile);
175 void writeTree(std::ostream& stream); //e.g. stream = cout
177 int getTreeMaxDepth();
178 int getTreeMinDepth();
179 ulong getPositions();
183 bool iterateGetBit();
185 ulong iterateGetRank(bool bit);
187 bool getLastBitDeleted(){return lastBitDeleted;}
188 ulong getLastRank(){return lastRank;}
190 void checkSubTree(BVNode *n);
192 void updateCounters(BVNode *n);
193 void updateCountersOnPathToRoot(BVNode *walk);
196 void printNode(ulong i);
211 std::bitset<2*logn> *tempbit;
213 // content of BVNode, for debugging:
214 void printNode(BVNode *n);
217 ulong getLocalRank(BVNode* n, ulong position);
218 ulong getLocalSelect0(BVNode* n, ulong query);
219 ulong getLocalSelect1(BVNode* n, ulong query);
221 void deleteNode(BVNode *n);
222 void deleteLeaf(BVNode *leaf);