Struct BitSet 

pub struct BitSet<S: BitStore = usize> { /* private fields */ }

A compact data structure for storing bits

Examples

let mut bs = BitSet::from(0u8);

bs.set(3);
bs.set(7);

assert_eq!(bs.get(3), Some(true));
assert_eq!(bs.get(7), Some(true));
assert_eq!(bs.get(2), Some(false));

Implementations

impl<S: BitStoreConst> BitSet<S>

pub const fn new() -> Self

Creates a new BitSet with all bits set to 0. This is equivalent to BitSet::empty.

Examples

let bs = BitSet::<u8>::new();

pub const fn empty() -> Self

Creates a new BitSet with all bits set to 0.

Examples

let bs = BitSet::<u8>::empty();

pub const fn full() -> Self

Creates a new BitSet with all bits set to 1.

Examples

let bs = BitSet::<u8>::full();

impl<S: BitStore> BitSet<S>

pub fn get(&self, index: u32) -> Option<bool>

Gets the value of the bit at the specified index.

Examples

let mut bs = BitSet::from(0u8);
bs.set(3);
assert_eq!(bs.get(3), Some(true));
assert_eq!(bs[3], true);

pub unsafe fn get_unchecked(&self, index: u32) -> bool

Gets the value of the bit at the specified index without checking that the index is in bounds.

Safety

Using an index that is out of bounds may lead to undefined behavior.

Examples

let mut bs = BitSet::from(0u8);
bs.set(3);
assert_eq!(unsafe { bs.get_unchecked(3) }, true);

pub const fn len(&self) -> u32

Returns the number of bits in the BitSet.

Examples

let bs = BitSet::from(0u8);
assert_eq!(bs.len(), 8);
let bs = BitSet::from(0u16);
assert_eq!(bs.len(), 16);
let bs = BitSet::from([0u16; 2]);
assert_eq!(bs.len(), 32);

pub fn is_empty(&self) -> bool

Returns true if the BitSet is empty, i.e., all bits are unset.

Examples

let bs = BitSet::from(0u16);
assert!(bs.is_empty());

pub fn is_full(&self) -> bool

Returns true if the BitSet is full, i.e., all bits are set.

Examples

let bs = BitSet::from(!0u16);
assert!(bs.is_full());

pub fn any(&self) -> bool

Returns true if the BitSet contains any set bits.

Examples

let mut bs = BitSet::from(0u16);
assert!(!bs.any());
bs.set(3);
assert!(bs.any());

pub const fn iter(&self) -> Bits<&S>

Returns a borrowed iterator over the bits in the BitSet.

pub fn ones(&self) -> impl Iterator<Item = u32> + DoubleEndedIterator + '_

Returns an iterator over the indices of the set bits in the BitSet.

pub fn into_ones(self) -> impl Iterator<Item = u32> + DoubleEndedIterator

Returns an iterator over the indices of the set bits in the BitSet.

impl<S: BitStoreMut> BitSet<S>

pub fn set(&mut self, index: u32) -> Option<bool>

Sets the bit at the specified index, and returns original value.

Examples

let mut bs = BitSet::from(0u8);
assert_eq!(bs.set(3), Some(false));
assert_eq!(bs.get(3), Some(true));

pub unsafe fn set_unchecked(&mut self, index: u32) -> bool

Sets the bit at the specified index without checking that the index is in bounds, and returns original value.

Safety

Using an index that is out of bounds may lead to undefined behavior.

Examples

let mut bs = BitSet::from(0u8);
assert_eq!(unsafe { bs.set_unchecked(3) }, false);
assert_eq!(bs.get(3), Some(true));

pub fn unset(&mut self, index: u32) -> Option<bool>

Unsets the bit at the specified index, and returns original value.

Examples

let mut bs = BitSet::from(0u8);
bs.negate();
assert_eq!(bs.unset(3), Some(true));
assert_eq!(bs.get(3), Some(false));

pub unsafe fn unset_unchecked(&mut self, index: u32) -> bool

Unsets the bit at the specified index without checking that the index is in bounds, and returns original value.

Safety

Using an index that is out of bounds may lead to undefined behavior.

Examples

let mut bs = BitSet::from(0u8);
bs.negate();
assert_eq!(unsafe { bs.unset_unchecked(3) }, true);
assert_eq!(bs.get(3), Some(false));

