poppy_filters/bitset/
array.rs

1/// Array based bitset implementation.
2/// N gives the size in Bytes of the bucket
3#[derive(Debug, Clone)]
4pub struct BitSet<const N: usize>([u8; N]);
5
6impl<const N: usize> BitSet<N> {
7    /// Creates a new bitset
8    pub const fn new() -> Self {
9        Self([0; N])
10    }
11
12    #[inline(always)]
13    fn set_value_nth_bit(&mut self, index: usize, value: bool) -> bool {
14        let iblock = index / 8;
15        // equivalent to index % 8
16        let mask = (value as u8) << (index & 7);
17        let old = self.0[iblock] & mask == mask;
18        self.0[iblock] |= mask;
19        old
20    }
21
22    /// Set the value of the nth bit (set to 1)
23    ///
24    /// # Panics
25    ///
26    /// Panic on index out of bound
27    #[inline(always)]
28    pub fn set_nth_bit(&mut self, index: usize) -> bool {
29        self.set_value_nth_bit(index, true)
30    }
31
32    /// Unset the value of the nth bit (set to 0)
33    ///
34    /// # Panics
35    ///
36    /// Panic on index out of bound
37    #[inline(always)]
38    pub fn unset_nth_bit(&mut self, index: usize) -> bool {
39        self.set_value_nth_bit(index, false)
40    }
41
42    /// Get the value of the nth bit
43    ///
44    /// # Panics
45    ///
46    /// Panic on index out of bound
47    #[inline(always)]
48    pub fn get_nth_bit(&self, index: usize) -> bool {
49        let iblock = index / 8;
50        // equivalent to index % 8
51        let mask = 1u8 << (index & 7);
52        self.0[iblock] & mask == mask
53    }
54
55    #[inline(always)]
56    pub fn as_slice(&self) -> &[u8] {
57        self.0.as_slice()
58    }
59
60    #[inline(always)]
61    pub fn as_mut_slice(&mut self) -> &mut [u8] {
62        self.0.as_mut_slice()
63    }
64
65    /// Clears out a bitset (set all the bits to 0)
66    #[inline]
67    pub fn clear(&mut self) {
68        self.0.iter_mut().for_each(|b| *b = 0);
69    }
70
71    /// Returns the size in bits of the bitset
72    #[inline]
73    pub const fn bit_len(&self) -> usize {
74        N * 8
75    }
76
77    /// Returns the size in bytes of the bitset
78    #[inline]
79    pub const fn byte_len(&self) -> usize {
80        N
81    }
82
83    /// Counts bits to one in the current set
84    #[inline]
85    pub fn count_ones(&self) -> usize {
86        self.0.iter().map(|b| b.count_ones() as usize).sum()
87    }
88
89    /// Make the union of the current set with another one
90    #[inline]
91    pub fn union(&mut self, other: &Self) {
92        (0..self.0.len()).for_each(|i| self.0[i] |= other.0[i])
93    }
94
95    /// Make the intersection of the current set with another one
96    #[inline]
97    pub fn intersection(&mut self, other: &Self) {
98        (0..self.0.len()).for_each(|i| self.0[i] &= other.0[i])
99    }
100
101    /// Count bits to one in common between two sets
102    #[inline]
103    pub const fn count_ones_in_common(&self, other: &Self) -> usize {
104        let mut count = 0;
105        let mut i = 0;
106        loop {
107            if i == self.0.len() {
108                break;
109            }
110            count += (self.0[i] & other.0[i]).count_ones() as usize;
111            i += 1;
112        }
113        count
114    }
115
116    /// Counts bits to zero in the current set
117    #[inline]
118    pub fn count_zeros(&self) -> usize {
119        self.0.iter().map(|b| b.count_zeros() as usize).sum()
120    }
121
122    /// Returns the size in bytes of the bitset
123    #[inline]
124    pub const fn byte_size() -> usize {
125        N
126    }
127
128    /// Returns the size in bytes of the bitset
129    #[inline]
130    pub const fn bit_size() -> usize {
131        N * 8
132    }
133}
poppy_filters/bitset/array.rs

poppy_filters/bitset/
array.rs
