Struct Bitset 

pub struct Bitset<const N: usize, Z = u8>(pub Z)
where
    Z: PosInt;

A set of bitflags representing positive integers in the range 1..=N.

For the rationale behind how this struct works, please visit the crate root.

Type Parameters

• N (required): The maximum integer represented by the set.
  • A Bitset<N, _> represents integers 1..=N, and will ignore integers outside this range.
• Z (optional): The unsigned integer type used to store the bitflags (e.g. u8, u16, usize).
  • Defaults to u8, which allows the set to represent integers 1..=256, which should be more than enough to cover most use cases.

Notes

• A subtle distinction is that Z dictates how many integers the bitset could represent, while N tells the struct and programmer how many it actually does represent.
• To optimise space efficiency, you should make Z as small as possible for your use case N.
  • However, if you make it too small such that it can’t represent integers up to N, you’ll likely encounter overflow errors caused by bitshifting.¹

Usage

Bitset is designed to be as ergonomic as possible. It does everything a HashSet<usize> could, while feeling like a 0b_xxxx_xxxx bitflag integer.

Instantiation

When instantiating a Bitset, you’ll need to specify N.²

// A bitset representing numbers 1..=3
let bitset = Bitset::<3>::from([1,2,3]);
 
// A bitset representing numbers 1..=8
let bitset = Bitset::<8>::from([1,2,3,4,5,6,7,8]);
// or more conveniently:
let bitset = Bitset::<8>::all();
// or even more conveniently:
let bitset = byteset![1;8];
 
// A bitset representing numbers 1..=1000 (need a larger `Z`!)
let bitset = Bitset::<1000, u16>::none();
 
// Or instantiate manually, passing the bit representation directly:
let bitset = Bitset::<4>(0b_0101);
let equiv  = Bitset::<4>::from([1,3]);
assert_eq!(bitset, equiv);

Access

To retrieve the integers the bitset represents, use .members():

use std::collections::HashSet;
 
let bitset = Bitset::<7>::from([1,3,7]);
let digits = bitset.members();
 
assert_eq!(digits, HashSet::from([1,3,7]));

Bitset<Z> implements Deref<Z>, so the underlying bits can easily be accessed by dereferencing through *bitset.

let mut bitset = Bitset::<8>(0b_0100_1010);
assert_eq!(*bitset, 0b_0100_1010);
 
*bitset += 1;
assert_eq!(*bitset, 0b_0100_1011)

Operations

The union, intersection, difference set operations can be accessed via the |, &, / operations, respectively.

let left = byteset![1,2,3];
let right = byteset![3,4,5];
 
assert_eq!(left | right, byteset![1;5]);
assert_eq!(left & right, byteset![3]);
assert_eq!(left / right, byteset![1,2]);

Add and remove individual elements via the + and - operators, respectively.

let mut bitset = byteset![1,2];
 
bitset += 3;
assert_eq!(bitset, byteset![1,2,3]);
 
bitset -= 1;
assert_eq!(bitset, byteset![2,3]);

---

1. This will hopefully be remedied in future. ↩

2. Unfortunately, N cannot be inferred from a collection even if we wanted to, since it’s a const generic. However, in future, a macro constructor could achieve this at compile time! ↩

Tuple Fields

0: Z

The underlying integer used to represent the set. When written in binary, each bit represents whether a number is present in the set (1 if present, 0 if not).

Access this integer by dereferencing a Bitset:

let bitset = Bitset::<4>(0b_1011);
let bits = *bitset;
assert_eq!(bits, 0b_1011);

Implementations

impl<Z, const N: usize> Bitset<N, Z>

where Z: PosInt,

pub fn none() -> Self

Construct a set with no bits enabled.

Usage

 
let off = Bitset::<4>::none();
assert_eq!(*off, 0b_0000);

pub fn all() -> Self

Construct a set with all bits enabled.

Usage

 
let off = Bitset::<4>::all();
assert_eq!(*off, 0b_1111);

impl<Z, const N: usize> Bitset<N, Z>

where Z: PosInt,

pub fn is_empty(&self) -> bool

Is the set empty?

pub fn is_single(&self) -> bool

Does the set contain only 1 element?

pub fn is_full(&self) -> bool

Is the set full? (i.e. it contains every integer in 1..=N)

pub fn len(&self) -> usize

How many integers are in the set?

pub fn members(&self) -> HashSet<usize>

Get the integers present in the set.

Usage

use std::collections::HashSet;
 
let bitset = byteset![1,3,7];
let nums = bitset.members();
 
assert_eq!(nums, HashSet::from([1,3,7]));

pub fn max(&self) -> Option<usize>

Get the maximum integer present in the set, or 0 if the set is empty.

assert_eq!(byteset![].max(),      None);
assert_eq!(byteset![1,2,6].max(), Some(6));

pub fn single(&self) -> Option<usize>

If the set contains only 1 element, return it in a Some(), else None.

This is more convenient and efficient than bitset.is_single().then_some(bitset.max().unwrap()).

