incbwt/bits/rlevector.h

   1 #ifndef RLEVECTOR_H
   2 #define RLEVECTOR_H
   3
   4 #include <fstream>
   5
   6 #include "bitvector.h"
   7
   8
   9 namespace CSA
  10 {
  11
  12
  13 /*
  14   This class is used to construct a RLEVector.
  15 */
  16
  17 class RLEEncoder : public VectorEncoder
  18 {
  19   public:
  20     RLEEncoder(usint block_bytes, usint superblock_size = VectorEncoder::SUPERBLOCK_SIZE);
  21     ~RLEEncoder();
  22
  23 //    void setBit(usint value);
  24     void setRun(usint start, usint len);
  25
  26     inline void RLEncode(usint diff, usint len)
  27     {
  28       this->size += diff + len - 1;
  29       this->items += len;
  30       this->buffer->writeDeltaCode(diff);
  31       this->buffer->writeDeltaCode(len);
  32     }
  33 };
  34
  35
  36 /*
  37   This is a run-length encoded bit vector using delta coding.
  38 */
  39
  40 class RLEVector : public BitVector
  41 {
  42   public:
  43     RLEVector(std::ifstream& file);
  44     RLEVector(RLEEncoder& encoder, usint universe_size);
  45     ~RLEVector();
  46
  47 //--------------------------------------------------------------------------
  48
  49     usint rank(usint value, bool at_least = false);
  50
  51     usint select(usint index);
  52     usint selectNext();
  53
  54     pair_type valueAfter(usint value);
  55     pair_type nextValue();
  56
  57     pair_type selectRun(usint index, usint max_length);
  58     pair_type selectNextRun(usint max_length);
  59
  60     bool isSet(usint value);
  61
  62 //--------------------------------------------------------------------------
  63
  64     usint reportSize();
  65
  66   protected:
  67     usint run;
  68
  69     inline void valueLoop(usint value)
  70     {
  71       this->getSample(this->sampleForValue(value));
  72       this->run = 0;
  73
  74       if(this->val >= value) { return; }
  75       while(this->cur < this->block_items)
  76       {
  77         this->val += this->buffer->readDeltaCode();
  78         this->cur++;
  79         this->run = this->buffer->readDeltaCode() - 1;
  80         if(this->val >= value) { break; }
  81
  82         this->cur += this->run;
  83         this->val += this->run;
  84         if(this->val >= value)
  85         {
  86           this->run = this->val - value;
  87           this->val = value;
  88           this->cur -= this->run;
  89           break;
  90         }
  91         this->run = 0;
  92       }
  93     }
  94 };
  95
  96
  97 } // namespace CSA
  98
  99
 100 #endif // RLEVECTOR_H