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
  15 DeltaVector::DeltaVector(std::FILE * file) :
  16   BitVector(file)
  17 {
  18 }
  19
  20
  21 DeltaVector::DeltaVector(Encoder& encoder, usint universe_size) :
  22   BitVector(encoder, universe_size)
  23 {
  24 }
  25
  26 DeltaVector::~DeltaVector()
  27 {
  28 }
  29
  30 //--------------------------------------------------------------------------
  31
  32 usint
  33 DeltaVector::reportSize() const
  34 {
  35   usint bytes = sizeof(*this);
  36   bytes += BitVector::reportSize();
  37   return bytes;
  38 }
  39
  40 //--------------------------------------------------------------------------
  41
  42 DeltaVector::Iterator::Iterator(const DeltaVector& par) :
  43   BitVector::Iterator(par)
  44 {
  45 }
  46
  47 DeltaVector::Iterator::~Iterator()
  48 {
  49 }
  50
  51 usint
  52 DeltaVector::Iterator::rank(usint value, bool at_least)
  53 {
  54   const DeltaVector& par = (const DeltaVector&)(this->parent);
  55
  56   if(value >= par.size) { return par.items; }
  57   this->getSample(this->sampleForValue(value));
  58
  59   while(this->cur < this->block_items && this->val < value)
  60   {
  61     this->val += this->buffer.readDeltaCode();
  62     this->cur++;
  63   }
  64
  65   usint idx = this->sample.first + this->cur + 1;
  66   if(!at_least && this->val > value) { idx--; }
  67   if(at_least && this->val < value)  { this->getSample(this->block + 1); }
  68   return idx;
  69 }
  70
  71 usint
  72 DeltaVector::Iterator::select(usint index)
  73 {
  74   const DeltaVector& par = (const DeltaVector&)(this->parent);
  75
  76   if(index >= par.items) { return par.size; }
  77   this->getSample(this->sampleForIndex(index));
  78
  79   usint lim = index - this->sample.first;
  80   for(; this->cur < lim; this->cur++)
  81   {
  82     this->val += this->buffer.readDeltaCode();
  83   }
  84
  85   return this->val;
  86 }
  87
  88 usint
  89 DeltaVector::Iterator::selectNext()
  90 {
  91   if(this->cur >= this->block_items)
  92   {
  93     this->getSample(this->block + 1);
  94     return this->val;
  95   }
  96
  97   this->cur++;
  98   this->val += this->buffer.readDeltaCode();
  99   return this->val;
 100 }
 101
 102 pair_type
 103 DeltaVector::Iterator::valueAfter(usint value)
 104 {
 105   const DeltaVector& par = (const DeltaVector&)(this->parent);
 106
 107   if(value >= par.size) { return pair_type(par.size, par.items); }
 108   this->getSample(this->sampleForValue(value));
 109
 110   while(this->cur < this->block_items && this->val < value)
 111   {
 112     this->val += this->buffer.readDeltaCode();
 113     this->cur++;
 114   }
 115   if(this->val < value)
 116   {
 117     this->getSample(this->block + 1);
 118   }
 119
 120   return pair_type(this->val, this->sample.first + this->cur);
 121 }
 122
 123 pair_type
 124 DeltaVector::Iterator::nextValue()
 125 {
 126   if(this->cur >= this->block_items)
 127   {
 128     this->getSample(this->block + 1);
 129     return pair_type(this->val, this->sample.first);
 130   }
 131
 132   this->cur++;
 133   this->val += this->buffer.readDeltaCode();
 134   return pair_type(this->val, this->sample.first + this->cur);
 135 }
 136
 137 pair_type
 138 DeltaVector::Iterator::selectRun(usint index, usint max_length)
 139 {
 140   return pair_type(this->select(index), 0);
 141 }
 142
 143 pair_type
 144 DeltaVector::Iterator::selectNextRun(usint max_length)
 145 {
 146   return pair_type(this->selectNext(), 0);
 147 }
 148
 149 bool
 150 DeltaVector::Iterator::isSet(usint value)
 151 {
 152   const DeltaVector& par = (const DeltaVector&)(this->parent);
 153
 154   if(value >= par.size) { return false; }
 155   this->getSample(this->sampleForValue(value));
 156
 157   while(this->cur < this->block_items && this->val < value)
 158   {
 159     this->val += this->buffer.readDeltaCode();
 160     this->cur++;
 161   }
 162
 163   return (this->val == value);
 164 }
 165
 166 //--------------------------------------------------------------------------
 167
 168 DeltaEncoder::DeltaEncoder(usint block_bytes, usint superblock_size) :
 169   VectorEncoder(block_bytes, superblock_size)
 170 {
 171 }
 172
 173 DeltaEncoder::~DeltaEncoder()
 174 {
 175 }
 176
 177 void
 178 DeltaEncoder::setBit(usint value)
 179 {
 180   if(this->items == 0)
 181   {
 182     this->setFirstBit(value);
 183     return;
 184   }
 185   if(value < this->size) { return; }
 186
 187   usint diff = value + 1 - this->size;
 188   this->size = value + 1;
 189   this->items++;
 190   if(this->buffer->writeDeltaCode(diff)) { return; }
 191
 192   // Didn't fit into the block. A new sample & block required.
 193   this->addNewBlock();
 194 }
 195
 196 void
 197 DeltaEncoder::setRun(usint start, usint len)
 198 {
 199   for(usint i = start; i < start + len; i++)
 200   {
 201     this->setBit(i);
 202   }
 203 }
 204
 205 void
 206 DeltaEncoder::addBit(usint value)
 207 {
 208   this->setBit(value);
 209 }
 210
 211 void
 212 DeltaEncoder::addRun(usint start, usint len)
 213 {
 214   this->setRun(start, len);
 215 }
 216
 217 void
 218 DeltaEncoder::flush()
 219 {
 220 }
 221
 222 } // namespace CSA