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