incbwt/bits/deltavector.cpp

   1 #include <cstdlib>
   2
   3 #include "deltavector.h"
   4
   5
   6 namespace CSA
   7 {
   8
   9
  10 DeltaVector::DeltaVector(std::ifstream& file) :
  11   BitVector(file)
  12 {
  13 }
  14 DeltaVector::DeltaVector(std::FILE * file) :
  15   BitVector(file)
  16 {
  17 }
  18
  19
  20 DeltaVector::DeltaVector(DeltaEncoder& encoder, usint universe_size) :
  21   BitVector(encoder, universe_size)
  22 {
  23 }
  24
  25 DeltaVector::~DeltaVector()
  26 {
  27 }
  28
  29 //--------------------------------------------------------------------------
  30
  31 usint
  32 DeltaVector::rank(usint value, bool at_least)
  33 {
  34   if(value >= this->size) { return this->items; }
  35   this->getSample(this->sampleForValue(value));
  36
  37   while(this->cur < this->block_items && this->val < value)
  38   {
  39     this->val += this->buffer->readDeltaCode();
  40     this->cur++;
  41   }
  42
  43   usint idx = this->sample.first + this->cur + 1;
  44   if(!at_least && this->val > value) { idx--; }
  45   if(at_least && this->val < value)  { this->getSample(this->block + 1); }
  46   return idx;
  47 }
  48
  49 usint
  50 DeltaVector::select(usint index)
  51 {
  52   if(index >= this->items) { return this->size; }
  53   this->getSample(this->sampleForIndex(index));
  54
  55   usint lim = index - this->sample.first;
  56   for(; this->cur < lim; this->cur++)
  57   {
  58     this->val += this->buffer->readDeltaCode();
  59   }
  60
  61   return this->val;
  62 }
  63
  64 usint
  65 DeltaVector::selectNext()
  66 {
  67   if(this->cur >= this->block_items)
  68   {
  69     this->getSample(this->block + 1);
  70     return this->val;
  71   }
  72
  73   this->cur++;
  74   this->val += this->buffer->readDeltaCode();
  75   return this->val;
  76 }
  77
  78 pair_type
  79 DeltaVector::valueAfter(usint value)
  80 {
  81   if(value >= this->size) { return pair_type(this->size, this->items); }
  82   this->getSample(this->sampleForValue(value));
  83
  84   while(this->cur < this->block_items && this->val < value)
  85   {
  86     this->val += this->buffer->readDeltaCode();
  87     this->cur++;
  88   }
  89   if(this->val < value)
  90   {
  91     this->getSample(this->block + 1);
  92   }
  93
  94   return pair_type(this->val, this->sample.first + this->cur);
  95 }
  96
  97 pair_type
  98 DeltaVector::nextValue()
  99 {
 100   if(this->cur >= this->block_items)
 101   {
 102     this->getSample(this->block + 1);
 103     return pair_type(this->val, this->sample.first);
 104   }
 105
 106   this->cur++;
 107   this->val += this->buffer->readDeltaCode();
 108   return pair_type(this->val, this->sample.first + this->cur);
 109 }
 110
 111 pair_type
 112 DeltaVector::selectRun(usint index, usint max_length)
 113 {
 114   return pair_type(this->select(index), 0);
 115 }
 116
 117 pair_type
 118 DeltaVector::selectNextRun(usint max_length)
 119 {
 120   return pair_type(this->selectNext(), 0);
 121 }
 122
 123 bool
 124 DeltaVector::isSet(usint value)
 125 {
 126   if(value >= this->size) { return false; }
 127   this->getSample(this->sampleForValue(value));
 128
 129   while(this->cur < this->block_items && this->val < value)
 130   {
 131     this->val += this->buffer->readDeltaCode();
 132     this->cur++;
 133   }
 134
 135   return (this->val == value);
 136 }
 137
 138 //--------------------------------------------------------------------------
 139
 140 usint
 141 DeltaVector::reportSize()
 142 {
 143   usint bytes = sizeof(*this);
 144   bytes += BitVector::reportSize();
 145   return bytes;
 146 }
 147
 148 //--------------------------------------------------------------------------
 149
 150 DeltaEncoder::DeltaEncoder(usint block_bytes, usint superblock_size) :
 151   VectorEncoder(block_bytes, superblock_size)
 152 {
 153 }
 154
 155 DeltaEncoder::~DeltaEncoder()
 156 {
 157 }
 158
 159 void
 160 DeltaEncoder::setBit(usint value)
 161 {
 162   if(this->items == 0)
 163   {
 164     this->setFirstBit(value);
 165     return;
 166   }
 167   if(value < this->size) { return; }
 168
 169   usint diff = value + 1 - this->size;
 170   this->size = value + 1;
 171   this->items++;
 172   if(this->buffer->writeDeltaCode(diff)) { return; }
 173
 174   // Didn't fit into the block. A new sample & block required.
 175   this->addNewBlock();
 176 }
 177
 178
 179 } // namespace CSA