4 #include "../misc/utils.h"
11 RLEVector::RLEVector(std::ifstream& file) :
16 RLEVector::RLEVector(RLEEncoder& encoder, usint universe_size) :
17 BitVector(encoder, universe_size)
21 RLEVector::~RLEVector()
25 //--------------------------------------------------------------------------
28 RLEVector::rank(usint value, bool at_least)
30 if(value >= this->size) { return this->items; }
32 this->valueLoop(value);
34 usint idx = this->sample.first + this->cur + 1;
35 if(!at_least && this->val > value)
39 if(at_least && this->val < value)
41 this->getSample(this->block + 1);
43 idx = this->sample.first + this->cur + 1;
49 RLEVector::select(usint index)
51 if(index >= this->items) { return this->size; }
52 this->getSample(this->sampleForIndex(index));
55 usint lim = index - this->sample.first;
56 while(this->cur < lim)
58 this->val += this->buffer->readDeltaCode();
59 usint temp = this->buffer->readDeltaCode();
60 this->val += temp - 1;
65 this->run = this->cur - lim;
66 this->cur -= this->run;
67 this->val -= this->run;
74 RLEVector::selectNext()
76 if(this->cur >= this->block_items)
78 this->getSample(this->block + 1);
91 this->val += this->buffer->readDeltaCode();
92 this->run = this->buffer->readDeltaCode() - 1;
99 RLEVector::valueAfter(usint value)
101 if(value >= this->size) { return pair_type(this->size, this->items); }
103 this->valueLoop(value);
105 if(this->val < value)
107 this->getSample(this->block + 1);
111 return pair_type(this->val, this->sample.first + this->cur);
115 RLEVector::nextValue()
117 if(this->cur >= this->block_items)
119 this->getSample(this->block + 1);
121 return pair_type(this->val, this->sample.first);
132 this->val += this->buffer->readDeltaCode();
133 this->run = this->buffer->readDeltaCode() - 1;
136 return pair_type(this->val, this->sample.first + this->cur);
140 RLEVector::selectRun(usint index, usint max_length)
142 usint value = this->select(index);
144 usint len = std::min(max_length, this->run);
145 this->run -= len; this->cur += len; this->val += len;
147 return pair_type(value, len);
151 RLEVector::selectNextRun(usint max_length)
153 usint value = this->selectNext();
155 usint len = std::min(max_length, this->run);
156 this->run -= len; this->cur += len; this->val += len;
158 return pair_type(value, len);
162 RLEVector::isSet(usint value)
164 if(value >= this->size) { return false; }
166 this->valueLoop(value);
168 return (this->val == value);
171 //--------------------------------------------------------------------------
174 RLEVector::reportSize()
176 usint bytes = sizeof(*this);
177 bytes += BitVector::reportSize();
181 //--------------------------------------------------------------------------
183 RLEEncoder::RLEEncoder(usint block_bytes, usint superblock_size) :
184 VectorEncoder(block_bytes, superblock_size)
188 RLEEncoder::~RLEEncoder()
193 RLEEncoder::setRun(usint start, usint len)
197 this->setFirstBit(start);
200 this->RLEncode(1, len - 1);
204 if(start < this->size || len == 0) { return; }
206 // Write as much into the buffer as possible.
207 usint diff = start + 1 - this->size;
208 usint free_bits = this->buffer->bitsLeft();
209 usint code_bits = this->buffer->deltaCodeLength(diff);
210 if(free_bits > code_bits) // At least a part of the run fits into the block.
212 free_bits -= code_bits;
213 usint run_bits = this->buffer->deltaCodeLength(len);
214 if(run_bits <= free_bits)
216 this->RLEncode(diff, len);
220 // Encode as much as possible and let the rest spill.
222 while(llen + 2 * length(llen + 1) - 1 <= free_bits) { llen++; }
223 llen = ((usint)1 << llen) - 1;
225 this->RLEncode(diff, llen);
228 // A new sample will be added.
234 this->size = start + 1;
238 // Didn't fit into the block. A new sample & block required.
242 this->RLEncode(1, len - 1);