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
impl BitSet
Sourcepub fn new() -> Self
pub fn new() -> Self
Constructs a new, empty BitSet
.
§Examples
let mut set = BitSet::new();
set.insert(7);
assert_eq!(1, set.element_count());
Sourcepub fn with_capacity(capacity: usize) -> Self
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());
Sourcepub fn capacity(&self) -> usize
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);
Sourcepub fn is_empty(&self) -> bool
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());
Sourcepub fn element_count(&self) -> usize
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());
Sourcepub fn shrink_to_fit(&mut self)
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);
Sourcepub fn set(&mut self, idx: usize, value: bool)
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));
Sourcepub fn insert(&mut self, idx: usize)
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));
Sourcepub fn remove(&mut self, idx: usize)
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));
Sourcepub fn flip(&mut self, idx: usize)
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));
Sourcepub fn get(&self, idx: usize) -> bool
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));
Sourcepub fn is_disjoint(&self, other: &BitSet) -> bool
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);
Sourcepub fn is_subset(&self, other: &BitSet) -> bool
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);
Sourcepub fn is_superset(&self, other: &BitSet) -> bool
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);
Sourcepub fn highest_bit(&self) -> Option<usize>
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());
Sourcepub fn lowest_bit(&self) -> Option<usize>
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());
Sourcepub fn iter(&self) -> IdxIter<&Self> ⓘ
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§
Source§impl<'a> Extend<&'a usize> for BitSet
impl<'a> Extend<&'a usize> for BitSet
Source§fn extend<I: IntoIterator<Item = &'a usize>>(&mut self, iter: I)
fn extend<I: IntoIterator<Item = &'a usize>>(&mut self, iter: I)
Source§fn extend_one(&mut self, item: A)
fn extend_one(&mut self, item: A)
extend_one
)Source§fn extend_reserve(&mut self, additional: usize)
fn extend_reserve(&mut self, additional: usize)
extend_one
)Source§impl Extend<usize> for BitSet
impl Extend<usize> for BitSet
Source§fn extend<I: IntoIterator<Item = usize>>(&mut self, iter: I)
fn extend<I: IntoIterator<Item = usize>>(&mut self, iter: I)
Source§fn extend_one(&mut self, item: A)
fn extend_one(&mut self, item: A)
extend_one
)Source§fn extend_reserve(&mut self, additional: usize)
fn extend_reserve(&mut self, additional: usize)
extend_one
)