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