Struct BitSet

pub struct BitSet<const LOWER: usize, const UPPER: usize, T: Integer> { /* private fields */ }

A set, similar to std::collections::HashSet, but with a number of limitations in order to improve the performance for specific use cases.

It limits the set members to unsigned integers within a range specified by the generic parameters, which allows set membership to be boiled to down to a boolean or a bit. For uses cases that fit these constraints, it significantly increases performance compared to regular hash sets; even ones with integer specific hashers, simply because there is no hashing.

The members of the set need to implement the Integer trait, which is currently implemented for u8, u16, u32, and usize. I specifically left out u64, because on a 32bit machine usize would be 32bit, and casting from a u64 to usize would truncate.

Implementations

impl<const LOWER: usize, const UPPER: usize, T: Integer> BitSet<LOWER, UPPER, T>

pub fn new() -> Self

Construct a new BitSet<LOWER, UPPER, T>, where LOWER and UPPER are usize integers that denote the boundaries of the BitSet, and T is a type implementing the Integer trait

use firims::BitSet;
let foo = BitSet::<10, 20, usize>::new();

pub fn len(&self) -> usize

Returns the number of elements in the set.

use firims::BitSet;

let mut foo = BitSet::<0, 32, usize>::from([1, 10, 5]);
assert_eq!(foo.len(), 3);

foo.remove(&1);
assert_eq!(foo.len(), 2);

pub fn is_empty(&self) -> bool

Checks whether the set is empty.

use firims::BitSet;

let mut foo = BitSet::<0, 32, usize>::from([1]);
assert_eq!(foo.len(), 1);
assert!(!foo.is_empty());

foo.remove(&1);
assert!(foo.is_empty());

pub fn clear(&mut self)

Removes all items from set.

use firims::BitSet;

let mut foo = BitSet::<0, 32, usize>::from([1, 10, 5]);
assert_eq!(foo.len(), 3);
assert!(!foo.is_empty());

foo.clear();
assert_eq!(foo.len(), 0);
assert!(foo.is_empty());

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

Return whether an item is part of the set.

use firims::BitSet;

let mut foo = BitSet::<3, 32, usize>::from([3, 10, 5]);

assert_eq!(foo.len(), 3);
assert!(foo.contains(&3));
assert!(foo.contains(&10));
assert!(foo.contains(&5));

pub fn insert(&mut self, x: T)

Insert an item into the set.

This item x has to be constrained to LOWER <= x <= UPPER

use firims::BitSet;

let mut foo = BitSet::<0, 32, usize>::new();
foo.insert(0);
foo.insert(10);
foo.insert(32);
assert!(foo.contains(&0));
assert!(foo.contains(&10));
assert!(foo.contains(&32));
assert!(!foo.contains(&2));

foo.remove(&0);
foo.remove(&10);
foo.remove(&32);
assert!(!foo.contains(&0));
assert!(!foo.contains(&10));
assert!(!foo.contains(&32));

pub fn remove(&mut self, x: &T)

Removes an item from the set.

use firims::BitSet;

let mut foo = BitSet::<0, 32, usize>::from([1]);
assert!(foo.contains(&1));

foo.remove(&1);
assert!(!foo.contains(&1));

pub fn retain(&mut self, f: impl Fn(T) -> bool)

Using the predicate f passed to this method, filter the set such that it only retains elements fulfilling the predicate.

use firims::BitSet;

let mut foo = BitSet::<0, 32, usize>::from([1, 2, 3]);

foo.retain(|x| x % 2 == 0);

assert!(foo.contains(&2));
assert!(!foo.contains(&1));
assert!(!foo.contains(&3));

pub fn take(&mut self, v: &T) -> Option<T>

Removes and returns the value in the set, if any, that is equal to the given one.

Also returns none, if the value is outside of the bounds of the BitSet.

use firims::BitSet;

let mut foo = BitSet::<0, 32, usize>::from([1, 2, 3]);

assert_eq!(foo.len(), 3);
assert!(foo.contains(&2));
assert_eq!(foo.take(&2), Some(2));
assert_eq!(foo.len(), 2);
assert_eq!(foo.take(&2), None);

pub fn iter(&self) -> Iter<'_, LOWER, UPPER, T>

An iterator visiting all values of the set in ascending order.

use firims::BitSet;

let mut foo = BitSet::<2, 5, usize>::from([2, 4, 5]);

let mut iter = foo.iter();
assert_eq!(iter.next(), Some(2));
assert_eq!(iter.next(), Some(4));
assert_eq!(iter.next(), Some(5));
assert_eq!(iter.next(), None);

