pub struct ChunkedBitSet<T> {
domain_size: usize,
chunks: Box<[Chunk]>,
marker: PhantomData<T>,
}
Expand description
A fixed-size bitset type with a partially dense, partially sparse representation. The bitset is broken into chunks, and chunks that are all zeros or all ones are represented and handled very efficiently.
This type is especially efficient for sets that typically have a large
domain_size
with significant stretches of all zeros or all ones, and also
some stretches with lots of 0s and 1s mixed in a way that causes trouble
for IntervalSet
.
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
§chunks: Box<[Chunk]>
The chunks. Each one contains exactly CHUNK_BITS values, except the last one which contains 1..=CHUNK_BITS values.
marker: PhantomData<T>
Implementations§
Source§impl<T> ChunkedBitSet<T>
impl<T> ChunkedBitSet<T>
pub fn domain_size(&self) -> usize
Source§impl<T: Idx> ChunkedBitSet<T>
impl<T: Idx> ChunkedBitSet<T>
Sourcefn new(domain_size: usize, is_empty: bool) -> Self
fn new(domain_size: usize, is_empty: bool) -> Self
Creates a new bitset with a given domain_size
and chunk kind.
Sourcepub fn new_empty(domain_size: usize) -> Self
pub fn new_empty(domain_size: usize) -> Self
Creates a new, empty bitset with a given domain_size
.
Sourcepub fn new_filled(domain_size: usize) -> Self
pub fn new_filled(domain_size: usize) -> Self
Creates a new, filled bitset with a given domain_size
.
pub fn iter(&self) -> ChunkedBitIter<'_, T> ⓘ
Sourcepub fn insert_all(&mut self)
pub fn insert_all(&mut self)
Sets all bits to true.
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).
Trait Implementations§
Source§impl<T: Idx> BitRelations<ChunkedBitSet<T>> for BitSet<T>
impl<T: Idx> BitRelations<ChunkedBitSet<T>> for BitSet<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<ChunkedBitSet<T>> for ChunkedBitSet<T>
impl<T: Idx> BitRelations<ChunkedBitSet<T>> for ChunkedBitSet<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<HybridBitSet<T>> for ChunkedBitSet<T>
impl<T: Idx> BitRelations<HybridBitSet<T>> for ChunkedBitSet<T>
fn union(&mut self, other: &HybridBitSet<T>) -> bool
fn subtract(&mut self, other: &HybridBitSet<T>) -> bool
fn intersect(&mut self, _other: &HybridBitSet<T>) -> bool
Source§impl<T> Clone for ChunkedBitSet<T>
impl<T> Clone for ChunkedBitSet<T>
Source§fn clone_from(&mut self, from: &Self)
fn clone_from(&mut self, from: &Self)
WARNING: this implementation of clone_from will panic if the two
bitsets have different domain sizes. This constraint is not inherent to
clone_from
, but it works with the existing call sites and allows a
faster implementation, which is important because this function is hot.
Source§impl<T: Idx> Debug for ChunkedBitSet<T>
impl<T: Idx> Debug for ChunkedBitSet<T>
Source§impl<T: PartialEq> PartialEq for ChunkedBitSet<T>
impl<T: PartialEq> PartialEq for ChunkedBitSet<T>
impl<T: Eq> Eq for ChunkedBitSet<T>
impl<T> StructuralPartialEq for ChunkedBitSet<T>
Auto Trait Implementations§
impl<T> Freeze for ChunkedBitSet<T>
impl<T> RefUnwindSafe for ChunkedBitSet<T>where
T: RefUnwindSafe,
impl<T> !Send for ChunkedBitSet<T>
impl<T> !Sync for ChunkedBitSet<T>
impl<T> Unpin for ChunkedBitSet<T>where
T: Unpin,
impl<T> UnwindSafe for ChunkedBitSet<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§unsafe fn clone_to_uninit(&self, dst: *mut T)
unsafe fn clone_to_uninit(&self, dst: *mut T)
clone_to_uninit
)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.Source§impl<T> IntoEither for T
impl<T> IntoEither for T
Source§fn into_either(self, into_left: bool) -> Either<Self, Self>
fn into_either(self, into_left: bool) -> Either<Self, Self>
self
into a Left
variant of Either<Self, Self>
if into_left
is true
.
Converts self
into a Right
variant of Either<Self, Self>
otherwise. Read moreSource§fn into_either_with<F>(self, into_left: F) -> Either<Self, Self>
fn into_either_with<F>(self, into_left: F) -> Either<Self, Self>
self
into a Left
variant of Either<Self, Self>
if into_left(&self)
returns true
.
Converts self
into a Right
variant of Either<Self, Self>
otherwise. Read moreSource§impl<T> Pointable for T
impl<T> Pointable for T
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: 24 bytes