growable_bitmap/

lib.rs

//! A crate providing a growable compact boolean array that can be
//! parameterized on its storage.
//!
//! See the `GrowableBitMap` type for more information.
//!
//! # TODO:
//!
//! This crate is not feature-complete at all. Below are some features I want
//! to add before marking it as `1.0`:
//!
//! - `BitOr` (with another `GrowableBitMap`).
//! - `BitOrAssign` (with another `GrowableBitMap`).
//! - `BitAnd` (with another `GrowableBitMap`).
//! - `BitAndAssign` (with another `GrowableBitMap`).
//! - `BitXor` (with another `GrowableBitMap`).
//! - `BitXorAssign` (with another `GrowableBitMap`).
//!
//! - When `const-generics` become available, possibly use them as storage ?
//!
//! - [Rust 1.48.0+ / Intra-doc links]: Use intra-doc links in documentation.
//!   Right now there are no links because they're painful to write once you've
//!   been introduced to the wonder intra-doc links are.
use std::fmt;

mod storage;
pub use storage::BitStorage;

/// A growable compact boolean array that can be parameterized on its storage.
///
/// Bits are stored contiguously. The first value is packed into the least
/// significant bits of the first word of the backing storage.
///
/// The storage must implement the unsafe trait `BitStorage`.
///
/// # Caveats
///
/// - The `GrowableBitMap::set_bit` method may allocate way too much memory
///   compared to what you really need (if for example, you only plan to set
///   the bits between 1200 and 1400). In this case, storing the offset of
///   1200 somewhere else and storing the values in the range `0..=200` in the
///   `GrowableBitMap` is probably the most efficient solution.
#[derive(Clone, Eq, PartialEq, Ord, PartialOrd, Hash)]
pub struct GrowableBitMap<S>
where
    S: BitStorage,
{
    // The storage for the bits.
    bits: Vec<S>,
}

impl<S> fmt::Debug for GrowableBitMap<S>
where
    S: BitStorage + fmt::Debug,
{
    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
        fmt.debug_list().entries(self.bits.iter()).finish()
    }
}

