incbwt/bits/nibblevector.cpp

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