1#include "bitvector.h"
2#include "popcount.h"
3
4namespace marisa_alpha {
5namespace {
6
7const UInt8 SelectTable[8][256] = {
8  {
9    7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
10    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
11    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
12    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
13    6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
14    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
15    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
16    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
17    7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
18    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
19    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
20    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
21    6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
22    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
23    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
24    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
25  },
26  {
27    7, 7, 7, 1, 7, 2, 2, 1, 7, 3, 3, 1, 3, 2, 2, 1,
28    7, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
29    7, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1,
30    5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
31    7, 6, 6, 1, 6, 2, 2, 1, 6, 3, 3, 1, 3, 2, 2, 1,
32    6, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
33    6, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1,
34    5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
35    7, 7, 7, 1, 7, 2, 2, 1, 7, 3, 3, 1, 3, 2, 2, 1,
36    7, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
37    7, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1,
38    5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
39    7, 6, 6, 1, 6, 2, 2, 1, 6, 3, 3, 1, 3, 2, 2, 1,
40    6, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
41    6, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1,
42    5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1
43  },
44  {
45    7, 7, 7, 7, 7, 7, 7, 2, 7, 7, 7, 3, 7, 3, 3, 2,
46    7, 7, 7, 4, 7, 4, 4, 2, 7, 4, 4, 3, 4, 3, 3, 2,
47    7, 7, 7, 5, 7, 5, 5, 2, 7, 5, 5, 3, 5, 3, 3, 2,
48    7, 5, 5, 4, 5, 4, 4, 2, 5, 4, 4, 3, 4, 3, 3, 2,
49    7, 7, 7, 6, 7, 6, 6, 2, 7, 6, 6, 3, 6, 3, 3, 2,
50    7, 6, 6, 4, 6, 4, 4, 2, 6, 4, 4, 3, 4, 3, 3, 2,
51    7, 6, 6, 5, 6, 5, 5, 2, 6, 5, 5, 3, 5, 3, 3, 2,
52    6, 5, 5, 4, 5, 4, 4, 2, 5, 4, 4, 3, 4, 3, 3, 2,
53    7, 7, 7, 7, 7, 7, 7, 2, 7, 7, 7, 3, 7, 3, 3, 2,
54    7, 7, 7, 4, 7, 4, 4, 2, 7, 4, 4, 3, 4, 3, 3, 2,
55    7, 7, 7, 5, 7, 5, 5, 2, 7, 5, 5, 3, 5, 3, 3, 2,
56    7, 5, 5, 4, 5, 4, 4, 2, 5, 4, 4, 3, 4, 3, 3, 2,
57    7, 7, 7, 6, 7, 6, 6, 2, 7, 6, 6, 3, 6, 3, 3, 2,
58    7, 6, 6, 4, 6, 4, 4, 2, 6, 4, 4, 3, 4, 3, 3, 2,
59    7, 6, 6, 5, 6, 5, 5, 2, 6, 5, 5, 3, 5, 3, 3, 2,
60    6, 5, 5, 4, 5, 4, 4, 2, 5, 4, 4, 3, 4, 3, 3, 2
61  },
62  {
63    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 3,
64    7, 7, 7, 7, 7, 7, 7, 4, 7, 7, 7, 4, 7, 4, 4, 3,
65    7, 7, 7, 7, 7, 7, 7, 5, 7, 7, 7, 5, 7, 5, 5, 3,
66    7, 7, 7, 5, 7, 5, 5, 4, 7, 5, 5, 4, 5, 4, 4, 3,
67    7, 7, 7, 7, 7, 7, 7, 6, 7, 7, 7, 6, 7, 6, 6, 3,
68    7, 7, 7, 6, 7, 6, 6, 4, 7, 6, 6, 4, 6, 4, 4, 3,
69    7, 7, 7, 6, 7, 6, 6, 5, 7, 6, 6, 5, 6, 5, 5, 3,
70    7, 6, 6, 5, 6, 5, 5, 4, 6, 5, 5, 4, 5, 4, 4, 3,
71    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 3,
72    7, 7, 7, 7, 7, 7, 7, 4, 7, 7, 7, 4, 7, 4, 4, 3,
73    7, 7, 7, 7, 7, 7, 7, 5, 7, 7, 7, 5, 7, 5, 5, 3,
74    7, 7, 7, 5, 7, 5, 5, 4, 7, 5, 5, 4, 5, 4, 4, 3,
75    7, 7, 7, 7, 7, 7, 7, 6, 7, 7, 7, 6, 7, 6, 6, 3,
76    7, 7, 7, 6, 7, 6, 6, 4, 7, 6, 6, 4, 6, 4, 4, 3,
77    7, 7, 7, 6, 7, 6, 6, 5, 7, 6, 6, 5, 6, 5, 5, 3,
78    7, 6, 6, 5, 6, 5, 5, 4, 6, 5, 5, 4, 5, 4, 4, 3
79  },
80  {
81    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
82    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 4,
83    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 5,
84    7, 7, 7, 7, 7, 7, 7, 5, 7, 7, 7, 5, 7, 5, 5, 4,
85    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6,
86    7, 7, 7, 7, 7, 7, 7, 6, 7, 7, 7, 6, 7, 6, 6, 4,
87    7, 7, 7, 7, 7, 7, 7, 6, 7, 7, 7, 6, 7, 6, 6, 5,
88    7, 7, 7, 6, 7, 6, 6, 5, 7, 6, 6, 5, 6, 5, 5, 4,
89    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
90    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 4,
91    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 5,
92    7, 7, 7, 7, 7, 7, 7, 5, 7, 7, 7, 5, 7, 5, 5, 4,
93    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6,
94    7, 7, 7, 7, 7, 7, 7, 6, 7, 7, 7, 6, 7, 6, 6, 4,
95    7, 7, 7, 7, 7, 7, 7, 6, 7, 7, 7, 6, 7, 6, 6, 5,
96    7, 7, 7, 6, 7, 6, 6, 5, 7, 6, 6, 5, 6, 5, 5, 4
97  },
98  {
99    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
100    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
101    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
102    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 5,
103    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
104    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6,
105    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6,
106    7, 7, 7, 7, 7, 7, 7, 6, 7, 7, 7, 6, 7, 6, 6, 5,
107    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
108    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
109    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
110    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 5,
111    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
112    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6,
113    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6,
114    7, 7, 7, 7, 7, 7, 7, 6, 7, 7, 7, 6, 7, 6, 6, 5
115  },
116  {
117    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
118    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
119    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
120    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
121    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
122    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
123    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
124    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6,
125    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
126    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
127    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
128    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
129    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
130    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
131    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
132    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6
133  },
134  {
135    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
136    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
137    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
138    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
139    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
140    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
141    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
142    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
143    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
144    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
145    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
146    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
147    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
148    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
149    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
150    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
151  }
152};
153
154}  // namespace
155
156BitVector::BitVector()
157    : blocks_(), size_(0), ranks_(), select0s_(), select1s_() {}
158
159void BitVector::build() {
160  Vector<Rank> ranks;
161  const UInt32 num_blocks = (size_ / 512) + (((size_ % 512) != 0) ? 1 : 0);
162  ranks.resize(num_blocks + 1);
163  Vector<UInt32> select0s;
164  Vector<UInt32> select1s;
165  UInt32 num_0s = 0;
166  UInt32 num_1s = 0;
167  for (UInt32 i = 0; i < size_; ++i) {
168    if ((i % 64) == 0) {
169      UInt32 rank_id = i / 512;
170      switch ((i / 64) % 8) {
171        case 0: {
172          ranks[rank_id].set_abs(num_1s);
173          break;
174        }
175        case 1: {
176          ranks[rank_id].set_rel1(num_1s - ranks[rank_id].abs());
177          break;
178        }
179        case 2: {
180          ranks[rank_id].set_rel2(num_1s - ranks[rank_id].abs());
181          break;
182        }
183        case 3: {
184          ranks[rank_id].set_rel3(num_1s - ranks[rank_id].abs());
185          break;
186        }
187        case 4: {
188          ranks[rank_id].set_rel4(num_1s - ranks[rank_id].abs());
189          break;
190        }
191        case 5: {
192          ranks[rank_id].set_rel5(num_1s - ranks[rank_id].abs());
193          break;
194        }
195        case 6: {
196          ranks[rank_id].set_rel6(num_1s - ranks[rank_id].abs());
197          break;
198        }
199        case 7: {
200          ranks[rank_id].set_rel7(num_1s - ranks[rank_id].abs());
201          break;
202        }
203      }
204    }
205    if ((*this)[i]) {
206      if ((num_1s % 512) == 0) {
207        select1s.push_back(i);
208      }
209      ++num_1s;
210    } else {
211      if ((num_0s % 512) == 0) {
212        select0s.push_back(i);
213      }
214      ++num_0s;
215    }
216  }
217  if ((size_ % 512) != 0) {
218    UInt32 rank_id = (size_ - 1) / 512;
219    switch (((size_ - 1) / 64) % 8) {
220      case 0: {
221        ranks[rank_id].set_rel1(num_1s - ranks[rank_id].abs());
222      }
223      case 1: {
224        ranks[rank_id].set_rel2(num_1s - ranks[rank_id].abs());
225      }
226      case 2: {
227        ranks[rank_id].set_rel3(num_1s - ranks[rank_id].abs());
228      }
229      case 3: {
230        ranks[rank_id].set_rel4(num_1s - ranks[rank_id].abs());
231      }
232      case 4: {
233        ranks[rank_id].set_rel5(num_1s - ranks[rank_id].abs());
234      }
235      case 5: {
236        ranks[rank_id].set_rel6(num_1s - ranks[rank_id].abs());
237      }
238      case 6: {
239        ranks[rank_id].set_rel7(num_1s - ranks[rank_id].abs());
240        break;
241      }
242    }
243  }
244  ranks.back().set_abs(num_1s);
245  select0s.push_back(size_);
246  select1s.push_back(size_);
247  select0s.shrink();
248  select1s.shrink();
249
250  blocks_.shrink();
251  ranks_.swap(&ranks);
252  select0s_.swap(&select0s);
253  select1s_.swap(&select1s);
254}
255
256void BitVector::mmap(Mapper *mapper, const char *filename,
257    long offset, int whence) {
258  MARISA_ALPHA_THROW_IF(mapper == NULL, MARISA_ALPHA_PARAM_ERROR);
259  Mapper temp_mapper;
260  temp_mapper.open(filename, offset, whence);
261  map(temp_mapper);
262  temp_mapper.swap(mapper);
263}
264
265void BitVector::map(const void *ptr, std::size_t size) {
266  Mapper mapper(ptr, size);
267  map(mapper);
268}
269
270void BitVector::map(Mapper &mapper) {
271  BitVector temp;
272  temp.blocks_.map(mapper);
273  mapper.map(&temp.size_);
274  temp.ranks_.map(mapper);
275  temp.select0s_.map(mapper);
276  temp.select1s_.map(mapper);
277  temp.swap(this);
278}
279
280void BitVector::load(const char *filename,
281    long offset, int whence) {
282  Reader reader;
283  reader.open(filename, offset, whence);
284  read(reader);
285}
286
287void BitVector::fread(std::FILE *file) {
288  Reader reader(file);
289  read(reader);
290}
291
292void BitVector::read(int fd) {
293  Reader reader(fd);
294  read(reader);
295}
296
297void BitVector::read(std::istream &stream) {
298  Reader reader(&stream);
299   read(reader);
300}
301
302void BitVector::read(Reader &reader) {
303  BitVector temp;
304  temp.blocks_.read(reader);
305  reader.read(&temp.size_);
306  temp.ranks_.read(reader);
307  temp.select0s_.read(reader);
308  temp.select1s_.read(reader);
309  temp.swap(this);
310}
311
312void BitVector::save(const char *filename, bool trunc_flag,
313    long offset, int whence) const {
314  Writer writer;
315  writer.open(filename, trunc_flag, offset, whence);
316  write(writer);
317}
318
319void BitVector::fwrite(std::FILE *file) const {
320  Writer writer(file);
321  write(writer);
322}
323
324void BitVector::write(int fd) const {
325  Writer writer(fd);
326  write(writer);
327}
328
329void BitVector::write(std::ostream &stream) const {
330  Writer writer(&stream);
331  write(writer);
332}
333
334void BitVector::write(Writer &writer) const {
335  blocks_.write(writer);
336  writer.write(size_);
337  ranks_.write(writer);
338  select0s_.write(writer);
339  select1s_.write(writer);
340}
341
342UInt32 BitVector::rank1(UInt32 i) const {
343  MARISA_ALPHA_DEBUG_IF(i > size_, MARISA_ALPHA_PARAM_ERROR);
344  const Rank &rank = ranks_[i / 512];
345  UInt32 offset = rank.abs();
346  switch ((i / 64) % 8) {
347    case 1: {
348      offset += rank.rel1();
349      break;
350    }
351    case 2: {
352      offset += rank.rel2();
353      break;
354    }
355    case 3: {
356      offset += rank.rel3();
357      break;
358    }
359    case 4: {
360      offset += rank.rel4();
361      break;
362    }
363    case 5: {
364      offset += rank.rel5();
365      break;
366    }
367    case 6: {
368      offset += rank.rel6();
369      break;
370    }
371    case 7: {
372      offset += rank.rel7();
373      break;
374    }
375  }
376  switch ((i / 32) % 2) {
377    case 1: {
378      offset += PopCount(blocks_[(i / 32) - 1]).lo32();
379    }
380    case 0: {
381      offset += PopCount(blocks_[i / 32] & ((1U << (i % 32)) - 1)).lo32();
382      break;
383    }
384  }
385  return offset;
386}
387
388UInt32 BitVector::select0(UInt32 i) const {
389  UInt32 select_id = i / 512;
390  MARISA_ALPHA_DEBUG_IF((select_id + 1) >= select0s_.size(),
391      MARISA_ALPHA_PARAM_ERROR);
392  if ((i % 512) == 0) {
393    return select0s_[select_id];
394  }
395  UInt32 begin = select0s_[select_id] / 512;
396  UInt32 end = (select0s_[select_id + 1] + 511) / 512;
397  if (begin + 10 >= end) {
398    while (i >= ((begin + 1) * 512) - ranks_[begin + 1].abs()) {
399      ++begin;
400    }
401  } else {
402    while (begin + 1 < end) {
403      UInt32 middle = (begin + end) / 2;
404      if (i < (middle * 512) - ranks_[middle].abs()) {
405        end = middle;
406      } else {
407        begin = middle;
408      }
409    }
410  }
411  const UInt32 rank_id = begin;
412  i -= (rank_id * 512) - ranks_[rank_id].abs();
413
414  const Rank &rank = ranks_[rank_id];
415  UInt32 block_id = rank_id * 16;
416  if (i < (256U - rank.rel4())) {
417    if (i < (128U - rank.rel2())) {
418      if (i >= (64U - rank.rel1())) {
419        block_id += 2;
420        i -= 64 - rank.rel1();
421      }
422    } else if (i < (192U - rank.rel3())) {
423      block_id += 4;
424      i -= 128 - rank.rel2();
425    } else {
426      block_id += 6;
427      i -= 192 - rank.rel3();
428    }
429  } else if (i < (384U - rank.rel6())) {
430    if (i < (320U - rank.rel5())) {
431      block_id += 8;
432      i -= 256 - rank.rel4();
433    } else {
434      block_id += 10;
435      i -= 320 - rank.rel5();
436    }
437  } else if (i < (448U - rank.rel7())) {
438    block_id += 12;
439    i -= 384 - rank.rel6();
440  } else {
441    block_id += 14;
442    i -= 448 - rank.rel7();
443  }
444
445  UInt32 block = ~blocks_[block_id];
446  PopCount count(block);
447  if (i >= count.lo32()) {
448    ++block_id;
449    i -= count.lo32();
450    block = ~blocks_[block_id];
451    count = PopCount(block);
452  }
453
454  UInt32 bit_id = block_id * 32;
455  if (i < count.lo16()) {
456    if (i >= count.lo8()) {
457      bit_id += 8;
458      block >>= 8;
459      i -= count.lo8();
460    }
461  } else if (i < count.lo24()) {
462    bit_id += 16;
463    block >>= 16;
464    i -= count.lo16();
465  } else {
466    bit_id += 24;
467    block >>= 24;
468    i -= count.lo24();
469  }
470  return bit_id + SelectTable[i][block & 0xFF];
471}
472
473UInt32 BitVector::select1(UInt32 i) const {
474  UInt32 select_id = i / 512;
475  MARISA_ALPHA_DEBUG_IF((select_id + 1) >= select1s_.size(),
476      MARISA_ALPHA_PARAM_ERROR);
477  if ((i % 512) == 0) {
478    return select1s_[select_id];
479  }
480  UInt32 begin = select1s_[select_id] / 512;
481  UInt32 end = (select1s_[select_id + 1] + 511) / 512;
482  if (begin + 10 >= end) {
483    while (i >= ranks_[begin + 1].abs()) {
484      ++begin;
485    }
486  } else {
487    while (begin + 1 < end) {
488      UInt32 middle = (begin + end) / 2;
489      if (i < ranks_[middle].abs()) {
490        end = middle;
491      } else {
492        begin = middle;
493      }
494    }
495  }
496  const UInt32 rank_id = begin;
497  i -= ranks_[rank_id].abs();
498
499  const Rank &rank = ranks_[rank_id];
500  UInt32 block_id = rank_id * 16;
501  if (i < rank.rel4()) {
502    if (i < rank.rel2()) {
503      if (i >= rank.rel1()) {
504        block_id += 2;
505        i -= rank.rel1();
506      }
507    } else if (i < rank.rel3()) {
508      block_id += 4;
509      i -= rank.rel2();
510    } else {
511      block_id += 6;
512      i -= rank.rel3();
513    }
514  } else if (i < rank.rel6()) {
515    if (i < rank.rel5()) {
516      block_id += 8;
517      i -= rank.rel4();
518    } else {
519      block_id += 10;
520      i -= rank.rel5();
521    }
522  } else if (i < rank.rel7()) {
523    block_id += 12;
524    i -= rank.rel6();
525  } else {
526    block_id += 14;
527    i -= rank.rel7();
528  }
529
530  UInt32 block = blocks_[block_id];
531  PopCount count(block);
532  if (i >= count.lo32()) {
533    ++block_id;
534    i -= count.lo32();
535    block = blocks_[block_id];
536    count = PopCount(block);
537  }
538
539  UInt32 bit_id = block_id * 32;
540  if (i < count.lo16()) {
541    if (i >= count.lo8()) {
542      bit_id += 8;
543      block >>= 8;
544      i -= count.lo8();
545    }
546  } else if (i < count.lo24()) {
547    bit_id += 16;
548    block >>= 16;
549    i -= count.lo16();
550  } else {
551    bit_id += 24;
552    block >>= 24;
553    i -= count.lo24();
554  }
555  return bit_id + SelectTable[i][block & 0xFF];
556}
557
558void BitVector::clear() {
559  BitVector().swap(this);
560}
561
562void BitVector::swap(BitVector *rhs) {
563  MARISA_ALPHA_THROW_IF(rhs == NULL, MARISA_ALPHA_PARAM_ERROR);
564  blocks_.swap(&rhs->blocks_);
565  Swap(&size_, &rhs->size_);
566  ranks_.swap(&rhs->ranks_);
567  select0s_.swap(&rhs->select0s_);
568  select1s_.swap(&rhs->select1s_);
569}
570
571}  // namespace marisa_alpha
572