Feature Request: BitSet wrapper for BitVec

[bjchambers]

I believe that BitVec provides all the necessary functionality to implement a BitSet wrapper, in a way that would be reasonably convenient.

• Inserting an element -- resize (inserting 0) if needed to grow the array, then set the index to 1.
• Contains -- check to see if the index is 1
• Iterator -- iter_ones
• Union / Intersection -- use existing BitAnd and BitOr implementations

The main thing it would provide is a way to use BitVec as a set without needing to explicitly manage the length.

Does this seem like a worthwhile addition (at least behind a feature flag)?

Right now I use bitvec for vectors and bit-set (https://crates.io/crates/bit-set) for the set operations, which then means I also depend (transitively) on bit-vec. The latter two seem less maintained, so it would be nice to have a single standard crate for both vector and set-like operations.

[myrrlyn]

If I'm reading this correctly, the only missing API is the resizing insert? Contains is .get(idx).unwrap_or(false), .iter_ones() and the Boolean arithmetic traits work as described.

To your favor, I have already extended the BitSlice API to include bit-set functions. Arbitrary insertion could be done as simply as

impl<T, O> BitVec<T, O> where T: BitStore, O: BitOrder {
  pub fn reallocating_insert(&mut self, idx: usize, value: bool) {
    if self.len() <= idx {
      // ensure that `idx` itself is allocated
      self.resize(idx + 1, false);
    }
    self.set(idx, value);
  }
}

If you'd like to try this out in a patched fork and see if it works for you, I'd be willing to accept a PR if you want the contribution credit, or I can just put it in the upcoming 1.1 myself.

[bjchambers]

I think that would be a good start. The other things that could be useful in this direction:

• A version of reallocating_insert that takes Iterator<Item = usize>. That could be useful to (possibly) do the reallocation once, although I guess that would need to know the upper bound, so may be not possible (unless the iterator was sorted or something).
• A struct that wrapped BitVec and implemented a BitSet like interface (contains, insert, etc.). But -- that could also be implemented for each use if needed.

Looking at the method, I do believe it would help with my use case.

[bjchambers]

It may also need additional functionality for things like union and intersect. Looking deeper, the BitAnd and BitOr seem to truncate the length to the first set, rather then resizing.