bittree.h

   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 // 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
  27
  28 #ifndef BVTree
  29 #define BVTree BVTree
  30
  31 #include <iostream>
  32 #include <bitset>
  33 #include <cstdlib>
  34 #include <map>
  35 #include <stack>
  36 #include <cmath>
  37 #include <fstream>
  38 #include <vector>
  39 #include <cstdio>
  40
  41 #include "rbtree.h"
  42 #include "Tools.h"
  43
  44 #ifndef uchar
  45 #define uchar unsigned char
  46 #endif
  47 #ifndef ulong
  48 #define ulong unsigned long
  49 #endif
  50
  51
  52
  53 const int logn = (W * 2);
  54
  55 //upperBound = 2 * logn;
  56 //lowerBound = logn / 2;
  57
  58
  59 class BVNode;
  60 class BVTree;
  61
  62 void callUpdateCounters(RBNode *n, RBTree *T);
  63 void callUpdateCountersOnPathToRoot(RBNode *n, RBTree *T);
  64
  65 class BVNode : public RBNode
  66 {
  67         public:
  68         ulong myPositions; // 4*4 bytes = 16 bytes
  69         ulong myRank;
  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
  72
  73         std::bitset<2*logn> *block; // 4 words
  74
  75
  76         BVNode()
  77                 : RBNode(this), myPositions(0), myRank(0), subTreePositions(0), subTreeRank(0), block(0) {
  78         }
  79
  80
  81         BVNode(BVNode* n)
  82                 : RBNode(n), myPositions(0), myRank(0), subTreePositions(0), subTreeRank(0), block(0) {
  83         }
  84
  85         ~BVNode(){
  86                 delete block;
  87                 block = 0;
  88         }
  89
  90
  91         BVNode* getParent(){
  92                 return ((BVNode*) ((RBNode*) this)->parent);
  93         }
  94
  95         BVNode* getLeft(){
  96                 return ((BVNode*) ((RBNode*) this)->left);
  97         }
  98
  99         BVNode* getRight(){
 100                 return ((BVNode*) ((RBNode*) this)->right);
 101         }
 102
 103         void setParent(BVNode* n){
 104                 ((RBNode*) this)->parent=(RBNode*)n;
 105         }
 106
 107         void setLeft(BVNode* n){
 108                 ((RBNode*) this)->left=(RBNode*)n;
 109         }
 110
 111         void setRight(BVNode* n){
 112                 ((RBNode*) this)->right=(RBNode*)n;
 113         }
 114
 115 };
 116
 117
 118 class BVTree : public RBTree{
 119 public:
 120
 121   //Constructors
 122   BVTree(){
 123
 124         setNil(new BVNode());
 125         setRoot(getNil());
 126
 127         tempnil = getNil();
 128
 129         tempbit = new std::bitset<2*logn>;
 130   }
 131
 132   //Destructor:
 133   ~BVTree();
 134
 135   bool operator[](ulong);
 136
 137
 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);
 142
 143   ulong rank0(ulong i);
 144   ulong rank1(ulong i);
 145   ulong rank(bool b, ulong i){return b?rank1(i):rank0(i);}
 146
 147   ulong select0(ulong i);
 148   ulong select1(ulong i);
 149   ulong select(bool b, ulong i){return b?select1(i):select0(i);}
 150
 151   void setRoot(BVNode* n){
 152         ((RBTree*) this)->root=(RBNode*)n;
 153   }
 154
 155   BVNode* getRoot(){
 156         return ((BVNode*) ((RBTree*) this)->root);
 157   }
 158
 159   void setNil(BVNode* n){
 160         tempnil = n;
 161         ((RBTree*) this)->nil=(RBNode*)n;
 162   }
 163
 164   BVNode* getNil(){
 165         return tempnil;
 166
 167   }
 168
 169   // write bits back into a stream:
 170   ulong* getBits();
 171   void writeTree(char *writefile);
 172   void writeTree(std::ostream& stream); //e.g. stream = cout
 173
 174   int getTreeMaxDepth();
 175   int getTreeMinDepth();
 176   ulong getPositions();
 177   ulong getRank();
 178
 179   void iterateReset();
 180   bool iterateGetBit();
 181   bool iterateNext();
 182   ulong iterateGetRank(bool bit);
 183
 184   bool getLastBitDeleted(){return lastBitDeleted;}
 185   ulong getLastRank(){return lastRank;}
 186
 187   void checkSubTree(BVNode *n);
 188
 189   void updateCounters(BVNode *n);
 190   void updateCountersOnPathToRoot(BVNode *walk);
 191
 192   //debug:
 193   void printNode(ulong i);
 194
 195 protected:
 196
 197   ulong iterate;
 198   ulong iterateLocal;
 199   ulong iterateRank;
 200   BVNode *iterateNode;
 201
 202   BVNode *tempnil;
 203
 204   bool lastBitDeleted;
 205   ulong lastRank;
 206
 207
 208   std::bitset<2*logn> *tempbit;
 209
 210   // content of BVNode, for debugging:
 211   void printNode(BVNode *n);
 212
 213   // other operations:
 214   ulong getLocalRank(BVNode* n, ulong position);
 215   ulong getLocalSelect0(BVNode* n, ulong query);
 216   ulong getLocalSelect1(BVNode* n, ulong query);
 217
 218   void deleteNode(BVNode *n);
 219   void deleteLeaf(BVNode *leaf);
 220 };
 221
 222
 223 #endif
 224