pub fn change(&mut self, index: u32, value: bool) -> Option<bool>

Changes the bit at the specified index to value, and returns original value.

Examples

let mut bs = BitSet::from(0u8);
assert_eq!(bs.change(3, true), Some(false));
assert_eq!(bs.get(3), Some(true));
assert_eq!(bs.change(3, false), Some(true));
assert_eq!(bs.get(3), Some(false));

pub unsafe fn change_unchecked(&mut self, index: u32, value: bool) -> bool

Changes the bit at the specified index to value without checking that the index is in bounds, and returns original value.

Safety

Using an index that is out of bounds may lead to undefined behavior.

Examples

let mut bs = BitSet::from(0u8);
assert_eq!(unsafe { bs.change_unchecked(3, true) }, false);
assert_eq!(bs.get(3), Some(true));
assert_eq!(unsafe { bs.change_unchecked(3, false) }, true);
assert_eq!(bs.get(3), Some(false));

pub fn union_with(&mut self, other: &Self)

Performs the union of two BitSets, modifying self in place.

Examples

let mut bs1 = BitSet::from(0u16);
let mut bs2 = BitSet::from(0o16);

bs1.set(3);
bs1.set(7);

bs2.set(7);
bs2.set(9);

bs1.union_with(&bs2);

assert_eq!(bs1.get(3), Some(true));
assert_eq!(bs1.get(7), Some(true));
assert_eq!(bs1.get(9), Some(true));

pub fn intersect_with(&mut self, other: &Self)

Performs the intersection of two BitSets, modifying self in place.

Examples

let mut bs1 = BitSet::from(0u16);
let mut bs2 = BitSet::from(0u16);

bs1.set(3);
bs1.set(7);

bs2.set(7);
bs2.set(9);

bs1.intersect_with(&bs2);

assert_eq!(bs1.get(3), Some(false));
assert_eq!(bs1.get(7), Some(true));
assert_eq!(bs1.get(9), Some(false));

pub fn difference_with(&mut self, other: &Self)

Performs the difference of two BitSets, modifying self in place.

Examples

let mut bs1 = BitSet::from(0u16);
let mut bs2 = BitSet::from(0u16);

bs1.set(3);
bs1.set(7);

bs2.set(7);
bs2.set(9);

bs1.difference_with(&bs2);

assert_eq!(bs1.get(3), Some(true));
assert_eq!(bs1.get(7), Some(false));
assert_eq!(bs1.get(9), Some(false));

pub fn symmetric_difference_with(&mut self, other: &Self)

Performs the symmetric difference of two BitSets, modifying self in place.

Examples

let mut bs1 = BitSet::from(0u16);
let mut bs2 = BitSet::from(0u16);

bs1.set(3);
bs1.set(7);

bs2.set(7);
bs2.set(9);

bs1.symmetric_difference_with(&bs2);

assert_eq!(bs1.get(3), Some(true));
assert_eq!(bs1.get(7), Some(false));
assert_eq!(bs1.get(9), Some(true));

pub fn negate(&mut self)

Performs the negation of all the bits, modifying self in place.

Examples

let mut bs1 = BitSet::from(0u16);

bs1.set(3);
bs1.set(7);
bs1.negate();

assert_eq!(bs1.get(3), Some(false));
assert_eq!(bs1.get(7), Some(false));
assert_eq!(bs1.get(9), Some(true));

impl<S: BitStoreMut + Clone> BitSet<S>

pub fn union(&self, other: &Self) -> Self

Performs the union of two BitSets.

Examples

let mut bs1 = BitSet::from(0u16);
let mut bs2 = BitSet::from(0o16);

bs1.set(3);
bs1.set(7);

bs2.set(7);
bs2.set(9);

let bs3 = bs1.union(&bs2);

assert_eq!(bs3.get(3), Some(true));
assert_eq!(bs3.get(7), Some(true));
assert_eq!(bs3.get(9), Some(true));

pub fn intersection(&self, other: &Self) -> Self

Performs the intersection of two BitSets.

Examples

let mut bs1 = BitSet::from(0u16);
let mut bs2 = BitSet::from(0u16);

bs1.set(3);
bs1.set(7);

bs2.set(7);
bs2.set(9);

