incbwt/bits/bitvector.h

   1 #ifndef BITVECTOR_H
   2 #define BITVECTOR_H
   3
   4 #include <fstream>
   5 #include <list>
   6
   7 #include "../misc/definitions.h"
   8 #include "bitbuffer.h"
   9
  10
  11 namespace CSA
  12 {
  13
  14
  15 /*
  16   This class provides the core functionality for encoding a bit vector.
  17 */
  18
  19 class VectorEncoder
  20 {
  21   public:
  22     const static usint SUPERBLOCK_SIZE = MEGABYTE;
  23
  24     // We assume superblock size is divisible by block and sample size.
  25     VectorEncoder(usint block_bytes, usint superblock_size = SUPERBLOCK_SIZE);
  26     ~VectorEncoder();
  27
  28 /*
  29     This should be implemented in any inherited class.
  30
  31     void setBit(usint value);  // Values must be in increasing order.
  32     void setRun(usint start, usint len);
  33 */
  34
  35     void addNewBlock();
  36     void setFirstBit(usint value);
  37
  38     usint size, items, blocks;
  39     usint block_size, superblock_bytes;
  40
  41     WriteBuffer*      buffer;
  42
  43     std::list<usint*> array_blocks;
  44     usint*            array;
  45     usint             blocks_in_superblock, current_blocks;
  46
  47     std::list<usint*> sample_blocks;
  48     usint*            samples;
  49     usint             samples_in_superblock, current_samples;
  50
  51   protected:
  52
  53     // These are not allowed.
  54     VectorEncoder();
  55     VectorEncoder(const VectorEncoder&);
  56     VectorEncoder& operator = (const VectorEncoder&);
  57 };
  58
  59
  60 /*
  61   This class provides the core functionality for a bit vector.
  62 */
  63
  64 class BitVector
  65 {
  66   public:
  67     const static usint INDEX_RATE = 5;
  68
  69     BitVector(std::ifstream& file);
  70     BitVector(std::FILE * file);
  71     BitVector(VectorEncoder& encoder, usint universe_size);
  72     ~BitVector();
  73
  74 //--------------------------------------------------------------------------
  75
  76     void writeTo(std::ofstream& file) const;
  77     void writeTo(std::FILE *file) const;
  78
  79     inline usint getSize() const { return this->size; }
  80     inline usint getNumberOfItems() const { return this->items; }
  81     inline usint getBlockSize() const { return this->block_size; }
  82
  83     // This returns only the sizes of the dynamically allocated structures.
  84     usint reportSize() const;
  85
  86     usint getCompressedSize() const;
  87
  88 //--------------------------------------------------------------------------
  89
  90     class Iterator
  91     {
  92       public:
  93         Iterator(const BitVector& par);
  94         ~Iterator();
  95
  96         inline bool hasNext() const
  97         {
  98           return (this->sample.first + this->cur < this->parent.items - 1);
  99         }
 100
 101       protected:
 102         const BitVector& parent;
 103
 104         usint      block;
 105         pair_type  sample;
 106         usint      cur, val, run; // cur == 0 is the sample
 107         usint      block_items;
 108
 109         ReadBuffer buffer, samples;
 110
 111         /*
 112           These functions return the sample corresponding to the block the given
 113           index/value might be found in. Parameters are assumed to be valid.
 114         */
 115         usint sampleForIndex(usint index);
 116         usint sampleForValue(usint value);
 117
 118         inline void getSample(usint sample_number)
 119         {
 120           this->block = sample_number;
 121           this->samples.goToItem(2 * sample_number);
 122           this->sample.first = this->samples.readItem();
 123           this->sample.second = this->samples.readItem();
 124           this->cur = 0;
 125           this->val = this->sample.second;
 126           this->block_items = this->samples.readItem() - this->sample.first - 1;
 127           this->buffer.moveBuffer(this->parent.array + (this->block * this->parent.block_size));
 128         }
 129
 130         // These are not allowed.
 131         Iterator();
 132         Iterator(const Iterator&);
 133         Iterator& operator = (const Iterator&);
 134     };
 135
 136 /*
 137     These should be implemented in any actual iterator.
 138
 139     // rank invalidates the iterator
 140     // regular:   \sum_{i = 0}^{value} V[i]
 141     // at_least:  \sum_{i = 0}^{value - 1} V[i] + 1
 142     usint rank(usint value, bool at_least = false);
 143
 144     usint select(usint index);      // \min value: \sum_{i = 0}^{value} V[i] = index + 1
 145     usint selectNext();
 146
 147     pair_type valueAfter(usint value); // (\min i >= value: V[i] = 1, rank(i) - 1)
 148     pair_type nextValue();
 149
 150     // These versions of select return (value, length_of_run).
 151     // max_length is an upper bound for the length of the run returned.
 152     // V[value] is not included in the length of the run
 153     // These functions are not greedy: the actual length of the run can be more than reported.
 154     // This can happen even if max_length was not reached.
 155     // length_of_run is actually the number of extra items returned past value
 156
 157     pair_type selectRun(usint index, usint max_length);
 158     pair_type selectNextRun(usint max_length);
 159
 160     // isSet invalidates the iterator
 161     bool isSet(usint value); // V[value]
 162 */
 163
 164 //--------------------------------------------------------------------------
 165
 166   protected:
 167     usint size, items;
 168
 169     const usint* array;
 170     usint        block_size;
 171     usint        number_of_blocks;
 172
 173     /*
 174       Each sample is (rank(i) - 1, i) where V[i] = 1.
 175       Number of samples is number_of_blocks + 1.
 176     */
 177     ReadBuffer*  samples;
 178     usint        integer_bits;
 179
 180     ReadBuffer*  rank_index;
 181     usint        rank_rate;
 182
 183     ReadBuffer*  select_index;
 184     usint        select_rate;
 185
 186     /*
 187        These functions build a higher level index for faster rank/select queries.
 188        The index consists of about (number of samples) / INDEX_RATE pointers.
 189        The bit vector cannot be used without the index.
 190     */
 191     void indexForRank();
 192     void indexForSelect();
 193
 194     // These are not allowed.
 195     BitVector();
 196     BitVector(const BitVector&);
 197     BitVector& operator = (const BitVector&);
 198 };
 199
 200
 201 } // namespace CSA
 202
 203
 204 #endif // BITVECTOR_H