rose-bitsets

Crates.io	rose-bitsets
lib.rs	rose-bitsets
version	0.1.0-beta
created_at	2025-04-11 22:02:53.872174+00
updated_at	2025-04-11 23:30:08.75006+00
description	Small, fixed-size bitsets for storing integers/indices.
homepage
repository	https://github.com/RosieTheGhostie/rose-bitsets
max_upload_size
id	1630379
size	43,795

RoseTheGhost (RosieTheGhostie)

documentation

https://docs.rs/rose-bitsets/latest/

README

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¹
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²
mask_0_to_i
mask_i_to_N²
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³. 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);

Because operator overloading is achieved via traits, it isn't currently possible to use the overloads inside const contexts. ↩
The N is a placeholder for the set's capacity (e.g., 16 for a BitSet16). ↩ ↩²
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. ↩

Commit count: 15