Struct dense_bitset::BitSet

pub struct BitSet { /* fields omitted */ }

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

Methods

impl BitSet

pub fn new() -> Self

Constructs a new, empty BitSet.

Examples

let mut set = BitSet::new();

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Important traits for IdxIter<B>

impl<B: Borrow<BitSet>> Iterator for IdxIter<B> type Item = usize;

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

Trait Implementations

impl Clone for BitSet

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for BitSet

fn fmt(&self, f: &mut Formatter) -> Result

Formats the value using the given formatter.

impl Default for BitSet

fn default() -> BitSet

Returns the "default value" for a type.

impl Eq for BitSet

impl<'a> Extend<&'a usize> for BitSet

fn extend<I: IntoIterator<Item = &'a usize>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

impl Extend<usize> for BitSet

fn extend<I: IntoIterator<Item = usize>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

impl<'a> FromIterator<&'a bool> for BitSet

fn from_iter<U: IntoIterator<Item = &'a bool>>(iter: U) -> BitSet

Creates a value from an iterator.

impl<'a> FromIterator<&'a usize> for BitSet

fn from_iter<U: IntoIterator<Item = &'a usize>>(iter: U) -> BitSet

Creates a value from an iterator.

impl FromIterator<bool> for BitSet

fn from_iter<U: IntoIterator<Item = bool>>(iter: U) -> BitSet

Creates a value from an iterator.

impl FromIterator<usize> for BitSet

fn from_iter<U: IntoIterator<Item = usize>>(iter: U) -> BitSet

Creates a value from an iterator.

impl IntoIterator for BitSet

type Item = usize

The type of the elements being iterated over.

type IntoIter = IdxIter<BitSet>

Which kind of iterator are we turning this into?

Important traits for IdxIter<B>

impl<B: Borrow<BitSet>> Iterator for IdxIter<B> type Item = usize;

fn into_iter(self) -> IdxIter<BitSet>

Creates an iterator from a value.

impl PartialEq<BitSet> for BitSet

fn eq(&self, rhs: &Self) -> bool

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

#[must_use] fn ne(&self, other: &Rhs) -> bool

This method tests for !=.