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 */
  33
  34     void addNewBlock();
  35     void setFirstBit(usint value);
  36
  37     usint size, items, blocks;
  38     usint block_size, superblock_bytes;
  39
  40     FastBitBuffer*   buffer;
  41
  42     std::list<usint*> array_blocks;
  43     usint*            array;
  44     usint             blocks_in_superblock, current_blocks;
  45
  46     std::list<usint*> sample_blocks;
  47     usint*            samples;
  48     usint             samples_in_superblock, current_samples;
  49 };
  50
  51
  52 /*
  53   This class provides the core functionality for a bit vector.
  54 */
  55
  56 class BitVector
  57 {
  58   public:
  59     const static usint INDEX_RATE = 5;
  60
  61     BitVector(std::ifstream& file);
  62     BitVector(VectorEncoder& encoder, usint universe_size);
  63     ~BitVector();
  64
  65     void writeTo(std::ofstream& file);
  66
  67 //--------------------------------------------------------------------------
  68
  69 /*
  70     These should be implemented in any actual bit vector.
  71
  72     // rank is not iterator-safe
  73     // regular:   \sum_{i = 0}^{value} V[i]
  74     // at_least:  \sum_{i = 0}^{value - 1} V[i] + 1
  75     usint rank(usint value, bool at_least = false);
  76
  77     usint select(usint index);      // \min value: \sum_{i = 0}^{value} V[i] = index + 1
  78     usint selectNext();
  79
  80     pair_type valueAfter(usint value); // (\min i >= value: V[i] = 1, rank(i) - 1)
  81     pair_type nextValue();
  82
  83     // These versions of select return (value, length_of_run).
  84     // max_length is an upper bound for the length of the run returned.
  85     // V[value] is not included in the length of the run
  86     // These functions are not greedy: the actual length of the run can be more than reported.
  87     // This can happen even if max_length was not reached.
  88     // length_of_run is actually the number of extra items returned past value
  89
  90     pair_type selectRun(usint index, usint max_length);
  91     pair_type selectNextRun(usint max_length);
  92
  93     // isSet is not iterator-safe
  94     bool isSet(usint value); // V[value]
  95 */
  96
  97     inline bool hasNext()
  98     {
  99       return (this->sample.first + cur < this->items - 1);
 100     }
 101
 102 //--------------------------------------------------------------------------
 103
 104     inline usint getSize() { return this->size; }
 105     inline usint getNumberOfItems() { return this->items; }
 106     inline usint getBlockSize() { return this->block_size; }
 107
 108     // This returns only the sizes of dynamically allocated structures.
 109     usint reportSize();
 110
 111   protected:
 112     usint size, items;
 113
 114     FastBitBuffer* buffer;
 115     usint*          array;
 116     usint           block_size;
 117     usint           number_of_blocks;
 118
 119     /*
 120       Each sample is (rank(i) - 1, i) where V[i] = 1.
 121       Number of samples is number_of_blocks + 1.
 122     */
 123     FastBitBuffer* samples;
 124     usint           integer_bits;
 125
 126     FastBitBuffer* rank_index;
 127     usint           rank_rate;
 128
 129     FastBitBuffer* select_index;
 130     usint           select_rate;
 131
 132     // Iterator data. These are enough for a gap-encoded vector.
 133     usint      block;
 134     pair_type  sample;
 135     usint      cur, val;     // cur == 0 is the sample
 136     usint      block_items;
 137
 138     /*
 139       These functions return the sample corresponding to the block the given
 140       index/value might be found in. Parameters are assumed to be valid.
 141     */
 142     usint sampleForIndex(usint index);
 143     usint sampleForValue(usint value);
 144
 145     inline void getSample(usint sample_number)
 146     {
 147       this->block = sample_number;
 148       this->samples->goToItem(2 * sample_number);
 149       this->sample.first = this->samples->readItem();
 150       this->sample.second = this->samples->readItem();
 151       this->cur = 0;
 152       this->val = this->sample.second;
 153       this->block_items = this->samples->readItem() - this->sample.first - 1;
 154       this->buffer->moveBuffer(this->array + (this->block * this->block_size));
 155     }
 156
 157     /*
 158        These functions build a higher level index for faster rank/select queries.
 159        The index consists of about (number of samples) / INDEX_RATE pointers.
 160        The bit vector cannot be used without the index.
 161     */
 162     void indexForRank();
 163     void indexForSelect();
 164 };
 165
 166
 167 } // namespace CSA
 168
 169
 170 #endif // BITVECTOR_H