bmap 0.2.2

//! Container of bits adressable by an index.

use std::fmt;

pub mod err;

pub use err::Error;

/// Number of bits per slot in the bits vector.
const NUM_WORD_BITS: usize = std::mem::size_of::<usize>() * 8;


/// A compact list of bits.
pub struct CountedBitmap {
  bits: Vec<usize>,

  /// Number of bits in bit map.
  length: usize,

  /// Number of remaining bits.  This is functionally equivalent to "total
  /// number of zeroes in the container".
  remain: usize
}

impl fmt::Debug for CountedBitmap {
  fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
    let blocks: Vec<String> = self
      .iter_ones_block()
      .map(|(first, last)| {
        if first != last {
          format!("{}-{}", first, last)
        } else {
          format!("{}", first)
        }
      })
      .collect();
    let set_blocks = blocks.join(",");
    write!(
      f,
      "BMap {{ length: {}, remain: {}, [{}] }}",
      self.length, self.remain, set_blocks
    )
  }
}


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(())
  }

  /// Set a bit, where it is assumed that the caller has validated that the
  /// `idx` parameter is valid.
  ///
  /// ```
  /// use bmap::CountedBitmap;
  ///
  /// let mut bmap = CountedBitmap::new(4);
  /// unsafe { bmap.set_unchecked(2) };
  /// assert_eq!(bmap.is_set(2).unwrap(), true);
  /// ```
  ///
  /// # Safety
  /// The caller must ensure that `idx` is within bounds.
  #[inline]
  pub unsafe fn set_unchecked(&mut self, idx: usize) {
    let (iword, bitval) = self.get_bidx_unchecked(idx);
    let v = self.bits.get_unchecked_mut(iword);
    if *v & bitval == 0 {
      *v |= bitval;
      self.remain -= 1;
    }
  }

  /// 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);
  /// ```
  pub fn iter_zeroes(&self) -> BitValIter {
    BitValIter {
      bmap: self,
      idx: 0,
      set: false
    }
  }


  /// 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);
  /// ```
  pub fn iter_ones(&self) -> BitValIter {
    BitValIter {
      bmap: self,
      idx: 0,
      set: true
    }
  }


  /// 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 {
    BitBlocksIter {
      bmap: self,
      idx: 0,
      set: false
    }
  }


  /// 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 {
    BitBlocksIter {
      bmap: self,
      idx: 0,
      set: true
    }
  }
}


pub struct BitIter<'a> {
  bmap: &'a CountedBitmap,
  idx: usize
}

impl<'a> Iterator for BitIter<'a> {
  type Item = bool;
  fn next(&mut self) -> Option<Self::Item> {
    if self.idx < self.bmap.len() {
      let val = self.bmap.is_set_unchecked(self.idx);
      self.idx += 1;
      Some(val)
    } else {
      None
    }
  }
}

impl<'a> ExactSizeIterator for BitIter<'a> {
  fn len(&self) -> usize {
    self.bmap.len()
  }
}


pub struct BitValIter<'a> {
  bmap: &'a CountedBitmap,
  idx: usize,

  /// 'true' means search for 1's.  `false` means search for 0's.
  set: bool
}


impl<'a> Iterator for BitValIter<'a> {
  type Item = usize;
  fn next(&mut self) -> Option<Self::Item> {
    // ToDo: Can skip entire words
    while self.idx < self.bmap.length {
      let val = self.bmap.is_set_unchecked(self.idx);
      if self.set == val {
        let idx = self.idx;
        self.idx += 1;
        return Some(idx);
      } else {
        self.idx += 1;
        continue;
      }
    }
    None
  }
}

impl<'a> ExactSizeIterator for BitValIter<'a> {
  fn len(&self) -> usize {
    if self.set {
      // seaching for 1's
      self.bmap.length - self.bmap.remain
    } else {
      // seaching for 0's
      self.bmap.remain
    }
  }
}


