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
|
#pragma once
#include "bit_vector.hpp"
namespace succinct {
namespace detail {
template <typename WordGetter>
class darray {
public:
darray()
: m_positions()
{}
darray(bit_vector const& bv)
: m_positions()
{
mapper::mappable_vector<uint64_t> const& data = bv.data();
std::vector<uint64_t> cur_block_positions;
std::vector<int64_t> block_inventory;
std::vector<uint16_t> subblock_inventory;
std::vector<uint64_t> overflow_positions;
for (uint64_t word_idx = 0; word_idx < data.size(); ++word_idx) {
uint64_t cur_pos = word_idx * 64;
uint64_t cur_word = WordGetter()(data, word_idx);
unsigned long l;
while (broadword::lsb(cur_word, l)) {
cur_pos += l;
cur_word >>= l;
if (cur_pos >= bv.size()) break;
cur_block_positions.push_back(cur_pos);
if (cur_block_positions.size() == block_size) {
flush_cur_block(cur_block_positions, block_inventory, subblock_inventory, overflow_positions);
}
// can't do >>= l + 1, can be 64
cur_word >>= 1;
cur_pos += 1;
m_positions += 1;
}
}
if (cur_block_positions.size()) {
flush_cur_block(cur_block_positions, block_inventory, subblock_inventory, overflow_positions);
}
m_block_inventory.steal(block_inventory);
m_subblock_inventory.steal(subblock_inventory);
m_overflow_positions.steal(overflow_positions);
}
template <typename Visitor>
void map(Visitor& visit) {
visit
(m_positions, "m_positions")
(m_block_inventory, "m_block_inventory")
(m_subblock_inventory, "m_subblock_inventory")
(m_overflow_positions, "m_overflow_positions")
;
}
void swap(darray& other) {
std::swap(other.m_positions, m_positions);
m_block_inventory.swap(other.m_block_inventory);
m_subblock_inventory.swap(other.m_subblock_inventory);
m_overflow_positions.swap(other.m_overflow_positions);
}
inline uint64_t select(bit_vector const& bv, uint64_t idx) const
{
assert(idx < num_positions());
uint64_t block = idx / block_size;
int64_t block_pos = m_block_inventory[block];
if (block_pos < 0) {
uint64_t overflow_pos = uint64_t(-block_pos - 1);
return m_overflow_positions[overflow_pos + (idx % block_size)];
}
uint64_t subblock = idx / subblock_size;
uint64_t start_pos = uint64_t(block_pos) + m_subblock_inventory[subblock];
uint64_t reminder = idx % subblock_size;
mapper::mappable_vector<uint64_t> const& data = bv.data();
if (!reminder) {
return start_pos;
} else {
uint64_t word_idx = start_pos / 64;
uint64_t word_shift = start_pos % 64;
uint64_t word = WordGetter()(data, word_idx) & (uint64_t(-1) << word_shift);
while (true) {
uint64_t popcnt = broadword::popcount(word);
if (reminder < popcnt) break;
reminder -= popcnt;
word = WordGetter()(data, ++word_idx);
}
return 64 * word_idx + broadword::select_in_word(word, reminder);
}
}
inline uint64_t num_positions() const {
return m_positions;
}
protected:
static void flush_cur_block(std::vector<uint64_t>& cur_block_positions, std::vector<int64_t>& block_inventory,
std::vector<uint16_t>& subblock_inventory, std::vector<uint64_t>& overflow_positions)
{
if (cur_block_positions.back() - cur_block_positions.front() < max_in_block_distance) {
block_inventory.push_back(int64_t(cur_block_positions.front()));
for (size_t i = 0; i < cur_block_positions.size(); i += subblock_size) {
subblock_inventory.push_back(uint16_t(cur_block_positions[i] - cur_block_positions.front()));
}
} else {
block_inventory.push_back(-int64_t(overflow_positions.size()) - 1);
for (size_t i = 0; i < cur_block_positions.size(); ++i) {
overflow_positions.push_back(cur_block_positions[i]);
}
for (size_t i = 0; i < cur_block_positions.size(); i += subblock_size) {
subblock_inventory.push_back(uint16_t(-1));
}
}
cur_block_positions.clear();
}
static const size_t block_size = 1024;
static const size_t subblock_size = 32;
static const size_t max_in_block_distance = 1 << 16;
uint64_t m_positions;
mapper::mappable_vector<int64_t> m_block_inventory;
mapper::mappable_vector<uint16_t> m_subblock_inventory;
mapper::mappable_vector<uint64_t> m_overflow_positions;
};
struct identity_getter
{
uint64_t operator()(mapper::mappable_vector<uint64_t> const& data, size_t idx) const {
return data[idx];
}
};
struct negating_getter
{
uint64_t operator()(mapper::mappable_vector<uint64_t> const& data, size_t idx) const {
return ~data[idx];
}
};
}
typedef detail::darray<detail::identity_getter> darray1;
typedef detail::darray<detail::negating_getter> darray0;
}
|
