compact_bitset 0.1.3

//! A type for storing fixed-size boolean arrays densely to optimize space
//!
//! Inspired by C++'s std::vector<bool> implementation
//!
//! # Overview
//!
//! `compact_bitset` adds a new container type, [`CompactBitset`]. A `CompactBitset`
//! stores boolean variables so that one bit is used per `bool`. It is designed for cases
//! where a boolean array is necessary, but `Vec<bool>` or a slice is undesired due to
//! space requirements. The `CompactBitset` reduces size used per `bool` to an eighth of
//! what it would otherwise be.
//!
//! # Details
//!
//! `CompactBitset` uses the proxy types `BitRef` and `BitRefMut` for indexing operations.
//!
//! These two types deref to `bool` and implement comparison to `bool` as well as each other.
//!
//! Writing to a `BitRefMut` alters the bit that it symbolically references in the `CompactBitset`.
//!
//! `BitRef` and `BitRefMut` contain references to their parent `CompactBitset`. Thus, any number of
//! `BitRef`s can be borrowed from a `CompactBitset`, but only 1 `BitRefMut` may be active at a time.
//! This allows `BitRef` and `BitRefMut` to take advantage of the safety guarantees of references.
//!
//! `BitIter` allows the user to immutably iterate the `CompactBitset` via a wrapper around a `BitRef`
//! with its index incremented. It contains all standard `Iterator` functionality.
//!
//! `BitIterMut` may be on the roadmap, but a current implementation has not successfully been created
//! without use of `unsafe`.

use std::{fmt::Debug, mem::size_of};

mod bitref;
use bitref::{BitRef, BitRefMut};

pub mod bititer;
pub use bititer::*;

use num_traits::{PrimInt, Unsigned};

/// A fixed-size bitset that has a storage density of 1 bit to 1 `bool`.
///
/// `CompactBitset`'s data is implemented through unsigned integers, and uses their bits to
/// store its data.
///
/// The type parameter `T` is the unsigned type which `CompactBitset` uses to store its data.
///
/// `CompactBitset`'s indexing is implemented through the proxy types `BitRef` and `BitRefMut` that
/// simulate indexing into a single bit.
///
/// # Example
/// ```
/// use compact_bitset::CompactBitset;
///
/// let mut bitset = CompactBitset::<u8>::new();
/// assert_eq!(bitset.at(0), false);
/// bitset.at_mut(3).set(true);
/// assert_eq!(bitset.at(3), true);
/// ```

#[derive(Default)]
pub struct CompactBitset<T: PrimInt + Unsigned> {
    data: T,
}

impl<'parent, T: PrimInt + Unsigned> CompactBitset<T> {
    /// The length and number of bits in the set.
    pub const BITS: usize = size_of::<T>() * 8;

    /// Creates a new empty bitset.
    pub fn new() -> Self {
        Self {
            data: T::from(0).unwrap(),
        }
    }

    /// Creates a new bitset initialized with a slice.
    /// Once const_evaluatable_checked is stabilized, the length of the array will be specified as
    /// the associated const `BITS`, however, for now this is not possible on stable, so
    /// `N` will need to be verified at runtime.
    pub fn from_slice<const N: usize>(slice: [bool; N]) -> Self {
        assert_eq!(
            N,
            Self::BITS,
            "Slice and bitset are different sizes: expected slice of length {}, got {}",
            Self::BITS,
            N
        );
        let mut bitset = Self::new();
        for (idx, item) in slice.iter().enumerate() {
            bitset.at_mut(idx).set(*item);
        }
        bitset
    }

    pub fn iter<'this>(&'this self) -> BitIter<'this, T> {
        BitIter { bitref: self.at(0) }
    }

    pub fn to_vec(&self) -> Vec<bool> {
        self.iter().collect()
    }

    /// Returns the length of the bitset.
    pub const fn len(&self) -> usize {
        Self::BITS
    }

    /// Returns a `BitRef` that symbolically references the bit at `index`.
    /// The `BitRef` has the lifetime of `&self`.
    pub fn at<'this>(&'this self, index: usize) -> BitRef<'this, T> {
        assert!(index < Self::BITS);
        BitRef::<'this, T> {
            parent: self,
            idx: index,
        }
    }

    /// Returns a `BitRefMut` that symbolically mutably references the bit at `index`.
    /// The `BitRefMut` has the lifetime of `&mut self`.
    pub fn at_mut<'this>(&'this mut self, index: usize) -> BitRefMut<'this, T> {
        assert!(index < Self::BITS);
        BitRefMut::<'this, T> {
            parent: self,
            idx: index,
        }
    }

    /// Sets the bit at the index to the value.
    /// Shortcuts the pattern `set.at_mut.set(value)`.
    pub fn set_at(&mut self, index: usize, value: bool) {
        self.at_mut(index).set(value);
    }
}

impl<T: PrimInt + Unsigned> PartialEq for CompactBitset<T> {
    #[inline(always)]
    fn eq(&self, other: &Self) -> bool {
        self.data == other.data
    }
}

impl<T: PrimInt + Unsigned> Debug for CompactBitset<T> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        let mut string = String::new();
        for item in self.iter() {
            string.push_str(format!("{}, ", *item).as_str());
        }
        string.remove(string.len() - 1);
        string.remove(string.len() - 1);
        write!(f, "CompactBitset([{string}])")
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn creation() {
        let bitset = CompactBitset::<u8>::new();
        assert_eq!(bitset.at(0), false);
    }

    #[test]
    fn alteration() {
        let mut bitset = CompactBitset::<u8>::new();
        bitset.at_mut(3).set(true);
        println!("set at 3:");
        assert_eq!(*bitset.at(3), true);
    }

    #[test]
    #[should_panic]
    fn out_of_bounds() {
        let mut bitset = CompactBitset::<u16>::new();
        bitset.at_mut(16).set(true);
    }

    #[test]
    fn stored_bitref() {
        let mut bitset = CompactBitset::<u32>::new();
        bitset.at_mut(2).set(true);
        assert_eq!(bitset.at(2), true);
    }

    #[test]
    fn iter_zip_map() {
        let alternating =
            CompactBitset::<u8>::from_slice([true, false, true, false, true, false, true, false]);
        let alternating_double =
            CompactBitset::<u8>::from_slice([true, true, false, false, true, true, false, false]);
        let anded: CompactBitset<u8> = alternating
            .iter()
            .zip(alternating_double.iter())
            .map(|(a, b)| *a & *b)
            .collect();
        assert_eq!(
            anded,
            CompactBitset::<u8>::from_slice([true, false, false, false, true, false, false, false])
        );
    }

    #[test]
    fn iter_next() {
        let alternating =
            CompactBitset::<u8>::from_slice([true, false, true, false, true, false, true, false]);
        let mut iter = alternating.iter().enumerate();
        let mut final_i = 0;
        while let Some((i, b)) = iter.next() {
            //b is true on the even indices
            assert_eq!(b, (i % 2) == 0);
            final_i = i;
        }
        assert_eq!(final_i, alternating.len() - 1);
        assert!(iter.next().is_none());
        assert!(iter.next().is_none());
    }
}