Simple Swift Array Extension

Question

Trying to extend Array type to use binary sorting to insert elements in order. Here's my playground code:

  extension Array  {

      func insertionIndexOf(elem: T , isOrderedBefore: (T, T) -> Bool) -> Int {
       var lo = 0
       var hi = self.count - 1
       while lo <= hi {
        let mid = (lo + hi)/2
        if isOrderedBefore(self[mid], elem) {
            lo = mid + 1
        } else if isOrderedBefore(elem, self[mid]) {
            hi = mid - 1
        } else {
            return mid
        }
    }
        return 0 
 }


  mutating func insertOrdered(elem: T){
     let index = self.insertionIndexOf(elem, isOrderedBefore: { (a , b)     in return (a > b) } )
     return insert(elem, atIndex: index)
}

}

I get a compiler error: "cannot invoke insertionIndexOf with argument list of type ( T , isOrderedBefore: (_, _) -> _) "

The curious thing is, if I use instead:

    mutating func insertOrdered(elem: T){
         let index = self.insertionIndexOf(elem, isOrderedBefore: { (a , b) in return false } )
         return insert(elem, atIndex: index)
        }

The compiler calms down but the array insertion will not be ordered, :( of course. Please any ideas?? Thank you.

(using Xcode 6.3 beta 2 - Swift 1.2)

Answer 1

As of Swift 2, this can be achieved with protocol extension methods:

extension CollectionType where Generator.Element : Comparable, Index == Int {

    func insertionIndexOf(elem: Generator.Element) -> Int {
        var lo = 0
        var hi = self.count - 1
        while lo <= hi {
            let mid = (lo + hi)/2
            if self[mid] < elem {
                lo = mid + 1
            } else if elem < self[mid] {
                hi = mid - 1
            } else {
                return mid // found at position mid
            }
        }
        return lo // not found, would be inserted at position lo
    }
}

extension RangeReplaceableCollectionType where Generator.Element : Comparable, Index == Int {

    mutating func insertOrdered(elem: Generator.Element) {
        let index = self.insertionIndexOf(elem)
        self.insert(elem, atIndex: index)
    }
}

Example:

var ar = [1, 3, 5, 7]
ar.insertOrdered(6)
print(ar) // [1, 3, 5, 6, 7]

The methods are not defined for struct Array directly, but for some protocol to which Array conforms, and which provides the necessary methods.

For the first method, that is CollectionType because that provides the (reading) subscript access, and the collection element type is required to be Comparable.

The second method mutates the collection, here the more restrictive protocol RangeReplaceableCollectionType is required.

Answer 2

You are trying to evaluate a > b, but T may not be Comparable. It's not possible to write an extension like this today. What you'd like to be able to say is:

extension Array where T: Comparable {

But that's not possible in Swift currently. The compiler team has indicated that it is a priority, but we don't know when it may come to Swift.

Your best approach is to either make this a function:

func insertOrdered<T: Comparable>(inout xs: [T], x: T)

Or make a new object that HAS-A array:

struct OrderedArray<T: Comparable> : ... {
    var values: [T]
    func insertionIndexOf(elem: T , isOrderedBefore: (T, T) -> Bool) -> Int
    mutating func inserOrdered(elem: T)
    ...
}