Crate rose_bitsets

Expand description

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. ↩

Structs§

Ascending: An iteration order that starts with the smallest end/items and ends with the largest.
BitSet8b8: A set of 8 bits.
BitSet16b16: A set of 16 bits.
BitSet32b32: A set of 32 bits.
BitSet64b64: A set of 64 bits.
BitSet128b128: A set of 128 bits.
BitSetIndices8b8: An iterator over the indices of the bits that are set in a BitSet8.
BitSetIndices16b16: An iterator over the indices of the bits that are set in a BitSet16.
BitSetIndices32b32: An iterator over the indices of the bits that are set in a BitSet32.
BitSetIndices64b64: An iterator over the indices of the bits that are set in a BitSet64.
BitSetIndices128b128: An iterator over the indices of the bits that are set in a BitSet128.
BitSetIndicesSizebSize: An iterator over the indices of the bits that are set in a BitSetSize.
BitSetIter8b8: An iterator over the bits of a BitSet8.
BitSetIter16b16: An iterator over the bits of a BitSet16.
BitSetIter32b32: An iterator over the bits of a BitSet32.
BitSetIter64b64: An iterator over the bits of a BitSet64.
BitSetIter128b128: An iterator over the bits of a BitSet128.
BitSetIterSizebSize: An iterator over the bits of a BitSetSize.
BitSetSizebsize: A bitset the length of a pointer.
Descending: An iteration order that starts with the largest end/items and ends with the smallest.