Struct BitSet 

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

This type represents a fixed-size bit set.

It is implemented as a wrapper around an array of primitive integers. Each bit in the array represents the presence or absence of an element in the set.

This type is #![repr(transparent)] and guaranteed to have the same memory representation as the inner bit array.

Type Parameters

• T: The primitive integer type used to store the bits. It must be a primitive integer.
• N: The number of elements of type T in the inner array representation.

This allows the user of the type to choose the best combination for their use-case.

Capacity

The total capacity of the BitSet (i.e., the maximum value that can be stored) is determined by the chosen T and N by the formula N * size_of::<T>() * 8. For example:

• BitSet<u8, 1> has a capacity of 8 bits.
• BitSet<u64, 4> has a capacity of 256 bits.

Type alias

This crate also provides several type alias for this type with the most common capacity usages, with the optimal choices of T and N for the most common targets.

Panics

All non-try functions taking a bit parameter panics if the bit is bigger than the capacity of the set. For non-panicking versions, use try_.

Implementations

impl<const N: usize> BitSet<i8, N>

pub const fn new() -> Self

Create an empty instance of BitSet.

Examples

use rbitset::BitSet;

let set = BitSet::<u8, 1>::new();

impl<const N: usize> BitSet<i16, N>

pub const fn new() -> Self

Create an empty instance of BitSet.

Examples

use rbitset::BitSet;

let set = BitSet::<u8, 1>::new();

impl<const N: usize> BitSet<i32, N>

pub const fn new() -> Self

Create an empty instance of BitSet.

Examples

use rbitset::BitSet;

let set = BitSet::<u8, 1>::new();

impl<const N: usize> BitSet<i64, N>

pub const fn new() -> Self

Create an empty instance of BitSet.

Examples

use rbitset::BitSet;

let set = BitSet::<u8, 1>::new();

impl<const N: usize> BitSet<i128, N>

pub const fn new() -> Self

Create an empty instance of BitSet.

Examples

use rbitset::BitSet;

let set = BitSet::<u8, 1>::new();

impl<const N: usize> BitSet<isize, N>

pub const fn new() -> Self

Create an empty instance of BitSet.

Examples

use rbitset::BitSet;

let set = BitSet::<u8, 1>::new();

impl<const N: usize> BitSet<u8, N>

pub const fn new() -> Self

Create an empty instance of BitSet.

Examples

use rbitset::BitSet;

let set = BitSet::<u8, 1>::new();

impl<const N: usize> BitSet<u16, N>

pub const fn new() -> Self

Create an empty instance of BitSet.

Examples

use rbitset::BitSet;

let set = BitSet::<u8, 1>::new();

impl<const N: usize> BitSet<u32, N>

pub const fn new() -> Self

Create an empty instance of BitSet.

Examples

use rbitset::BitSet;

let set = BitSet::<u8, 1>::new();

impl<const N: usize> BitSet<u64, N>

pub const fn new() -> Self

Create an empty instance of BitSet.

Examples

use rbitset::BitSet;

let set = BitSet::<u8, 1>::new();

Examples found in repository

examples/strspn.rs (line 23)

fn strspn(s: &[u8], accept: &[u8]) -> usize {
    let mut allow = BitSet256::new();

    for &c in accept {
        allow.insert(c as usize);
    }

    for (i, &c) in s.iter().enumerate() {
        if !allow.contains(c as usize) {
            return i;
        }
    }
    s.len()
}

impl<const N: usize> BitSet<u128, N>

pub const fn new() -> Self

Create an empty instance of BitSet.

Examples

use rbitset::BitSet;

let set = BitSet::<u8, 1>::new();

impl<const N: usize> BitSet<usize, N>

pub const fn new() -> Self

Create an empty instance of BitSet.

Examples

use rbitset::BitSet;

let set = BitSet::<u8, 1>::new();

impl<T: PrimInt + Default, const N: usize> BitSet<T, N>

pub fn with_default() -> Self

Create an empty instance with default value.

