Struct growable_bitmap::GrowableBitMap

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

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

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

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

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

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

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

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.

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

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

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

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

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

Trait Implementations

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

fn clone(&self) -> GrowableBitMap<S>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<S> Debug for GrowableBitMap<S> where
    S: BitStorage + Debug, 

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

Formats the value using the given formatter.

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

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

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<S: Ord> Ord for GrowableBitMap<S> where
    S: BitStorage, 

fn cmp(&self, other: &GrowableBitMap<S>) -> 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<S: PartialEq> PartialEq<GrowableBitMap<S>> for GrowableBitMap<S> where
    S: BitStorage, 

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

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

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

This method tests for !=.

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

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

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

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

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

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

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

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

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

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

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

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

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