1use std::ops::{Range, RangeBounds, RangeInclusive};
2
3use usize_bounds::UsizeBounds;
4
5const W: usize = u64::BITS as usize;
6
7const RANK_LARGE_LEN: usize = 1024; const RANK_SMALL_LEN: usize = 16; const RANK_BIT_PATTERNS: usize = 1 << RANK_SMALL_LEN;
10
11const SELECT_SMALL_LEN: usize = 15; const SELECT_LARGE_SPARSE_LEN: usize = 12946;
13const SELECT_LARGE_POPCNT: usize = 17;
14const SELECT_LARGE_NODE_LEN: usize = 4;
15const SELECT_LARGE_BRANCH: usize = 4;
16const SELECT_WORD_BIT_PATTERNS: usize = 1 << SELECT_SMALL_LEN;
17const SELECT_TREE_BIT_PATTERNS: usize =
18 1 << (SELECT_LARGE_NODE_LEN * SELECT_LARGE_BRANCH);
19
20const _ASSERTION: () = {
21 let popcnt = SELECT_LARGE_POPCNT;
22 let node_len = SELECT_LARGE_NODE_LEN;
23 let branch = SELECT_LARGE_BRANCH;
24
25 let node_popcnt = !(!0 << node_len);
26 if node_popcnt * branch < popcnt {
27 panic!();
28 }
29};
30
31pub type Rs01Dict = Rs01DictGenerics<
32 RANK_LARGE_LEN,
33 RANK_SMALL_LEN,
34 RANK_BIT_PATTERNS,
35 SELECT_SMALL_LEN,
36 SELECT_LARGE_SPARSE_LEN,
37 SELECT_LARGE_POPCNT,
38 SELECT_LARGE_NODE_LEN,
39 SELECT_LARGE_BRANCH,
40 SELECT_WORD_BIT_PATTERNS,
41 SELECT_TREE_BIT_PATTERNS,
42>;
43
44pub struct Rs01DictGenerics<
45 const RANK_LARGE_LEN: usize,
46 const RANK_SMALL_LEN: usize,
47 const RANK_BIT_PATTERNS: usize,
48 const SELECT_SMALL_LEN: usize,
49 const SELECT_LARGE_SPARSE_LEN: usize,
50 const SELECT_LARGE_POPCNT: usize,
51 const SELECT_LARGE_NODE_LEN: usize,
52 const SELECT_LARGE_BRANCH: usize,
53 const SELECT_WORD_BIT_PATTERNS: usize,
54 const SELECT_TREE_BIT_PATTERNS: usize,
55> {
56 buf: SimpleBitVec,
57 rank_index: RankIndex<RANK_LARGE_LEN, RANK_SMALL_LEN, RANK_BIT_PATTERNS>,
58 select1_index: SelectIndex<
59 SELECT_SMALL_LEN,
60 SELECT_LARGE_SPARSE_LEN,
61 SELECT_LARGE_POPCNT,
62 SELECT_LARGE_NODE_LEN,
63 SELECT_LARGE_BRANCH,
64 SELECT_WORD_BIT_PATTERNS,
65 SELECT_TREE_BIT_PATTERNS,
66 >,
67 select0_index: SelectIndex<
68 SELECT_SMALL_LEN,
69 SELECT_LARGE_SPARSE_LEN,
70 SELECT_LARGE_POPCNT,
71 SELECT_LARGE_NODE_LEN,
72 SELECT_LARGE_BRANCH,
73 SELECT_WORD_BIT_PATTERNS,
74 SELECT_TREE_BIT_PATTERNS,
75 >,
76}
77
78struct SimpleBitVec {
79 buf: Vec<u64>,
80 len: usize,
81}
82
83struct RankIndex<
84 const LARGE_LEN: usize,
85 const SMALL_LEN: usize,
86 const BIT_PATTERNS: usize,
87> {
88 large: Vec<u32>,
89 small: Vec<u16>,
90}
91
92struct SelectIndex<
93 const SMALL_LEN: usize,
94 const LARGE_SPARSE_LEN: usize,
95 const LARGE_POPCNT: usize,
96 const LARGE_NODE_LEN: usize,
97 const LARGE_BRANCH: usize,
98 const WORD_BIT_PATTERNS: usize,
99 const TREE_BIT_PATTERNS: usize,
100> {
101 inner: Vec<
102 SelectIndexInner<
103 SMALL_LEN,
104 LARGE_SPARSE_LEN,
105 LARGE_POPCNT,
106 LARGE_NODE_LEN,
107 LARGE_BRANCH,
108 WORD_BIT_PATTERNS,
109 TREE_BIT_PATTERNS,
110 >,
111 >,
112}
113
114enum SelectIndexInner<
115 const SMALL_LEN: usize,
116 const LARGE_SPARSE_LEN: usize,
117 const LARGE_POPCNT: usize,
118 const LARGE_NODE_LEN: usize,
119 const LARGE_BRANCH: usize,
120 const WORD_BIT_PATTERNS: usize,
121 const TREE_BIT_PATTERNS: usize,
122> {
123 Sparse(Vec<usize>),
124 Dense(SimpleBitVec, usize),
125}
126
127trait RankLookup<const SMALL_LEN: usize, const BIT_PATTERNS: usize> {
128 const WORD: [[u8; SMALL_LEN]; BIT_PATTERNS];
129}
130
131trait SelectLookup<
132 const NODE_LEN: usize,
133 const POPCNT: usize,
134 const TREE_BIT_PATTERNS: usize,
135 const SMALL_LEN: usize,
136 const WORD_BIT_PATTERNS: usize,
137>
138{
139 const TREE: [[(u8, u8); POPCNT]; TREE_BIT_PATTERNS];
140 const WORD: [[u8; SMALL_LEN]; WORD_BIT_PATTERNS];
141}
142
143const fn rank_lookup<const SMALL_LEN: usize, const BIT_PATTERNS: usize>()
144-> [[u8; SMALL_LEN]; BIT_PATTERNS] {
145 let mut table = [[0; SMALL_LEN]; BIT_PATTERNS];
146 let mut i = 0;
147 while i < BIT_PATTERNS {
148 table[i][0] = (i & 1) as _;
149 let mut j = 1;
150 while j < SMALL_LEN {
151 table[i][j] = table[i][j - 1] + (i >> j & 1) as u8;
152 j += 1;
153 }
154 i += 1;
155 }
156 table
157}
158
159#[warn(long_running_const_eval)]
160const fn select_tree_lookup<
161 const NODE_LEN: usize,
162 const POPCNT: usize,
163 const BRANCH: usize,
164 const BIT_PATTERNS: usize,
165>() -> [[(u8, u8); POPCNT]; BIT_PATTERNS] {
166 let mut table = [[(0, 0); POPCNT]; BIT_PATTERNS];
167 let mut i = 0;
168 while i < BIT_PATTERNS {
169 let mut j = 0;
170 let mut index = 0;
171 while j < BRANCH {
172 let count = i >> (j * NODE_LEN) & !(!0 << NODE_LEN);
175 let mut k = 0;
176 while k < count && index < POPCNT {
177 table[i][index] = (j as _, (index - k) as _);
178 index += 1;
179 k += 1;
180 }
181 j += 1;
182 }
183 i += 1;
184 }
185 table
186}
187
188const fn select_word_lookup<
189 const SMALL_LEN: usize,
190 const BIT_PATTERNS: usize,
191>() -> [[u8; SMALL_LEN]; BIT_PATTERNS] {
192 let mut table = [[0; SMALL_LEN]; BIT_PATTERNS];
193 let mut i = 0;
194 while i < BIT_PATTERNS {
195 let mut j = 0;
196 let mut count = 0;
197 while j < SMALL_LEN {
198 if i >> j & 1 != 0 {
199 table[i][count] = j as _;
200 count += 1;
201 }
202 j += 1;
203 }
204 i += 1;
205 }
206 table
207}
208
209impl<
210 const RANK_LARGE_LEN: usize,
211 const RANK_SMALL_LEN: usize,
212 const RANK_BIT_PATTERNS: usize,
213 const SELECT_SMALL_LEN: usize,
214 const SELECT_LARGE_SPARSE_LEN: usize,
215 const SELECT_LARGE_POPCNT: usize,
216 const SELECT_LARGE_NODE_LEN: usize,
217 const SELECT_LARGE_BRANCH: usize,
218 const SELECT_WORD_BIT_PATTERNS: usize,
219 const SELECT_TREE_BIT_PATTERNS: usize,
220>
221 Rs01DictGenerics<
222 RANK_LARGE_LEN,
223 RANK_SMALL_LEN,
224 RANK_BIT_PATTERNS,
225 SELECT_SMALL_LEN,
226 SELECT_LARGE_SPARSE_LEN,
227 SELECT_LARGE_POPCNT,
228 SELECT_LARGE_NODE_LEN,
229 SELECT_LARGE_BRANCH,
230 SELECT_WORD_BIT_PATTERNS,
231 SELECT_TREE_BIT_PATTERNS,
232 >
233{
234 pub fn new(a: &[bool]) -> Self {
235 let buf = SimpleBitVec::from(a);
236 let rank_index = RankIndex::<
237 RANK_LARGE_LEN,
238 RANK_SMALL_LEN,
239 RANK_BIT_PATTERNS,
240 >::new(&buf);
241 let select1_index = SelectIndex::<
242 SELECT_SMALL_LEN,
243 SELECT_LARGE_SPARSE_LEN,
244 SELECT_LARGE_POPCNT,
245 SELECT_LARGE_NODE_LEN,
246 SELECT_LARGE_BRANCH,
247 SELECT_WORD_BIT_PATTERNS,
248 SELECT_TREE_BIT_PATTERNS,
249 >::new::<true>(&buf);
250 let select0_index = SelectIndex::<
251 SELECT_SMALL_LEN,
252 SELECT_LARGE_SPARSE_LEN,
253 SELECT_LARGE_POPCNT,
254 SELECT_LARGE_NODE_LEN,
255 SELECT_LARGE_BRANCH,
256 SELECT_WORD_BIT_PATTERNS,
257 SELECT_TREE_BIT_PATTERNS,
258 >::new::<false>(&buf);
259 Self { buf, rank_index, select1_index, select0_index }
260 }
261
262 pub fn rank1(&self, i: usize) -> usize {
263 self.rank_index.rank(i, &self.buf)
264 }
265 pub fn rank0(&self, i: usize) -> usize { i + 1 - self.rank1(i) }
266
267 fn rank<const X: bool>(&self, i: usize) -> usize {
268 if X { self.rank1(i) } else { self.rank0(i) }
269 }
270
271 pub fn select1(&self, i: usize) -> usize {
272 self.select1_index.select::<true>(i, &self.buf)
273 }
274 pub fn select0(&self, i: usize) -> usize {
275 self.select0_index.select::<false>(i, &self.buf)
276 }
277
278 fn count<const X: bool>(&self, range: impl RangeBounds<usize>) -> usize {
279 let Range { start, end } = range.to_range(self.buf.len);
280 if start == end {
281 0
282 } else if start == 0 {
283 self.rank::<X>(end - 1)
284 } else {
285 self.rank::<X>(end - 1) - self.rank::<X>(start - 1)
286 }
287 }
288
289 pub fn count1(&self, range: impl RangeBounds<usize>) -> usize {
290 self.count::<true>(range)
291 }
292 pub fn count0(&self, range: impl RangeBounds<usize>) -> usize {
293 self.count::<false>(range)
294 }
295}
296
297impl From<(Vec<u64>, usize)> for SimpleBitVec {
298 fn from((buf, len): (Vec<u64>, usize)) -> Self { Self { buf, len } }
299}
300
301impl From<&[bool]> for SimpleBitVec {
302 fn from(a: &[bool]) -> Self {
303 let len = a.len();
304 let n = (len + W - 1) / W;
305 let mut buf = vec![0; n];
306 for i in 0..len {
307 if a[i] {
308 buf[i / W] |= 1 << (i % W);
309 }
310 }
311 Self { buf, len }
312 }
313}
314
315impl SimpleBitVec {
316 fn new() -> Self { Self { buf: vec![], len: 0 } }
317
318 fn len(&self) -> usize { self.len }
319
320 fn get_single(&self, i: usize) -> bool {
321 debug_assert!(i < self.len);
322 self.buf[i / W] >> (i % W) & 1 != 0
323 }
324
325 fn get<const X: bool>(&self, Range { start, end }: Range<usize>) -> u64 {
326 debug_assert!(end - start <= 64);
327 debug_assert!(end <= self.len);
328
329 let mask = !(!0 << (end - start));
330 let res = if start == end {
331 0
332 } else if start % W == 0 {
333 self.buf[start / W] & mask
334 } else if end <= (start / W + 1) * W {
335 self.buf[start / W] >> (start % W)
336 } else {
337 self.buf[start / W] >> (start % W)
338 | self.buf[end / W] << (W - start % W)
339 };
340 (if X { res } else { !res }) & mask
341 }
342
343 fn push(&mut self, w: u64, len: usize) {
344 assert!(len == W || w & (!0 << len) == 0);
345
346 if len == 0 {
347 } else if self.len % W == 0 {
349 self.buf.push(w);
351 } else {
352 self.buf[self.len / W] |= w << (self.len % W);
353 if self.len % W + len > W {
354 self.buf.push(w >> (W - self.len % W));
355 }
356 }
357 self.len += len;
358 }
359
360 fn push_vec(&mut self, other: Self) {
361 for (k, &w) in other.buf.iter().enumerate() {
362 let il = k * W;
363 let ir = other.len.min(il + W);
364 self.push(w, ir - il);
365 }
366 }
367
368 fn pad_zero(&mut self, new_len: usize) {
369 if new_len <= self.len {
370 return;
371 }
372 let n = (new_len + W - 1) / W;
373 self.buf.resize(n, 0);
374 self.len = new_len;
375 }
376
377 fn chunks<const X: bool>(
378 &self,
379 size: usize,
380 ) -> impl Iterator<Item = u64> + '_ {
381 (0..self.len)
382 .step_by(size)
383 .map(move |i| self.get::<X>(i..self.len.min(i + size)))
384 }
385}
386
387impl<const LARGE_LEN: usize, const SMALL_LEN: usize, const BIT_PATTERNS: usize>
388 RankLookup<SMALL_LEN, BIT_PATTERNS>
389 for RankIndex<LARGE_LEN, SMALL_LEN, BIT_PATTERNS>
390{
391 const WORD: [[u8; SMALL_LEN]; BIT_PATTERNS] =
392 rank_lookup::<SMALL_LEN, BIT_PATTERNS>();
393}
394
395impl<const LARGE_LEN: usize, const SMALL_LEN: usize, const BIT_PATTERNS: usize>
396 RankIndex<LARGE_LEN, SMALL_LEN, BIT_PATTERNS>
397{
398 fn new(a: &SimpleBitVec) -> Self {
399 let mut small = vec![];
400 let mut large = vec![];
401 let mut small_acc = 0;
402 let mut large_acc = 0;
403 let per = LARGE_LEN / SMALL_LEN;
404 for (c, i) in a
405 .chunks::<true>(SMALL_LEN)
406 .map(|ai| Self::WORD[ai as usize][SMALL_LEN - 1] as u16)
407 .zip((0..per).cycle())
408 {
409 small.push(small_acc);
410 small_acc = if i < per - 1 { small_acc + c } else { 0 };
411
412 if i == 0 {
413 large.push(large_acc);
414 }
415 large_acc += c as u32;
416 }
417
418 Self { large, small }
419 }
420
421 fn rank(&self, n: usize, b: &SimpleBitVec) -> usize {
422 let large_acc = self.large[n / LARGE_LEN] as usize;
423 let small_acc = self.small[n / SMALL_LEN] as usize;
424 let il = n / SMALL_LEN * SMALL_LEN;
425 let ir = b.len().min(il + SMALL_LEN);
426 let w = b.get::<true>(il..ir);
427 let small = Self::WORD[w as usize][n % SMALL_LEN] as usize;
428 large_acc + small_acc + small
429 }
430}
431
432impl<
433 const SMALL_LEN: usize,
434 const LARGE_SPARSE_LEN: usize,
435 const LARGE_POPCNT: usize,
436 const LARGE_NODE_LEN: usize,
437 const LARGE_BRANCH: usize,
438 const WORD_BIT_PATTERNS: usize,
439 const TREE_BIT_PATTERNS: usize,
440>
441 SelectIndex<
442 SMALL_LEN,
443 LARGE_SPARSE_LEN,
444 LARGE_POPCNT,
445 LARGE_NODE_LEN,
446 LARGE_BRANCH,
447 WORD_BIT_PATTERNS,
448 TREE_BIT_PATTERNS,
449 >
450{
451 fn new<const X: bool>(b: &SimpleBitVec) -> Self {
452 let n = b.len();
453
454 let mut cur = vec![];
455 let mut res = vec![];
456 let mut start = 0;
457 for i in 0..n {
458 if b.get_single(i) == X {
459 cur.push(i);
460 }
461 if cur.len() >= LARGE_POPCNT || i == n - 1 {
462 let tmp = std::mem::take(&mut cur);
463 res.push(SelectIndexInner::new::<X>(tmp, start..=i, b));
464 start = i + 1
465 }
466 }
467 Self { inner: res }
468 }
469
470 fn select<const X: bool>(&self, i: usize, b: &SimpleBitVec) -> usize {
471 self.inner[i / LARGE_POPCNT].select::<X>(i % LARGE_POPCNT, b)
472 }
473}
474
475impl<
476 const SMALL_LEN: usize,
477 const LARGE_SPARSE_LEN: usize,
478 const LARGE_POPCNT: usize,
479 const LARGE_NODE_LEN: usize,
480 const LARGE_BRANCH: usize,
481 const WORD_BIT_PATTERNS: usize,
482 const TREE_BIT_PATTERNS: usize,
483>
484 SelectLookup<
485 LARGE_NODE_LEN,
486 LARGE_POPCNT,
487 TREE_BIT_PATTERNS,
488 SMALL_LEN,
489 WORD_BIT_PATTERNS,
490 >
491 for SelectIndexInner<
492 SMALL_LEN,
493 LARGE_SPARSE_LEN,
494 LARGE_POPCNT,
495 LARGE_NODE_LEN,
496 LARGE_BRANCH,
497 WORD_BIT_PATTERNS,
498 TREE_BIT_PATTERNS,
499 >
500{
501 const TREE: [[(u8, u8); LARGE_POPCNT]; TREE_BIT_PATTERNS] =
502 select_tree_lookup::<
503 LARGE_NODE_LEN,
504 LARGE_POPCNT,
505 LARGE_BRANCH,
506 TREE_BIT_PATTERNS,
507 >();
508 const WORD: [[u8; SMALL_LEN]; WORD_BIT_PATTERNS] =
509 select_word_lookup::<SMALL_LEN, WORD_BIT_PATTERNS>();
510}
511
512impl<
513 const SMALL_LEN: usize,
514 const LARGE_SPARSE_LEN: usize,
515 const LARGE_POPCNT: usize,
516 const LARGE_NODE_LEN: usize,
517 const LARGE_BRANCH: usize,
518 const WORD_BIT_PATTERNS: usize,
519 const TREE_BIT_PATTERNS: usize,
520>
521 SelectIndexInner<
522 SMALL_LEN,
523 LARGE_SPARSE_LEN,
524 LARGE_POPCNT,
525 LARGE_NODE_LEN,
526 LARGE_BRANCH,
527 WORD_BIT_PATTERNS,
528 TREE_BIT_PATTERNS,
529 >
530{
531 fn new<const X: bool>(
532 a: Vec<usize>,
533 range: RangeInclusive<usize>,
534 b: &SimpleBitVec,
535 ) -> Self {
536 let start = *range.start();
537 let end = range.end() + 1;
538 if end - start >= LARGE_SPARSE_LEN {
539 Self::Sparse(a)
540 } else {
541 Self::new_dense::<X>(b, start..end)
542 }
543 }
544
545 fn new_dense<const X: bool>(
546 b: &SimpleBitVec,
547 Range { start, end }: Range<usize>,
548 ) -> Self {
549 let rl = &RankIndex::<0, SMALL_LEN, WORD_BIT_PATTERNS>::WORD;
550 let len = end - start;
551
552 let leaf = {
553 let mut leaf = SimpleBitVec::new();
554 for i in 0..(len + SMALL_LEN - 1) / SMALL_LEN {
555 let il = start + i * SMALL_LEN;
556 let ir = end.min(il + SMALL_LEN);
557 let w = b.get::<X>(il..ir);
558 leaf.push(rl[w as usize][SMALL_LEN - 1] as u64, LARGE_NODE_LEN);
559 }
560 leaf
561 };
562
563 let mut tree = vec![];
564 let mut last = leaf;
565 while last.len() > LARGE_NODE_LEN {
566 let mut cur = SimpleBitVec::new();
567 let tmp = last;
568 {
569 let mut it = tmp.chunks::<true>(LARGE_NODE_LEN);
570 let mut trunc = None;
571 while let Some(mut sum) = it.next() {
572 sum += (1..LARGE_BRANCH)
573 .filter_map(|_| it.next())
574 .sum::<u64>();
575 if sum & (!0 << LARGE_NODE_LEN) != 0 {
576 trunc = Some(sum);
577 sum &= !(!0 << LARGE_NODE_LEN);
578 }
579 cur.push(sum, LARGE_NODE_LEN);
580 }
581 if let Some(sum) = trunc {
582 if cur.len() > LARGE_NODE_LEN {
583 panic!("invalid popcount, {}", sum);
584 }
585 }
586 }
587 tree.push(tmp);
588 last = cur;
589 }
590
591 let mut level_len = LARGE_NODE_LEN * LARGE_BRANCH;
592 let mut tree_len = level_len;
593 let mut tree_flatten = SimpleBitVec::new();
594 for level in tree.into_iter().rev() {
595 tree_flatten.push_vec(level);
596 tree_flatten.pad_zero(tree_len);
597 level_len *= LARGE_BRANCH;
598 tree_len += level_len;
599 }
600
601 Self::Dense(tree_flatten, start)
602 }
603
604 fn select<const X: bool>(&self, i: usize, b: &SimpleBitVec) -> usize {
608 match self {
609 Self::Sparse(index) => index[i],
610 Self::Dense(tree, start) => {
611 let mut i = i;
612 let mut nth_word = 0;
613 let mut level_off = 0;
614 let mut level_count = LARGE_BRANCH;
615 while level_off * LARGE_NODE_LEN < tree.len() {
616 let il = (level_off + nth_word) * LARGE_NODE_LEN;
617 let ir = il + LARGE_NODE_LEN * LARGE_BRANCH;
618 let w = tree.get::<true>(il..ir);
619 let (branch, rank) = Self::TREE[w as usize][i];
620 nth_word = (nth_word + branch as usize) * LARGE_BRANCH;
621 level_off += level_count;
622 level_count *= LARGE_BRANCH;
623 i -= rank as usize;
624 }
625
626 nth_word /= LARGE_BRANCH;
627 let il = start + nth_word * SMALL_LEN;
628 let ir = b.len().min(il + SMALL_LEN);
629 let w = b.get::<X>(il..ir);
630 start
631 + nth_word * SMALL_LEN
632 + Self::WORD[w as usize][i] as usize
633 }
634 }
635 }
636}
637
638#[cfg(test)]
639macro_rules! bitvec {
640 ($lit:literal) => {
641 $lit.iter()
642 .filter(|&&b| matches!(b, b'0' | b'1'))
643 .map(|&b| b != b'0')
644 .collect::<Vec<_>>()
645 };
646}
647
648#[cfg(test)]
649mod tests {
650 use crate::*;
651
652 #[test]
653 fn test_rank_lookup() {
654 let table = rank_lookup::<3, 8>();
655
656 assert_eq!(&table[0b000][..3], [0, 0, 0]);
657 assert_eq!(&table[0b100][..3], [0, 0, 1]);
658 assert_eq!(&table[0b010][..3], [0, 1, 1]);
659 assert_eq!(&table[0b110][..3], [0, 1, 2]);
660 assert_eq!(&table[0b001][..3], [1, 1, 1]);
661 assert_eq!(&table[0b101][..3], [1, 1, 2]);
662 assert_eq!(&table[0b011][..3], [1, 2, 2]);
663 assert_eq!(&table[0b111][..3], [1, 2, 3]);
664 }
665
666 #[test]
667 #[cfg(any())]
668 fn test_select_tree_lookup() {
669 let table = select_tree_lookup::<3, 9, 3, 512>();
670 let tmp: [_; 9] = table[0b_010_100_011][..9].try_into().unwrap();
672
673 assert_eq!(tmp.map(|x| x.0), [0, 0, 0, 1, 1, 1, 1, 2, 2]);
674 assert_eq!(tmp.map(|x| x.1), [0, 0, 0, 3, 3, 3, 3, 7, 7]);
675 }
676
677 #[test]
678 fn test_select_word_lookup() {
679 let table = select_word_lookup::<3, 8>();
680
681 assert_eq!(&table[0b001][..1], [0]);
682 assert_eq!(&table[0b010][..1], [1]);
683 assert_eq!(&table[0b011][..2], [0, 1]);
684 assert_eq!(&table[0b100][..1], [2]);
685 assert_eq!(&table[0b101][..2], [0, 2]);
686 assert_eq!(&table[0b110][..2], [1, 2]);
687 assert_eq!(&table[0b111][..3], [0, 1, 2]);
688 }
689
690 #[test]
691 fn test_select_index() {
692 let a = bitvec!(b"110 001 001 000 010 010");
693 let b = SimpleBitVec::from(a.as_slice());
694 let slt = SelectIndex::<3, 1000, 12, 4, 3, 8, 4096>::new::<true>(&b);
695
696 let expected: Vec<_> = (0..a.len()).filter(|&i| a[i]).collect();
701 for i in 0..expected.len() {
702 assert_eq!(slt.select::<true>(i, &b), expected[i]);
703 }
704 }
705
706 #[test]
707 fn test_all_zero() {
708 let n = 1000;
709 let a = vec![false; n];
710 let rs = Rs01Dict::new(&a);
711
712 for i in 0..n {
713 assert_eq!(rs.rank1(i), 0);
714 assert_eq!(rs.rank0(i), i + 1);
715 assert_eq!(rs.select0(i), i);
716 }
717 }
718}