Big pile of feature suggestions from usage

[thomcc]

Hi. I've recently used rangemap in a project which does a bunch of work with unicode character properties and data. My code is usually using maps and sets with keys of either u32 or a custom UChar type (due to the need to represent surrogates, and a few other reasons).

Anyway, here's a huge list of features I wanted or spent time looking for:

1. A way to negate/toggle/xor everything inside a provided range, mutably. I would use this to perform set complement, for example some_codepoint_set.negate(0..=char::MAX as u32) would be (similar to [^...] in a regex character class). In my case, I don't expect any overlap, so it's possible I can implement this using gaps() if I give up the restriction on it being in-place.

2. More generally, it would be nice to have the set operation iterators for union/intersection/difference/symmetric_difference, similar to what BTreeSet has here: https://doc.rust-lang.org/nightly/std/collections/btree_set/index.html. These should split/merge/remove ranges as appropriate. If making them iterators sucks too much, it'd be fine if they produced new sets, honestly.

3. A way to construct and extend sets from an iterator of T (or from (K, V) for the map types). This would take the user iterator and group into ranges opportunistically before inserting. In the relatively common case that the input is actually sorted already, this would avoid a lot of work (much more efficient than inserting one by one or from single-size ranges).

   Here's code I'm using to turn Iterator<u32> into Iterator<Range<u32>>, which opportunistically speeds things up if the u32s happen to be sorted (or at least nearby). You can have it if it's useful to you (although I suspect making it generic would change it): https://gist.github.com/thomcc/d739850062e483e703921a7633445eec (it might have bugs, but either I haven't found them, or I added them when cleaning it up to put it in a gist).

4. {RangeInclusiveSet,RangeSet}::contains_range, which would return true iff the specified range is a subrange of one of the existing ranges. This can be implemented currently using get and checking if the result range entirely covers what you want to query. I suspect a get_range that returns the range directly would be good too.

5. It would be nice if you implemented Debug for your iterator types. (I often use evcxr_repl to play around with libraries while I learn how to use them, and it's tedious to have to remember a .collect::<Vec<_>>() everywhere).

6. It would be nice if the functions which just perform lookup (at least) took impl RangeBounds rather than using the &RangeInclusive<T>/&Range<T>.

   In my code I use inclusive ranges everywhere, but avoid RangeInclusive wherever possible due to its terrible ergonomics, bigger size, and general weirdness. Instead, I have a custom range type (which implements RangeBounds) without those caveats.

7. Not sure if intentional: StepLite is not implemented for char (but Step from libcore is). I wouldn't have used it anyway, but I noticed this. If the omission is intentional, you should document it. (The surrogate gap makes char's a bit awkward here, so I could understand it being deliberate).

Anyway, in practice, the fact that I wasn't able to find a good way to perform set operations (1 and 2) means I was only able to move to this for the range maps, and had to keep my current (inversion-list-based) range set type.

Feel free to reach out to me on discord (zuurr) to talk about any of this.

Dverall despite all the suggestions, I like the crate. I wish I saw it sooner.

[ripytide]

(Disclaimer I'm very biased as the author). Have you looked at nodit which I think manages features 4 (called contains_entire_interval()) and 6, I'd be curious as to what your thoughts were as one of my initial goals in the project was to be more flexible (at the cost of verbosity) than this wonderful crate.

Feature 1 sounds very useful, if I were to implement it I'd probably build it by running gaps_trimmed()/gaps_untrimmed() and save the result in a vec followed by remove_overlapping() followed by inserting the saved vec of gaps back into the set.

I'm not sure feature 5 is possible in the general case as most iterators are lazy so you may need to collect() them before they look readable.

[jeffparsons]

@thomcc Hello 👋 and thanks for your detailed feedback!

First, to set expectations: I currently have very limited time to spare for rangemap right now ($LIFE), so I'm only likely to do bug fixes and very simple changes in the short term.

Some of your suggestions would be difficult to implement well without BTreeMap cursors, which are slowly maturing upstream. Once there's something that looks like it's likely to be stabilised, I plan to rewrite the internals of rangemap to use those. Initially I will focus on feature-parity with the existing implementation, and it will be gated behind a feature flag so as not to cause an unnecessary MSRV bump.

Once that's done, I'll be adding extra features again, and I'll be sure to work through your list. 😀