regexsolver 1.0.0

#[derive(Clone, PartialEq, Eq, Debug, Hash)]
pub struct FastBitVec {
    bits: Vec<u64>,
    n: usize,
}

impl std::fmt::Display for FastBitVec {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        for i in 0..self.n {
            let bit = if self.get(i) { 1 } else { 0 };
            write!(f, "{bit}")?;
        }
        Ok(())
    }
}

impl FastBitVec {
    #[inline]
    pub fn from_elem(n: usize, bit: bool) -> Self {
        let nblocks = if n.is_multiple_of(64) {
            n / 64
        } else {
            n / 64 + 1
        };
        let bits = vec![if bit { !0_u64 } else { 0_u64 }; nblocks];
        let mut bit_vec = FastBitVec { bits, n };
        bit_vec.fix_last_block();
        bit_vec
    }

    fn fix_last_block(&mut self) {
        if let Some((last_block, used_bits)) = self.last_block_mut_with_mask() {
            *last_block &= used_bits;
        }
    }

    #[inline]
    fn last_block_mut_with_mask(&mut self) -> Option<(&mut u64, u64)> {
        let extra_bits = self.len() % 64;
        if extra_bits > 0 {
            let mask = (1 << extra_bits) - 1;
            let storage_len = self.bits.len();
            Some((&mut self.bits[storage_len - 1], mask))
        } else {
            None
        }
    }

    #[inline]
    pub fn len(&self) -> usize {
        self.n
    }

    #[inline]
    pub fn get(&self, i: usize) -> bool {
        assert!(i < self.n, "The provided bit index is out of bound.");
        let w = i / 64;
        let b = i % 64;
        (self.bits[w] & (1 << b)) != 0
    }

    #[inline]
    pub fn set(&mut self, i: usize, x: bool) {
        assert!(i < self.n, "The provided bit index is out of bound.");
        let w = i / 64;
        let b = i % 64;
        let flag = 1 << b;
        let val = if x {
            self.bits[w] | flag
        } else {
            self.bits[w] & !flag
        };
        self.bits[w] = val;
    }

    #[inline]
    pub fn complement(&mut self) {
        for w in &mut self.bits {
            *w = !*w;
        }
        self.fix_last_block();
    }

    /// The binary operations combine blocks pairwise with `zip`, which would
    /// silently truncate to the shorter operand if two bitvectors built over
    /// different spanning sets were ever combined, producing a wrong
    /// language instead of a loud failure. Catch that in debug builds (and
    /// therefore in every test run).
    #[inline]
    fn assert_same_len(&self, other: &Self) {
        debug_assert_eq!(
            self.n, other.n,
            "conditions built over different spanning sets cannot be combined"
        );
    }

    #[inline]
    pub fn union(&mut self, other: &Self) {
        self.assert_same_len(other);
        for (a, b) in self.bits.iter_mut().zip(&other.bits) {
            let w = *a | b;
            *a = w;
        }
    }

    #[inline]
    pub fn intersection(&mut self, other: &Self) {
        self.assert_same_len(other);
        for (a, b) in self.bits.iter_mut().zip(&other.bits) {
            let w = *a & b;
            *a = w;
        }
    }

    #[inline]
    pub fn difference(&mut self, other: &Self) {
        self.assert_same_len(other);
        for (a, b) in self.bits.iter_mut().zip(&other.bits) {
            *a &= !b;
        }
    }

    #[inline]
    pub fn has_intersection(&self, other: &Self) -> bool {
        self.assert_same_len(other);
        for (a, b) in self.bits.iter().zip(&other.bits) {
            if *a & b != 0 {
                return true;
            }
        }
        false
    }

    #[inline]
    pub fn empty(&self) -> bool {
        self.bits.iter().all(|w| w == &0)
    }

    #[inline]
    pub fn total(&self) -> bool {
        let mut last_word = !0;
        self.bits.iter().all(|elem| {
            let tmp = last_word;
            last_word = *elem;
            tmp == !0
        }) && (last_word == Self::mask_for_bits(self.n))
    }

    fn mask_for_bits(bits: usize) -> u64 {
        (!0) >> ((64 - bits % 64) % 64)
    }

    pub fn bits(&self) -> Vec<bool> {
        let mut bits = Vec::with_capacity(self.n);
        for i in 0..self.n {
            bits.push(self.get(i));
        }
        bits
    }

    /// Iterates the indices of the set bits in ascending order, word-wise
    /// (no allocation).
    #[inline]
    pub fn iter_set_bits(&self) -> impl Iterator<Item = usize> + '_ {
        self.bits
            .iter()
            .enumerate()
            .flat_map(|(word_index, &word)| {
                let mut remaining = word;
                std::iter::from_fn(move || {
                    if remaining == 0 {
                        None
                    } else {
                        let bit = remaining.trailing_zeros() as usize;
                        remaining &= remaining - 1;
                        Some(word_index * 64 + bit)
                    }
                })
            })
    }
}