let bs3 = bs1.intersection(&bs2);

assert_eq!(bs3.get(3), Some(false));
assert_eq!(bs3.get(7), Some(true));
assert_eq!(bs3.get(9), Some(false));

pub fn difference(&self, other: &Self) -> Self

Performs the difference of two BitSets.

Examples

let mut bs1 = BitSet::from(0u16);
let mut bs2 = BitSet::from(0u16);

bs1.set(3);
bs1.set(7);

bs2.set(7);
bs2.set(9);

let bs3 = bs1.difference(&bs2);

assert_eq!(bs3.get(3), Some(true));
assert_eq!(bs3.get(7), Some(false));
assert_eq!(bs3.get(9), Some(false));

pub fn symmetric_difference(&self, other: &Self) -> Self

Performs the symmetric difference of two BitSets.

Examples

let mut bs1 = BitSet::from(0u16);
let mut bs2 = BitSet::from(0u16);

bs1.set(3);
bs1.set(7);

bs2.set(7);
bs2.set(9);

let bs3 = bs1.symmetric_difference(&bs2);

assert_eq!(bs3.get(3), Some(true));
assert_eq!(bs3.get(7), Some(false));
assert_eq!(bs3.get(9), Some(true));

pub fn negation(&self) -> Self

Performs the negation of all the bits.

Examples

let mut bs1 = BitSet::from(0u16);

bs1.set(3);
bs1.set(7);
let bs2 = bs1.negation();

assert_eq!(bs2.get(3), Some(false));
assert_eq!(bs2.get(7), Some(false));
assert_eq!(bs2.get(9), Some(true));

pub fn is_subset(&self, other: &Self) -> bool

Returns true if self is a subset of other, i.e., every bit in self is set in other.

Examples

let mut bs1 = BitSet::from(0u8);
let mut bs2 = BitSet::from(0u8);

bs1.set(7);

bs2.set(3);
bs2.set(7);

assert!(bs1.is_subset(&bs2));

pub fn is_superset(&self, other: &Self) -> bool

Returns true if self is a superset of other, i.e., every bit in other is set in self.

Examples

let mut bs1 = BitSet::from(0u8);
let mut bs2 = BitSet::from(0u8);

bs1.set(3);
bs1.set(7);

bs2.set(7);

assert!(bs1.is_superset(&bs2));

pub fn is_disjoint(&self, other: &Self) -> bool

Returns true if self and other have no common bits set, i.e., their intersection is empty.

Examples

let mut bs1 = BitSet::from(0u8);
let mut bs2 = BitSet::from(0u8);

bs1.set(3);

bs2.set(7);

assert!(bs1.is_disjoint(&bs2));

Trait Implementations

impl<S: BitStore> Binary for BitSet<S>

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

Formats the value using the given formatter.

impl<S: BitStoreMut + Clone> BitAnd for BitSet<S>

type Output = BitSet<S>

The resulting type after applying the & operator.

fn bitand(self, rhs: Self) -> Self::Output

Performs the & operation.

impl<S: BitStoreMut> BitAndAssign for BitSet<S>

fn bitand_assign(&mut self, rhs: Self)

Performs the &= operation.

impl<S: BitStoreMut + Clone> BitOr for BitSet<S>

type Output = BitSet<S>

The resulting type after applying the | operator.

fn bitor(self, rhs: Self) -> Self::Output

Performs the | operation.

impl<S: BitStoreMut> BitOrAssign for BitSet<S>

fn bitor_assign(&mut self, rhs: Self)

Performs the |= operation.

impl<S: BitStoreMut + Clone> BitXor for BitSet<S>

type Output = BitSet<S>

The resulting type after applying the ^ operator.

fn bitxor(self, rhs: Self) -> Self::Output

Performs the ^ operation.

impl<S: BitStoreMut> BitXorAssign for BitSet<S>

fn bitxor_assign(&mut self, rhs: Self)

Performs the ^= operation.

impl<S: Clone + BitStore> Clone for BitSet<S>

fn clone(&self) -> BitSet<S>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<S: BitStore> Debug for BitSet<S>

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

Formats the value using the given formatter.

impl<S: BitStore + DefaultIsEmpty> Default for BitSet<S>

fn default() -> Self

Returns the “default value” for a type.