pub fn drain(&mut self) -> Drain<'_, LOWER, UPPER, T>

A draining iterator visiting all values of the set in ascending order, each iteration removing that value from the set.

use firims::BitSet;

let mut foo = BitSet::<2, 5, usize>::from([2, 4, 5]);

assert!(!foo.is_empty());
{
    let mut iter = foo.drain();
    assert_eq!(iter.next(), Some(2));
    assert_eq!(iter.next(), Some(4));
    assert_eq!(iter.next(), Some(5));
    assert_eq!(iter.next(), None);
}
assert!(foo.is_empty());

pub fn difference<'a>( &'a self, rhs: &'a Self, ) -> Difference<'a, LOWER, UPPER, T>

Visits the values representing the difference, i.e., the values that are in self but not in other.

use firims::BitSet;

let foo = BitSet::<1, 10, usize>::from([1, 2, 3]);
let bar = BitSet::<1, 10, usize>::from([4, 2, 3, 4]);

let diff: BitSet::<1, 10, usize> = foo.difference(&bar).collect();
assert_eq!(diff, [1].iter().collect());
assert_eq!(diff.len(), 1);

let diff: BitSet::<1, 10, usize> = bar.difference(&foo).collect();
assert_eq!(diff, [4].iter().collect());
assert_eq!(diff.len(), 1);

pub fn symmetric_difference<'a>( &'a self, rhs: &'a Self, ) -> SymmetricDifference<'a, LOWER, UPPER, T>

Visits the values representing the symmetric difference, i.e., the values that are in self or in other but not in both.

use firims::BitSet;

let foo = BitSet::<1, 10, usize>::from([1, 2, 3]);
let bar = BitSet::<1, 10, usize>::from([4, 2, 3, 4]);

let diff1: BitSet::<1, 10, usize> = foo.symmetric_difference(&bar).collect();
let diff2: BitSet::<1, 10, usize> = bar.symmetric_difference(&foo).collect();
assert_eq!(diff1, diff2);
assert_eq!(diff1, [1, 4].iter().collect());

pub fn intersection<'a>( &'a self, rhs: &'a Self, ) -> Intersection<'a, LOWER, UPPER, T>

Visits the values representing the intersection, i.e., the values that are both in self and other.

When an equal element is present in self and other then the resulting Intersection may yield copies of one or the other. This can be relevant if T contains fields which are not compared by its Eq implementation, and may hold different value between the two equal copies of T in the two sets.

use firims::BitSet;

let foo = BitSet::<1, 10, usize>::from([1, 2, 3]);
let bar = BitSet::<1, 10, usize>::from([4, 2, 3, 4]);

let intersect: BitSet::<1, 10, usize> = foo.intersection(&bar).collect();
assert_eq!(intersect, [2, 3].iter().collect());

pub fn union<'a>(&'a self, rhs: &'a Self) -> Union<'a, LOWER, UPPER, T>

Visits the values representing the union, i.e., all the values in self or other, without duplicates.

use firims::BitSet;

let foo = BitSet::<1, 10, usize>::from([1, 2, 3]);
let bar = BitSet::<1, 10, usize>::from([4, 2, 3, 4]);

let un: BitSet::<1, 10, usize> = foo.union(&bar).collect();
assert_eq!(un, [1, 2, 3, 4].iter().collect());

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

Returns true of self and other do not share any elements.

use firims::BitSet;

let mut foo = BitSet::<0, 32, usize>::from([1, 2, 3]);
let mut bar = BitSet::<0, 32, usize>::from([4, 5, 6]);

assert!(foo.is_disjoint(&bar));

foo.insert(4);
assert!(!foo.is_disjoint(&bar));

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

Returns true if the set is a subset of another, i.e., other contains at least all the values in self.

use firims::BitSet;

let foo = BitSet::<0, 5, usize>::from([1, 2, 3]);
let mut bar = BitSet::<0, 5, usize>::new();

assert_eq!(bar.is_subset(&foo), true);
bar.insert(2);
assert_eq!(bar.is_subset(&foo), true);
bar.insert(4);
assert_eq!(bar.is_subset(&foo), false);

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

Returns true if the set is a superset of another, i.e., self contains at least all the values in other.

use firims::BitSet;

let foo = BitSet::<0, 5, usize>::from([1, 2]);
let mut bar = BitSet::<0, 5, usize>::new();

assert_eq!(bar.is_superset(&foo), false);

bar.insert(0);
bar.insert(1);
assert_eq!(bar.is_superset(&foo), false);

bar.insert(2);
assert_eq!(bar.is_superset(&foo), true);

Trait Implementations

