[swift-evolution] [Proposal] Add .order() family of methods to Collection

[Dave Abrahams]

on Mon Apr 11 2016, Taras Zakharko <swift-evolution at swift.org> wrote:

> Hi, 
>
> I think it depends on how expensive the indexed access is on the collection. I
> use it primarily on arrays, where self[i] essentially boils down to a pointer
> dereference, so I expect the generated code to be very efficient. Your version
> might be faster for collection with expensive element access, but it should be
> slower for arrays and the like, as it involves additional intermediate structure
> allocations and copies. 
>
> — Taras
>
>     Just a side note that you could also:
>
>     extension SequenceType {
>     func order(@noescape isOrderedBefore: (Generator.Element, Generator.Element)
>     -> Bool) -> [Int] {
>     return enumerate().sort{ isOrderedBefore($0.1, $1.1) }.map{ $0.0 }
>     }
>     }
>
>     (0...3).reverse().order(<) // [3, 2, 1, 0]
>
>     This way you can `order` all sequences, and it is more efficient as you
>     don’t fetch elements by index inside the `isOrderedBefore`. (You could also
>     *not* `map` at the end and return all the elements along with their original
>     indexes.)
>

This is about as efficient as it gets:

extension CollectionType  {
  func order(@noescape isOrderedBefore areInOrder: (Generator.Element, Generator.Element) -> Bool) -> [Index] {
    var a = Array(indices)
    a.sortInPlace { areInOrder(self[$0], self[$1]) }
    return a
  }
}

-- 
Dave