4 #include "../misc/utils.h"
11 RLEVector::RLEVector(std::ifstream& file) :
16 RLEVector::RLEVector(Encoder& encoder, usint universe_size) :
17 BitVector(encoder, universe_size)
21 RLEVector::~RLEVector()
25 //--------------------------------------------------------------------------
28 RLEVector::reportSize() const
30 usint bytes = sizeof(*this);
31 bytes += BitVector::reportSize();
35 //--------------------------------------------------------------------------
37 RLEVector::Iterator::Iterator(const RLEVector& par) :
38 BitVector::Iterator(par)
42 RLEVector::Iterator::~Iterator()
47 RLEVector::Iterator::rank(usint value, bool at_least)
49 const RLEVector& par = (const RLEVector&)(this->parent);
51 if(value >= par.size) { return par.items; }
53 this->valueLoop(value);
55 usint idx = this->sample.first + this->cur + 1;
56 if(!at_least && this->val > value)
60 if(at_least && this->val < value)
62 this->getSample(this->block + 1);
64 idx = this->sample.first + this->cur + 1;
70 RLEVector::Iterator::select(usint index)
72 const RLEVector& par = (const RLEVector&)(this->parent);
74 if(index >= par.items) { return par.size; }
75 this->getSample(this->sampleForIndex(index));
78 usint lim = index - this->sample.first;
79 while(this->cur < lim)
81 this->val += this->buffer.readDeltaCode();
82 usint temp = this->buffer.readDeltaCode();
83 this->val += temp - 1;
88 this->run = this->cur - lim;
89 this->cur -= this->run;
90 this->val -= this->run;
97 RLEVector::Iterator::selectNext()
99 if(this->cur >= this->block_items)
101 this->getSample(this->block + 1);
114 this->val += this->buffer.readDeltaCode();
115 this->run = this->buffer.readDeltaCode() - 1;
122 RLEVector::Iterator::valueAfter(usint value)
124 const RLEVector& par = (const RLEVector&)(this->parent);
126 if(value >= par.size) { return pair_type(par.size, par.items); }
128 this->valueLoop(value);
130 if(this->val < value)
132 this->getSample(this->block + 1);
136 return pair_type(this->val, this->sample.first + this->cur);
140 RLEVector::Iterator::nextValue()
142 if(this->cur >= this->block_items)
144 this->getSample(this->block + 1);
146 return pair_type(this->val, this->sample.first);
157 this->val += this->buffer.readDeltaCode();
158 this->run = this->buffer.readDeltaCode() - 1;
161 return pair_type(this->val, this->sample.first + this->cur);
165 RLEVector::Iterator::selectRun(usint index, usint max_length)
167 usint value = this->select(index);
169 usint len = std::min(max_length, this->run);
170 this->run -= len; this->cur += len; this->val += len;
172 return pair_type(value, len);
176 RLEVector::Iterator::selectNextRun(usint max_length)
178 usint value = this->selectNext();
180 usint len = std::min(max_length, this->run);
181 this->run -= len; this->cur += len; this->val += len;
183 return pair_type(value, len);
187 RLEVector::Iterator::isSet(usint value)
189 const RLEVector& par = (const RLEVector&)(this->parent);
191 if(value >= par.size) { return false; }
193 this->valueLoop(value);
195 return (this->val == value);
199 RLEVector::Iterator::countRuns()
201 const RLEVector& par = (const RLEVector&)(this->parent);
203 if(par.items == 0) { return 0; }
206 pair_type res = this->selectRun(0, par.items);
207 usint last = res.first + res.second;
209 while(last < par.size)
211 res = this->selectNextRun(par.items);
212 if(res.first < par.size && res.first > last + 1) { runs++; }
213 last = res.first + res.second;
219 //--------------------------------------------------------------------------
221 RLEEncoder::RLEEncoder(usint block_bytes, usint superblock_size) :
222 VectorEncoder(block_bytes, superblock_size),
227 RLEEncoder::~RLEEncoder()
232 RLEEncoder::setBit(usint value)
234 this->setRun(value, 1);
238 RLEEncoder::setRun(usint start, usint len)
242 this->setFirstBit(start);
245 this->RLEncode(1, len - 1);
249 if(start < this->size || len == 0) { return; }
251 // Write as much into the buffer as possible.
252 usint diff = start + 1 - this->size;
253 usint free_bits = this->buffer->bitsLeft();
254 usint code_bits = this->buffer->deltaCodeLength(diff);
255 if(free_bits > code_bits) // At least a part of the run fits into the block.
257 free_bits -= code_bits;
258 usint run_bits = this->buffer->deltaCodeLength(len);
259 if(run_bits <= free_bits)
261 this->RLEncode(diff, len);
265 // Encode as much as possible and let the rest spill.
267 while(llen + 2 * length(llen + 1) - 1 <= free_bits) { llen++; }
268 llen = ((usint)1 << llen) - 1;
270 this->RLEncode(diff, llen);
273 // A new sample will be added.
279 this->size = start + 1;
283 // Didn't fit into the block. A new sample & block required.
287 this->RLEncode(1, len - 1);
292 RLEEncoder::addBit(usint value)
294 this->addRun(value, 1);
298 RLEEncoder::addRun(usint start, usint len)
300 if(this->run.second == 0)
302 this->run = pair_type(start, len);
304 else if(start == this->run.first + this->run.second)
306 this->run.second += len;
310 this->setRun(this->run.first, this->run.second);
311 this->run = pair_type(start, len);
318 this->setRun(this->run.first, this->run.second);
319 this->run.second = 0;