impl<const LOWER: usize, const UPPER: usize, T: Integer> BitAnd<&BitSet<LOWER, UPPER, T>> for &BitSet<LOWER, UPPER, T>

fn bitand(self, rhs: &BitSet<LOWER, UPPER, T>) -> Self::Output

Returns the intersection of self and rhs as a new BitSet<LOWER, UPPER, T>.

use firims::BitSet;

let a = BitSet::<1, 6, usize>::from([1, 2, 3]);
let b = BitSet::<1, 6, usize>::from([2, 3, 4]);

let set = &a & &b;

let mut i = 0;
let expected = [2, 3];
for x in &set {
    assert!(expected.contains(&x));
    i += 1;
}
assert_eq!(i, expected.len());

type Output = BitSet<LOWER, UPPER, T>

The resulting type after applying the & operator.

impl<const LOWER: usize, const UPPER: usize, T: Integer> BitOr<&BitSet<LOWER, UPPER, T>> for &BitSet<LOWER, UPPER, T>

fn bitor(self, rhs: &BitSet<LOWER, UPPER, T>) -> Self::Output

Returns the union of self and rhs as a new BitSet<LOWER, UPPER, T>.

use firims::BitSet;

let a = BitSet::<1, 6, usize>::from([1, 2, 3]);
let b = BitSet::<1, 6, usize>::from([3, 4, 5]);

let set = &a | &b;

let mut i = 0;
let expected = [1, 2, 3, 4, 5];
for x in &set {
    assert!(expected.contains(&x));
    i += 1;
}
assert_eq!(i, expected.len());

type Output = BitSet<LOWER, UPPER, T>

The resulting type after applying the | operator.

impl<const LOWER: usize, const UPPER: usize, T: Integer> BitXor<&BitSet<LOWER, UPPER, T>> for &BitSet<LOWER, UPPER, T>

fn bitxor(self, rhs: &BitSet<LOWER, UPPER, T>) -> Self::Output

Returns the symmetric difference of self and rhs as a new BitSet<LOWER, UPPER, T>.

use firims::BitSet;

let a = BitSet::<1, 6, usize>::from([1, 2, 3]);
let b = BitSet::<1, 6, usize>::from([3, 4, 5]);

let set = &a ^ &b;

let mut i = 0;
let expected = [1, 2, 4, 5];
for x in &set {
    assert!(expected.contains(&x));
    i += 1;
}
assert_eq!(i, expected.len());

type Output = BitSet<LOWER, UPPER, T>

The resulting type after applying the ^ operator.

impl<const LOWER: usize, const UPPER: usize, T: Clone + Integer> Clone for BitSet<LOWER, UPPER, T>

fn clone(&self) -> BitSet<LOWER, UPPER, T>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<const LOWER: usize, const UPPER: usize, T: Integer> Debug for BitSet<LOWER, UPPER, T>

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

Formats the value using the given formatter.

impl<const LOWER: usize, const UPPER: usize, T: Integer> Default for BitSet<LOWER, UPPER, T>

fn default() -> Self

Constructs an empty BitSet.

use firims::BitSet;
let foo = BitSet::<10, 20, usize>::default();

impl<'a, const LOWER: usize, const UPPER: usize, T: Integer> Extend<&'a T> for BitSet<LOWER, UPPER, T>

fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I)

Extends a BitSet<LOWER, UPPER, T> with the contents of an iterator.

use firims::BitSet;

let mut a = BitSet::<1, 6, usize>::from([1, 2, 3]);
a.extend(&[3, 4, 5]);

assert_eq!(a.len(), 5);
assert_eq!(a, [1, 2, 3, 4, 5].iter().collect());

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<const LOWER: usize, const UPPER: usize, T: Integer> Extend<T> for BitSet<LOWER, UPPER, T>

fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I)

Extends a BitSet<LOWER, UPPER, T> with the contents of an iterator.

use firims::BitSet;

let mut a = BitSet::<1, 6, usize>::from([1, 2, 3]);
a.extend([3, 4, 5]);

assert_eq!(a.len(), 5);
assert_eq!(a, [1, 2, 3, 4, 5].iter().collect());

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<const LOWER: usize, const UPPER: usize, const M: usize, T: Integer> From<[T; M]> for BitSet<LOWER, UPPER, T>

fn from(value: [T; M]) -> Self

Construct a BitSet<LOWER, UPPER, T> from an array of Ts.

use firims::BitSet;

let mut a = BitSet::<1, 6, usize>::from([1, 2, 3]);

assert_eq!(a.len(), 3);
assert_eq!(a, [1, 2, 3].iter().collect());

