Simple quick array expansion

Question

Trying to expand an array type to use binary sorting to insert elements in order. Here is 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 call insertionIndexOf with argument list type (T, isOrderedBefore: (_, _) → _)"

Curious 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 is reassuring, but the insertion of the array will not be ordered: (of course. Please, any ideas? Thanks.

(using Xcode 6.3 beta 2 - Swift 1.2)

Answer 1

You are trying to evaluate a > b , but T may not be Comparable . It’s impossible to write an extension like today. What do you want to say:

 extension Array where T: Comparable { 

But this is not possible right now in Swift. The compiler team has indicated that this is a priority, but we do not know when this can happen in Swift.

Your best approach is to make this a function:

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

Or create a new object in which the HAS-A array:

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

Answer 2

With Swift 2, this can be achieved using 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] 

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

For the first method, that is, CollectionType , because it provides access to the index (read) and the collection item type must be Comparable .

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