bitvec
bitvec copied to clipboard
Add BitSet
Implements #171.
I was also interested in this, so, I decided to take the time to actually create a reasonable wrapper that fits well into the library. It borrows its API from the most similar existing structure in libstd, which is BTreeSet.
This is an "MVP" implementation, meaning that it offers an API that is still useful but missing a few operations that don't have implementations elsewhere in the crate. Specifically, it omits:
is_disjoint,is_subset,is_supersetchecks: I feel like these kinds of checks should probably have a mirrored API forBitSlicebefore they're implemented here. Specifically, some way of representing binary folds like(x & y).not_all()without allocating.Difference,SymmetricDifference,Intersection, andUnion: these also should have a similar API onBitSlice, except closer to(x & y).iter_ones()without allocatingIntoIterator: while iterators over references just useIterOnes, this would require anIterOnes-like iterator forBitBoxto be efficient.
I've added commented-out boilerplate for those omitted implementations so that someone who has the desire for them knows where to start. If this isn't reasonable to include in the released library, I'd be more than happy to remove them, but I figured I might as well include my work here.
The most relevant design decision here is that this is explicitly a wrapper around BitVec, which means it doesn't add affordances you'd get from something like BTreeSet which will precompute the number of elements in the set. This also means that you can freely access the underlying BitVec without disrupting any invariants.
That said, there is one "invariant" that is offered internally by utilities: in some cases, it's most useful to ensure that the set is "trimmed," i.e. the last bit is a one. Two sets can be compared by comparing their trimmed versions, which I call "shrunken" in the code since it lines up closer to the existing shrink_to_fit method. (Even though it's not quite the same.) I try to uphold this invariant in some of the methods (not leaving too much "slack" at the end of the set), but it's not explicitly required for the methods to work.