impl<S> GrowableBitMap<S>
where
    S: BitStorage,
{
    /// Creates a new, empty `GrowableBitMap`.
    ///
    /// This does not allocate anything.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use growable_bitmap::{GrowableBitMap, BitStorage};
    ///
    /// assert!(GrowableBitMap::<u8>::new().is_empty());
    /// ```
    pub fn new() -> Self {
        Self { bits: Vec::new() }
    }

    /// Constructs a new, empty `GrowableBitMap` with the specified capacity
    /// **in bits**.
    ///
    /// When `capacity` is zero, nothing is allocated.
    ///
    /// When `capacity` is not zero, the bit `capacity - 1` can be set without
    /// any other allocation and the returned `GrowableBitMap` is guaranteed
    /// to be able to hold `capacity` bits without reallocating (and maybe more
    /// if the given `capacity` is not a multiple of the number of bits in one
    /// instance of the backing storage).
    ///
    /// # Examples
    ///
    /// ```rust
    /// use growable_bitmap::{GrowableBitMap, BitStorage};
    ///
    /// let mut b = GrowableBitMap::<u16>::with_capacity(16);
    /// assert!(b.is_empty());
    /// assert_eq!(b.capacity(), 16);
    ///
    /// b.set_bit(15);
    /// assert_eq!(b.capacity(), 16);
    ///
    /// b.set_bit(17);
    /// assert!(b.capacity() >= 16);
    /// ```
    pub fn with_capacity(capacity: usize) -> Self {
        if capacity == 0 {
            return Self::new();
        }

        let div = capacity / S::BITS_IN_STORAGE;
        // Ensures the allocated capacity is enough for values like 125 with a
        // storage of `u8`:
        //
        // - `div` is 15
        // - `capacity % S::BITS_IN_STORAGE` is 5 so `rem` is 1.
        //
        // The final capacity will be 16 `u8`s -> 128 bits, enough for the
        // 125 bits asked for.
        let rem = (capacity % S::BITS_IN_STORAGE != 0) as usize;

        Self {
            bits: Vec::with_capacity(div + rem),
        }
    }

    /// `true` if the `GrowableBitMap` is empty.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use growable_bitmap::{GrowableBitMap, BitStorage};
    ///
    /// let mut b = GrowableBitMap::<u32>::new();
    /// assert!(b.is_empty());
    ///
    /// b.set_bit(25);
    /// assert!(!b.is_empty());
    /// ```
    pub fn is_empty(&self) -> bool {
        self.bits.is_empty() || self.bits.iter().all(|bits| bits.is_empty())
    }

    /// Gets the bit at the given index and returns `true` when it is set to 1,
    /// `false` when it is not.
    ///
    /// This will **not** panic if the index is out of range of the backing
    /// storage, only return `false`.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use growable_bitmap::{GrowableBitMap, BitStorage};
    ///
    /// let mut b = GrowableBitMap::<u64>::new();
    /// assert!(!b.get_bit(0));
    /// assert!(!b.get_bit(15));
    ///
    /// b.set_bit(15);
    /// assert!(!b.get_bit(0));
    /// assert!(b.get_bit(15));
    /// ```
    pub fn get_bit(&self, index: usize) -> bool {
        let bits_index = index / S::BITS_IN_STORAGE;

        // Since the bits_index does not exist in the storage, the bit at
        // `index` is logically 0.
        if self.bits.len() <= bits_index {
            return false;
        }

        let elem = &self.bits[bits_index];

        // SAFETY: we have ensure throught the steps above that the index
        // passed to `elem.set_bit` is in range of `0..S::BITS_IN_STORAGE`.
        //
        // Example with a `u8`:
        //
        // `u8::BITS_IN_STORAGE` is 8.
        // `index` is 21.
        //
        // `bits_index` = 2
        // `index - bits_index * S::BITS_IN_STORAGE` = 21 - 2 * 8 = 5 < 8
        unsafe { elem.get_bit(index - bits_index * S::BITS_IN_STORAGE) }
    }

    /// Sets the bit at the given index and returns whether the bit was set
    /// to 1 by this call or not.
    ///
    /// Note: This will grow the backing storage as needed to have enough
    /// storage for the given index. If you set the bit 12800 with a storage of
    /// `u8`s the backing storage will allocate 1600 `u8`s since
    /// `sizeof::<u8>() == 1` byte.
    ///
    /// See also the `Caveats` section on `GrowableBitMap`.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use growable_bitmap::{GrowableBitMap, BitStorage};
    ///
    /// let mut b = GrowableBitMap::<u128>::new();
    /// assert!(b.set_bit(0)); // Bit 0 was not set before, returns true.
    /// assert!(!b.set_bit(0)); // Bit 0 was already set, returns false.
    ///
    /// assert!(b.set_bit(255)); // The bitmap will grow as needed to set the bit.
    /// ```
    pub fn set_bit(&mut self, index: usize) -> bool {
        let bits_index = index / S::BITS_IN_STORAGE;

        // Ensure there are enough elements in the `bits` storage.
        if self.bits.len() <= bits_index {
            self.bits.resize_with(bits_index + 1, S::empty);
        }

        let elem = &mut self.bits[bits_index];

        // SAFETY: we have ensure throught the steps above that the index
        // passed to `elem.set_bit` is in range of `0..S::BITS_IN_STORAGE`.
        //
        // Example with a `u8`:
        //
        // `u8::BITS_IN_STORAGE` is 8.
        // `index` is 21.
        //
        // `bits_index` = 2
        // `index - bits_index * S::BITS_IN_STORAGE` = 21 - 2 * 8 = 5 < 8
        unsafe { elem.set_bit(index - bits_index * S::BITS_IN_STORAGE) }
    }

    /// Clears the bit at the given index and returns whether the bit was set
    /// to 0 by this call or not.
    ///
    /// Note: this function will never allocate nor free memory, even when
    /// the bit being cleared is the last 1 in the value at the end of the
    /// backing storage.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use growable_bitmap::{GrowableBitMap, BitStorage};
    ///
    /// let mut b = GrowableBitMap::<u8>::new();
    /// assert!(!b.clear_bit(3)); // Bit 0 was not set before, returns false.
    ///
    /// b.set_bit(3);
    /// assert!(b.clear_bit(3));
    /// ```
    ///
    /// Testing the effects on capacity:
    ///
    /// ```rust
    /// use growable_bitmap::{GrowableBitMap, BitStorage};
    ///
    /// let mut b = GrowableBitMap::<u8>::new();
    /// b.set_bit(125);
    ///
    /// let old_capa = b.capacity();
    /// b.clear_bit(125);
    /// assert_eq!(old_capa, b.capacity());
    /// ```
    pub fn clear_bit(&mut self, index: usize) -> bool {
        let bits_index = index / S::BITS_IN_STORAGE;

        // Since the bits_index does not exist in the storage, the bit at
        // `index` is logically 0.
        if self.bits.len() <= bits_index {
            return false;
        }

        let elem = &mut self.bits[bits_index];

        // SAFETY: we have ensure throught the steps above that the index
        // passed to `elem.set_bit` is in range of `0..S::BITS_IN_STORAGE`.
        //
        // Example with a `u8`:
        //
        // `u8::BITS_IN_STORAGE` is 8.
        // `index` is 21.
        //
        // `bits_index` = 2
        // `index - bits_index * S::BITS_IN_STORAGE` = 21 - 2 * 8 = 5 < 8
        unsafe { elem.clear_bit(index - bits_index * S::BITS_IN_STORAGE) }
    }

    /// Clears the bitmap, removing all values (setting them all to 0).
    ///
    /// This method has no effect on the allocated capacity of the bitmap.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use growable_bitmap::{GrowableBitMap, BitStorage};
    ///
    /// let mut b = GrowableBitMap::<u16>::new();
    /// b.set_bit(4);
    /// assert!(!b.is_empty());
    ///
    /// b.clear();
    /// assert!(b.is_empty());
    /// ```
    ///
    /// Testing the effects on capacity:
    ///
    /// ```rust
    /// use growable_bitmap::{GrowableBitMap, BitStorage};
    ///
    /// let mut b = GrowableBitMap::<u16>::new();
    /// b.set_bit(125);
    ///
    /// let old_capa = b.capacity();
    /// b.clear();
    /// assert_eq!(old_capa, b.capacity());
    /// ```
    pub fn clear(&mut self) {
        self.bits.clear();
    }

    /// Counts the number of bits that are set to 1 in the whole bitmap.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use growable_bitmap::{GrowableBitMap, BitStorage};
    ///
    /// let mut b = GrowableBitMap::<u32>::new();
    /// assert_eq!(b.count_ones(), 0);
    ///
    /// b.set_bit(2);
    /// assert_eq!(b.count_ones(), 1);
    ///
    /// b.set_bit(9);
    /// assert_eq!(b.count_ones(), 2);
    ///
    /// b.clear();
    /// assert_eq!(b.count_ones(), 0);
    /// ```
    pub fn count_ones(&self) -> usize {
        self.bits
            .iter()
            .map(|store| store.count_ones() as usize)
            .sum::<usize>()
    }

    /// Returns the number of bits the bitmap can hold without reallocating.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use growable_bitmap::{GrowableBitMap, BitStorage};
    ///
    /// let mut b = GrowableBitMap::<u64>::new();
    /// assert_eq!(b.capacity(), 0);
    ///
    /// b.set_bit(380);
    /// assert_eq!(b.capacity(), 384);
    /// ```
    pub fn capacity(&self) -> usize {
        self.bits.capacity() * S::BITS_IN_STORAGE
    }

    /// Shrinks the capacity of the `GrowableBitMap` as much as possible.
    ///
    /// It will drop down as close as possible to the length needed to store
    /// the last bit set to 1 and not more but the allocator may still inform
    /// the bitmap that there is space for a few more elements.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use growable_bitmap::{GrowableBitMap, BitStorage};
    ///
    /// let mut b = GrowableBitMap::<u128>::with_capacity(381);
    ///
    /// b.set_bit(127);
    /// b.set_bit(380);
    /// assert_eq!(b.capacity(), 384);
    ///
    /// b.clear_bit(380);
    /// b.shrink_to_fit();
    /// assert_eq!(b.capacity(), 128);
    /// ```
    pub fn shrink_to_fit(&mut self) {
        // Ignoring the values at the end that are 0.
        let last_set_bit_index = self
            .bits
            .iter()
            .rev()
            .skip_while(|&store| store.is_empty())
            .count();

        self.bits.truncate(last_set_bit_index);
        self.bits.shrink_to_fit();
    }
}

