pub struct DenseBitSet<T> {
domain_size: usize,
words: SmallVec<[u64; 2]>,
marker: PhantomData<T>,
}
Expand description
A fixed-size bitset type with a dense representation.
Note 1: Since this bitset is dense, if your domain is big, and/or relatively homogeneous (for example, with long runs of bits set or unset), then it may be preferable to instead use a MixedBitSet, or an IntervalSet. They should be more suited to sparse, or highly-compressible, domains.
Note 2: Use GrowableBitSet
if you need support for resizing after creation.
T
is an index type, typically a newtyped usize
wrapper, but it can also
just be usize
.
All operations that involve an element will panic if the element is equal to or greater than the domain size. All operations that involve two bitsets will panic if the bitsets have differing domain sizes.
Fields§
§domain_size: usize
§words: SmallVec<[u64; 2]>
§marker: PhantomData<T>
Implementations§
Source§impl<T> DenseBitSet<T>
impl<T> DenseBitSet<T>
Sourcepub fn domain_size(&self) -> usize
pub fn domain_size(&self) -> usize
Gets the domain size.
Source§impl<T: Idx> DenseBitSet<T>
impl<T: Idx> DenseBitSet<T>
Sourcepub fn new_empty(domain_size: usize) -> DenseBitSet<T>
pub fn new_empty(domain_size: usize) -> DenseBitSet<T>
Creates a new, empty bitset with a given domain_size
.
Sourcepub fn new_filled(domain_size: usize) -> DenseBitSet<T>
pub fn new_filled(domain_size: usize) -> DenseBitSet<T>
Creates a new, filled bitset with a given domain_size
.
Sourcefn clear_excess_bits(&mut self)
fn clear_excess_bits(&mut self)
Clear excess bits in the final word.
Sourcepub fn superset(&self, other: &DenseBitSet<T>) -> bool
pub fn superset(&self, other: &DenseBitSet<T>) -> bool
Is self
is a (non-strict) superset of other
?
pub fn insert_range(&mut self, elems: impl RangeBounds<T>)
Sourcepub fn insert_all(&mut self)
pub fn insert_all(&mut self)
Sets all bits to true.
Sourcepub fn iter(&self) -> BitIter<'_, T> ⓘ
pub fn iter(&self) -> BitIter<'_, T> ⓘ
Iterates over the indices of set bits in a sorted order.
pub fn last_set_in(&self, range: impl RangeBounds<T>) -> Option<T>
Sourcepub fn union<Rhs>(&mut self, other: &Rhs) -> boolwhere
Self: BitRelations<Rhs>,
pub fn union<Rhs>(&mut self, other: &Rhs) -> boolwhere
Self: BitRelations<Rhs>,
Sets self = self | other
and returns true
if self
changed
(i.e., if new bits were added).
Sourcepub fn subtract<Rhs>(&mut self, other: &Rhs) -> boolwhere
Self: BitRelations<Rhs>,
pub fn subtract<Rhs>(&mut self, other: &Rhs) -> boolwhere
Self: BitRelations<Rhs>,
Sets self = self - other
and returns true
if self
changed.
(i.e., if any bits were removed).
Sourcepub fn intersect<Rhs>(&mut self, other: &Rhs) -> boolwhere
Self: BitRelations<Rhs>,
pub fn intersect<Rhs>(&mut self, other: &Rhs) -> boolwhere
Self: BitRelations<Rhs>,
Sets self = self & other
and return true
if self
changed.
(i.e., if any bits were removed).
Sourcepub fn union_not(&mut self, other: &DenseBitSet<T>)
pub fn union_not(&mut self, other: &DenseBitSet<T>)
Sets self = self | !other
.
FIXME: Incorporate this into BitRelations
and fill out
implementations for other bitset types, if needed.
Trait Implementations§
Source§impl<T: Idx> BitRelations<ChunkedBitSet<T>> for DenseBitSet<T>
impl<T: Idx> BitRelations<ChunkedBitSet<T>> for DenseBitSet<T>
fn union(&mut self, other: &ChunkedBitSet<T>) -> bool
fn subtract(&mut self, _other: &ChunkedBitSet<T>) -> bool
fn intersect(&mut self, other: &ChunkedBitSet<T>) -> bool
Source§impl<T: Idx> BitRelations<DenseBitSet<T>> for DenseBitSet<T>
impl<T: Idx> BitRelations<DenseBitSet<T>> for DenseBitSet<T>
fn union(&mut self, other: &DenseBitSet<T>) -> bool
fn subtract(&mut self, other: &DenseBitSet<T>) -> bool
fn intersect(&mut self, other: &DenseBitSet<T>) -> bool
Source§impl<T> Clone for DenseBitSet<T>
impl<T> Clone for DenseBitSet<T>
Source§impl<T: Idx> Debug for DenseBitSet<T>
impl<T: Idx> Debug for DenseBitSet<T>
Source§impl<T: Idx> From<DenseBitSet<T>> for GrowableBitSet<T>
impl<T: Idx> From<DenseBitSet<T>> for GrowableBitSet<T>
Source§fn from(bit_set: DenseBitSet<T>) -> Self
fn from(bit_set: DenseBitSet<T>) -> Self
Source§impl<T: Idx> From<GrowableBitSet<T>> for DenseBitSet<T>
impl<T: Idx> From<GrowableBitSet<T>> for DenseBitSet<T>
Source§fn from(bit_set: GrowableBitSet<T>) -> Self
fn from(bit_set: GrowableBitSet<T>) -> Self
Source§impl<T: Hash> Hash for DenseBitSet<T>
impl<T: Hash> Hash for DenseBitSet<T>
Source§impl<T: PartialEq> PartialEq for DenseBitSet<T>
impl<T: PartialEq> PartialEq for DenseBitSet<T>
Source§impl<T: Idx> ToString for DenseBitSet<T>
impl<T: Idx> ToString for DenseBitSet<T>
impl<T: Eq> Eq for DenseBitSet<T>
impl<T> StructuralPartialEq for DenseBitSet<T>
Auto Trait Implementations§
impl<T> Freeze for DenseBitSet<T>
impl<T> RefUnwindSafe for DenseBitSet<T>where
T: RefUnwindSafe,
impl<T> Send for DenseBitSet<T>where
T: Send,
impl<T> Sync for DenseBitSet<T>where
T: Sync,
impl<T> Unpin for DenseBitSet<T>where
T: Unpin,
impl<T> UnwindSafe for DenseBitSet<T>where
T: UnwindSafe,
Blanket Implementations§
Source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
Source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
Source§impl<T> CloneToUninit for Twhere
T: Clone,
impl<T> CloneToUninit for Twhere
T: Clone,
Source§impl<Q, K> Equivalent<K> for Q
impl<Q, K> Equivalent<K> for Q
Source§impl<Q, K> Equivalent<K> for Q
impl<Q, K> Equivalent<K> for Q
Source§impl<Q, K> Equivalent<K> for Q
impl<Q, K> Equivalent<K> for Q
Source§fn equivalent(&self, key: &K) -> bool
fn equivalent(&self, key: &K) -> bool
key
and return true
if they are equal.Layout§
Note: Most layout information is completely unstable and may even differ between compilations. The only exception is types with certain repr(...)
attributes. Please see the Rust Reference's “Type Layout” chapter for details on type layout guarantees.
Size: 32 bytes