incbwt/bits/array.h

   1 #ifndef ARRAY_H
   2 #define ARRAY_H
   3
   4 #include <fstream>
   5 #include <list>
   6
   7 #include "../misc/definitions.h"
   8 #include "bitbuffer.h"
   9
  10
  11 namespace CSA
  12 {
  13
  14 /*
  15   Delta-coded array for storing positive integers.
  16   Do not try to encode value 0!
  17 */
  18
  19
  20 class ArrayEncoder
  21 {
  22   public:
  23     const static usint SUPERBLOCK_SIZE = MEGABYTE;
  24
  25     // We assume superblock size is divisible by block and sample size.
  26     ArrayEncoder(usint block_bytes, usint superblock_size = SUPERBLOCK_SIZE);
  27     ~ArrayEncoder();
  28
  29     void addItem(usint value);
  30
  31     void addNewBlock();
  32
  33     usint items, blocks;
  34     usint block_size, superblock_bytes;
  35
  36     WriteBuffer*      buffer;
  37
  38     std::list<usint*> array_blocks;
  39     usint*            array;
  40     usint             blocks_in_superblock, current_blocks;
  41
  42     std::list<usint*> sample_blocks;
  43     usint*            samples;
  44     usint             samples_in_superblock, current_samples;
  45
  46   protected:
  47
  48     // These are not allowed.
  49     ArrayEncoder();
  50     ArrayEncoder(const ArrayEncoder&);
  51     ArrayEncoder& operator = (const ArrayEncoder&);
  52 };
  53
  54
  55 class Array
  56 {
  57   public:
  58     const static usint INDEX_RATE = 5;
  59
  60     Array(std::ifstream& file);
  61     Array(ArrayEncoder& encoder);
  62     ~Array();
  63
  64 //--------------------------------------------------------------------------
  65
  66     void writeTo(std::ofstream& file) const;
  67
  68     inline usint getSize() const { return this->items; }
  69     inline usint getBlockSize() const { return this->block_size; }
  70
  71     usint reportSize() const;
  72
  73 //--------------------------------------------------------------------------
  74
  75     class Iterator
  76     {
  77       public:
  78         Iterator(const Array& par);
  79         ~Iterator();
  80
  81         // Returns 0 if the index is invalid.
  82         usint getItem(usint index);
  83         usint nextItem();
  84
  85         inline bool hasNext() const
  86         {
  87           return (this->sample + this->cur < this->parent.getSize());
  88         }
  89
  90       private:
  91         const Array& parent;
  92
  93         usint block, sample, cur, block_items;
  94
  95         ReadBuffer buffer, samples;
  96
  97         /*
  98           This function returns the sample corresponding to the block the given
  99           index might be found in. Parameter is assumed to be valid.
 100         */
 101         usint sampleForIndex(usint index);
 102
 103         inline void getSample(usint sample_number)
 104         {
 105           this->block = sample_number;
 106           this->sample = this->samples.readItem(sample_number);
 107           this->cur = 0;
 108           this->block_items = this->samples.readItem() - this->sample;
 109           this->buffer.moveBuffer(this->parent.array + (this->block * this->parent.block_size));
 110         }
 111
 112         // These are not allowed.
 113         Iterator();
 114         Iterator(const Iterator&);
 115         Iterator& operator = (const Iterator&);
 116     };
 117
 118 //--------------------------------------------------------------------------
 119
 120   protected:
 121     usint          items;
 122
 123     ReadBuffer*    buffer;
 124     const usint*   array;
 125     bool           delete_array;  // Do we own the array?
 126     usint          block_size;
 127     usint          number_of_blocks;
 128
 129     /*
 130       Each sample tells how many items are contained in the previous blocks.
 131     */
 132     ReadBuffer*    samples;
 133     usint          integer_bits;
 134
 135     ReadBuffer*    item_index;
 136     usint          index_rate;
 137
 138     /*
 139       Build a higher level index for faster queries.
 140       The index consists of about (number of samples) / INDEX_RATE pointers.
 141       The array cannot be used without the index.
 142     */
 143     void buildIndex();
 144
 145     // These are not allowed.
 146     Array();
 147     Array(const Array&);
 148     Array& operator = (const Array&);
 149 };
 150
 151
 152 } // namespace CSA
 153
 154
 155 #endif // ARRAY_H