Cargo.toml
README.md
www/index.md
www/changelog.md
src/err.rs
src/lib.rs

[package]
name = "bmap"
version = "0.2.0"
edition = "2021"
license = "0BSD"
# https://crates.io/category_slugs
categories = [ "data-structures" ]
keywords = [ "bitmap", "bitvec" ]
repository = "https://repos.qrnch.tech/pub/bmap"
description = "A bitmap with an internal counter."
exclude = [
  ".fossil-settings",
  "www",
  ".efiles",
  ".fslckout",
  "rustfmt.toml"
]

# https://doc.rust-lang.org/cargo/reference/manifest.html#the-badges-section
[badges]
maintenance = { status = "passively-maintained" }

[dependencies]

use std::fmt;

#[derive(Debug)]
pub enum Error {
  OutOfBounds
}

impl std::error::Error for Error {}

impl fmt::Display for Error {
  fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
    match self {
      Error::OutOfBounds => {
        write!(f, "Out of bounds")
      }
    }
  }
}

}


impl CountedBitmap {
  /// Create a new bit vector which can hold `bitcount` number of bits.
  ///
  /// All bits will be initialized to `0`.
  pub fn new(bitcount: usize) -> Self {
    let align = NUM_WORD_BITS; // number of bits in bitvec slot
    let num = bitcount;
    let len = (num + align - 1) / align;

    let bits = vec![0; len];

    Self {
      bits,
      length: bitcount,
      remain: bitcount

    }
  }

  /// Return the number of bits in bitmap.
  ///
  /// ```
  /// use bmap::CountedBitmap;
  ///
  /// let bmap = CountedBitmap::new(42);
  /// assert_eq!(bmap.len(), 42);
  /// ```
  #[inline(always)]
  pub fn len(&self) -> usize {
    self.length
  }
  /// Returns true if no bits have been set.
  ///
  /// ```
  /// use bmap::CountedBitmap;
  ///
  /// let mut bmap = CountedBitmap::new(42);
  /// assert!(bmap.is_empty());
  ///
  /// bmap.set(11);
  /// assert!(!bmap.is_empty());
  ///
  /// // Special case -- a zero-length bitmap is considered to be empty
  /// let bmap = CountedBitmap::new(0);
  /// assert!(bmap.is_empty());
  /// ```
  pub fn is_empty(&self) -> bool {
    self.remain == self.length
  }

  /// Return number of bits that have not been set.  (I.e. number of bits
  /// remaining to be set).
  ///
  /// ```
  /// use bmap::CountedBitmap;
  ///
  /// let mut bmap = CountedBitmap::new(4);
  /// assert_eq!(bmap.remain(), 4);
  /// bmap.set(1);
  /// assert_eq!(bmap.remain(), 3);
  /// ```
  #[inline(always)]
  pub fn remain(&self) -> usize {
    self.remain
  }


  /// Return how many many bits are set to 1 in relative terms.  The returned
  /// value will be a value between 0.0 and 1.0 (inclusive-inclusive).  For a
  /// 0-length bit vector the value 1.0 will be returned.
  pub fn progress(&self) -> f64 {
    if self.is_empty() {
      1.0
    } else {
      let done = (self.length - self.remain) as f64;
      done / self.len() as f64
    }
  }


  /// Return a boolean indicating whether all bits have been set.
  ///
  /// ```
  /// use bmap::CountedBitmap;
  ///
  /// let mut bmap = CountedBitmap::new(2);
  /// assert!(bmap.is_finished() == false);
  /// bmap.set(0);
  /// assert!(bmap.is_finished() == false);
  /// bmap.set(1);
  /// assert!(bmap.is_finished() == true);
  ///
  /// // Special case: zero-length bitmap is always finished.
  /// let mut bmap = CountedBitmap::new(0);
  /// assert!(bmap.is_finished() == true);
  /// ```
  #[inline(always)]
  pub fn is_finished(&self) -> bool {
    self.remain == 0
  }