pub struct BitBlocksIter<'a> {
  bmap: &'a CountedBitmap,
  idx: usize,

  /// 'true' means return blocks of 1's.  `false` means return blocks of for
  /// 0's.
  set: bool
}


impl<'a> Iterator for BitBlocksIter<'a> {
  type Item = (usize, usize);
  fn next(&mut self) -> Option<Self::Item> {
    while self.idx < self.bmap.length {
      // As long as the current bit is _not_ the one of interest, keep
      // increasing index and retrying.  If there are not more blocks of
      // interest the outer while loop will terminate.
      let val = self.bmap.is_set_unchecked(self.idx);
      if self.set != val {
        self.idx += 1;
        continue;
      }

      // If this point has been reached a range will be returned, because a bit
      // of interest has been encountered and it's within the range.

      let low = self.idx;
      self.idx += 1;

      // Keep scanning until either the end has been reached or wrong type of
      // bit is encountered.

      let high = loop {
        if self.idx < self.bmap.length {
          let val = self.bmap.is_set_unchecked(self.idx);
          if self.set == val {
            // Still within the same block -- keep going
            self.idx += 1;
            continue;
          } else {
            // Found uninteresting bit, so block has ended
            let idx = self.idx - 1;

            // No need to rescan this block next run
            self.idx += 1;
            break idx;
          }
        } else {
          // end -- return last valid index
          break self.idx - 1;
        }
      };


      return Some((low, high));
    }

    None
  }
}


/// Internals
impl CountedBitmap {
  /// Number of words in the bitmap.
  #[allow(dead_code)]
  fn word_count(&self) -> usize {
    self.bits.len()
  }

  /// Returns a two-tuple `(index, bitvalue)`.
  #[inline(always)]
  fn get_bidx(&self, idx: usize) -> Result<(usize, usize), Error> {
    if idx >= self.length {
      return Err(Error::OutOfBounds);
    }

    let t = self.get_bidx_unchecked(idx);

    Ok(t)
  }


  /// Returns a two-tuple `(index, bitvalue)`.
  #[inline(always)]
  fn get_bidx_unchecked(&self, idx: usize) -> (usize, usize) {
    // Don't worry about the division and modulo -- as long as NUM_WORD_BITS is
    // a power of two the compiler will generate raw bit operations rather than
    // actual division and modulo.

    let iword = idx / NUM_WORD_BITS;

    let ibit = idx % NUM_WORD_BITS;
    let bitval = 1 << ibit;

    (iword, bitval)
  }


  #[inline(always)]
  fn is_set_unchecked(&self, idx: usize) -> bool {
    let (iword, bitval) = self.get_bidx_unchecked(idx);
    let v = unsafe { self.bits.get_unchecked(iword) };
    v & bitval != 0
  }
}


#[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());
  }

  #[test]
  fn dbg_output0() {
    let bmap = CountedBitmap::new(3);
    let s = format!("{:?}", bmap);
    assert_eq!(s, "BMap { length: 3, remain: 3, [] }");
  }

  #[test]
  fn dbg_output1() {
    let mut bmap = CountedBitmap::new(3);
    bmap.set(1).unwrap();
    let s = format!("{:?}", bmap);
    assert_eq!(s, "BMap { length: 3, remain: 2, [1] }");
  }

  #[test]
  fn dbg_output2() {
    let mut bmap = CountedBitmap::new(5);
    bmap.set(1).unwrap();
    bmap.set(2).unwrap();
    let s = format!("{:?}", bmap);
    assert_eq!(s, "BMap { length: 5, remain: 3, [1-2] }");
  }

  #[test]
  fn dbg_output3() {
    let mut bmap = CountedBitmap::new(7);
    bmap.set(1).unwrap();
    bmap.set(2).unwrap();

    bmap.set(4).unwrap();
    bmap.set(5).unwrap();

    let s = format!("{:?}", bmap);
    assert_eq!(s, "BMap { length: 7, remain: 3, [1-2,4-5] }");
  }
}

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