bitvec icon indicating copy to clipboard operation
bitvec copied to clipboard

Add BitSet

Open clarfonthey opened this issue 2 years ago • 0 comments
trafficstars

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_superset checks: I feel like these kinds of checks should probably have a mirrored API for BitSlice before they're implemented here. Specifically, some way of representing binary folds like (x & y).not_all() without allocating.
  • Difference, SymmetricDifference, Intersection, and Union: these also should have a similar API on BitSlice, except closer to (x & y).iter_ones() without allocating
  • IntoIterator: while iterators over references just use IterOnes, this would require an IterOnes-like iterator for BitBox to 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.

clarfonthey avatar Jul 26 '23 03:07 clarfonthey