  /// Given a bit index, return `true` is the corresponding bit is set.  Return
  /// `false` otherwise.
  ///
  /// ```
  /// use bmap::CountedBitmap;
  ///
  /// let mut bmap = CountedBitmap::new(2);
  /// assert_eq!(bmap.is_set(0).unwrap(), false);
  /// bmap.set(0).unwrap();
  /// assert_eq!(bmap.is_set(0).unwrap(), true);
  /// ```
  #[inline(always)]
  pub fn is_set(&self, idx: usize) -> Result<bool, Error> {
    let (iword, bitval) = self.get_bidx(idx)?;

    // SAFETY: The index has been validated already.
    let v = unsafe { self.bits.get_unchecked(iword) };

    Ok(v & bitval != 0)
  }


  /// Set a bit.
  ///
  /// ```
  /// use bmap::CountedBitmap;
  ///
  /// let mut bmap = CountedBitmap::new(4);
  /// bmap.set(2).unwrap();
  /// ```
  #[inline(always)]
  pub fn set(&mut self, idx: usize) -> Result<(), Error> {
    let (iword, bitval) = self.get_bidx(idx)?;

    // SAFETY: The index has been validated already.
    let v = unsafe { self.bits.get_unchecked_mut(iword) };
    if *v & bitval == 0 {
      *v |= bitval;
      self.remain -= 1;
    }
    Ok(())
  }


  /// Clear a bit.
  ///
  /// ```
  /// use bmap::CountedBitmap;
  ///
  /// let mut bmap = CountedBitmap::new(4);
  /// bmap.set(2).unwrap();
  /// assert_eq!(bmap.is_set(2).unwrap(), true);
  /// bmap.unset(2).unwrap();
  /// assert_eq!(bmap.is_set(2).unwrap(), false);
  /// ```
  #[inline(always)]
  pub fn unset(&mut self, idx: usize) -> Result<(), Error> {
    let (iword, bitval) = self.get_bidx(idx)?;

    // SAFETY: The index has been validated already.
    let v = unsafe { self.bits.get_unchecked_mut(iword) };
    if *v & bitval != 0 {
      *v &= !bitval;
      self.remain += 1;
    }
    Ok(())
  }


  /// Clear the bitmap.
  ///
  /// Sets all bits to zero and resets the remaining counter.
  pub fn clear(&mut self) {
    self.bits.as_mut_slice().fill(0);
    self.remain = self.length;
  }


  /// If bit at the specified index is not set, then call closure.  If closure
  /// returns `true` then set bit.
  ///
  /// ```
  /// use bmap::CountedBitmap;
  ///
  /// let mut bmap = CountedBitmap::new(1);
  /// let mut set_to_true = false;
  /// let ret = bmap
  ///   .cond_set(0, || {
  ///     set_to_true = true;
  ///     true
  ///   })
  ///   .unwrap();
  /// assert_eq!(ret, true);
  /// assert_eq!(bmap.is_finished(), true);
  /// assert_eq!(set_to_true, true);
  /// ```
  pub fn cond_set<F>(&mut self, idx: usize, mut f: F) -> Result<bool, Error>
  where
    F: FnMut() -> bool
  {
    let (iword, bitval) = self.get_bidx(idx)?;

    // SAFETY: The index has already been validated.
    let v = unsafe { self.bits.get_unchecked_mut(iword) };
    if *v & bitval == 0 && f() {

      *v |= bitval;
      self.remain -= 1;
      Ok(true)
    } else {

      Ok(false)
    }
  }
}


/// Iterators.
impl CountedBitmap {
  /// Return an iterator that returns each of the container's bit values as
  /// booleans.
  ///
  /// ```
  /// use bmap::CountedBitmap;
  /// let mut bmap = CountedBitmap::new(4);
  /// bmap.set(1).unwrap();
  /// bmap.set(2).unwrap();
  /// let mut it = bmap.iter().enumerate();
  /// assert_eq!(it.next(), Some((0, false)));
  /// assert_eq!(it.next(), Some((1, true)));
  /// assert_eq!(it.next(), Some((2, true)));
  /// assert_eq!(it.next(), Some((3, false)));
  /// assert_eq!(it.next(), None);
  /// ```
  pub fn iter(&self) -> BitIter {
    BitIter { bmap: self, idx: 0 }
  }


