SE-0270 (fourth review): Add Collection operations on noncontiguous elements

[Karl]

@nnnnnnnn

The thing that makes RangeSet different is that it enables a group of operations that apply across many different collection types. That makes it akin to the group of range types that are already in the standard library, in addition to the use cases where it can be useful as a standalone data structure on its own.

Yeah, what I mean by this is that there are 3 options:

1. Put it in swift-collections, alongside other non-core but still very useful collection types.
2. Put it in the standard library's core module.
3. Put it in the standard library, in a non-core module.

And I think there are reasonable arguments for each of them.

With regards to option 3, I believe @lorentey (who I'll ask to please correct me if I'm misremembering) has expressed a desire that many (if not all?) data structures currently in the swift-collections package migrate to the standard library eventually.

I would presume, given our recent trend of separating the standard library in to explicitly import-ed submodules, that those collections would also go in some kind of submodule. Maybe we should consider RangeSet the first of these collections, and namespace it in a submodule.

Or will we go the other way and put everything in to the core standard library? Including Deque, Heap, OrderedDictionary, SortedDictionary, TreeDictionary, etc?

I think it is worth considering where the line between the "core" and "non-core" standard library is, and where RangeSet fits on that spectrum. I'm not sure that offering generic operations/extensions is quite enough to say that it is obviously a "core" data type; it offers some neat functionality, but lots of generic algorithms and data-structures are able to offer neat functionality for any base collection type.

@nnnnnnnn

Your SegmentedLine type certainly looks useful! I don't think there's anything in this proposal that would prohibit consideration of a range-based dictionary as an addition to the standard library or another package.

I hope I've illustrated that there are other, useful, range-based data structures which we may be interested in providing. That's really what the goal was.

The idea is that, if we view RangeSet as being but one member of a family of range-based data structures, that may inform the choice about whether it is namespaced in a submodule.

[John_McCall]

SE-0270 has been accepted. Thank you all for participated in the review; if you have further questions or comments, please continue them in that thread.

John McCall
Review Manager