macro_rules! growable_bitmap_storage_integer_tests {
    ($(($int: ty, $mod_name: ident))*) => {
        $(
            #[cfg(test)]
            mod $mod_name {
                use super::*;

                #[test]
                fn new() {
                    let bm = GrowableBitMap::<$int>::new();
                    let bm2 = GrowableBitMap {
                        bits: Vec::<$int>::new(),
                    };

                    assert_eq!(bm, bm2);
                }

                #[test]
                fn with_capacity() {
                    let bm = GrowableBitMap::<$int>::with_capacity(0);
                    let vec = Vec::<$int>::with_capacity(0);
                    assert_eq!(bm.bits.capacity(), vec.capacity());

                    let bm = GrowableBitMap::<$int>::with_capacity(11);
                    let vec = Vec::<$int>::with_capacity(11);
                    assert!(bm.bits.capacity() >= vec.capacity() / <$int>::BITS_IN_STORAGE);
                }

                #[test]
                fn is_empty() {
                    let bm = GrowableBitMap::<$int>::new();
                    assert!(bm.is_empty());

                    let mut bm = GrowableBitMap::<$int>::with_capacity(3);
                    assert!(bm.is_empty());

                    bm.set_bit(7);
                    assert!(!bm.is_empty());

                    bm.clear_bit(7);
                    assert!(bm.is_empty());

                    bm.set_bit(7);
                    bm.set_bit(3);
                    bm.set_bit(4);
                    assert!(!bm.is_empty());

                    bm.clear();
                    assert!(bm.is_empty());
                }

                #[test]
                fn get_bit() {
                    let bm = GrowableBitMap::<$int>::new();

                    assert!(!bm.get_bit(0));
                    assert!(!bm.get_bit(7));

                    // Ensuring `get_bit` does not allocate.
                    let old_capa = bm.capacity();
                    assert!(!bm.get_bit(200000003));
                    assert_eq!(old_capa, bm.capacity());

                    let mut bm = bm;
                    bm.set_bit(0);
                    bm.set_bit(6);

                    assert!(bm.get_bit(0));
                    assert!(bm.get_bit(6));

                    // Still false.
                    assert!(!bm.get_bit(7));
                    assert!(!bm.get_bit(3));
                }

                #[test]
                fn set_bit() {
                    let mut bm = GrowableBitMap::<$int>::new();

                    assert!(bm.set_bit(0));
                    assert!(bm.set_bit(7));

                    assert!(!bm.set_bit(0));

                    // Ensuring `set_bit` does allocate when necessary.
                    let old_capa = bm.capacity();
                    assert!(bm.set_bit(150));
                    assert!(old_capa <= bm.capacity());
                    assert!(bm.get_bit(150));
                }

                #[test]
                fn clear_bit() {
                    let mut bm = GrowableBitMap::<$int>::new();

                    assert!(!bm.clear_bit(0));
                    assert!(!bm.clear_bit(7));

                    bm.set_bit(0);
                    assert!(bm.clear_bit(0));

                    // Ensuring `clear_bit` does not allocate nor free.
                    let old_capa = bm.capacity();
                    assert!(!bm.clear_bit(200000003));
                    assert_eq!(old_capa, bm.capacity());

                    bm.set_bit(150);
                    assert!(bm.clear_bit(150));

                    assert!(bm.is_empty());
                }

                #[test]
                fn clear() {
                    let mut bm = GrowableBitMap::<$int>::new();

                    bm.clear();
                    assert!(bm.is_empty());

                    bm.set_bit(253);
                    // Ensuring `clear_bit` does not allocate nor free.
                    let old_capa = bm.capacity();
                    bm.clear();
                    assert_eq!(old_capa, bm.capacity());

                    bm.set_bit(30);
                    bm.set_bit(4);

                    bm.clear();
                    assert!(bm.is_empty());
               }

                #[test]
                fn count_ones() {
                    let mut bm = GrowableBitMap::<$int>::new();
                    assert_eq!(bm.count_ones(), 0);

                    bm.set_bit(0);
                    assert_eq!(bm.count_ones(), 1);

                    bm.set_bit(30);
                    assert_eq!(bm.count_ones(), 2);

                    bm.set_bit(7);
                    assert_eq!(bm.count_ones(), 3);

                    bm.clear_bit(0);
                    assert_eq!(bm.count_ones(), 2);

                    bm.clear();
                    assert_eq!(bm.count_ones(), 0);
                }

                #[test]
                fn capacity() {
                    let mut bm = GrowableBitMap::<$int>::new();
                    assert_eq!(bm.capacity(), 0);

                    bm.set_bit(511);
                    assert_eq!(bm.capacity(), 512);
                }

                #[test]
                fn shrink_to_fit() {
                    let mut bm = GrowableBitMap::<$int>::with_capacity(381);
                    bm.set_bit(127);
                    bm.set_bit(380);
                    assert_eq!(bm.capacity(), 384);

                    bm.clear_bit(380);
                    bm.shrink_to_fit();
                    assert_eq!(bm.capacity(), 128);
                }
            }
         )*
    }
}

growable_bitmap_storage_integer_tests! {
    (u8, test_u8)
    (u16, test_u16)
    (u32, test_u32)
    (u64, test_u64)
    (u128, test_u128)
}