  /// Create an iterator that will return the indexes of all zeroes in the bit
  /// map.
  ///
  /// ```
  /// use bmap::CountedBitmap;
  /// let mut bmap = CountedBitmap::new(4);
  /// bmap.set(1).unwrap();
  /// bmap.set(2).unwrap();
  /// let mut it = bmap.iter_zeroes();
  /// assert_eq!(it.next(), Some(0));
  /// assert_eq!(it.next(), Some(3));
  /// assert_eq!(it.next(), None);
  /// ```

  /// Create an iterator that will return the indexes of all ones in the bit
  /// map.
  ///
  /// ```
  /// use bmap::CountedBitmap;
  /// let mut bmap = CountedBitmap::new(4);
  /// bmap.set(1).unwrap();
  /// bmap.set(2).unwrap();
  /// let mut it = bmap.iter_ones();
  /// assert_eq!(it.next(), Some(1));
  /// assert_eq!(it.next(), Some(2));
  /// assert_eq!(it.next(), None);
  /// ```

  /// Create an iterator that will return index ranges of contiguous blocks of
  /// zeroes.
  ///
  /// ```
  /// use bmap::CountedBitmap;
  /// let mut bmap = CountedBitmap::new(4);
  /// bmap.set(0).unwrap();
  /// bmap.set(1).unwrap();
  /// let mut it = bmap.iter_zeroes_block();
  /// assert_eq!(it.next(), Some((2, 3)));
  /// assert_eq!(it.next(), None);
  /// ```
  pub fn iter_zeroes_block(&self) -> BitBlocksIter {

  /// Create an iterator that will return index ranges of contiguous blocks of
  /// ones.
  ///
  ///
  /// ```
  /// use bmap::CountedBitmap;
  /// let mut bmap = CountedBitmap::new(4);
  /// bmap.set(0).unwrap();
  /// bmap.set(1).unwrap();
  /// let mut it = bmap.iter_ones_block();
  /// assert_eq!(it.next(), Some((0, 1)));
  /// assert_eq!(it.next(), None);
  /// ```
  pub fn iter_ones_block(&self) -> BitBlocksIter {

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

  #[test]
  fn size() {
    let bmap = CountedBitmap::new(0);
    assert_eq!(bmap.len(), 0);
    assert_eq!(bmap.word_count(), 0);

    let bmap = CountedBitmap::new(1);
    assert_eq!(bmap.len(), 1);
    assert_eq!(bmap.word_count(), 1);

    let idx = NUM_WORD_BITS - 1;
    let bmap = CountedBitmap::new(idx);
    assert_eq!(bmap.len(), idx);
    assert_eq!(bmap.word_count(), 1);

    let bmap = CountedBitmap::new(NUM_WORD_BITS);
    assert_eq!(bmap.len(), NUM_WORD_BITS);
    assert_eq!(bmap.word_count(), 1);

    let idx = NUM_WORD_BITS + 1;
    let bmap = CountedBitmap::new(idx);
    assert_eq!(bmap.len(), idx);
    assert_eq!(bmap.word_count(), 2);
  }

  #[test]
  fn finished() {
    let bmap = CountedBitmap::new(0);
    assert!(bmap.is_finished());

    let mut bmap = CountedBitmap::new(1);
    assert!(!bmap.is_finished());
    bmap.set(0).unwrap();
    assert!(bmap.is_finished());
  }
}

// vim: set ft=rust et sw=2 ts=2 sts=2 cinoptions=2 tw=79 :

# Change Log

⚠️  indicates a breaking change.

## [Unreleased]

[Details](/vdiff?from=bmap-0.1.0&to=trunk)

### Added

- `CountedBitmap::is_empty()` returns `true` is no bits have been set in the
  bit map. 

### Changed

- ⚠️ `CountedBitmap::new()` made infallible.

### Removed

---

## [0.1.0]

Initial release.

# CountedBitmap

`bmap::CountedBitmap` is an array of bits, with methods to set/clear bits by
index, and a built-in counter used to keep track of how many bits have been
set.

This crate has a very specific use case.  You are *probably* looking for the
[bitvec](https://crates.io/crates/bitvec) crate.


## Change log

The details of changes can always be found in the timeline, but for a
high-level view of changes between released versions there's a manually
maintained [Change Log](./changelog.md).