d0e81388d57c3da952dea04305c81c3ad004190d
[SXSI/TextCollection.git] / incbwt / bits / nibblevector.cpp
1 #include <cstdlib>
2
3 #include "nibblevector.h"
4 #include "../misc/utils.h"
5
6
7 namespace CSA
8 {
9
10
11 NibbleVector::NibbleVector(std::ifstream& file) :
12   BitVector(file)
13 {
14 }
15
16 NibbleVector::NibbleVector(Encoder& encoder, usint universe_size) :
17   BitVector(encoder, universe_size)
18 {
19 }
20
21 NibbleVector::~NibbleVector()
22 {
23 }
24
25 //--------------------------------------------------------------------------
26
27 usint
28 NibbleVector::reportSize() const
29 {
30   usint bytes = sizeof(*this);
31   bytes += BitVector::reportSize();
32   return bytes;
33 }
34
35 //--------------------------------------------------------------------------
36
37 NibbleVector::Iterator::Iterator(const NibbleVector& par) :
38   BitVector::Iterator(par),
39   use_rle(false)
40 {
41 }
42
43 NibbleVector::Iterator::~Iterator()
44 {
45 }
46
47 // FIXME gap encoding for all operations
48
49 usint
50 NibbleVector::Iterator::rank(usint value, bool at_least)
51 {
52   const NibbleVector& par = (const NibbleVector&)(this->parent);
53
54   if(value >= par.size) { return par.items; }
55
56   this->valueLoop(value);
57
58   usint idx = this->sample.first + this->cur + 1;
59   if(!at_least && this->val > value)
60   {
61     idx--;
62   }
63   if(at_least && this->val < value)
64   {
65     this->getSample(this->block + 1);
66     idx = this->sample.first + this->cur + 1;
67   }
68   return idx;
69 }
70
71 usint
72 NibbleVector::Iterator::select(usint index)
73 {
74   const NibbleVector& par = (const NibbleVector&)(this->parent);
75
76   if(index >= par.items) { return par.size; }
77   this->getSample(this->sampleForIndex(index));
78
79   usint lim = index - this->sample.first;
80   while(this->cur < lim)
81   {
82     this->val += this->buffer.readNibbleCode();
83     usint temp = this->buffer.readNibbleCode();
84     this->val += temp - 1;
85     this->cur += temp;
86   }
87   if(this->cur > lim)
88   {
89     this->run = this->cur - lim;
90     this->cur -= this->run;
91     this->val -= this->run;
92   }
93
94   return this->val;
95 }
96
97 usint
98 NibbleVector::Iterator::selectNext()
99 {
100   if(this->cur >= this->block_items)
101   {
102     this->getSample(this->block + 1);
103     return this->val;
104   }
105
106   this->cur++;
107   if(this->run > 0)
108   {
109     this->val++;
110     this->run--;
111   }
112   else
113   {
114     this->val += this->buffer.readNibbleCode();
115     this->run = this->buffer.readNibbleCode() - 1;
116   }
117
118   return this->val;
119 }
120
121 pair_type
122 NibbleVector::Iterator::valueAfter(usint value)
123 {
124   const NibbleVector& par = (const NibbleVector&)(this->parent);
125
126   if(value >= par.size) { return pair_type(par.size, par.items); }
127
128   this->valueLoop(value);
129
130   if(this->val < value)
131   {
132     this->getSample(this->block + 1);
133   }
134
135   return pair_type(this->val, this->sample.first + this->cur);
136 }
137
138 pair_type
139 NibbleVector::Iterator::nextValue()
140 {
141   if(this->cur >= this->block_items)
142   {
143     this->getSample(this->block + 1);
144     return pair_type(this->val, this->sample.first);
145   }
146
147   this->cur++;
148   if(this->run > 0)
149   {
150     this->val++;
151     this->run--;
152   }
153   else
154   {
155     this->val += this->buffer.readNibbleCode();
156     this->run = this->buffer.readNibbleCode() - 1;
157   }
158
159   return pair_type(this->val, this->sample.first + this->cur);
160 }
161
162 pair_type
163 NibbleVector::Iterator::selectRun(usint index, usint max_length)
164 {
165   usint value = this->select(index);
166
167   usint len = std::min(max_length, this->run);
168   this->run -= len; this->cur += len; this->val += len;
169
170   return pair_type(value, len);
171 }
172
173 pair_type
174 NibbleVector::Iterator::selectNextRun(usint max_length)
175 {
176   usint value = this->selectNext();
177
178   usint len = std::min(max_length, this->run);
179   this->run -= len; this->cur += len; this->val += len;
180
181   return pair_type(value, len);
182 }
183
184 bool
185 NibbleVector::Iterator::isSet(usint value)
186 {
187   const NibbleVector& par = (const NibbleVector&)(this->parent);
188
189   if(value >= par.size) { return false; }
190
191   this->valueLoop(value);
192
193   return (this->val == value);
194 }
195
196 usint
197 NibbleVector::Iterator::countRuns()
198 {
199   const NibbleVector& par = (const NibbleVector&)(this->parent);
200
201   if(par.items == 0) { return 0; }
202
203   usint runs = 1;
204   pair_type res = this->selectRun(0, par.items);
205   usint last = res.first + res.second;
206
207   while(last < par.size)
208   {
209     res = this->selectNextRun(par.items);
210     if(res.first < par.size && res.first > last + 1) { runs++; }
211     last = res.first + res.second;
212   }
213
214   return runs;
215 }
216
217 //--------------------------------------------------------------------------
218
219 NibbleEncoder::NibbleEncoder(usint block_bytes, usint superblock_size) :
220   VectorEncoder(block_bytes, superblock_size)
221 {
222 }
223
224 NibbleEncoder::~NibbleEncoder()
225 {
226 }
227
228 void
229 NibbleEncoder::setBit(usint value)
230 {
231   this->setRun(value, 1);
232 }
233
234 // FIXME for gap encoding
235 void
236 NibbleEncoder::setRun(usint start, usint len)
237 {
238   if(this->items == 0)
239   {
240     this->setFirstBit(start);
241     if(len > 1)
242     {
243       this->nibbleEncode(1, len - 1);
244     }
245     return;
246   }
247   if(start < this->size || len == 0) { return; }
248
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.
254   {
255     free_bits -= code_bits;
256     usint run_bits = this->buffer->nibbleCodeLength(len);
257     if(run_bits <= free_bits)
258     {
259       this->nibbleEncode(diff, len);
260       return;
261     }
262
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);
266     len -= llen;
267
268     // A new sample will be added.
269     this->size++;
270     this->items++;
271   }
272   else
273   {
274     this->size = start + 1;
275     this->items++;
276   }
277
278   // Didn't fit into the block. A new sample & block required.
279   this->addNewBlock();
280   if(len > 1)
281   {
282     this->nibbleEncode(1, len - 1);
283   }
284 }
285
286
287 } // namespace CSA