10 BitVector::BitVector(std::ifstream& file) :
11 rank_index(0), select_index(0)
13 file.read((char*)&(this->size), sizeof(this->size));
14 file.read((char*)&(this->items), sizeof(this->items));
15 file.read((char*)&(this->number_of_blocks), sizeof(this->number_of_blocks));
16 file.read((char*)&(this->block_size), sizeof(this->block_size));
18 usint* array_buffer = new usint[this->block_size * this->number_of_blocks];
19 file.read((char*)(array_buffer), this->block_size * this->number_of_blocks * sizeof(usint));
20 this->array = array_buffer;
22 this->integer_bits = length(this->size);
23 this->samples = new ReadBuffer(file, 2 * (this->number_of_blocks + 1), this->integer_bits);
26 this->indexForSelect();
29 BitVector::BitVector(std::FILE * file) :
30 rank_index(0), select_index(0)
32 std::fread(&(this->size), sizeof(this->size), 1, file);
33 std::fread(&(this->items), sizeof(this->items), 1, file);
34 std::fread(&(this->number_of_blocks), sizeof(this->number_of_blocks), 1, file);
35 std::fread(&(this->block_size), sizeof(this->block_size), 1, file);
37 usint* array_buffer = new usint[this->block_size * this->number_of_blocks];
38 std::fread(array_buffer, sizeof(usint), this->block_size * this->number_of_blocks, file);
39 this->array = array_buffer;
41 this->integer_bits = length(this->size);
42 this->samples = new ReadBuffer(file, 2 * (this->number_of_blocks + 1), this->integer_bits);
45 this->indexForSelect();
49 BitVector::BitVector(VectorEncoder& encoder, usint universe_size) :
50 size(universe_size), items(encoder.items),
51 block_size(encoder.block_size),
52 number_of_blocks(encoder.blocks),
53 rank_index(0), select_index(0)
55 usint* array_buffer = new usint[this->block_size * this->number_of_blocks];
57 this->integer_bits = length(this->size);
58 WriteBuffer sample_buffer(2 * (this->number_of_blocks + 1), this->integer_bits);
60 // Copy & linearize the array.
62 for(std::list<usint*>::iterator iter = encoder.array_blocks.begin(); iter != encoder.array_blocks.end(); iter++)
64 memcpy(array_buffer + pos, *iter, encoder.superblock_bytes);
65 pos += encoder.block_size * encoder.blocks_in_superblock;
67 memcpy(array_buffer + pos, encoder.array, encoder.current_blocks * encoder.block_size * sizeof(usint));
68 this->array = array_buffer;
70 // Compress the samples.
71 for(std::list<usint*>::iterator iter = encoder.sample_blocks.begin(); iter != encoder.sample_blocks.end(); iter++)
74 for(usint i = 0; i < 2 * encoder.samples_in_superblock; i++)
76 sample_buffer.writeItem(buf[i]);
79 for(usint i = 0; i < 2 * encoder.current_samples; i++)
81 sample_buffer.writeItem(encoder.samples[i]);
83 sample_buffer.writeItem(this->items);
84 sample_buffer.writeItem(this->size);
86 this->samples = sample_buffer.getReadBuffer();
89 this->indexForSelect();
92 BitVector::~BitVector()
96 delete this->rank_index;
97 delete this->select_index;
100 //--------------------------------------------------------------------------
103 BitVector::writeTo(std::ofstream& file) const
105 file.write((char*)&(this->size), sizeof(this->size));
106 file.write((char*)&(this->items), sizeof(this->items));
107 file.write((char*)&(this->number_of_blocks), sizeof(this->number_of_blocks));
108 file.write((char*)&(this->block_size), sizeof(this->block_size));
109 file.write((char*)(this->array), this->block_size * this->number_of_blocks * sizeof(usint));
110 this->samples->writeBuffer(file);
113 BitVector::writeTo(FILE* file) const
115 std::fwrite(&(this->size), sizeof(this->size), 1, file);
116 std::fwrite(&(this->items), sizeof(this->items), 1, file);
117 std::fwrite(&(this->number_of_blocks), sizeof(this->number_of_blocks), 1, file);
118 std::fwrite(&(this->block_size), sizeof(this->block_size), 1, file);
119 std::fwrite(this->array, sizeof(usint), this->block_size * this->number_of_blocks, file);
120 this->samples->writeBuffer(file);
124 BitVector::reportSize() const
126 // We assume the reportSize() of derived classes includes any class variables of BitVector.
127 usint bytes = this->block_size * this->number_of_blocks * sizeof(usint);
128 bytes += this->samples->reportSize();
129 bytes += this->rank_index->reportSize();
130 bytes += this->select_index->reportSize();
135 BitVector::getCompressedSize() const
137 return this->block_size * this->number_of_blocks * sizeof(usint);
140 //--------------------------------------------------------------------------
143 BitVector::indexForRank()
145 delete this->rank_index;
147 usint value_samples = (this->number_of_blocks + BitVector::INDEX_RATE - 1) / BitVector::INDEX_RATE;
148 this->rank_rate = (this->size + value_samples - 1) / value_samples;
149 value_samples = (this->size + this->rank_rate - 1) / this->rank_rate + 1;
150 WriteBuffer index_buffer(value_samples, length(this->number_of_blocks - 1));
152 usint current = 0, pointer = 0;
153 this->samples->goToItem(2);
154 while(this->samples->hasNextItem())
156 this->samples->skipItem();
157 usint limit = this->samples->readItem();
158 while(current < limit)
160 index_buffer.writeItem(pointer);
161 current += this->rank_rate;
165 index_buffer.writeItem(this->number_of_blocks - 1);
167 this->rank_index = index_buffer.getReadBuffer();
171 BitVector::indexForSelect()
173 delete this->select_index;
175 usint index_samples = (this->number_of_blocks + BitVector::INDEX_RATE - 1) / BitVector::INDEX_RATE;
176 this->select_rate = (this->items + index_samples - 1) / index_samples;
177 index_samples = (this->items + this->select_rate - 1) / this->select_rate + 1;
178 WriteBuffer index_buffer(index_samples, length(this->number_of_blocks - 1));
180 usint current = 0, pointer = 0;
181 this->samples->goToItem(2);
182 while(this->samples->hasNextItem())
184 usint limit = this->samples->readItem();
185 this->samples->skipItem();
186 while(current < limit)
188 index_buffer.writeItem(pointer);
189 current += this->select_rate;
193 index_buffer.writeItem(this->number_of_blocks - 1);
195 this->select_index = index_buffer.getReadBuffer();
198 //--------------------------------------------------------------------------
200 BitVector::Iterator::Iterator(const BitVector& par) :
202 buffer(par.array, par.block_size),
203 samples(*(par.samples))
207 BitVector::Iterator::~Iterator()
212 BitVector::Iterator::sampleForIndex(usint index)
214 usint low = this->parent.select_index->readItemConst(index / this->parent.select_rate);
215 usint high = this->parent.number_of_blocks - 1;
217 this->samples.goToItem(2 * low + 2);
218 for(; low < high; low++)
220 if(this->samples.readItem() > index) { return low; }
221 this->samples.skipItem();
228 BitVector::Iterator::sampleForValue(usint value)
230 usint low = this->parent.rank_index->readItemConst(value / this->parent.rank_rate);
231 usint high = this->parent.number_of_blocks - 1;
233 this->samples.goToItem(2 * low + 3);
234 for(; low < high; low++)
236 if(this->samples.readItem() > value) { return low; }
237 this->samples.skipItem();
243 //--------------------------------------------------------------------------
245 VectorEncoder::VectorEncoder(usint block_bytes, usint superblock_size) :
246 size(0), items(0), blocks(0),
247 block_size(BYTES_TO_WORDS(block_bytes)),
248 superblock_bytes(superblock_size)
250 this->array = new usint[this->superblock_bytes / sizeof(usint)];
251 memset(this->array, 0, this->superblock_bytes);
252 this->blocks_in_superblock = this->superblock_bytes / (sizeof(usint) * this->block_size);
253 this->current_blocks = 0;
255 this->samples = new usint[this->superblock_bytes / sizeof(usint)];
256 this->samples_in_superblock = this->superblock_bytes / (2 * sizeof(usint));
257 this->current_samples = 0;
259 this->buffer = new WriteBuffer(this->array, this->block_size);
262 VectorEncoder::~VectorEncoder()
264 delete[] this->array;
267 for(std::list<usint*>::iterator iter = this->array_blocks.begin(); iter != this->array_blocks.end(); iter++)
272 delete[] this->samples;
273 for(std::list<usint*>::iterator iter = this->sample_blocks.begin(); iter != this->sample_blocks.end(); iter++)
280 VectorEncoder::addNewBlock()
283 this->current_blocks++;
284 this->current_samples++;
286 // Do we need a new superblock for the block?
287 if(this->current_blocks > this->blocks_in_superblock)
289 this->array_blocks.push_back(this->array);
290 this->array = new usint[this->superblock_bytes / sizeof(usint)];
291 memset(this->array, 0, this->superblock_bytes);
292 this->current_blocks = 1;
294 this->buffer->moveBuffer(this->array + (this->block_size * (this->current_blocks - 1)));
296 // Do we need a new superblock for the sample?
297 if(this->current_samples > this->samples_in_superblock)
299 this->sample_blocks.push_back(this->samples);
300 this->samples = new usint[this->superblock_bytes / sizeof(usint)];
301 this->current_samples = 1;
303 this->samples[2 * this->current_samples - 2] = this->items - 1;
304 this->samples[2 * this->current_samples - 1] = this->size - 1;
308 VectorEncoder::setFirstBit(usint value)
310 this->samples[0] = 0;
311 this->samples[1] = value;
313 this->size = value + 1;
317 this->current_blocks = 1;
318 this->current_samples = 1;