Implement `SortedSet`, `SortedDictionary`

[lorentey]

OrderedSet and OrderedDictionary work great when we need to keep their elements in the order they were inserted, or if we only need to infrequently reorder/sort them. However, inserting (or removing) an element from the middle of the collection takes linear time in both cases, which makes these generic types less suitable for maintaining a sorted collection. It would be very much desirable for Swift developers to have access to efficient sorted collection types.

Self-balancing search trees naturally keep their elements sorted, and they implement efficient (O(log(n))) insertions and removals from anywhere in the collection -- so they seem an ideal choice for the implementation of a standard suite of sorted collections.

Binary search trees and similar low-fanout search tree variants (such as AVL trees or red-black trees) need to maintain a multitude of internal references, so they come with an inappropriately large memory overhead. High fanout search trees such as in-memory B-trees organize their elements into a tree of small contiguous buffers (up to a couple thousand items or so), and this makes them far more efficient in practice -- in terms of both space and time.

Unlike collections that store their elements in a single, contiguous buffer, tree-based collections also allow different versions of the same tree to share some of their storage, by simply referring to the same nodes within the tree. This makes them potentially more efficient than the existing standard collection types when implementing the copy-on-write optimization. (In B-tree's case, we can maintain a nice balance between lookup and CoW performance by having the inner nodes of the tree have a lower maximum fanout number than leaves.)

We'd like this package to implement a great set of sorted collection types based on an in-memory B-tree implementation.

struct SortedSet<Element: Comparable>: BidirectionalCollection, SetAlgebra {....}
struct SortedDictionary<Key: Comparable, Value> { ... }

struct SortedBag<Element: Comparable> { ... }
struct SortedMultimap<Key: Comparable, Value> { ... }

[codeman7]

Hey @lorentey have you kicked this work off? I'd love to contribute and help out if possible.

[Jeehut]

Just want to add that the types SortedSet and SortedDictionary would also allow for finally adding binary search to Swift. The API could look very familiar, but under the hoods it would be much faster by using binary search:

let sortedNumbers: SortedSet = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
if let firstMatchingIndex = sortedNumbers.index(where: { $0 > 5 }) {
  let firstMatch = sortedNumbers[firstMatchingIndex]
}

The index(where:) method would then include the binary search algorithm.

Also, @lorentey I don't quite understand why you're restricting adding sorted variants to Set and Dictionary only, I think Array deserves one just as much. The only reason there's no OrderedArray in this library is because Array is order by definition. But it's not sorted, so we should also have a SortedArray.

See also my own SortedArray implementation that I have been already using in production for years.

[kylemacomber]

I think the SortedBag that @lorentey mentions at the end of the issue would effectively be the same as a SortedArray. It's interesting to consider what the more approachable name is.

[Jeehut]

@kylemacomber I was already wondering what the SortedBag is supposed to mean. Never heard Bag as a type name before, maybe it's just me but I find it confusing. We should use known terms, I would say. Array seems an obvious one.

[lorentey]

"Bag" is a well-established name for a set that allows duplicates; it's less clinical sounding as "multiset", but that is definitely a viable name for it. (For what it's worth, multiset seems to be more popular these days; see e.g. Guava, LLVM, or Boost. However, contrast this with Eclipse, Apache Commons, and others. Knuth also prefers the term multiset, and that probably seals the deal for me. 😉)

At this early in the implementation stage though, I think it would probably be better to think about the abstract construct and the operations it would provide, rather than the exact name we would end up labeling it under.

(E.g., note that there is a distinction between a multiset that stores each individual duplicate, and one that merely counts duplicates. For a sorted collection intended to serve as a replacement for O(n^2) sorted array implementations, I expect we'd need the former variant.)

The word "array" has some strong connotations with random-access indexing to me. I don't know if I'd like to use the term SortedArray to mean anything other than an Array that is sorted. (And to be clear, I don't think adding a SortedArray in this sense would be a high priority for this package.)

<aside>(My problem with names for less universally established mathematical (or programming) concepts is the same as my problem with indentation styles and football clubs -- I find people tend to stick to whatever they got first exposed to, and they sometimes form overly strong attachments to them. This includes myself, of course.)</aside>

[codeman7]

What would the process generally look like for someone to contribute? Both from a personal aspect as well as from a professional one if possible?

[CTMacUser]

Just want to add that the types SortedSet and SortedDictionary would also allow for finally adding binary search to Swift.

That should probably be in the Algorithms library, so any collection that stores its elements in-order can take advantage of it, not just specific container types. (In fact, I think it has one right now, and I've proposed at least another in the past.)

[lorentey]

Provisionally putting on the 1.1.0 milestone. This may get bumped off if we take too much time on persistent collections, but let's assume otherwise for now.