2 releases

Uses new Rust 2024

new 0.1.0-beta	Apr 11, 2025

#332 in Math

25 downloads per month

MIT license

33KB
421 lines

Small, fixed-size bitsets for storing integers/indices.

Provides up to six bitset types, one for each primitive unsigned integer. These types are:

Type	Underlying Type	Feature	Enabled by Default?
`BitSet8`	`u8`	b8	✓
`BitSet16`	`u16`	b16	✓
`BitSet32`	`u32`	b32	✓
`BitSet64`	`u64`	b64	✓
`BitSet128`	`u128`	b128	✗
`BitSetSize`	`usize`	bsize	✗

Operations

All the following operations are designed to be...

fast: 𝒪(1) time complexity
memory-efficient: 𝒪(1) space complexity
intuitive: similar interface to std::collections::HashSet
const-friendly: usable inside const contexts[^1]
safe: no unsafe code

The Fundamentals

The following operators are fundamental enough to set theory that they warrant operator overloads.

Math	Method Call	Overloaded Operators
𝐴^𝑐	`a.complement()`	`Neg::neg` (`-a`) `Not::not` (`!a`)
𝐴 ∩ 𝐵	`a.intersection(b)`	`BitAnd::bitand` (`a & b`)
𝐴 ∪ 𝐵	`a.union(b)`	`BitOr::bitor` (`a \| b`)
𝐴 ∖ 𝐵	`a.difference(b)`	`Sub::sub` (`a - b`)
𝐴 Δ 𝐵	`a.symmetric_difference(b)`	`BitXor::bitxor` (`a ^ b`)
𝐴 = 𝐵	`a.is(b)`	`PartialEq::eq` (`a == b`)
𝐴 ≠ 𝐵	`a.is_not(b)`	`PartialEq::ne` (`a != b`)

Comparisons and Bitset Metadata

Bitsets support a variety of comparison operators. Though they aren't similar enough to methods in core::cmp::PartialOrd to warrant operator overloads, they are still very useful tools for working with sets.

Metadata-like methods (e.g., len) are lumped in with the comparisons because it is sometimes hard to draw a line between them.

Math	Method Calls
𝐴 ∩ 𝐵 = ∅	`a.is_disjoint(b)`
𝐴 ⊆ 𝐵	`a.is_subset(b)`
𝐴 ⊂ 𝐵	`a.is_strict_subset(b)`
𝐴 ⊇ 𝐵	`a.is_superset(b)`
𝐴 ⊃ 𝐵	`a.is_strict_superset(b)`
𝐴 = ∅	`a.is_empty()`
𝐴 = 𝑈	`a.is_full()`
\|𝐴\|	`a.len()`
𝑥 ∈ 𝐴	`a.contains(x)`
min(𝐴)	`a.min_index()`
max(𝐴)	`a.max_index()` `a.max_index_checked()`

Miscellaneous

These don't have a direct connection to set theory, but they are nice to have when working with bitsets.

Math	Method Calls
{ 𝑥 ∈ 𝐴 \| 𝑥 < 𝑖 }	`a.masked_0_to_i(i)` `a.cleared_i_to_N(i)` ²
{ 𝑥 ∈ 𝐴 \| 𝑥 ≥ 𝑖 }	`a.masked_i_to_N(i)` ² `a.cleared_0_to_i(i)`

Modification Methods

Because bitsets are meant to act like sets, they share many methods with std::collections::HashSet. Some have been added as well for those who like to aggressively optimize their code.

clear
clear_0_to_i
clear_i_to_N[^2]
mask_0_to_i
mask_i_to_N[^2]
insert
insert_quiet
replace
replace_quiet
remove
remove_quiet

Iteration

Each bitset also comes with two kinds of iterators:

BitSetIndices: Iterates over the indices of the enabled bits.
BitSetIter: Iterates over the values of all bits.

Both iterators can be used to traverse a set in either direction[^3]. For example, the following code would iterate over the indices in ascending order:

use rose_bitsets::{Ascending, BitSet8};

let set = BitSet8::from_bits(0b00101110);
let mut indices = set.iter_indices::<Ascending>();

assert_eq!(indices.next(), Some(1));
assert_eq!(indices.next(), Some(2));
assert_eq!(indices.next(), Some(3));
assert_eq!(indices.next(), Some(5));
assert_eq!(indices.next(), None);

[^1]: Because operator overloading is achieved via traits, it isn't currently possible to use the overloads inside const contexts. [^2]: The N is a placeholder for the set's capacity (e.g., 16 for a BitSet16). [^3]: By direction, I mean whether the significance increases or decreases as the iteration progresses. The Ascending mode iterates starting from the least significant end and works towards the most significant, whereas the Descending mode iterates starting from the most significant end and works towards the least significant.

Dependencies

~140KB