tdb_succinct/
smallbitarray.rs

1#[derive(Clone)]
2pub struct SmallBitArray {
3    val: u64,
4}
5
6impl std::fmt::Debug for SmallBitArray {
7    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
8        write!(f, "<{:b}>", self.val)
9    }
10}
11
12impl SmallBitArray {
13    pub const LEN: usize = u64::BITS as usize - 1;
14    pub fn new(val: u64) -> Self {
15        if val & 1 != 0 {
16            panic!("lsb set for a small bit array. this is reserved for future expansion");
17        }
18
19        Self { val }
20    }
21
22    pub fn get(&self, index: usize) -> bool {
23        if index >= Self::LEN {
24            panic!("index too high");
25        }
26
27        (self.val >> (Self::LEN - index) & 1) != 0
28    }
29
30    pub fn iter(&self) -> impl Iterator<Item = bool> {
31        SmallBitArrayIter {
32            val: self.val,
33            ix: 0,
34        }
35    }
36
37    pub fn inner(&self) -> u64 {
38        self.val
39    }
40
41    pub fn rank1(&self, index: usize) -> usize {
42        if index >= Self::LEN {
43            panic!("index too high");
44        }
45
46        let mask = !(u64::MAX >> (index as u32 + 1));
47        (self.val & mask).count_ones() as usize
48    }
49}
50
51#[derive(Clone)]
52pub struct SmallBitArrayIter {
53    val: u64,
54    ix: usize,
55}
56
57impl Iterator for SmallBitArrayIter {
58    type Item = bool;
59
60    fn next(&mut self) -> Option<bool> {
61        if self.ix >= SmallBitArray::LEN {
62            return None;
63        }
64
65        let result = (self.val & 0x80000000_00000000) != 0;
66
67        self.val <<= 1;
68        self.ix += 1;
69
70        Some(result)
71    }
72}
73
74#[cfg(test)]
75mod tests {
76    use super::*;
77    #[test]
78    #[should_panic(
79        expected = "lsb set for a small bit array. this is reserved for future expansion"
80    )]
81    fn panic_with_set_lsb() {
82        let val: u64 = 0b01101011_10111001_10010010_00000111_10010001_01100101_00000000_11111111;
83
84        let _x = SmallBitArray::new(val);
85    }
86    #[test]
87    fn get_from_small_bit_array() {
88        let val: u64 = 0b01101011_10111001_10010010_00000111_10010001_01100101_00000000_11111110;
89
90        let arr = SmallBitArray::new(val);
91
92        #[rustfmt::skip]
93        let expecteds = [
94            false, true, true, false, true, false, true, true,
95            true, false, true, true, true, false, false, true,
96            true, false, false, true, false, false, true, false,
97            false, false, false, false, false, true, true, true,
98            true, false, false, true, false, false, false, true,
99            false, true, true, false, false, true, false, true,
100            false, false, false, false, false, false, false, false,
101            true, true, true, true, true, true, true
102        ];
103
104        for (ix, &expected) in expecteds.iter().enumerate() {
105            assert_eq!(expected, arr.get(ix));
106        }
107    }
108    #[test]
109
110    fn iterate_small_bit_array() {
111        let val: u64 = 0b01101011_10111001_10010010_00000111_10010001_01100101_00000000_11111110;
112
113        let arr = SmallBitArray::new(val);
114
115        #[rustfmt::skip]
116        let expecteds = [
117            false, true, true, false, true, false, true, true,
118            true, false, true, true, true, false, false, true,
119            true, false, false, true, false, false, true, false,
120            false, false, false, false, false, true, true, true,
121            true, false, false, true, false, false, false, true,
122            false, true, true, false, false, true, false, true,
123            false, false, false, false, false, false, false, false,
124            true, true, true, true, true, true, true
125        ];
126
127        let iter = arr.iter();
128
129        for (&expected, actual) in expecteds.iter().zip(iter) {
130            assert_eq!(expected, actual);
131        }
132    }
133
134    #[test]
135    fn small_bit_array_rank() {
136        let val: u64 = 0b01101011_10111001_10010010_00000111_10010001_01100101_00000000_11111110;
137
138        let arr = SmallBitArray::new(val);
139
140        #[rustfmt::skip]
141        let expecteds = [
142            0, 1, 2, 2, 3, 3, 4, 5,
143            6, 6, 7, 8, 9, 9, 9, 10,
144            11, 11, 11, 12, 12, 12, 13, 13,
145            13, 13, 13, 13, 13, 14, 15, 16,
146            17, 17, 17, 18, 18, 18, 18, 19,
147            19, 20, 21, 21, 21, 22, 22, 23,
148            23, 23, 23, 23, 23, 23, 23, 23,
149            24, 25, 26, 27, 28, 29, 30
150        ];
151
152        for (ix, &expected) in expecteds.iter().enumerate() {
153            let rank = arr.rank1(ix);
154            assert_eq!(expected, rank);
155        }
156    }
157}
tdb_succinct/smallbitarray.rs

tdb_succinct/
smallbitarray.rs