impl<S: BitStore> From<S> for BitSet<S>

fn from(bits: S) -> Self

Converts to this type from the input type.

impl<S: BitStoreMut + BitStoreConst> FromIterator<u16> for BitSet<S>

fn from_iter<I: IntoIterator<Item = u16>>(iter: I) -> Self

Creates a value from an iterator.

impl<S: BitStoreMut + BitStoreConst> FromIterator<u32> for BitSet<S>

fn from_iter<I: IntoIterator<Item = u32>>(iter: I) -> Self

Creates a value from an iterator.

impl<S: BitStoreMut + BitStoreConst> FromIterator<u64> for BitSet<S>

fn from_iter<I: IntoIterator<Item = u64>>(iter: I) -> Self

Creates a value from an iterator.

impl<S: BitStoreMut + BitStoreConst> FromIterator<u8> for BitSet<S>

fn from_iter<I: IntoIterator<Item = u8>>(iter: I) -> Self

Creates a value from an iterator.

impl<S: BitStoreMut + BitStoreConst> FromIterator<usize> for BitSet<S>

fn from_iter<I: IntoIterator<Item = usize>>(iter: I) -> Self

Creates a value from an iterator.

impl<S: Hash + BitStore> Hash for BitSet<S>

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<S: BitStore> Index<u32> for BitSet<S>

type Output = bool

The returned type after indexing.

fn index(&self, index: u32) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<S: BitStore> IntoIterator for BitSet<S>

type Item = bool

The type of the elements being iterated over.

type IntoIter = Bits<S>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<S: BitStoreMut + Clone> Neg for BitSet<S>

type Output = BitSet<S>

The resulting type after applying the - operator.

fn neg(self) -> Self::Output

Performs the unary - operation.

impl<S: Ord + BitStore> Ord for BitSet<S>

fn cmp(&self, other: &BitSet<S>) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

where Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized,

Restrict a value to a certain interval.

impl<S: PartialEq + BitStore> PartialEq for BitSet<S>

fn eq(&self, other: &BitSet<S>) -> 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<S: PartialOrd + BitStore> PartialOrd for BitSet<S>

fn partial_cmp(&self, other: &BitSet<S>) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

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

Tests less than (for self and other) and is used by the < operator.

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

Tests less than or equal to (for self and other) and is used by the <= operator.

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

Tests greater than (for self and other) and is used by the > operator.

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

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl<S: BitStoreMut + Clone> Sub for BitSet<S>

type Output = BitSet<S>

The resulting type after applying the - operator.

fn sub(self, rhs: Self) -> Self::Output

Performs the - operation.

impl<S: BitStoreMut> SubAssign for BitSet<S>

fn sub_assign(&mut self, rhs: Self)

Performs the -= operation.

impl<S: BitStoreMut + BitStoreConst> TryFromIterator<u16> for BitSet<S>

type Error = IndexRangeError<u16>

fn try_from_iter<I: IntoIterator<Item = u16>>( iter: I, ) -> Result<Self, Self::Error>

impl<S: BitStoreMut + BitStoreConst> TryFromIterator<u32> for BitSet<S>

type Error = IndexRangeError<u32>

fn try_from_iter<I: IntoIterator<Item = u32>>( iter: I, ) -> Result<Self, Self::Error>

impl<S: BitStoreMut + BitStoreConst> TryFromIterator<u64> for BitSet<S>

type Error = IndexRangeError<u64>

fn try_from_iter<I: IntoIterator<Item = u64>>( iter: I, ) -> Result<Self, Self::Error>

impl<S: BitStoreMut + BitStoreConst> TryFromIterator<u8> for BitSet<S>

type Error = IndexRangeError<u8>

fn try_from_iter<I: IntoIterator<Item = u8>>( iter: I, ) -> Result<Self, Self::Error>

impl<S: BitStoreMut + BitStoreConst> TryFromIterator<usize> for BitSet<S>

type Error = IndexRangeError<usize>

fn try_from_iter<I: IntoIterator<Item = usize>>( iter: I, ) -> Result<Self, Self::Error>

impl<S: Copy + BitStore> Copy for BitSet<S>

impl<S: Eq + BitStore> Eq for BitSet<S>

impl<S: BitStore> StructuralPartialEq for BitSet<S>