bitset.rs

/// Trait for values that can be treted like bitsets.
pub trait BitSet {
    /// Exponent of the bitset size.
    type Exp: Unsigned;

    /// Size of the bitset.
    type Size: Unsigned;

    /// Exponent for bitset size.
    /// Bitset size is 2 ^ SIZE_EXP.b
    const SIZE_EXP: u32 = Self::Exp::U32;

    /// Size of the bitset.
    fn size() -> u64 {
        2u64.pow(Self::SIZE_EXP)
    }

    /// Check if bitset is empty.
    /// i.e. no bits are set.
    fn is_empty(&self) -> bool;

    /// Check if specified bit is set.
    ///
    /// # Safety
    ///
    /// `index` must be less than `size()`
    unsafe fn get(&self, index: u64) -> bool;

    /// Get set bit index at or after given index.
    ///
    /// # Safety
    ///
    /// `index` must be less than or equal to `size()`
    unsafe fn next(&self, index: u64) -> Option<u64>;
}


#[derive(Clone, Debug)]
#[cfg_attr(feature = "serde", serde::Serialize, serde::Deserialize)]
pub struct BitSetIndirect<M, T> {
    mask: M,
    indices: Vec<u16>,
    subsets: Vec<T>,
}

impl<M, T> Default for BitSetIndirect<M, T>
where
    M: Default,
{
    fn default() -> Self {
        BitSetIndirect {
            mask: M::default(),
            indices: Vec::new(),
            subsets: Vec::new(),
        }
    }
}

impl<M, T> BitSet for BitSetIndirect<M, T>
where
    M: BitSet,
    T: BitSet,
    M::Exp: IsLessOrEqual<U16, Output = B1>,
    M::Exp: std::ops::Add<T::Exp>,
    Sum<M::Exp, T::Exp>: Unsigned,
    M::Size: std::ops::Mul<T::Size>,
    Prod<M::Size, T::Size>: Unsigned,
{
    type Exp = Sum<M::Exp, T::Exp>;
    type Size = Prod<M::Size, T::Size>;

    fn is_empty(&self) -> bool {
        self.mask.is_empty()
    }

    unsafe fn get(&self, index: u64) -> bool {
        debug_assert!(index < Self::size());
        let x = index / T::size();
        let y = index % T::size();

        self.mask.get(x) && self.subsets[self.indices[x as usize] as usize].get(y)
    }

    unsafe fn next(&self, index: u64) -> Option<u64> {
        debug_assert!(index <= Self::size());
        let x = index / T::size();
        let y = index % T::size();

        if self.mask.get(x) {
            if let Some(ys) = self.subsets[self.indices[x as usize] as usize].next(y) {
                return Some(x * T::size() + ys);
            }
        }

        if let Some(xs) = self.mask.next(x + 1) {
            let ys = self.subsets[self.indices[xs as usize] as usize]
                .next(0)
                .expect("index least one bit must be set");

            Some(xs * T::size() + ys)
        } else {
            None
        }
    }
}