jackfirth / rebellion

A collection of core libraries for Racket
https://pkgs.racket-lang.org/package/rebellion
Apache License 2.0
80 stars 16 forks source link

Add sorted collections #501

Closed jackfirth closed 2 years ago

jackfirth commented 3 years ago

This is a work-in progress change that will add mutable and immutable sorted collections to Rebellion, including:

The immutable collections will also come with builders, which support the use case of building a collection up with many writes before any reads are performed (such as in a stream pipeline, e.g. (transduce numbers #:into (into-sorted-set natural<=>)). When created with builders, the immutable collections will not use a persistent representation under the hood to support constant-time random access and efficient iteration. Instead, the persistent representation will be created lazily the first time an immutable collection is used with the persistent update functions such as sorted-set-add. This combines the best of both worlds: use cases that don't need to interleave reads and writes get efficient random-access immutable collections, and use cases that do have their immutable collections upgraded to persistent collections automatically.

Lots of implementation work left to do. In particular, I still need to figure out how to represent subset views efficiently, especially for mutable collections. Also, the mutable collections won't be thread-safe but will provide fail-fast behavior on concurrent modification during iteration, like java's ConcurrentModificationException. This is too useful for detecting data races to ignore. In the future I may consider offering alternative thread-safe implementations, but the default mutable collection implementations won't change.

jackfirth commented 3 years ago

Remaining tasks for sorted sets:

jackfirth commented 2 years ago

I'm going to merge this as-is since it's already huge. All the basics for sorted sets are there sans detection of modification during iteration. I'll work on sorted maps next, since multisets, range sets, and range maps are all just views of sorted maps.