Struct CompoundBitSet

Source

pub struct CompoundBitSet { /* private fields */ }

Expand description

A large bit set backed by dynamically-sized storage.

§Example

use cranelift_bitset::CompoundBitSet;

// Create a new bitset.
let mut bitset = CompoundBitSet::new();

// Bitsets are initially empty.
assert!(bitset.is_empty());
assert_eq!(bitset.len(), 0);

// Insert into the bitset.
bitset.insert(444);
bitset.insert(555);
bitset.insert(666);

// Now the bitset is not empty.
assert_eq!(bitset.len(), 3);
assert!(!bitset.is_empty());
assert!(bitset.contains(444));
assert!(bitset.contains(555));
assert!(bitset.contains(666));

// Remove an element from the bitset.
let was_present = bitset.remove(666);
assert!(was_present);
assert!(!bitset.contains(666));
assert_eq!(bitset.len(), 2);

// Can iterate over the elements in the set.
let elems: Vec<_> = bitset.iter().collect();
assert_eq!(elems, [444, 555]);

Implementations§

Source §

impl CompoundBitSet

Source

pub fn new() -> Self

Construct a new, empty bit set.

§Example

use cranelift_bitset::CompoundBitSet;

let bitset = CompoundBitSet::new();

assert!(bitset.is_empty());

Source

pub fn with_capacity(capacity: usize) -> Self

Construct a new, empty bit set with space reserved to store any element x such that x < capacity.

The actual capacity reserved may be greater than that requested.

§Example

use cranelift_bitset::CompoundBitSet;

let bitset = CompoundBitSet::with_capacity(4096);

assert!(bitset.is_empty());
assert!(bitset.capacity() >= 4096);

Source

pub fn len(&self) -> usize

Get the number of elements in this bitset.

§Example

use cranelift_bitset::CompoundBitSet;

let mut bitset = CompoundBitSet::new();

assert_eq!(bitset.len(), 0);

bitset.insert(24);
bitset.insert(130);
bitset.insert(3600);

assert_eq!(bitset.len(), 3);

Source

pub fn capacity(&self) -> usize

Get n + 1 where n is the largest value that can be stored inside this set without growing the backing storage.

That is, this set can store any value x such that x < bitset.capacity() without growing the backing storage.

§Example

use cranelift_bitset::CompoundBitSet;

let mut bitset = CompoundBitSet::new();

// New bitsets have zero capacity -- they allocate lazily.
assert_eq!(bitset.capacity(), 0);

// Insert into the bitset, growing its capacity.
bitset.insert(999);

// The bitset must now have capacity for at least `999` elements,
// perhaps more.
assert!(bitset.capacity() >= 999);

Source

pub fn is_empty(&self) -> bool

Is this bitset empty?

§Example

use cranelift_bitset::CompoundBitSet;

let mut bitset = CompoundBitSet::new();

assert!(bitset.is_empty());

bitset.insert(1234);

assert!(!bitset.is_empty());

Source

pub fn contains(&self, i: usize) -> bool

Is i contained in this bitset?

§Example

use cranelift_bitset::CompoundBitSet;

let mut bitset = CompoundBitSet::new();

assert!(!bitset.contains(666));

bitset.insert(666);

assert!(bitset.contains(666));

Source

pub fn ensure_capacity(&mut self, n: usize)

Ensure there is space in this bitset for the values 0..n, growing the backing storage if necessary.

After calling bitset.ensure_capacity(n), inserting any element i where i < n is guaranteed to succeed without growing the bitset’s backing storage.

§Example

// We are going to do a series of inserts where `1000` will be the
// maximum value inserted. Make sure that our bitset has capacity for
// these elements once up front, to avoid growing the backing storage
// multiple times incrementally.
bitset.ensure_capacity(1001);

for i in 0..=1000 {
    if i % 2 == 0 {
        // Inserting this value should not require growing the backing
        // storage.
        assert!(bitset.capacity() > i);
        bitset.insert(i);
    }
}

Source

pub fn insert(&mut self, i: usize) -> bool

Insert i into this bitset.

Returns whether the value was newly inserted. That is:

If the set did not previously contain i then true is returned.
If the set already contained i then false is returned.

§Example

use cranelift_bitset::CompoundBitSet;

let mut bitset = CompoundBitSet::new();

// When an element is inserted that was not already present in the set,
// then `true` is returned.
let is_new = bitset.insert(1234);
assert!(is_new);

// The element is now present in the set.
assert!(bitset.contains(1234));

// And when the element is already in the set, `false` is returned from
// `insert`.
let is_new = bitset.insert(1234);
assert!(!is_new);

Source

pub fn remove(&mut self, i: usize) -> bool

Remove i from this bitset.

Returns whether i was previously in this set or not.

§Example

use cranelift_bitset::CompoundBitSet;

let mut bitset = CompoundBitSet::new();

// Removing an element that was not present in the set returns `false`.
let was_present = bitset.remove(456);
assert!(!was_present);

// And when the element was in the set, `true` is returned.
bitset.insert(456);
let was_present = bitset.remove(456);
assert!(was_present);

Source

pub fn max(&self) -> Option<usize>

Get the largest value in this set, or None if this set is empty.

§Example

use cranelift_bitset::CompoundBitSet;

let mut bitset = CompoundBitSet::new();

// Returns `None` if the bitset is empty.
assert!(bitset.max().is_none());

bitset.insert(123);
bitset.insert(987);
bitset.insert(999);

// Otherwise, it returns the largest value in the set.
assert_eq!(bitset.max(), Some(999));

Source

pub fn pop(&mut self) -> Option<usize>

Removes and returns the largest value in this set.

Returns None if this set is empty.

§Example

use cranelift_bitset::CompoundBitSet;

let mut bitset = CompoundBitSet::new();

bitset.insert(111);
bitset.insert(222);
bitset.insert(333);
bitset.insert(444);
bitset.insert(555);

assert_eq!(bitset.pop(), Some(555));
assert_eq!(bitset.pop(), Some(444));
assert_eq!(bitset.pop(), Some(333));
assert_eq!(bitset.pop(), Some(222));
assert_eq!(bitset.pop(), Some(111));
assert_eq!(bitset.pop(), None);

Source

pub fn clear(&mut self)

Remove all elements from this bitset.

§Example

use cranelift_bitset::CompoundBitSet;

let mut bitset = CompoundBitSet::new();

bitset.insert(100);
bitset.insert(200);
bitset.insert(300);

bitset.clear();

assert!(bitset.is_empty());

Source

pub fn iter(&self) -> Iter<'_> ⓘ

Iterate over the elements in this bitset.

The elements are always yielded in sorted order.

§Example

use cranelift_bitset::CompoundBitSet;

let mut bitset = CompoundBitSet::new();

bitset.insert(0);
bitset.insert(4096);
bitset.insert(123);
bitset.insert(456);
bitset.insert(789);

assert_eq!(
    bitset.iter().collect::<Vec<_>>(),
    [0, 123, 456, 789, 4096],
);