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 this->array = new usint[this->block_size * this->number_of_blocks];
19 file.read((char*)(this->array), this->block_size * this->number_of_blocks * sizeof(usint));
20 this->buffer = new FastBitBuffer(this->array, this->block_size);
22 this->integer_bits = length(this->size);
23 this->samples = new FastBitBuffer(file, 2 * (this->number_of_blocks + 1), this->integer_bits);
26 this->indexForSelect();
29 BitVector::BitVector(VectorEncoder& encoder, usint universe_size) :
30 size(universe_size), items(encoder.items),
31 block_size(encoder.block_size),
32 number_of_blocks(encoder.blocks),
33 rank_index(0), select_index(0)
35 this->array = new usint[this->block_size * this->number_of_blocks];
36 this->buffer = new FastBitBuffer(this->array, this->block_size);
38 this->integer_bits = length(this->size);
39 this->samples = new FastBitBuffer(2 * (this->number_of_blocks + 1), this->integer_bits);
41 // Copy & linearize the array.
43 for(std::list<usint*>::iterator iter = encoder.array_blocks.begin(); iter != encoder.array_blocks.end(); iter++)
45 memcpy(this->array + pos, *iter, encoder.superblock_bytes);
46 pos += encoder.block_size * encoder.blocks_in_superblock;
48 memcpy(this->array + pos, encoder.array, encoder.current_blocks * encoder.block_size * sizeof(usint));
50 // Compress the samples.
51 for(std::list<usint*>::iterator iter = encoder.sample_blocks.begin(); iter != encoder.sample_blocks.end(); iter++)
54 for(usint i = 0; i < 2 * encoder.samples_in_superblock; i++)
56 this->samples->writeItem(buf[i]);
59 for(usint i = 0; i < 2 * encoder.current_samples; i++)
61 this->samples->writeItem(encoder.samples[i]);
63 this->samples->writeItem(this->items);
64 this->samples->writeItem(this->size);
67 this->indexForSelect();
70 BitVector::~BitVector()
75 delete this->rank_index;
76 delete this->select_index;
80 BitVector::writeTo(std::ofstream& file)
82 file.write((char*)&(this->size), sizeof(this->size));
83 file.write((char*)&(this->items), sizeof(this->items));
84 file.write((char*)&(this->number_of_blocks), sizeof(this->number_of_blocks));
85 file.write((char*)&(this->block_size), sizeof(this->block_size));
86 file.write((char*)(this->array), this->block_size * this->number_of_blocks * sizeof(usint));
87 this->samples->writeBuffer(file, false);
90 //--------------------------------------------------------------------------
93 BitVector::reportSize()
95 usint bytes = this->buffer->reportSize();
96 bytes += this->block_size * this->number_of_blocks * sizeof(usint);
97 bytes += this->samples->reportSize();
98 bytes += this->rank_index->reportSize();
99 bytes += this->select_index->reportSize();
103 //--------------------------------------------------------------------------
106 BitVector::sampleForIndex(usint index)
108 usint low = this->select_index->readItem(index / this->select_rate);
109 usint high = this->select_index->readItem(index / this->select_rate + 1);
111 this->samples->goToItem(2 * low + 2);
112 for(; low < high; low++)
114 if(this->samples->readItem() > index) { return low; }
115 this->samples->skipItem();
122 BitVector::sampleForValue(usint value)
124 usint low = this->rank_index->readItem(value / this->rank_rate);
125 usint high = this->rank_index->readItem(value / this->rank_rate + 1);
127 this->samples->goToItem(2 * low + 3);
128 for(; low < high; low++)
130 if(this->samples->readItem() > value) { return low; }
131 this->samples->skipItem();
137 //--------------------------------------------------------------------------
140 BitVector::indexForRank()
142 delete this->rank_index;
144 usint value_samples = (this->number_of_blocks + BitVector::INDEX_RATE - 1) / BitVector::INDEX_RATE;
145 this->rank_rate = (this->size + value_samples - 1) / value_samples;
146 value_samples = (this->size + this->rank_rate - 1) / this->rank_rate + 1;
147 this->rank_index = new FastBitBuffer(value_samples, length(this->number_of_blocks - 1));
149 usint current = 0, pointer = 0;
150 this->samples->goToItem(2);
151 while(this->samples->hasNextItem())
153 this->samples->skipItem();
154 usint limit = this->samples->readItem();
155 while(current < limit)
157 this->rank_index->writeItem(pointer);
158 current += this->rank_rate;
162 this->rank_index->writeItem(this->number_of_blocks - 1);
166 BitVector::indexForSelect()
168 delete this->select_index;
170 usint index_samples = (this->number_of_blocks + BitVector::INDEX_RATE - 1) / BitVector::INDEX_RATE;
171 this->select_rate = (this->items + index_samples - 1) / index_samples;
172 index_samples = (this->items + this->select_rate - 1) / this->select_rate + 1;
173 this->select_index = new FastBitBuffer(index_samples, length(this->number_of_blocks - 1));
175 usint current = 0, pointer = 0;
176 this->samples->goToItem(2);
177 while(this->samples->hasNextItem())
179 usint limit = this->samples->readItem();
180 this->samples->skipItem();
181 while(current < limit)
183 this->select_index->writeItem(pointer);
184 current += this->select_rate;
188 this->select_index->writeItem(this->number_of_blocks - 1);
191 //--------------------------------------------------------------------------
193 VectorEncoder::VectorEncoder(usint block_bytes, usint superblock_size) :
194 size(0), items(0), blocks(0),
195 block_size(BYTES_TO_WORDS(block_bytes)),
196 superblock_bytes(superblock_size)
198 this->array = new usint[this->superblock_bytes / sizeof(usint)];
199 memset(this->array, 0, this->superblock_bytes);
200 this->blocks_in_superblock = this->superblock_bytes / (sizeof(usint) * this->block_size);
201 this->current_blocks = 0;
203 this->samples = new usint[this->superblock_bytes / sizeof(usint)];
204 this->samples_in_superblock = this->superblock_bytes / (2 * sizeof(usint));
205 this->current_samples = 0;
207 this->buffer = new FastBitBuffer(this->array, this->block_size);
210 VectorEncoder::~VectorEncoder()
212 delete[] this->array;
215 for(std::list<usint*>::iterator iter = this->array_blocks.begin(); iter != this->array_blocks.end(); iter++)
220 delete[] this->samples;
221 for(std::list<usint*>::iterator iter = this->sample_blocks.begin(); iter != this->sample_blocks.end(); iter++)
228 VectorEncoder::addNewBlock()
231 this->current_blocks++;
232 this->current_samples++;
234 // Do we need a new superblock for the block?
235 if(this->current_blocks > this->blocks_in_superblock)
237 this->array_blocks.push_back(this->array);
238 this->array = new usint[this->superblock_bytes / sizeof(usint)];
239 memset(this->array, 0, this->superblock_bytes);
240 this->current_blocks = 1;
242 this->buffer->moveBuffer(this->array + (this->block_size * (this->current_blocks - 1)));
244 // Do we need a new superblock for the sample?
245 if(this->current_samples > this->samples_in_superblock)
247 this->sample_blocks.push_back(this->samples);
248 this->samples = new usint[this->superblock_bytes / sizeof(usint)];
249 this->current_samples = 1;
251 this->samples[2 * this->current_samples - 2] = this->items - 1;
252 this->samples[2 * this->current_samples - 1] = this->size - 1;
256 VectorEncoder::setFirstBit(usint value)
258 this->samples[0] = 0;
259 this->samples[1] = value;
261 this->size = value + 1;
265 this->current_blocks = 1;
266 this->current_samples = 1;