#[derive(Debug, Clone, Copy)]
pub struct BitSet<const N: usize> {
words: [u128; N],
}
impl<const N: usize> Default for BitSet<N> {
fn default() -> Self {
Self::new()
}
}
impl<const N: usize> BitSet<N> {
pub const fn new() -> Self {
Self { words: [0; N] }
}
const fn word_at(&self, bit: usize) -> &u128 {
&self.words[bit / u128::BITS as usize]
}
const fn word_at_mut(&mut self, bit: usize) -> &mut u128 {
&mut self.words[bit / u128::BITS as usize]
}
const fn bit_word(&self, bit: usize) -> u128 {
1 << (bit % u128::BITS as usize)
}
pub const fn add(&mut self, bit: usize) {
*self.word_at_mut(bit) |= self.bit_word(bit);
}
pub const fn remove(&mut self, bit: usize) {
*self.word_at_mut(bit) &= !self.bit_word(bit);
}
pub const fn contains(&self, bit: usize) -> bool {
(*self.word_at(bit) & self.bit_word(bit)) != 0
}
pub const fn union(&mut self, other: BitSet<N>) {
let mut i = 0;
while i < N {
self.words[i] |= other.words[i];
i += 1;
}
}
}
#[cfg(test)]
mod test {
use super::BitSet;
#[test]
fn test() {
let mut set = BitSet::<2>::new();
set.add(0);
set.add(1);
set.add(10);
set.add(20);
set.add(30);
set.add(60);
set.add(100);
set.add(200);
set.add(255);
assert!(set.contains(0));
assert!(set.contains(1));
assert!(set.contains(10));
assert!(set.contains(20));
assert!(set.contains(30));
assert!(set.contains(60));
assert!(set.contains(100));
assert!(set.contains(200));
assert!(set.contains(255));
assert!(!set.contains(2));
assert!(!set.contains(3));
assert!(!set.contains(11));
assert!(!set.contains(21));
assert!(!set.contains(31));
assert!(!set.contains(61));
assert!(!set.contains(101));
assert!(!set.contains(201));
assert!(!set.contains(254));
assert!(!set.contains(32));
assert!(!set.contains(64));
assert!(!set.contains(128));
}
}