Fix syntax, add more stuff

[natecook1000]

This is the last revision, I promise!

• Fixes some incorrect syntax in the proposed APIs (e.g., Generator → Iterator)
• Adds two new APIs as customization points, Sequence._customContainsComparableElement(_:) and Collection._customIndexOfComparableElement(_:)
• Adds an example type that uses partitionedIndex(where:) to show how these proposed APIs are meeting the requested functionality
• Adds some justification for why I think the existing partition methods should go (do you all agree with this?)

Feedback? Questions? @j-haj @haravikk @lorenzoracca

[Haravikk]

About removal of the existing partition method(s), the only implementation I could find is under CollectionAlgorithms.swift.gyb, but there's so much going on in there that I have no idea what it does exactly, so my inclination is to rename the existing method(s) to something more obviously internal/implementation specific to avoid confusion.

The comments in there suggest that it work in a similar fashion to how the new partition method will work, albeit specifically intended to implement merge-sorting? But like I say, the .gyb file is pretty hard to parse through quickly so I may be misunderstanding it; if there's anything in there that can be a useful optimisation then it may be worth stealing from, but leaving it as an implementation detail of .sort is what I'd do I think. Hopefully someone who better understands it can weigh in, as if there's enough crossover it'd be nice to eliminate it entirely, but I can't really tell. I'll take another look later when I have more time.

[natecook1000]

The benefit of the existing partition method is that you don't need to start with an index. It basically moves elements forward and backward to make them partitioned relative to each other, then returns the partitioning index. Because you don't need an index at the start, it's useful when trying to sort a collection that doesn't have random-access indices. I don't think the sort method works with non-random-access collections anyway, and thinking about it more this version of partition might be the source of one the current sort's degenerate cases—adding new elements at the end of an already sorted array, then sorting again.

I definitely only meant that the current partition should move from public to internal—I'll clarify that in the proposal.

[natecook1000]

Huh, scratch that. The current partition is actually equivalent to the new partition called like this:

var a = Array(1...10)
// old:
a.partition()
// new (this was wrong):
// a.partition(where: { $0 < a.first! })
// new and correct:
if !a.isEmpty {
    let p = a.first!
    a.partition(where: { $0 < p })
}

Swift's capture semantics make this a little tricky, since a is mutating during the operation. This has unpredictable results, since a[0] might change during the course of partition:

a.partition(where: { $0 < a[0] })

[lorenzoracca]

Honestly, I think the old partition would be pretty much useless if we updated it with our new one.

IMHO it is relatively ineffective because I think that most lists still have random-access indices (making it a niche use), and as you specifically answered, the original version can still be implemented. Surely, it is tricky. Why don't we just propose to move the old one to internal and explain in the docs how to use the new partition to make it work as the current one?

At this point, we already changed enough that I don't think such a little change will be a problem. And by the way, I just looked at the future changes of Swift 3. To me, there are lots of bigger changes on the way.