Usage

assert_eq!( byteset![].single(),    None );
assert_eq!( byteset![1;8].single(), None );
assert_eq!( byteset![1].single(),   Some(1) );
assert_eq!( byteset![8].single(),   Some(8) );

impl<Z, const N: usize> Bitset<N, Z>

where Z: PosInt + Debug,

pub fn intersect_nonempty( &mut self, other: impl Into<Self>, ) -> Result<(), String>

Intersect self with other, returning an Err if the intersection is empty.

pub fn intersect_nonempty_panicking(&mut self, other: impl Into<Self>)

Intersect self with other, panicking with debug output if the resultant intersection is empty.

Trait Implementations

impl<Z, R, const N: usize> Add<R> for Bitset<N, Z>

where Z: PosInt, R: Into<Z>,

fn add(self, other: R) -> Self

Add an integer other to the set. Does nothing if other is not in the range 1..=N.

type Output = Bitset<N, Z>

The resulting type after applying the + operator.

impl<Z, R, const N: usize> AddAssign<R> for Bitset<N, Z>

where Z: PosInt, R: Into<Z>,

fn add_assign(&mut self, other: R)

Add an integer other to the set. Does nothing if other is not in the range 1..=N.

impl<Z, const N: usize> BitAnd for Bitset<N, Z>

where Z: PosInt,

type Output = Bitset<N, Z>

The resulting type after applying the & operator.

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

Performs the & operation.

impl<Z, const N: usize> BitAndAssign for Bitset<N, Z>

where Z: PosInt,

fn bitand_assign(&mut self, other: Self)

Performs the &= operation.

impl<Z, const N: usize> BitOr for Bitset<N, Z>

where Z: PosInt,

type Output = Bitset<N, Z>

The resulting type after applying the | operator.

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

Performs the | operation.

impl<Z, const N: usize> BitOrAssign for Bitset<N, Z>

where Z: PosInt,

fn bitor_assign(&mut self, other: Self)

Performs the |= operation.

impl<const N: usize, Z> Clone for Bitset<N, Z>

where Z: PosInt + Clone,

fn clone(&self) -> Bitset<N, Z>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<const N: usize, Z> Debug for Bitset<N, Z>

where Z: PosInt + Debug,

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

Formats the value using the given formatter.

impl<const N: usize, Z> Default for Bitset<N, Z>

where Z: PosInt + Default,

fn default() -> Bitset<N, Z>

Returns the “default value” for a type.

impl<Z, const N: usize> Deref for Bitset<N, Z>

where Z: PosInt,

type Target = Z

The resulting type after dereferencing.

fn deref(&self) -> &Self::Target

Dereferences the value.

impl<Z, const N: usize> DerefMut for Bitset<N, Z>

where Z: PosInt,

fn deref_mut(&mut self) -> &mut Z

Mutably dereferences the value.

impl<Z, const N: usize> Div for Bitset<N, Z>

where Z: PosInt,

type Output = Bitset<N, Z>

The resulting type after applying the / operator.

fn div(self, other: Self) -> Self::Output

Performs the / operation.

impl<Z, const N: usize> DivAssign for Bitset<N, Z>

where Z: PosInt,

fn div_assign(&mut self, other: Self)

Performs the /= operation.

impl<Z, T, const N: usize, const M: usize> From<[T; M]> for Bitset<N, Z>

where Z: PosInt, T: AnyInt,

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

Converts to this type from the input type.

impl<Z, T, const N: usize> FromIterator<T> for Bitset<N, Z>

where Z: PosInt, T: AnyInt,

fn from_iter<I>(iter: I) -> Self

where I: IntoIterator<Item = T>,

Construct a Bitset from an iterator of integers, accepting only those in 1..=N and ignoring others.

impl<Z, const N: usize> IntoIterator for Bitset<N, Z>

where Z: PosInt,

type Item = usize

The type of the elements being iterated over.

type IntoIter = BitsetIterator<N, Z>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<const N: usize, Z> PartialEq for Bitset<N, Z>

where Z: PosInt + PartialEq,

fn eq(&self, other: &Bitset<N, Z>) -> 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<Z, R, const N: usize> Sub<R> for Bitset<N, Z>

where Z: PosInt, R: Into<Z>,

fn sub(self, other: R) -> Self

Remove an integer other from the set. Does nothing if other is not in the range 1..=N.

type Output = Bitset<N, Z>

The resulting type after applying the - operator.

impl<Z, R, const N: usize> SubAssign<R> for Bitset<N, Z>

where Z: PosInt, R: Into<Z>,

fn sub_assign(&mut self, other: R)

Remove an integer other from the set. Does nothing if other is not in the range 1..=N.

impl<const N: usize, Z> Copy for Bitset<N, Z>

where Z: PosInt + Copy,

impl<const N: usize, Z> Eq for Bitset<N, Z>

where Z: PosInt + Eq,

impl<const N: usize, Z> StructuralPartialEq for Bitset<N, Z>

where Z: PosInt,