impl<'a, const LOWER: usize, const UPPER: usize, T: Integer> FromIterator<&'a T> for BitSet<LOWER, UPPER, T>

fn from_iter<I: IntoIterator<Item = &'a T>>(iter: I) -> Self

Construct a BitSet<LOWER, UPPER, T> from an iterator of &'a Ts.

use firims::BitSet;

let v = vec![1, 2, 3];
let a = BitSet::<1, 6, usize>::from_iter(v.iter());

assert_eq!(a.len(), 3);
assert_eq!(a, [1, 2, 3].iter().collect());

impl<const LOWER: usize, const UPPER: usize, T: Integer> FromIterator<T> for BitSet<LOWER, UPPER, T>

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

Construct a BitSet<LOWER, UPPER, T> from an iterator of Ts.

use firims::BitSet;

let v = vec![1, 2, 3];
let mut a = BitSet::<1, 6, usize>::from_iter(v.into_iter());

assert_eq!(a.len(), 3);
assert_eq!(a, [1, 2, 3].iter().collect());

impl<'a, const LOWER: usize, const UPPER: usize, T: Integer> IntoIterator for &'a BitSet<LOWER, UPPER, T>

fn into_iter(self) -> Self::IntoIter

A consuming iterator visiting all values of the set in ascending order.

use firims::BitSet;

let foo = BitSet::<2, 5, usize>::from([2, 4, 5]);
let foo_ref = &foo;

let mut iter = foo_ref.into_iter();
assert_eq!(iter.next(), Some(2));
assert_eq!(iter.next(), Some(4));
assert_eq!(iter.next(), Some(5));
assert_eq!(iter.next(), None);

type Item = T

The type of the elements being iterated over.

type IntoIter = Iter<'a, LOWER, UPPER, T>

Which kind of iterator are we turning this into?

impl<const LOWER: usize, const UPPER: usize, T: Integer> IntoIterator for BitSet<LOWER, UPPER, T>

fn into_iter(self) -> Self::IntoIter

A consuming iterator visiting all values of the set in ascending order.

use firims::BitSet;

let foo = BitSet::<2, 5, usize>::from([2, 4, 5]);

let mut iter = foo.into_iter();
assert_eq!(iter.next(), Some(2));
assert_eq!(iter.next(), Some(4));
assert_eq!(iter.next(), Some(5));
assert_eq!(iter.next(), None);

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<LOWER, UPPER, T>

Which kind of iterator are we turning this into?

impl<const LOWER: usize, const UPPER: usize, T: Integer + PartialEq> PartialEq for BitSet<LOWER, UPPER, T>

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

Compares two BitSets.

use firims::BitSet;

let a = BitSet::<1, 6, usize>::from([1, 2, 3]);
let b = BitSet::<1, 6, usize>::from([2, 3]);
let c = BitSet::<1, 6, usize>::from([1, 2, 3]);

assert!(a != b);
assert!(a == c);

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<const LOWER: usize, const UPPER: usize, T: Integer> Sub for &BitSet<LOWER, UPPER, T>

fn sub(self, rhs: &BitSet<LOWER, UPPER, T>) -> Self::Output

Returns the difference of self and rhs as a new BitSet<LOWER, UPPER, T>.

Current limitation: the generic parameters of the lhs and rhs need to the exact same.

use firims::BitSet;

let mut foo = BitSet::<2, 5, usize>::new();
foo.insert(2);
foo.insert(4);
foo.insert(5);

let mut bar = BitSet::<2, 5, usize>::new();
bar.insert(3);
bar.insert(4);

let baz = &foo - &bar;
assert_eq!(foo.len(), 3);
assert_eq!(bar.len(), 2);
assert_eq!(baz.len(), 2);

assert_eq!(baz.contains(&2), true);
assert_eq!(baz.contains(&3), false);
assert_eq!(baz.contains(&4), false);
assert_eq!(baz.contains(&5), true);

type Output = BitSet<LOWER, UPPER, T>

The resulting type after applying the - operator.

impl<const LOWER: usize, const UPPER: usize, T: Integer + Eq> Eq for &BitSet<LOWER, UPPER, T>

impl<const LOWER: usize, const UPPER: usize, T: Integer> RefUnwindSafe for BitSet<LOWER, UPPER, T>

impl<const LOWER: usize, const UPPER: usize, T: Integer> Send for BitSet<LOWER, UPPER, T>

impl<const LOWER: usize, const UPPER: usize, T: Integer> Sync for BitSet<LOWER, UPPER, T>

impl<const LOWER: usize, const UPPER: usize, T: Integer> UnwindSafe for BitSet<LOWER, UPPER, T>