Struct GrowableBitMap

Source

pub struct GrowableBitMap<S>where
    S: BitStorage,
{ /* private fields */ }

Expand description

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.

Implementations§

Source §

impl<S> GrowableBitMap<S>
where S: BitStorage,

Source

pub fn new() -> Self

Creates a new, empty GrowableBitMap.

This does not allocate anything.

§Examples

use growable_bitmap::{GrowableBitMap, BitStorage};

assert!(GrowableBitMap::<u8>::new().is_empty());

Source

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, 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);

Source

pub fn is_empty(&self) -> bool

true if the GrowableBitMap is empty.

§Examples

use growable_bitmap::{GrowableBitMap, BitStorage};

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

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

Source

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, 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));

Source

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, 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.

Source

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, 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:

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

Source

pub fn clear(&mut self)

Clears the bitmap, removing all values (setting them all to 0).

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

§Examples

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:

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

Source

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, 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);

Source

pub fn capacity(&self) -> usize

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

§Examples

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);

Source

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, 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);