This function is the same as new but without the constness.

Examples

use rbitset::BitSet;

let set = BitSet::<u32, 7>::new();

pub fn clear(&mut self)

Clears the set, disabling all bits, removing all elements.

Probably faster than what fill(.., false) would be.

Examples

use rbitset::BitSet8;

let mut set = BitSet8::new();
set.insert(1);
assert!(!set.is_empty());
set.clear();
assert!(set.is_empty());

impl<T, const N: usize> BitSet<T, N>

pub fn into_inner(self) -> [T; N]

Return the inner integer array.

Examples

use rbitset::BitSet8;

let set = BitSet8::from_iter([1u8, 2, 3]);
assert_eq!(set.into_inner(), [0b00001110]);

pub const fn capacity() -> usize

Returns the capacity of the set, in other words how many bits it can hold.

This function may very well overflow if the size or length is too big, but if you’re making that big allocations you probably got bigger things to worry about.

Examples

use rbitset::BitSet;

let capacity = BitSet::<u32, 3>::capacity();
assert_eq!(capacity, 32 * 3);

pub const fn from_ref(inner: &mut [T; N]) -> &mut Self

Transmutes a reference to a borrowed bit array to a borrowed BitSet with the same lifetime.

Examples

use rbitset::BitSet;

let mut raw = [0b00001110, 0u8];
let set = BitSet::from_ref(&mut raw);
assert!(set.contains(1));
assert!(set.contains(2));
assert!(set.contains(3));

impl<T: PrimInt, const N: usize> BitSet<T, N>

pub fn try_append<U, const M: usize>( &mut self, other: &mut BitSet<U, M>, ) -> Result<(), BitSetError>

where U: PrimInt,

Tries to move all elements from other into self, leaving other empty.

Examples

use rbitset::BitSet16;

let mut a = BitSet16::new();
a.insert(1);
a.insert(2);
a.insert(3);

let mut b = BitSet16::new();
b.insert(3);
b.insert(4);
b.insert(5);

a.try_append(&mut b).expect("An error occurred");

assert_eq!(a.len(), 5);
assert_eq!(b.len(), 0);

assert!(a.contains(1));
assert!(a.contains(2));
assert!(a.contains(3));
assert!(a.contains(4));
assert!(a.contains(5));

pub fn try_insert(&mut self, bit: usize) -> Result<bool, BitSetError>

Tries to add a value to the set.

If the set did not have this value present, true is returned.

If the set did have this value present, false is returned.

Examples

use rbitset::{BitSet16, BitSetError};

let mut set = BitSet16::new();

assert_eq!(set.try_insert(2), Ok(true));
assert_eq!(set.try_insert(2), Ok(false));
assert_eq!(set.try_insert(16), Err(BitSetError::BiggerThanCapacity));

pub unsafe fn insert_unchecked(&mut self, bit: usize) -> bool

Inserts a value to the set without making any checks.

If the set did not have this value present, true is returned.

If the set did have this value present, false is returned.

Safety

Behavior is undefined if any of the following conditions are violated:

• The bit value is bigger than the capacity of the bitset

pub fn try_remove(&mut self, bit: usize) -> Result<bool, BitSetError>

Removes a value from the set. Returns whether the value was present in the set.

If the bit is already disabled this is a no-op.

Examples

use rbitset::BitSet8;

let mut set = BitSet8::new();

set.insert(2);
assert_eq!(set.remove(2), true);
assert_eq!(set.remove(2), false);

pub unsafe fn remove_unchecked(&mut self, bit: usize) -> bool

Removes a value from the set without any checking. Returns whether the value was present in the set.

If the bit is already disabled this is a no-op.

Safety

Behavior is undefined if any of the following conditions are violated:

• The bit value is bigger than the capacity of the bitset

pub fn append<U, const M: usize>(&mut self, other: &mut BitSet<U, M>)

where U: PrimInt,

Move all elements from other into self, leaving other empty.

Panics

