Struct BitSet

Source

pub struct BitSet { /* private fields */ }

Expand description

A variably sized, heap allocated, dense bitset implemented using no unsafe code.

§Examples

use dense_bitset::BitSet;

let mut set = BitSet::new();

set.insert(7);
set.set(4, true);
set.flip(5);

assert_eq!(set, [7, 4, 5].iter().collect());

set.remove(7);
set.flip(4);
set.set(5, false);

assert!(set.is_empty());

let a: BitSet = [2, 5, 12, 17].iter().collect();
let b: BitSet = [2, 12].iter().collect();

assert!(!a.is_disjoint(&b));
assert!(b.is_subset(&a));
assert!(a.is_superset(&b));

Implementations§

Source §

impl BitSet

Source

pub fn new() -> Self

Constructs a new, empty BitSet.

§Examples

let mut set = BitSet::new();

set.insert(7);
assert_eq!(1, set.element_count());

Source

pub fn with_capacity(capacity: usize) -> Self

Constructs a new, empty BitSet with at least the specified capacity. All indices which are smaller than this capacity, can be used without requiring a reallocation.

§Examples

let mut set = BitSet::with_capacity(100);
let capacity = set.capacity();
assert!(capacity >= 100);
set.insert(99);
assert_eq!(capacity, set.capacity());

Source

pub fn capacity(&self) -> usize

Returns the capacity of this BitSet. All indices which are smaller than this capacity, can be used without requiring a reallocation.

§Examples

let mut set = BitSet::with_capacity(100);
assert!(set.capacity() >= 100);

Source

pub fn is_empty(&self) -> bool

Returns true if no entries are set to false.

§Examples

let mut set = BitSet::new();
assert!(set.is_empty());

set.insert(99);
assert!(!set.is_empty());

set.remove(99);
assert!(set.is_empty());

Source

pub fn element_count(&self) -> usize

Returns the amount of entries set to true.

§Examples

let mut set = BitSet::new();
assert_eq!(0, set.element_count());

set.insert(1729);
set.insert(1337);
assert_eq!(2, set.element_count());

Source

pub fn shrink_to_fit(&mut self)

Shrinks the capacity as much as possible.

While the capacity will drop down as close as possible to the biggest set idx, there might still be space for a few more elements.

§Examples

let mut set = BitSet::with_capacity(1000);
set.extend([100, 200, 300].iter());
assert!(set.capacity() >= 1000);

set.shrink_to_fit();
assert!(set.capacity() > 300);

Source

pub fn set(&mut self, idx: usize, value: bool)

Sets the entry at idx to value.

§Examples

let mut set = BitSet::new();

set.set(1337, true);
assert_eq!(true, set.get(1337));

set.set(1337, false);
assert_eq!(false, set.get(1337));

Source

pub fn insert(&mut self, idx: usize)

Sets the entry at idx to true.

§Examples

let mut set = BitSet::new();

set.insert(69);
assert_eq!(true, set.get(69));

set.remove(69);
assert_eq!(false, set.get(69));

Source

pub fn remove(&mut self, idx: usize)

Sets the entry at idx to false.

§Examples

let mut set = BitSet::new();

set.insert(42);
assert_eq!(true, set.get(42));

set.remove(42);
assert_eq!(false, set.get(42));

Source

pub fn flip(&mut self, idx: usize)

Inverts the value of the entry at idx.

§Examples

let mut set = BitSet::new();
assert_eq!(false, set.get(42));

set.flip(42);
assert_eq!(true, set.get(42));

set.flip(42);
assert_eq!(false, set.get(42));

Source

pub fn get(&self, idx: usize) -> bool

Returns the value of the entry at idx.

§Examples

let mut set = BitSet::new();
assert_eq!(false, set.get(7));

set.insert(6);
assert_eq!(false, set.get(7));

set.insert(7);
assert_eq!(true, set.get(7));

Source

pub fn is_disjoint(&self, other: &BitSet) -> bool

Returns if self and other do not share a true element with the same index. This is equivalent to checking for an empty intersection.

§Examples

let a: BitSet = [1, 2, 3].iter().collect();
let mut b = BitSet::new();

assert_eq!(a.is_disjoint(&b), true);
b.insert(4);
assert_eq!(a.is_disjoint(&b), true);
b.insert(1);
assert_eq!(a.is_disjoint(&b), false);

Source

pub fn is_subset(&self, other: &BitSet) -> bool

Returns true if the set is a subset of other, meaning other contains at least all the values in self.

§Examples

let sup: BitSet = [1, 2, 3].iter().collect();
let mut set = BitSet::new();

assert_eq!(set.is_subset(&sup), true);
set.insert(2);
assert_eq!(set.is_subset(&sup), true);
set.insert(4);
assert_eq!(set.is_subset(&sup), false);

Source

pub fn is_superset(&self, other: &BitSet) -> bool

Returns true if self is a superset of other, meaning self contains at least all the values in other.

§Examples

let sup: BitSet = [1, 2].iter().collect();
let mut set = BitSet::new();

assert_eq!(set.is_superset(&sup), false);

set.insert(0);
set.insert(1);
assert_eq!(set.is_superset(&sup), false);

set.insert(2);
assert_eq!(set.is_superset(&sup), true);

Source

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

Returns the highest index for which the entry which is set to true. In case there is no true entry, this method returns None.

§Examples

let mut set = BitSet::new();
assert_eq!(None, set.highest_bit());

set.insert(3);
set.insert(7);
set.insert(4);
assert_eq!(Some(7), set.highest_bit());

Source

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

Returns the lowest index for which the entry is set to true. In case there is no true entry, this method returns None.

§Examples

let mut set = BitSet::new();
assert_eq!(None, set.lowest_bit());

set.insert(3);
set.insert(7);
set.insert(4);
assert_eq!(Some(3), set.lowest_bit());

Source

pub fn iter(&self) -> IdxIter<&Self> ⓘ

Returns an iterator over the bitset which returns all indices of entries set to true. The indices are sorted from lowest to highest.

§Examples

let set: BitSet = [1, 12, 19, 4].iter().copied().collect();
let mut iter = set.iter();

assert_eq!(Some(1), iter.next());
assert_eq!(Some(4), iter.next());
assert_eq!(Some(12), iter.next());
assert_eq!(Some(19), iter.next());
assert_eq!(None, iter.next());