Index: .efiles ================================================================== --- .efiles +++ .efiles @@ -1,5 +1,6 @@ Cargo.toml README.md +www/index.md +www/changelog.md src/err.rs src/lib.rs -www/index.md Index: Cargo.toml ================================================================== --- Cargo.toml +++ Cargo.toml @@ -1,10 +1,11 @@ [package] name = "bmap" -version = "0.1.0" +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 = [ @@ -12,8 +13,12 @@ "www", ".efiles", ".fslckout", "rustfmt.toml" ] + +# https://doc.rust-lang.org/cargo/reference/manifest.html#the-badges-section +[badges] +maintenance = { status = "passively-maintained" } [dependencies] Index: src/err.rs ================================================================== --- src/err.rs +++ src/err.rs @@ -7,11 +7,11 @@ impl std::error::Error for Error {} impl fmt::Display for Error { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { - match &*self { + match self { Error::OutOfBounds => { write!(f, "Out of bounds") } } } Index: src/lib.rs ================================================================== --- src/lib.rs +++ src/lib.rs @@ -23,89 +23,110 @@ 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) -> Result { + 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 mut bits = Vec::with_capacity(len); - bits.resize(len, 0); - Ok(Self { + 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).unwrap(); + /// + /// 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).unwrap(); + /// + /// 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.len() == 0 { + 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).unwrap(); + /// + /// 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).unwrap(); + /// + /// 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)] @@ -116,16 +137,16 @@ let v = unsafe { self.bits.get_unchecked(iword) }; Ok(v & bitval != 0) } - /// Set a bit. /// /// ``` /// use bmap::CountedBitmap; - /// let mut bmap = CountedBitmap::new(4).unwrap(); + /// + /// 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)?; @@ -137,16 +158,16 @@ self.remain -= 1; } Ok(()) } - /// Clear a bit. /// /// ``` /// use bmap::CountedBitmap; - /// let mut bmap = CountedBitmap::new(4).unwrap(); + /// + /// 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); /// ``` @@ -161,27 +182,25 @@ 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).unwrap(); + /// let mut bmap = CountedBitmap::new(1); /// let mut set_to_true = false; /// let ret = bmap /// .cond_set(0, || { /// set_to_true = true; /// true @@ -197,18 +216,17 @@ { 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 { - if f() { - *v |= bitval; - self.remain -= 1; - return Ok(true); - } - } - Ok(false) + if *v & bitval == 0 && f() { + *v |= bitval; + self.remain -= 1; + Ok(true) + } else { + Ok(false) + } } } /// Iterators. @@ -216,11 +234,11 @@ /// Return an iterator that returns each of the container's bit values as /// booleans. /// /// ``` /// use bmap::CountedBitmap; - /// let mut bmap = CountedBitmap::new(4).unwrap(); + /// 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))); @@ -236,11 +254,11 @@ /// Create an iterator that will return the indexes of all zeroes in the bit /// map. /// /// ``` /// use bmap::CountedBitmap; - /// let mut bmap = CountedBitmap::new(4).unwrap(); + /// 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)); @@ -258,11 +276,11 @@ /// Create an iterator that will return the indexes of all ones in the bit /// map. /// /// ``` /// use bmap::CountedBitmap; - /// let mut bmap = CountedBitmap::new(4).unwrap(); + /// 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)); @@ -280,11 +298,11 @@ /// Create an iterator that will return index ranges of contiguous blocks of /// zeroes. /// /// ``` /// use bmap::CountedBitmap; - /// let mut bmap = CountedBitmap::new(4).unwrap(); + /// 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); @@ -302,11 +320,11 @@ /// ones. /// /// /// ``` /// use bmap::CountedBitmap; - /// let mut bmap = CountedBitmap::new(4).unwrap(); + /// 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); @@ -499,41 +517,41 @@ mod tests { use super::*; #[test] fn size() { - let bmap = CountedBitmap::new(0).unwrap(); + let bmap = CountedBitmap::new(0); assert_eq!(bmap.len(), 0); assert_eq!(bmap.word_count(), 0); - let bmap = CountedBitmap::new(1).unwrap(); + 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).unwrap(); + let bmap = CountedBitmap::new(idx); assert_eq!(bmap.len(), idx); assert_eq!(bmap.word_count(), 1); - let bmap = CountedBitmap::new(NUM_WORD_BITS).unwrap(); + 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).unwrap(); + let bmap = CountedBitmap::new(idx); assert_eq!(bmap.len(), idx); assert_eq!(bmap.word_count(), 2); } #[test] fn finished() { - let bmap = CountedBitmap::new(0).unwrap(); - assert_eq!(bmap.is_finished(), true); + let bmap = CountedBitmap::new(0); + assert!(bmap.is_finished()); - let mut bmap = CountedBitmap::new(1).unwrap(); - assert_eq!(bmap.is_finished(), false); + let mut bmap = CountedBitmap::new(1); + assert!(!bmap.is_finished()); bmap.set(0).unwrap(); - assert_eq!(bmap.is_finished(), true); + assert!(bmap.is_finished()); } } // vim: set ft=rust et sw=2 ts=2 sts=2 cinoptions=2 tw=79 : ADDED www/changelog.md Index: www/changelog.md ================================================================== --- /dev/null +++ www/changelog.md @@ -0,0 +1,25 @@ +# 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. + Index: www/index.md ================================================================== --- www/index.md +++ www/index.md @@ -1,2 +1,16 @@ # 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).