This function may panic if other contains activated bits bigger than what self capacity. Check try_append for a non-panicking version.

Examples

use rbitset::BitSet16;

let mut a = BitSet16::new();
a.insert(1);
a.insert(2);
a.insert(3);

let mut b = BitSet16::new();
b.insert(3);
b.insert(4);
b.insert(5);

a.append(&mut b);

assert_eq!(a.len(), 5);
assert_eq!(b.len(), 0);

assert!(a.contains(1));
assert!(a.contains(2));
assert!(a.contains(3));
assert!(a.contains(4));
assert!(a.contains(5));

pub fn insert(&mut self, bit: usize) -> bool

Adds a value to the set.

If the set did not have this value present, true is returned.

If the set did have this value present, false is returned.

Panics

This function may panic if bit value trying to be inserted is bigger than the capacity of the BitSet. Check try_insert for a non-panicking version.

Examples

use rbitset::BitSet16;

let mut set = BitSet16::new();

assert_eq!(set.insert(2), true);
assert_eq!(set.insert(2), false);
assert_eq!(set.len(), 1);

Examples found in repository

examples/strspn.rs (line 26)

fn strspn(s: &[u8], accept: &[u8]) -> usize {
    let mut allow = BitSet256::new();

    for &c in accept {
        allow.insert(c as usize);
    }

    for (i, &c) in s.iter().enumerate() {
        if !allow.contains(c as usize) {
            return i;
        }
    }
    s.len()
}

pub fn remove(&mut self, bit: usize) -> bool

Removes a value from the set. Returns whether the value was present in the set.

If the bit is already disabled this is a no-op.

Panics

This function may panic if bit value trying to be removed is bigger than the capacity of the BitSet. Check try_remove for a non-panicking version.

Examples

use rbitset::BitSet8;

let mut set = BitSet8::new();

set.insert(2);
assert_eq!(set.remove(2), true);
assert_eq!(set.remove(2), false);

pub fn retain<F>(&mut self, f: F)

where F: FnMut(usize) -> bool,

Retains only the elements specified by the predicate.

In other words, remove all elements e for which f(&e) returns false. The elements are visited in ascending order.

Examples

use rbitset::BitSet16;

let mut set = BitSet16::from_iter([1u8, 2, 3, 4, 5, 6]);
// Keep only the even numbers.
set.retain(|k| k % 2 == 0);
let res = BitSet16::from_iter([2u8, 4, 6]);
assert_eq!(set, res);

pub fn contains(&self, bit: usize) -> bool

Returns true if the specified bit is enabled, in other words, if the set contains a value.

Examples

use rbitset::BitSet8;

let set = BitSet8::from_iter([1u8, 2, 3]);
assert_eq!(set.contains(1), true);
assert_eq!(set.contains(4), false);

Examples found in repository

examples/strspn.rs (line 30)

fn strspn(s: &[u8], accept: &[u8]) -> usize {
    let mut allow = BitSet256::new();

    for &c in accept {
        allow.insert(c as usize);
    }

    for (i, &c) in s.iter().enumerate() {
        if !allow.contains(c as usize) {
            return i;
        }
    }
    s.len()
}

pub fn try_contains(&self, bit: usize) -> Result<bool, BitSetError>

Returns true if the specified bit is enabled, in other words, if the set contains a value.

Examples

use rbitset::BitSet8;

let set = BitSet8::from_iter([1u8, 2, 3]);
assert_eq!(set.try_contains(1), Ok(true));
assert_eq!(set.try_contains(4), Ok(false));

pub fn len(&self) -> usize

Returns the number of elements in the set.

Examples

use rbitset::BitSet16;

let mut set = BitSet16::new();
assert_eq!(set.len(), 0);
set.insert(1);
assert_eq!(set.len(), 1);

pub fn is_empty(&self) -> bool

Returns true if the set contains no elements.

Examples

use rbitset::BitSet16;

let mut set = BitSet16::new();
assert!(set.is_empty());
set.insert(1);
assert!(!set.is_empty());

