Struct growable_bitmap::GrowableBitMap

pub struct GrowableBitMap { /* fields omitted */ }

A growable compact boolean array.

Bits are stored contiguously. The first value is packed into the least significant bits of the first word of the backing storage.

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.
• Right now the only implemented storage integer is u8.

Implementations

impl GrowableBitMap

pub const fn new() -> Self

Creates a new, empty GrowableBitMap.

This does not allocate anything.

Examples

use growable_bitmap::GrowableBitMap;

assert!(GrowableBitMap::new().is_empty());

pub fn with_capacity(capacity: usize) -> Self

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

use growable_bitmap::GrowableBitMap;

let mut b = GrowableBitMap::with_capacity(8);
assert!(b.is_empty());
assert_eq!(b.capacity(), 8);

b.set_bit(7);
assert_eq!(b.capacity(), 8);

b.set_bit(10);
assert!(b.capacity() >= 8);

pub fn is_empty(&self) -> bool

true if the GrowableBitMap is empty.

Examples

use growable_bitmap::GrowableBitMap;

let mut b = GrowableBitMap::new();
assert!(b.is_empty());

b.set_bit(3);
assert!(!b.is_empty());

pub fn get_bit(&self, index: usize) -> bool

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

use growable_bitmap::GrowableBitMap;

let mut b = GrowableBitMap::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 set_bit(&mut self, index: usize) -> bool

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 u8s the backing storage will allocate 1600 u8s since sizeof::<u8>() == 1 byte.

See also the Caveats section on GrowableBitMap.

Examples

use growable_bitmap::GrowableBitMap;

let mut b = GrowableBitMap::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(10)); // The bitmap will grow as needed to set the bit.

pub fn clear_bit(&mut self, index: usize) -> bool

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

use growable_bitmap::GrowableBitMap;

let mut b = GrowableBitMap::new();
assert!(!b.clear_bit(0)); // Bit 0 was not set before, returns false.

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

pub fn clear(&mut self)

Clears the bitmap, removing all values.

This method has no effect on the allocated capacity of the bitmap.

Examples

use growable_bitmap::GrowableBitMap;

let mut b = GrowableBitMap::new();
b.set_bit(4);
assert!(!b.is_empty());

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

pub fn count_ones(&self) -> usize

Counts the number of bits that are set to 1 in the whole bitmap.

Examples

use growable_bitmap::GrowableBitMap;

let mut b = GrowableBitMap::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);

pub fn capacity(&self) -> usize

Returns the number of bits the bitmap can hold without reallocating.

Examples

use growable_bitmap::GrowableBitMap;

let mut b = GrowableBitMap::new();
assert_eq!(b.capacity(), 0);

b.set_bit(125);
assert_eq!(b.capacity(), 128);

pub fn shrink_to_fit(&mut self)

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

use growable_bitmap::GrowableBitMap;

let mut b = GrowableBitMap::with_capacity(125);

b.set_bit(63);
b.set_bit(127);
assert_eq!(b.capacity(), 128);

b.clear_bit(127);
b.shrink_to_fit();
assert_eq!(b.capacity(), 64);

Trait Implementations

impl Clone for GrowableBitMap

fn clone(&self) -> GrowableBitMap

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for GrowableBitMap

fn fmt(&self, fmt: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Eq for GrowableBitMap

impl Hash for GrowableBitMap

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H) where
    H: Hasher, 

Feeds a slice of this type into the given Hasher.

impl Ord for GrowableBitMap

fn cmp(&self, other: &GrowableBitMap) -> Ordering

This method returns an Ordering between self and other.

#[must_use]fn max(self, other: Self) -> Self

Compares and returns the maximum of two values.

#[must_use]fn min(self, other: Self) -> Self

Compares and returns the minimum of two values.

#[must_use]fn clamp(self, min: Self, max: Self) -> Self

🔬 This is a nightly-only experimental API. (clamp)

Restrict a value to a certain interval.

impl PartialEq<GrowableBitMap> for GrowableBitMap

fn eq(&self, other: &GrowableBitMap) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &GrowableBitMap) -> bool

This method tests for !=.

impl PartialOrd<GrowableBitMap> for GrowableBitMap

fn partial_cmp(&self, other: &GrowableBitMap) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &GrowableBitMap) -> bool

This method tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &GrowableBitMap) -> bool

This method tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &GrowableBitMap) -> bool

This method tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &GrowableBitMap) -> bool

This method tests greater than or equal to (for self and other) and is used by the >= operator.

impl StructuralEq for GrowableBitMap

impl StructuralPartialEq for GrowableBitMap