incbwt/bits/rlevector.cpp

   1 #include <cstdlib>
   2
   3 #include "rlevector.h"
   4 #include "../misc/utils.h"
   5
   6
   7 namespace CSA
   8 {
   9
  10
  11 RLEVector::RLEVector(std::ifstream& file) :
  12   BitVector(file)
  13 {
  14 }
  15
  16 RLEVector::RLEVector(Encoder& encoder, usint universe_size) :
  17   BitVector(encoder, universe_size)
  18 {
  19 }
  20
  21 RLEVector::~RLEVector()
  22 {
  23 }
  24
  25 //--------------------------------------------------------------------------
  26
  27 usint
  28 RLEVector::reportSize() const
  29 {
  30   usint bytes = sizeof(*this);
  31   bytes += BitVector::reportSize();
  32   return bytes;
  33 }
  34
  35 //--------------------------------------------------------------------------
  36
  37 RLEVector::Iterator::Iterator(const RLEVector& par) :
  38   BitVector::Iterator(par)
  39 {
  40 }
  41
  42 RLEVector::Iterator::~Iterator()
  43 {
  44 }
  45
  46 usint
  47 RLEVector::Iterator::rank(usint value, bool at_least)
  48 {
  49   const RLEVector& par = (const RLEVector&)(this->parent);
  50
  51   if(value >= par.size) { return par.items; }
  52
  53   this->valueLoop(value);
  54
  55   usint idx = this->sample.first + this->cur + 1;
  56   if(!at_least && this->val > value)
  57   {
  58     idx--;
  59   }
  60   if(at_least && this->val < value)
  61   {
  62     this->getSample(this->block + 1);
  63     this->run = 0;
  64     idx = this->sample.first + this->cur + 1;
  65   }
  66   return idx;
  67 }
  68
  69 usint
  70 RLEVector::Iterator::select(usint index)
  71 {
  72   const RLEVector& par = (const RLEVector&)(this->parent);
  73
  74   if(index >= par.items) { return par.size; }
  75   this->getSample(this->sampleForIndex(index));
  76   this->run = 0;
  77
  78   usint lim = index - this->sample.first;
  79   while(this->cur < lim)
  80   {
  81     this->val += this->buffer.readDeltaCode();
  82     usint temp = this->buffer.readDeltaCode();
  83     this->val += temp - 1;
  84     this->cur += temp;
  85   }
  86   if(this->cur > lim)
  87   {
  88     this->run = this->cur - lim;
  89     this->cur -= this->run;
  90     this->val -= this->run;
  91   }
  92
  93   return this->val;
  94 }
  95
  96 usint
  97 RLEVector::Iterator::selectNext()
  98 {
  99   if(this->cur >= this->block_items)
 100   {
 101     this->getSample(this->block + 1);
 102     this->run = 0;
 103     return this->val;
 104   }
 105
 106   this->cur++;
 107   if(this->run > 0)
 108   {
 109     this->val++;
 110     this->run--;
 111   }
 112   else
 113   {
 114     this->val += this->buffer.readDeltaCode();
 115     this->run = this->buffer.readDeltaCode() - 1;
 116   }
 117
 118   return this->val;
 119 }
 120
 121 pair_type
 122 RLEVector::Iterator::valueAfter(usint value)
 123 {
 124   const RLEVector& par = (const RLEVector&)(this->parent);
 125
 126   if(value >= par.size) { return pair_type(par.size, par.items); }
 127
 128   this->valueLoop(value);
 129
 130   if(this->val < value)
 131   {
 132     this->getSample(this->block + 1);
 133     this->run = 0;
 134   }
 135
 136   return pair_type(this->val, this->sample.first + this->cur);
 137 }
 138
 139 pair_type
 140 RLEVector::Iterator::nextValue()
 141 {
 142   if(this->cur >= this->block_items)
 143   {
 144     this->getSample(this->block + 1);
 145     this->run = 0;
 146     return pair_type(this->val, this->sample.first);
 147   }
 148
 149   this->cur++;
 150   if(this->run > 0)
 151   {
 152     this->val++;
 153     this->run--;
 154   }
 155   else
 156   {
 157     this->val += this->buffer.readDeltaCode();
 158     this->run = this->buffer.readDeltaCode() - 1;
 159   }
 160
 161   return pair_type(this->val, this->sample.first + this->cur);
 162 }
 163
 164 pair_type
 165 RLEVector::Iterator::selectRun(usint index, usint max_length)
 166 {
 167   usint value = this->select(index);
 168
 169   usint len = std::min(max_length, this->run);
 170   this->run -= len; this->cur += len; this->val += len;
 171
 172   return pair_type(value, len);
 173 }
 174
 175 pair_type
 176 RLEVector::Iterator::selectNextRun(usint max_length)
 177 {
 178   usint value = this->selectNext();
 179
 180   usint len = std::min(max_length, this->run);
 181   this->run -= len; this->cur += len; this->val += len;
 182
 183   return pair_type(value, len);
 184 }
 185
 186 bool
 187 RLEVector::Iterator::isSet(usint value)
 188 {
 189   const RLEVector& par = (const RLEVector&)(this->parent);
 190
 191   if(value >= par.size) { return false; }
 192
 193   this->valueLoop(value);
 194
 195   return (this->val == value);
 196 }
 197
 198 usint
 199 RLEVector::Iterator::countRuns()
 200 {
 201   const RLEVector& par = (const RLEVector&)(this->parent);
 202
 203   if(par.items == 0) { return 0; }
 204
 205   usint runs = 1;
 206   pair_type res = this->selectRun(0, par.items);
 207   usint last = res.first + res.second;
 208
 209   while(last < par.size)
 210   {
 211     res = this->selectNextRun(par.items);
 212     if(res.first < par.size && res.first > last + 1) { runs++; }
 213     last = res.first + res.second;
 214   }
 215
 216   return runs;
 217 }
 218
 219 //--------------------------------------------------------------------------
 220
 221 RLEEncoder::RLEEncoder(usint block_bytes, usint superblock_size) :
 222   VectorEncoder(block_bytes, superblock_size),
 223   run(EMPTY_PAIR)
 224 {
 225 }
 226
 227 RLEEncoder::~RLEEncoder()
 228 {
 229 }
 230
 231 void
 232 RLEEncoder::setBit(usint value)
 233 {
 234   this->setRun(value, 1);
 235 }
 236
 237 void
 238 RLEEncoder::setRun(usint start, usint len)
 239 {
 240   if(this->items == 0)
 241   {
 242     this->setFirstBit(start);
 243     if(len > 1)
 244     {
 245       this->RLEncode(1, len - 1);
 246     }
 247     return;
 248   }
 249   if(start < this->size || len == 0) { return; }
 250
 251   // Write as much into the buffer as possible.
 252   usint diff = start + 1 - this->size;
 253   usint free_bits = this->buffer->bitsLeft();
 254   usint code_bits = this->buffer->deltaCodeLength(diff);
 255   if(free_bits > code_bits) // At least a part of the run fits into the block.
 256   {
 257     free_bits -= code_bits;
 258     usint run_bits = this->buffer->deltaCodeLength(len);
 259     if(run_bits <= free_bits)
 260     {
 261       this->RLEncode(diff, len);
 262       return;
 263     }
 264
 265     // Encode as much as possible and let the rest spill.
 266     usint llen = 1;
 267     while(llen + 2 * length(llen + 1) - 1 <= free_bits) { llen++; }
 268     llen = ((usint)1 << llen) - 1;
 269
 270     this->RLEncode(diff, llen);
 271     len -= llen;
 272
 273     // A new sample will be added.
 274     this->size++;
 275     this->items++;
 276   }
 277   else
 278   {
 279     this->size = start + 1;
 280     this->items++;
 281   }
 282
 283   // Didn't fit into the block. A new sample & block required.
 284   this->addNewBlock();
 285   if(len > 1)
 286   {
 287     this->RLEncode(1, len - 1);
 288   }
 289 }
 290
 291 void
 292 RLEEncoder::addBit(usint value)
 293 {
 294   this->addRun(value, 1);
 295 }
 296
 297 void
 298 RLEEncoder::addRun(usint start, usint len)
 299 {
 300   if(this->run.second == 0)
 301   {
 302     this->run = pair_type(start, len);
 303   }
 304   else if(start == this->run.first + this->run.second)
 305   {
 306     this->run.second += len;
 307   }
 308   else
 309   {
 310     this->setRun(this->run.first, this->run.second);
 311     this->run = pair_type(start, len);
 312   }
 313 }
 314
 315 void
 316 RLEEncoder::flush()
 317 {
 318   this->setRun(this->run.first, this->run.second);
 319   this->run.second = 0;
 320 }
 321
 322
 323 } // namespace CSA