pub fn is_disjoint<U: PrimInt, const M: usize>( &self, other: &BitSet<U, M>, ) -> bool

Returns true if self has no elements in common with other. This is equivalent to checking for an empty intersection.

Examples

use rbitset::BitSet128;

let a = BitSet128::from_iter([1u8, 2, 3]);
let mut b = BitSet128::new();

assert!(a.is_disjoint(&b));
b.insert(4);
assert!(a.is_disjoint(&b));
b.insert(1);
assert!(!a.is_disjoint(&b));

pub fn is_subset<U: PrimInt, const M: usize>( &self, other: &BitSet<U, M>, ) -> bool

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

Examples

use rbitset::BitSet8;

let sup = BitSet8::from_iter([1u8, 2, 3]);
let mut set = BitSet8::new();

assert!(set.is_subset(&sup));
set.insert(2);
assert!(set.is_subset(&sup));
set.insert(4);
assert!(!set.is_subset(&sup));

pub fn is_superset<U: PrimInt, const M: usize>( &self, other: &BitSet<U, M>, ) -> bool

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

Examples

use rbitset::BitSet8;

let sub = BitSet8::from_iter([1u8, 2]);
let mut set = BitSet8::new();

assert!(!set.is_superset(&sub));

set.insert(0);
set.insert(1);
assert!(!set.is_superset(&sub));

set.insert(2);
assert!(set.is_superset(&sub));

pub fn count_ones(&self) -> u32

Returns the total number of enabled bits.

Examples

use rbitset::BitSet8;

let set = BitSet8::from_iter([1u8, 2, 3]);
assert_eq!(set.count_ones(), 3);

pub fn count_zeros(&self) -> u32

Returns the total number of disabled bits.

Examples

use rbitset::BitSet8;

let set = BitSet8::from_iter([1u8, 2, 3]);
assert_eq!(set.count_zeros(), 5);

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

Clears the set, returning all elements as an iterator. Keeps the allocated memory for reuse.

If the returned iterator is dropped before being fully consumed, it drops the remaining elements. The returned iterator keeps a mutable borrow on the vector to optimize its implementation.

Examples

use rbitset::BitSet8;

let mut set = BitSet8::from_iter([1u8, 2, 3]);
assert!(!set.is_empty());

for i in set.drain() {
    println!("{i}");
}

assert!(set.is_empty());

pub fn difference<'a, U: PrimInt, const M: usize>( &'a self, other: &'a BitSet<U, M>, ) -> Difference<'a, T, U, N, M>

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

Examples

use rbitset::BitSet8;

let a = BitSet8::from_iter([1u8, 2, 3]);
let b = BitSet8::from_iter([4u8, 2, 3, 4]);

// Can be seen as `a - b`.
for x in a.difference(&b) {
    println!("{x}"); // Print 1
}

let diff: BitSet8 = a.difference(&b).collect();
let res = BitSet8::from_iter([1u8]);
assert_eq!(diff, res);

// Note that difference is not symmetric,
// and `b - a` means something else:
let diff: BitSet8 = b.difference(&a).collect();
let res = BitSet8::from_iter([4u8]);
assert_eq!(diff, res);

pub fn intersection<'a, U: PrimInt, const M: usize>( &'a self, other: &'a BitSet<U, M>, ) -> Intersection<'a, T, U, N, M>

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

Examples

use rbitset::BitSet8;

let a = BitSet8::from_iter([1u8, 2, 3]);
let b = BitSet8::from_iter([4u8, 2, 3, 4]);

for x in a.intersection(&b) {
    println!("{x}");
}

let intersection: BitSet8 = a.intersection(&b).collect();
let test = BitSet8::from_iter([2u8, 3]);
assert_eq!(intersection, test);

pub fn symmetric_difference<'a, U: PrimInt, const M: usize>( &'a self, other: &'a BitSet<U, M>, ) -> SymmetricDifference<'a, T, U, N, M>

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

Examples

use rbitset::BitSet8;

