Struct DenseBitSet

pub struct DenseBitSet<T> { /* private fields */ }

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.

Implementations

impl<T> DenseBitSet<T>

pub fn domain_size(&self) -> usize

Gets the domain size.

impl<T: Idx> DenseBitSet<T>

pub fn new_empty(domain_size: usize) -> DenseBitSet<T>

Creates a new, empty bitset with a given domain_size.

pub fn new_filled(domain_size: usize) -> DenseBitSet<T>

Creates a new, filled bitset with a given domain_size.

pub fn clear(&mut self)

Clear all elements.

pub fn count(&self) -> usize

Count the number of set bits in the set.

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

Returns true if self contains elem.

pub fn superset(&self, other: &DenseBitSet<T>) -> bool

Is self is a (non-strict) superset of other?

pub fn is_empty(&self) -> bool

Is the set empty?

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

Insert elem. Returns whether the set has changed.

pub fn insert_range(&mut self, elems: impl RangeBounds<T>)

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.

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>

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

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

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

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

impl<T> Clone for DenseBitSet<T>

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

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

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

Formats the value using the given formatter.

impl<T: Idx> From<DenseBitSet<T>> for GrowableBitSet<T>

fn from(bit_set: DenseBitSet<T>) -> Self

Converts to this type from the input type.

impl<T: Idx> From<GrowableBitSet<T>> for DenseBitSet<T>

fn from(bit_set: GrowableBitSet<T>) -> Self

Converts to this type from the input type.

impl<T: Hash> Hash for DenseBitSet<T>

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<T: PartialEq> PartialEq for DenseBitSet<T>

fn eq(&self, other: &DenseBitSet<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: Idx> ToString for DenseBitSet<T>

fn to_string(&self) -> String

Converts the given value to a String.

impl<T: Eq> Eq for DenseBitSet<T>

impl<T> StructuralPartialEq for DenseBitSet<T>