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
|
#pragma once
#ifndef MARISA_GRIMOIRE_VECTOR_BIT_VECTOR_H_
#define MARISA_GRIMOIRE_VECTOR_BIT_VECTOR_H_
#include "rank-index.h"
#include "vector.h"
namespace marisa {
namespace grimoire {
namespace vector {
class BitVector {
public:
#if MARISA_WORD_SIZE == 64
typedef UInt64 Unit;
#else // MARISA_WORD_SIZE == 64
typedef UInt32 Unit;
#endif // MARISA_WORD_SIZE == 64
BitVector()
: units_(), size_(0), num_1s_(0), ranks_(), select0s_(), select1s_() {}
void build(bool enables_select0, bool enables_select1) {
BitVector temp;
temp.build_index(*this, enables_select0, enables_select1);
units_.shrink();
temp.units_.swap(units_);
swap(temp);
}
void map(Mapper &mapper) {
BitVector temp;
temp.map_(mapper);
swap(temp);
}
void read(Reader &reader) {
BitVector temp;
temp.read_(reader);
swap(temp);
}
void write(Writer &writer) const {
write_(writer);
}
void disable_select0() {
select0s_.clear();
}
void disable_select1() {
select1s_.clear();
}
void push_back(bool bit) {
MARISA_THROW_IF(size_ == MARISA_UINT32_MAX, MARISA_SIZE_ERROR);
if (size_ == (MARISA_WORD_SIZE * units_.size())) {
units_.resize(units_.size() + (64 / MARISA_WORD_SIZE), 0);
}
if (bit) {
units_[size_ / MARISA_WORD_SIZE] |=
(Unit)1 << (size_ % MARISA_WORD_SIZE);
++num_1s_;
}
++size_;
}
bool operator[](std::size_t i) const {
MARISA_DEBUG_IF(i >= size_, MARISA_BOUND_ERROR);
return (units_[i / MARISA_WORD_SIZE]
& ((Unit)1 << (i % MARISA_WORD_SIZE))) != 0;
}
std::size_t rank0(std::size_t i) const {
MARISA_DEBUG_IF(ranks_.empty(), MARISA_STATE_ERROR);
MARISA_DEBUG_IF(i > size_, MARISA_BOUND_ERROR);
return i - rank1(i);
}
std::size_t rank1(std::size_t i) const;
std::size_t select0(std::size_t i) const;
std::size_t select1(std::size_t i) const;
std::size_t num_0s() const {
return size_ - num_1s_;
}
std::size_t num_1s() const {
return num_1s_;
}
bool empty() const {
return size_ == 0;
}
std::size_t size() const {
return size_;
}
std::size_t total_size() const {
return units_.total_size() + ranks_.total_size()
+ select0s_.total_size() + select1s_.total_size();
}
std::size_t io_size() const {
return units_.io_size() + (sizeof(UInt32) * 2) + ranks_.io_size()
+ select0s_.io_size() + select1s_.io_size();
}
void clear() {
BitVector().swap(*this);
}
void swap(BitVector &rhs) {
units_.swap(rhs.units_);
marisa::swap(size_, rhs.size_);
marisa::swap(num_1s_, rhs.num_1s_);
ranks_.swap(rhs.ranks_);
select0s_.swap(rhs.select0s_);
select1s_.swap(rhs.select1s_);
}
private:
Vector<Unit> units_;
std::size_t size_;
std::size_t num_1s_;
Vector<RankIndex> ranks_;
Vector<UInt32> select0s_;
Vector<UInt32> select1s_;
void build_index(const BitVector &bv,
bool enables_select0, bool enables_select1);
void map_(Mapper &mapper) {
units_.map(mapper);
{
UInt32 temp_size;
mapper.map(&temp_size);
size_ = temp_size;
}
{
UInt32 temp_num_1s;
mapper.map(&temp_num_1s);
MARISA_THROW_IF(temp_num_1s > size_, MARISA_FORMAT_ERROR);
num_1s_ = temp_num_1s;
}
ranks_.map(mapper);
select0s_.map(mapper);
select1s_.map(mapper);
}
void read_(Reader &reader) {
units_.read(reader);
{
UInt32 temp_size;
reader.read(&temp_size);
size_ = temp_size;
}
{
UInt32 temp_num_1s;
reader.read(&temp_num_1s);
MARISA_THROW_IF(temp_num_1s > size_, MARISA_FORMAT_ERROR);
num_1s_ = temp_num_1s;
}
ranks_.read(reader);
select0s_.read(reader);
select1s_.read(reader);
}
void write_(Writer &writer) const {
units_.write(writer);
writer.write((UInt32)size_);
writer.write((UInt32)num_1s_);
ranks_.write(writer);
select0s_.write(writer);
select1s_.write(writer);
}
// Disallows copy and assignment.
BitVector(const BitVector &);
BitVector &operator=(const BitVector &);
};
} // namespace vector
} // namespace grimoire
} // namespace marisa
#endif // MARISA_GRIMOIRE_VECTOR_BIT_VECTOR_H_
|