let a = BitSet8::from_iter([1u8, 2, 3]);
let b = BitSet8::from_iter([4u8, 2, 3, 4]);

for x in a.symmetric_difference(&b) {
    println!("{x}");
}

let diff1: BitSet8 = a.symmetric_difference(&b).collect();
let diff2: BitSet8 = b.symmetric_difference(&a).collect();

assert_eq!(diff1, diff2);
let res = BitSet8::from_iter([1u8, 4]);
assert_eq!(diff1, res);

pub fn union<'a, U: PrimInt, const M: usize>( &'a self, other: &'a BitSet<U, M>, ) -> Union<'a, T, U, N, M>

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

Examples

use rbitset::BitSet8;

let a = BitSet8::from_iter([1u8, 2, 3]);
let b = BitSet8::from_iter([4u8, 2, 3, 4]);

for x in a.union(&b) {
    println!("{x}");
}

let union: BitSet8 = a.union(&b).collect();
let res = BitSet8::from_iter([1u8, 2, 3, 4]);
assert_eq!(union, res);

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

An iterator visiting all elements in the set.

Examples

use rbitset::BitSet8;

let mut set = BitSet8::new();
set.insert(1);
set.insert(2);

for x in set.iter() {
    println!("{x}");
}

impl<T: Default + PrimInt, const N: usize> BitSet<T, N>

pub fn fill<R: RangeBounds<usize>>(&mut self, range: R, on: bool)

Set all bits in a range.

fill(.., false) is effectively the same as clear().

Panics

Panics if the start or end bounds are more than the capacity.

Trait Implementations

impl<T, const N: usize> Binary for BitSet<T, N>

where T: Copy + Binary,

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

Formats the value using the given formatter.

impl<T: Clone, const N: usize> Clone for BitSet<T, N>

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

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T, const N: usize> Debug for BitSet<T, N>

where T: PrimInt,

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

Formats the bitset as a set of the bits that are currently set.

For the binary output of the structure, you can use the binary formatting ({:b} or {:#b}).

impl<T: PrimInt + Default, const N: usize> Default for BitSet<T, N>

fn default() -> Self

Returns the “default value” for a type.

impl<'de, T: PrimInt + Default, const N: usize> Deserialize<'de> for BitSet<T, N>

Available on crate feature serde only.

fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>

where D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<T: PrimInt, U: Into<usize>, const N: usize> Extend<U> for BitSet<T, N>

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

Extends a collection with the contents of an iterator.

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<T: PrimInt, const N: usize> From<[T; N]> for BitSet<T, N>

fn from(inner: [T; N]) -> Self

Converts to this type from the input type.

impl<T: PrimInt + Default, U: Into<usize>, const N: usize> FromIterator<U> for BitSet<T, N>

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

where I: IntoIterator<Item = U>,

Creates a value from an iterator.

impl<'a, T: PrimInt, const N: usize> IntoIterator for &'a BitSet<T, N>

type IntoIter = Iter<'a, T, N>

Which kind of iterator are we turning this into?

type Item = usize

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T: PrimInt, const N: usize> IntoIterator for BitSet<T, N>

type IntoIter = IntoIter<T, N>

Which kind of iterator are we turning this into?

type Item = usize

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T: PrimInt, const N: usize> Not for BitSet<T, N>

type Output = BitSet<T, N>

The resulting type after applying the ! operator.

fn not(self) -> Self::Output

Performs the unary ! operation.

impl<T: PartialEq, const N: usize> PartialEq for BitSet<T, N>

fn eq(&self, other: &BitSet<T, N>) -> 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: PrimInt, const N: usize> Serialize for BitSet<T, N>

Available on crate feature serde only.

fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>

where S: Serializer,

Serialize this value into the given Serde serializer.

impl<T: Copy, const N: usize> Copy for BitSet<T, N>

impl<T: Eq, const N: usize> Eq for BitSet<T, N>

impl<T, const N: usize> StructuralPartialEq for BitSet<T, N>