Navi Navi - 1 month ago 15
Swift Question

Stridable Protocol

I am trying to convert the following Swift 2.3 code:

//Example usage:
//(0 ..< 778).binarySearch { $0 < 145 } // 145
extension CollectionType where Index: RandomAccessIndexType {

/// Finds such index N that predicate is true for all elements up to
/// but not including the index N, and is false for all elements
/// starting with index N.
/// Behavior is undefined if there is no such N.
func binarySearch(predicate: Generator.Element -> Bool)
-> Index {
var low = startIndex
var high = endIndex
while low != high {
let mid = low.advancedBy(low.distanceTo(high) / 2)
if predicate(self[mid]) {
low = mid.advancedBy(1)
} else {
high = mid
}
}
return low
}
}


into Swift 3 as follows:

//Example usage:
//(0 ..< 778).binarySearch { $0 < 145 } // 145
extension Collection where Index: Strideable {

/// Finds such index N that predicate is true for all elements up to
/// but not including the index N, and is false for all elements
/// starting with index N.
/// Behavior is undefined if there is no such N.
func binarySearch(predicate: (Generator.Element) -> Bool)
-> Index {
var low = startIndex
var high = endIndex
while low != high {
let mid = low.advanced(by: low.distance(to: high) / 2)
if predicate(self[mid]) {
low = mid.advanced(to: 1)
} else {
high = mid
}
}
return low
}
}


The error


Binary operator '/' cannot be applied to operands of type 'self.Index.Stride' and 'Int'


is thrown at
let mid = low.advanced(by: low.distance(to: high) / 2)


Any help on how to fix it?

Answer

In Swift 3, "Collections move their index", compare A New Model for Collections and Indices on Swift evolution. In particular, you don't call advancedBy() on an index, but an index() method on the collection to advance indices.

So your method would be implemented in Swift 3 as

extension Collection {

    func binarySearch(predicate: (Iterator.Element) -> Bool) -> Index {
        var low = startIndex
        var high = endIndex
        while low != high {
            let mid = index(low, offsetBy: distance(from: low, to: high)/2)
            if predicate(self[mid]) {
                low = index(after: mid)
            } else {
                high = mid
            }
        }
        return low
    }
}

without requiring any restrictions on the index type.