Struct ChunkedBitSet

pub struct ChunkedBitSet<T> {
    domain_size: usize,
    chunks: Box<[Chunk]>,
    marker: PhantomData<T>,
}

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.

Best used via MixedBitSet, rather than directly, because MixedBitSet has better performance for small bitsets.

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

impl<T> ChunkedBitSet<T>

pub fn domain_size(&self) -> usize

impl<T: Idx> ChunkedBitSet<T>

fn new(domain_size: usize, is_empty: bool) -> Self

Creates a new bitset with a given domain_size and chunk kind.

pub fn new_empty(domain_size: usize) -> Self

Creates a new, empty bitset with a given domain_size.

pub fn new_filled(domain_size: usize) -> Self

Creates a new, filled bitset with a given domain_size.

pub fn clear(&mut self)

pub fn count(&self) -> usize

Count the number of bits in the set.

pub fn is_empty(&self) -> bool

pub fn contains(&self, elem: T) -> bool

Returns true if self contains elem.

pub fn iter(&self) -> ChunkedBitIter<'_, T>

pub fn insert(&mut self, elem: T) -> bool

Insert elem. Returns whether the set has changed.

pub fn insert_all(&mut self)

Sets all bits to true.

pub fn remove(&mut self, elem: T) -> bool

Returns true if the set has changed.

fn chunk_iter(&self, chunk_index: usize) -> ChunkIter<'_>

pub fn union<Rhs>(&mut self, other: &Rhs) -> bool

where Self: BitRelations<Rhs>,

Sets self = self | other and returns true if self changed (i.e., if new bits were added).

pub fn subtract<Rhs>(&mut self, other: &Rhs) -> bool

where Self: BitRelations<Rhs>,

Sets self = self - other and returns true if self changed. (i.e., if any bits were removed).

pub fn intersect<Rhs>(&mut self, other: &Rhs) -> bool

where Self: BitRelations<Rhs>,

Sets self = self & other and return true if self changed. (i.e., if any bits were removed).

Trait Implementations

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

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

impl<T> Clone for ChunkedBitSet<T>

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.

fn clone(&self) -> Self

Returns a copy of the value.

impl<T: Idx> Debug for ChunkedBitSet<T>

fn fmt(&self, w: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: PartialEq> PartialEq for ChunkedBitSet<T>

fn eq(&self, other: &ChunkedBitSet<T>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T: Eq> Eq for ChunkedBitSet<T>

impl<T> StructuralPartialEq for ChunkedBitSet<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