<div dir="ltr">Dave - I think it boils down to a gap in communication. We were under the impression that the goal was a pure extension of CollectionType, without making any requirements on Generator.Element (i.e., your requiring it to be comparable), where binary search, lower bound, and upper bound all work with the same unary predicate. Of course, as you demonstrated, it is trivial to implement when Generator.Element is Comparable, but if you relax that requirement it is not possible to create a set of functions (binary search, lower bound, upper bound) that all take the same unary predicate. We ultimately came up with a slightly different approach, implementing binary search similar to your example, but a different take on lower bound, upper bound, and range. I suppose we should just send out our proposal and get everyone's take on it.<div><br></div><div>Jeff</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Apr 28, 2016 at 5:06 PM, Dave Abrahams via swift-evolution <span dir="ltr"><<a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><br>
on Thu Apr 28 2016, Jeff Hajewski <<a href="mailto:swift-evolution@swift.org">swift-evolution@swift.org</a>> wrote:<br>
<br>
> Thanks for bringing this back into the spotlight Pyry. A few of us have been<br>
> working on this issue here:<br>
><br>
> <a href="https://github.com/lorenzoracca/Swift-binary-search" rel="noreferrer" target="_blank">https://github.com/lorenzoracca/Swift-binary-search</a><br>
><br>
> However we have sort of stalled as we have been unable to come up with a unary<br>
> approach that Dave suggested using just Bool return values. And of course, as<br>
> you say, the three case order enum would make this a trivial problem.<br>
><br>
> I guess the question is, do we move forward without a unary implementation and<br>
> update if/when we get a three case Order enum or do we wait on a three case<br>
> Order enum and implement a fully generic version once?<br>
<br>
Or you could just do it like this (Swift 2.2-compatible). Am I missing<br>
something?<br>
<br>
extension CollectionType {<br>
/// Returns the index of the first element satisfying `predicate`,<br>
/// or `endIndex` if no such element exists.<br>
///<br>
/// - Requires: `self` is partitioned with respect to `predicate`;<br>
/// that is, there exists an index `i` in `startIndex...endIndex`<br>
/// such that `predicate` returns `false` for every element of<br>
/// `self[startIndex..<i]` and returns `true` for every element<br>
/// of `self[i..<endIndex]`.<br>
@warn_unused_result<br>
public func binarySearch(<br>
predicate: (Self.Generator.Element)->Bool<br>
) -> Index {<br>
var len = count<br>
var min = startIndex<br>
while len > 0 {<br>
let half = len/2<br>
let middle = min.advancedBy(half)<br>
<br>
if !predicate(self[middle]) {<br>
min = middle.successor()<br>
len -= half.successor()<br>
} else {<br>
len = half<br>
}<br>
}<br>
return min<br>
}<br>
}<br>
<br>
extension CollectionType where Generator.Element : Comparable {<br>
/// Returns the index of the first element greater than or equal to<br>
/// `target`, or `endIndex` if no such element exists.<br>
///<br>
/// - Requires: `self` is sorted.<br>
@warn_unused_result<br>
public func lowerBound(target: Self.Generator.Element) -> Index {<br>
return binarySearch { $0 >= target }<br>
}<br>
<br>
/// Returns the index of the first element greater than<br>
/// `target`, or `endIndex` if no such element exists.<br>
///<br>
/// - Requires: `self` is sorted.<br>
@warn_unused_result<br>
public func upperBound(target: Self.Generator.Element) -> Index {<br>
return binarySearch { $0 > target }<br>
}<br>
}<br>
<br>
//===--- TEST IT ----------------------------------------------------------===//<br>
import Darwin<br>
for _ in 0..<1000 {<br>
// build a sorted array of up to 30 values in the range 0..<10<br>
var a : Array<Int> = []<br>
for _ in 0..<arc4random_uniform(30) {<br>
a.append(Int(arc4random_uniform(10)))<br>
}<br>
a.sortInPlace()<br>
<br>
print(a)<br>
<br>
for i in -3...14 {<br>
let l = a.lowerBound(i)<br>
let u = a.upperBound(i)<br>
assert(l >= 0)<br>
assert(u <= a.count)<br>
assert(l <= u)<br>
if l > 0 {<br>
assert(a[l - 1] < i)<br>
}<br>
if l < a.count {<br>
assert(a[l] >= i)<br>
}<br>
if u > 0 {<br>
assert(a[u - 1] <= i)<br>
}<br>
if u < a.count {<br>
assert(a[u] > i)<br>
}<br>
}<br>
}<br>
<span class="HOEnZb"><font color="#888888"><br>
--<br>
Dave<br>
<br>
_______________________________________________<br>
swift-evolution mailing list<br>
<a href="mailto:swift-evolution@swift.org">swift-evolution@swift.org</a><br>
<a href="https://lists.swift.org/mailman/listinfo/swift-evolution" rel="noreferrer" target="_blank">https://lists.swift.org/mailman/listinfo/swift-evolution</a><br>
</font></span></blockquote></div><br></div>