#[derive(Clone, PartialEq, Eq)]
pub struct BitSet {
    data: Vec<u32>,
    size: usize,
}

const BITS: usize = 32;

impl BitSet {
    pub fn new(size: usize) -> Self {
        Self {
            size,
            data: vec![0; size.div_ceil(32)],
        }
    }

    pub fn set(&mut self, bit: usize, val: bool) {
        assert!(bit < self.size);
        let idx = bit / BITS;
        let bit = bit % BITS;

        if val {
            self.data[idx] |= 1 << bit;
        } else {
            self.data[idx] &= !(1 << bit);
        }
    }

    pub fn get(&self, bit: usize) -> bool {
        assert!(bit < self.size);
        let idx = bit / BITS;
        let bit = bit % BITS;

        (self.data[idx] & (1 << bit)) != 0
    }

    pub fn set_all(&mut self, val: bool) {
        let val = if val { !0 } else { 0 };
        for d in self.data.iter_mut() {
            *d = val;
        }
    }
}

impl std::fmt::Debug for BitSet {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        for i in 0..self.size {
            if self.get(i) {
                write!(f, "1")?;
            } else {
                write!(f, "0")?;
            }
        }
        Ok(())
    }
}