3 #include "nibblevector.h"
4 #include "../misc/utils.h"
11 NibbleVector::NibbleVector(std::ifstream& file) :
16 NibbleVector::NibbleVector(Encoder& encoder, usint universe_size) :
17 BitVector(encoder, universe_size)
21 NibbleVector::~NibbleVector()
25 //--------------------------------------------------------------------------
28 NibbleVector::reportSize() const
30 usint bytes = sizeof(*this);
31 bytes += BitVector::reportSize();
35 //--------------------------------------------------------------------------
37 NibbleVector::Iterator::Iterator(const NibbleVector& par) :
38 BitVector::Iterator(par),
43 NibbleVector::Iterator::~Iterator()
47 // FIXME gap encoding for all operations
50 NibbleVector::Iterator::rank(usint value, bool at_least)
52 const NibbleVector& par = (const NibbleVector&)(this->parent);
54 if(value >= par.size) { return par.items; }
56 this->valueLoop(value);
58 usint idx = this->sample.first + this->cur + 1;
59 if(!at_least && this->val > value)
63 if(at_least && this->val < value)
65 this->getSample(this->block + 1);
66 idx = this->sample.first + this->cur + 1;
72 NibbleVector::Iterator::select(usint index)
74 const NibbleVector& par = (const NibbleVector&)(this->parent);
76 if(index >= par.items) { return par.size; }
77 this->getSample(this->sampleForIndex(index));
79 usint lim = index - this->sample.first;
80 while(this->cur < lim)
82 this->val += this->buffer.readNibbleCode();
83 usint temp = this->buffer.readNibbleCode();
84 this->val += temp - 1;
89 this->run = this->cur - lim;
90 this->cur -= this->run;
91 this->val -= this->run;
98 NibbleVector::Iterator::selectNext()
100 if(this->cur >= this->block_items)
102 this->getSample(this->block + 1);
114 this->val += this->buffer.readNibbleCode();
115 this->run = this->buffer.readNibbleCode() - 1;
122 NibbleVector::Iterator::valueAfter(usint value)
124 const NibbleVector& par = (const NibbleVector&)(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);
135 return pair_type(this->val, this->sample.first + this->cur);
139 NibbleVector::Iterator::nextValue()
141 if(this->cur >= this->block_items)
143 this->getSample(this->block + 1);
144 return pair_type(this->val, this->sample.first);
155 this->val += this->buffer.readNibbleCode();
156 this->run = this->buffer.readNibbleCode() - 1;
159 return pair_type(this->val, this->sample.first + this->cur);
163 NibbleVector::Iterator::selectRun(usint index, usint max_length)
165 usint value = this->select(index);
167 usint len = std::min(max_length, this->run);
168 this->run -= len; this->cur += len; this->val += len;
170 return pair_type(value, len);
174 NibbleVector::Iterator::selectNextRun(usint max_length)
176 usint value = this->selectNext();
178 usint len = std::min(max_length, this->run);
179 this->run -= len; this->cur += len; this->val += len;
181 return pair_type(value, len);
185 NibbleVector::Iterator::isSet(usint value)
187 const NibbleVector& par = (const NibbleVector&)(this->parent);
189 if(value >= par.size) { return false; }
191 this->valueLoop(value);
193 return (this->val == value);
197 NibbleVector::Iterator::countRuns()
199 const NibbleVector& par = (const NibbleVector&)(this->parent);
201 if(par.items == 0) { return 0; }
204 pair_type res = this->selectRun(0, par.items);
205 usint last = res.first + res.second;
207 while(last < par.size)
209 res = this->selectNextRun(par.items);
210 if(res.first < par.size && res.first > last + 1) { runs++; }
211 last = res.first + res.second;
217 //--------------------------------------------------------------------------
219 NibbleEncoder::NibbleEncoder(usint block_bytes, usint superblock_size) :
220 VectorEncoder(block_bytes, superblock_size)
224 NibbleEncoder::~NibbleEncoder()
229 NibbleEncoder::setBit(usint value)
231 this->setRun(value, 1);
234 // FIXME for gap encoding
236 NibbleEncoder::setRun(usint start, usint len)
240 this->setFirstBit(start);
243 this->nibbleEncode(1, len - 1);
247 if(start < this->size || len == 0) { return; }
249 // Write as much into the buffer as possible.
250 usint diff = start + 1 - this->size;
251 usint free_bits = this->buffer->bitsLeft();
252 usint code_bits = this->buffer->nibbleCodeLength(diff);
253 if(free_bits >= code_bits + 4) // At least a part of the run fits into the block.
255 free_bits -= code_bits;
256 usint run_bits = this->buffer->nibbleCodeLength(len);
257 if(run_bits <= free_bits)
259 this->nibbleEncode(diff, len);
263 // Encode as much as possible and let the rest spill.
264 usint llen = (usint)1 << (3 * (free_bits / 4));
265 this->nibbleEncode(diff, llen);
268 // A new sample will be added.
274 this->size = start + 1;
278 // Didn't fit into the block. A new sample & block required.
282 this->nibbleEncode(1, len - 1);