-
Notifications
You must be signed in to change notification settings - Fork 0
/
partitioned_sequence.hpp
349 lines (287 loc) · 13.2 KB
/
partitioned_sequence.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
#pragma once
#include <stdexcept>
#include "configuration.hpp"
#include "global_parameters.hpp"
#include "compact_elias_fano.hpp"
#include "indexed_sequence.hpp"
#include "integer_codes.hpp"
#include "util.hpp"
#include "optimal_partition.hpp"
namespace ds2i {
template <typename BaseSequence = indexed_sequence>
struct partitioned_sequence {
typedef BaseSequence base_sequence_type;
typedef typename base_sequence_type::enumerator base_sequence_enumerator;
template <typename Iterator>
static void write(succinct::bit_vector_builder& bvb,
Iterator begin,
uint64_t universe, uint64_t n,
global_parameters const& params)
{
assert(n > 0);
auto const& conf = configuration::get();
auto cost_fun = [&](uint64_t universe, uint64_t n) {
return base_sequence_type::bitsize(params, universe, n) + conf.fix_cost;
};
optimal_partition opt(begin, universe, n, cost_fun, conf.eps1, conf.eps2);
size_t partitions = opt.partition.size();
assert(partitions > 0);
assert(opt.partition.front() != 0);
assert(opt.partition.back() == n);
write_gamma_nonzero(bvb, partitions);
std::vector<uint64_t> cur_partition;
uint64_t cur_base = 0;
if (partitions == 1) {
cur_base = *begin;
Iterator it = begin;
for (size_t i = 0; i < n; ++i, ++it) {
cur_partition.push_back(*it - cur_base);
}
uint64_t universe_bits = ceil_log2(universe);
bvb.append_bits(cur_base, universe_bits);
// write universe only if non-singleton and not tight
if (n > 1) {
if (cur_base + cur_partition.back() + 1 == universe) {
// tight universe
write_delta(bvb, 0);
} else {
write_delta(bvb, cur_partition.back());
}
}
base_sequence_type::write(bvb, cur_partition.begin(),
cur_partition.back() + 1,
cur_partition.size(),
params);
} else {
succinct::bit_vector_builder bv_sequences;
std::vector<uint64_t> endpoints;
std::vector<uint64_t> upper_bounds;
uint64_t cur_i = 0;
Iterator it = begin;
cur_base = *begin;
upper_bounds.push_back(cur_base);
for (size_t p = 0; p < opt.partition.size(); ++p) {
cur_partition.clear();
uint64_t value = 0;
for (; cur_i < opt.partition[p]; ++cur_i, ++it) {
value = *it;
cur_partition.push_back(value - cur_base);
}
uint64_t upper_bound = value;
assert(cur_partition.size() > 0);
base_sequence_type::write(bv_sequences, cur_partition.begin(),
cur_partition.back() + 1,
cur_partition.size(), // XXX skip last one?
params);
endpoints.push_back(bv_sequences.size());
upper_bounds.push_back(upper_bound);
cur_base = upper_bound + 1;
}
succinct::bit_vector_builder bv_sizes;
compact_elias_fano::write(bv_sizes, opt.partition.begin(),
n, partitions - 1,
params);
succinct::bit_vector_builder bv_upper_bounds;
compact_elias_fano::write(bv_upper_bounds, upper_bounds.begin(),
universe, partitions + 1,
params);
uint64_t endpoint_bits = ceil_log2(bv_sequences.size() + 1);
write_gamma(bvb, endpoint_bits);
bvb.append(bv_sizes);
bvb.append(bv_upper_bounds);
for (uint64_t p = 0; p < endpoints.size() - 1; ++p) {
bvb.append_bits(endpoints[p], endpoint_bits);
}
bvb.append(bv_sequences);
}
}
class enumerator {
public:
typedef std::pair<uint64_t, uint64_t> value_type; // (position, value)
enumerator()
{}
enumerator(succinct::bit_vector const& bv, uint64_t offset,
uint64_t universe, uint64_t n,
global_parameters const& params)
: m_params(params)
, m_size(n)
, m_universe(universe)
, m_bv(&bv)
{
succinct::bit_vector::enumerator it(bv, offset);
m_partitions = read_gamma_nonzero(it);
if (m_partitions == 1) {
m_cur_partition = 0;
m_cur_begin = 0;
m_cur_end = n;
uint64_t universe_bits = ceil_log2(universe);
m_cur_base = it.take(universe_bits);
auto ub = 0;
if (n > 1) {
uint64_t universe_delta = read_delta(it);
ub = universe_delta ? universe_delta : (universe - m_cur_base - 1);
}
m_partition_enum = base_sequence_enumerator
(*m_bv, it.position(), ub + 1, n, m_params);
m_cur_upper_bound = m_cur_base + ub;
} else {
m_endpoint_bits = read_gamma(it);
uint64_t cur_offset = it.position();
m_sizes = compact_elias_fano::enumerator(bv, cur_offset,
n, m_partitions - 1,
params);
cur_offset += compact_elias_fano::bitsize(params, n,
m_partitions - 1);
m_upper_bounds = compact_elias_fano::enumerator(bv, cur_offset,
universe, m_partitions + 1,
params);
cur_offset += compact_elias_fano::bitsize(params, universe,
m_partitions + 1);
m_endpoints_offset = cur_offset;
uint64_t endpoints_size = m_endpoint_bits * (m_partitions - 1);
cur_offset += endpoints_size;
m_sequences_offset = cur_offset;
}
m_position = size();
slow_move();
}
value_type DS2I_ALWAYSINLINE move(uint64_t position)
{
assert(position <= size());
m_position = position;
if (m_position >= m_cur_begin && m_position < m_cur_end) {
uint64_t val = m_cur_base + m_partition_enum.move(m_position - m_cur_begin).second;
return value_type(m_position, val);
}
return slow_move();
}
// note: this is instantiated oly if BaseSequence has next_geq
value_type DS2I_ALWAYSINLINE next_geq(uint64_t lower_bound)
{
if (DS2I_LIKELY(lower_bound >= m_cur_base && lower_bound <= m_cur_upper_bound)) {
auto val = m_partition_enum.next_geq(lower_bound - m_cur_base);
m_position = m_cur_begin + val.first;
return value_type(m_position, m_cur_base + val.second);
}
return slow_next_geq(lower_bound);
}
value_type DS2I_ALWAYSINLINE next()
{
++m_position;
if (DS2I_LIKELY(m_position < m_cur_end)) {
uint64_t val = m_cur_base + m_partition_enum.next().second;
return value_type(m_position, val);
}
return slow_next();
}
uint64_t size() const
{
return m_size;
}
uint64_t prev_value() const
{
if (DS2I_UNLIKELY(m_position == m_cur_begin)) {
return m_cur_partition ? m_cur_base - 1 : 0;
} else {
return m_cur_base + m_partition_enum.prev_value();
}
}
uint64_t num_partitions() const
{
return m_partitions;
}
friend class partitioned_sequence_test;
private:
// the compiler does not seem smart enough to figure out that this
// is a very unlikely condition, and inlines the move(0) inside the
// next(), causing the code to grow. Since next is called in very
// tight loops, on microbenchmarks this causes an improvement of
// about 3ns on my i7 3Ghz
value_type DS2I_NOINLINE slow_next()
{
if (DS2I_UNLIKELY(m_position == m_size)) {
assert(m_cur_partition == m_partitions - 1);
auto val = m_partition_enum.next();
assert(val.first == m_partition_enum.size()); (void)val;
return value_type(m_position, m_universe);
}
switch_partition(m_cur_partition + 1);
uint64_t val = m_cur_base + m_partition_enum.move(0).second;
return value_type(m_position, val);
}
value_type DS2I_NOINLINE slow_move()
{
if (m_position == size()) {
if (m_partitions > 1) {
switch_partition(m_partitions - 1);
}
m_partition_enum.move(m_partition_enum.size());
return value_type(m_position, m_universe);
}
auto size_it = m_sizes.next_geq(m_position + 1); // need endpoint strictly > m_position
switch_partition(size_it.first);
uint64_t val = m_cur_base + m_partition_enum.move(m_position - m_cur_begin).second;
return value_type(m_position, val);
}
value_type DS2I_NOINLINE slow_next_geq(uint64_t lower_bound)
{
if (m_partitions == 1) {
if (lower_bound < m_cur_base) {
return move(0);
} else {
return move(size());
}
}
auto ub_it = m_upper_bounds.next_geq(lower_bound);
if (ub_it.first == 0) {
return move(0);
}
if (ub_it.first == m_upper_bounds.size()) {
return move(size());
}
switch_partition(ub_it.first - 1);
return next_geq(lower_bound);
}
void switch_partition(uint64_t partition)
{
assert(m_partitions > 1);
uint64_t endpoint = partition
? (m_bv->get_word56(m_endpoints_offset +
(partition - 1) * m_endpoint_bits)
& ((uint64_t(1) << m_endpoint_bits) - 1))
: 0;
uint64_t partition_begin = m_sequences_offset + endpoint;
m_bv->data().prefetch(partition_begin / 64);
m_cur_partition = partition;
auto size_it = m_sizes.move(partition);
m_cur_end = size_it.second;
m_cur_begin = m_sizes.prev_value();
auto ub_it = m_upper_bounds.move(partition + 1);
m_cur_upper_bound = ub_it.second;
m_cur_base = m_upper_bounds.prev_value() + (partition ? 1 : 0);
m_partition_enum = base_sequence_enumerator
(*m_bv, partition_begin,
m_cur_upper_bound - m_cur_base + 1,
m_cur_end - m_cur_begin,
m_params);
}
global_parameters m_params;
uint64_t m_partitions;
uint64_t m_endpoints_offset;
uint64_t m_endpoint_bits;
uint64_t m_sequences_offset;
uint64_t m_size;
uint64_t m_universe;
uint64_t m_position;
uint64_t m_cur_partition;
uint64_t m_cur_begin;
uint64_t m_cur_end;
uint64_t m_cur_base;
uint64_t m_cur_upper_bound;
succinct::bit_vector const* m_bv;
compact_elias_fano::enumerator m_sizes;
compact_elias_fano::enumerator m_upper_bounds;
base_sequence_enumerator m_partition_enum;
};
};
}