Sorted Collection Protocol

[kareman (Kare Morstol)]

Nice, I implemented your suggestions here and it made the code a lot simpler.

1

@nnnnnnnn

It looks like only random-access collections are using a binary search for finding an element, with forward and bidirectional collections still using a linear search. I think you could try a binary search with these too, since while the index advancement will still be O(n), you only need to perform O(log n) comparisons, which can be a big savings.

I did this, but my implementation recalculates count for every slice, which will be expensive for non-random-access collections; I think there are ways around this though. We should probably run some benchmarks to see which implementation is most efficient. But we need an ordered non-random-access collection type, and the only ones I can think of in the Standard Library are String and it's views, and it doesn't make much sense to sort those like DefaultIndices<String>, though it doesn’t support duplicate elements.

2

@nnnnnnnn

I don’t think this extension is necessary:

extension SortedCollection where Element: Comparable {
    public var areInIncreasingOrder: (Element, Element) -> Bool {
        return (<)
    }
}

That would prevent Comparable elements from being stored in reverse order, or in an order other than their comparable-ness. Your simplified initializers for SortedArray, though, are great, since they let a user easily create a sorted array with the default order.

But a conforming type can override this, like SortedArray does. Or maybe it is better to require conforming types to explicitly implement this, instead of doing it automatically?

4

@nnnnnnnn

If you have a sorted collection type that can be inserted into, you can generally also remove elements, right? Would removal need to be a different protocol, or could those operations join insertion? Finally, if you can remove all the elements from a collection and add more, that collection probably supports initializing an empty version of itself — I think your SortedArray type would support all these operations.

I added remove methods to SortedArray (and it has an empty initialiser), but I think only methods that can take advantage of the fact that the elements are sorted belong in the SortedCollection and MutableSortedCollection protocols. Like remove(Element) and remove(all: Element).

Note: MutableSortedCollection probably needs a better name, as it is nothing like MutableCollection.