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     // These versions try to combine the runs if possible.
  27     void addBit(usint value);
  28     void addRun(usint start, usint len);
  29     void flush(); // Call this when finished.
  30
  31     inline void RLEncode(usint diff, usint len)
  32     {
  33       this->size += diff + len - 1;
  34       this->items += len;
  35       this->buffer->writeDeltaCode(diff);
  36       this->buffer->writeDeltaCode(len);
  37     }
  38
  39   protected:
  40     pair_type run;
  41
  42     // These are not allowed.
  43     RLEEncoder();
  44     RLEEncoder(const RLEEncoder&);
  45     RLEEncoder& operator = (const RLEEncoder&);
  46 };
  47
  48
  49 /*
  50   This is a run-length encoded bit vector using delta coding.
  51 */
  52
  53 class RLEVector : public BitVector
  54 {
  55   public:
  56     typedef RLEEncoder Encoder;
  57
  58     RLEVector(std::ifstream& file);
  59     RLEVector(Encoder& encoder, usint universe_size);
  60     ~RLEVector();
  61
  62 //--------------------------------------------------------------------------
  63
  64     usint reportSize() const;
  65
  66 //--------------------------------------------------------------------------
  67
  68     class Iterator : public BitVector::Iterator
  69     {
  70       public:
  71         Iterator(const RLEVector& par);
  72         ~Iterator();
  73
  74         usint rank(usint value, bool at_least = false);
  75
  76         usint select(usint index);
  77         usint selectNext();
  78
  79         pair_type valueAfter(usint value);
  80         pair_type nextValue();
  81
  82         pair_type selectRun(usint index, usint max_length);
  83         pair_type selectNextRun(usint max_length);
  84
  85         bool isSet(usint value);
  86
  87         // Counts the number of 1-bit runs.
  88         usint countRuns();
  89
  90       protected:
  91
  92         inline void valueLoop(usint value)
  93         {
  94           this->getSample(this->sampleForValue(value));
  95           this->run = 0;
  96
  97           if(this->val >= value) { return; }
  98           while(this->cur < this->block_items)
  99           {
 100             this->val += this->buffer.readDeltaCode();
 101             this->cur++;
 102             this->run = this->buffer.readDeltaCode() - 1;
 103             if(this->val >= value) { break; }
 104
 105             this->cur += this->run;
 106             this->val += this->run;
 107             if(this->val >= value)
 108             {
 109               this->run = this->val - value;
 110               this->val = value;
 111               this->cur -= this->run;
 112               break;
 113             }
 114             this->run = 0;
 115           }
 116         }
 117
 118         // These are not allowed.
 119         Iterator();
 120         Iterator(const Iterator&);
 121         Iterator& operator = (const Iterator&);
 122     };
 123
 124 //--------------------------------------------------------------------------
 125
 126   protected:
 127
 128     // These are not allowed.
 129     RLEVector();
 130     RLEVector(const RLEVector&);
 131     RLEVector& operator = (const RLEVector&);
 132 };
 133
 134
 135 } // namespace CSA
 136
 137
 138 #endif // RLEVECTOR_H