incbwt/bits/nibblevector.h

   1 #ifndef NIBBLEVECTOR_H
   2 #define NIBBLEVECTOR_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 NibbleVector.
  15 */
  16
  17 class NibbleEncoder : public VectorEncoder
  18 {
  19   public:
  20     NibbleEncoder(usint block_bytes, usint superblock_size = VectorEncoder::SUPERBLOCK_SIZE);
  21     ~NibbleEncoder();
  22
  23     void setBit(usint value);
  24     void setRun(usint start, usint len);
  25
  26     // FIXME for gap encoding
  27     inline void nibbleEncode(usint diff, usint len)
  28     {
  29       this->size += diff + len - 1;
  30       this->items += len;
  31       this->buffer->writeNibbleCode(diff);
  32       this->buffer->writeNibbleCode(len);
  33     }
  34
  35   protected:
  36
  37     // These are not allowed.
  38     NibbleEncoder();
  39     NibbleEncoder(const NibbleEncoder&);
  40     NibbleEncoder& operator = (const NibbleEncoder&);
  41 };
  42
  43
  44 /*
  45   This bit vector uses nibble coding. Each block is either run-length encoded or
  46   gap encoded, depending on the first nibble.
  47
  48   // FIXME reverting to gap encoding not implemented yet
  49 */
  50
  51 class NibbleVector : public BitVector
  52 {
  53   public:
  54     typedef NibbleEncoder Encoder;
  55
  56     NibbleVector(std::ifstream& file);
  57     NibbleVector(Encoder& encoder, usint universe_size);
  58     ~NibbleVector();
  59
  60 //--------------------------------------------------------------------------
  61
  62     usint reportSize() const;
  63
  64 //--------------------------------------------------------------------------
  65
  66     class Iterator : public BitVector::Iterator
  67     {
  68       public:
  69         Iterator(const NibbleVector& par);
  70         ~Iterator();
  71
  72         usint rank(usint value, bool at_least = false);
  73
  74         usint select(usint index);
  75         usint selectNext();
  76
  77         pair_type valueAfter(usint value);
  78         pair_type nextValue();
  79
  80         pair_type selectRun(usint index, usint max_length);
  81         pair_type selectNextRun(usint max_length);
  82
  83         bool isSet(usint value);
  84
  85         // Counts the number of 1-bit runs.
  86         usint countRuns();
  87
  88         static const usint GAP_ENCODING = 0;
  89         static const usint RUN_LENGTH_ENCODING = 1;
  90
  91       protected:
  92
  93         // FIXME for gap encoding
  94         inline void valueLoop(usint value)
  95         {
  96           this->getSample(this->sampleForValue(value));
  97
  98           if(this->val >= value) { return; }
  99           while(this->cur < this->block_items)
 100           {
 101             this->val += this->buffer.readNibbleCode();
 102             this->cur++;
 103             this->run = this->buffer.readNibbleCode() - 1;
 104             if(this->val >= value) { break; }
 105
 106             this->cur += this->run;
 107             this->val += this->run;
 108             if(this->val >= value)
 109             {
 110               this->run = this->val - value;
 111               this->val = value;
 112               this->cur -= this->run;
 113               break;
 114             }
 115             this->run = 0;
 116           }
 117         }
 118
 119         inline void getSample(usint sample_number)
 120         {
 121           BitVector::Iterator::getSample(sample_number);
 122           this->run = 0;
 123 //           this->use_rle = this->buffer.readNibble();
 124         }
 125
 126         bool use_rle;
 127
 128         // These are not allowed.
 129         Iterator();
 130         Iterator(const Iterator&);
 131         Iterator& operator = (const Iterator&);
 132     };
 133
 134 //--------------------------------------------------------------------------
 135
 136   protected:
 137
 138     // These are not allowed.
 139     NibbleVector();
 140     NibbleVector(const NibbleVector&);
 141     NibbleVector& operator = (const NibbleVector&);
 142 };
 143
 144
 145 } // namespace CSA
 146
 147
 148 #endif // NIBBLEVECTOR_H