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(RLEEncoder& encoder, usint universe_size) :
  17   BitVector(encoder, universe_size)
  18 {
  19 }
  20
  21 RLEVector::~RLEVector()
  22 {
  23 }
  24
  25 //--------------------------------------------------------------------------
  26
  27 usint
  28 RLEVector::rank(usint value, bool at_least)
  29 {
  30   if(value >= this->size) { return this->items; }
  31
  32   this->valueLoop(value);
  33
  34   usint idx = this->sample.first + this->cur + 1;
  35   if(!at_least && this->val > value)
  36   {
  37     idx--;
  38   }
  39   if(at_least && this->val < value)
  40   {
  41     this->getSample(this->block + 1);
  42     this->run = 0;
  43     idx = this->sample.first + this->cur + 1;
  44   }
  45   return idx;
  46 }
  47
  48 usint
  49 RLEVector::select(usint index)
  50 {
  51   if(index >= this->items) { return this->size; }
  52   this->getSample(this->sampleForIndex(index));
  53   this->run = 0;
  54
  55   usint lim = index - this->sample.first;
  56   while(this->cur < lim)
  57   {
  58     this->val += this->buffer->readDeltaCode();
  59     usint temp = this->buffer->readDeltaCode();
  60     this->val += temp - 1;
  61     this->cur += temp;
  62   }
  63   if(this->cur > lim)
  64   {
  65     this->run = this->cur - lim;
  66     this->cur -= this->run;
  67     this->val -= this->run;
  68   }
  69
  70   return this->val;
  71 }
  72
  73 usint
  74 RLEVector::selectNext()
  75 {
  76   if(this->cur >= this->block_items)
  77   {
  78     this->getSample(this->block + 1);
  79     this->run = 0;
  80     return this->val;
  81   }
  82
  83   this->cur++;
  84   if(this->run > 0)
  85   {
  86     this->val++;
  87     this->run--;
  88   }
  89   else
  90   {
  91     this->val += this->buffer->readDeltaCode();
  92     this->run = this->buffer->readDeltaCode() - 1;
  93   }
  94
  95   return this->val;
  96 }
  97
  98 pair_type
  99 RLEVector::valueAfter(usint value)
 100 {
 101   if(value >= this->size) { return pair_type(this->size, this->items); }
 102
 103   this->valueLoop(value);
 104
 105   if(this->val < value)
 106   {
 107     this->getSample(this->block + 1);
 108     this->run = 0;
 109   }
 110
 111   return pair_type(this->val, this->sample.first + this->cur);
 112 }
 113
 114 pair_type
 115 RLEVector::nextValue()
 116 {
 117   if(this->cur >= this->block_items)
 118   {
 119     this->getSample(this->block + 1);
 120     this->run = 0;
 121     return pair_type(this->val, this->sample.first);
 122   }
 123
 124   this->cur++;
 125   if(this->run > 0)
 126   {
 127     this->val++;
 128     this->run--;
 129   }
 130   else
 131   {
 132     this->val += this->buffer->readDeltaCode();
 133     this->run = this->buffer->readDeltaCode() - 1;
 134   }
 135
 136   return pair_type(this->val, this->sample.first + this->cur);
 137 }
 138
 139 pair_type
 140 RLEVector::selectRun(usint index, usint max_length)
 141 {
 142   usint value = this->select(index);
 143
 144   usint len = std::min(max_length, this->run);
 145   this->run -= len; this->cur += len; this->val += len;
 146
 147   return pair_type(value, len);
 148 }
 149
 150 pair_type
 151 RLEVector::selectNextRun(usint max_length)
 152 {
 153   usint value = this->selectNext();
 154
 155   usint len = std::min(max_length, this->run);
 156   this->run -= len; this->cur += len; this->val += len;
 157
 158   return pair_type(value, len);
 159 }
 160
 161 bool
 162 RLEVector::isSet(usint value)
 163 {
 164   if(value >= this->size) { return false; }
 165
 166   this->valueLoop(value);
 167
 168   return (this->val == value);
 169 }
 170
 171 //--------------------------------------------------------------------------
 172
 173 usint
 174 RLEVector::reportSize()
 175 {
 176   usint bytes = sizeof(*this);
 177   bytes += BitVector::reportSize();
 178   return bytes;
 179 }
 180
 181 //--------------------------------------------------------------------------
 182
 183 RLEEncoder::RLEEncoder(usint block_bytes, usint superblock_size) :
 184   VectorEncoder(block_bytes, superblock_size)
 185 {
 186 }
 187
 188 RLEEncoder::~RLEEncoder()
 189 {
 190 }
 191
 192 void
 193 RLEEncoder::setRun(usint start, usint len)
 194 {
 195   if(this->items == 0)
 196   {
 197     this->setFirstBit(start);
 198     if(len > 1)
 199     {
 200       this->RLEncode(1, len - 1);
 201     }
 202     return;
 203   }
 204   if(start < this->size || len == 0) { return; }
 205
 206   // Write as much into the buffer as possible.
 207   usint diff = start + 1 - this->size;
 208   usint free_bits = this->buffer->bitsLeft();
 209   usint code_bits = this->buffer->deltaCodeLength(diff);
 210   if(free_bits > code_bits) // At least a part of the run fits into the block.
 211   {
 212     free_bits -= code_bits;
 213     usint run_bits = this->buffer->deltaCodeLength(len);
 214     if(run_bits <= free_bits)
 215     {
 216       this->RLEncode(diff, len);
 217       return;
 218     }
 219
 220     // Encode as much as possible and let the rest spill.
 221     usint llen = 1;
 222     while(llen + 2 * length(llen + 1) - 1 <= free_bits) { llen++; }
 223     llen = ((usint)1 << llen) - 1;
 224
 225     this->RLEncode(diff, llen);
 226     len -= llen;
 227
 228     // A new sample will be added.
 229     this->size++;
 230     this->items++;
 231   }
 232   else
 233   {
 234     this->size = start + 1;
 235     this->items++;
 236   }
 237
 238   // Didn't fit into the block. A new sample & block required.
 239   this->addNewBlock();
 240   if(len > 1)
 241   {
 242     this->RLEncode(1, len - 1);
 243   }
 244 }
 245
 246
 247 } // namespace CSA