-
Notifications
You must be signed in to change notification settings - Fork 17
/
elias_fano_list.hpp
68 lines (54 loc) · 1.49 KB
/
elias_fano_list.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
#pragma once
#include "elias_fano.hpp"
namespace succinct {
struct elias_fano_list
{
typedef uint64_t value_type;
elias_fano_list() {}
template <typename Range>
elias_fano_list(Range const& ints)
{
typedef typename boost::range_const_iterator<Range>::type iterator_t;
size_t s = 0;
size_t n = 0;
for (iterator_t iter = boost::begin(ints);
iter != boost::end(ints);
++iter) {
s += *iter;
n += 1;
}
elias_fano::elias_fano_builder ef_builder(s + 1, n);
size_t cur_base = 0;
for (iterator_t iter = boost::begin(ints);
iter != boost::end(ints);
++iter) {
cur_base += *iter;
ef_builder.push_back(cur_base);
}
elias_fano(&ef_builder, false).swap(m_ef);
}
value_type operator[](size_t idx) const
{
return m_ef.delta(idx);
}
size_t size() const
{
return m_ef.num_ones();
}
size_t sum() const {
return m_ef.size() - 1;
}
void swap(elias_fano_list& other)
{
m_ef.swap(other.m_ef);
}
template <typename Visitor>
void map(Visitor& visit) {
visit
(m_ef, "m_ef")
;
}
private:
elias_fano m_ef;
};
}