[swift-evolution] [Proposal] Add Binary Search functions to SequenceType

[Jeff Hajewski]

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.

Jeff

On Thu, Apr 28, 2016 at 5:06 PM, Dave Abrahams via swift-evolution <
swift-evolution at swift.org> wrote:

>
> on Thu Apr 28 2016, Jeff Hajewski <swift-evolution at swift.org> wrote:
>
> > Thanks for bringing this back into the spotlight Pyry. A few of us have
> been
> > working on this issue here:
> >
> > https://github.com/lorenzoracca/Swift-binary-search
> >
> > However we have sort of stalled as we have been unable to come up with a
> unary
> > approach that Dave suggested using just Bool return values. And of
> course, as
> > you say, the three case order enum would make this a trivial problem.
> >
> > I guess the question is, do we move forward without a unary
> implementation and
> > update if/when we get a three case Order enum or do we wait on a three
> case
> > Order enum and implement a fully generic version once?
>
> Or you could just do it like this (Swift 2.2-compatible).  Am I missing
> something?
>
> extension CollectionType {
>   /// Returns the index of the first element satisfying `predicate`,
>   /// or `endIndex` if no such element exists.
>   ///
>   /// - Requires: `self` is partitioned with respect to `predicate`;
>   ///   that is, there exists an index `i` in `startIndex...endIndex`
>   ///   such that `predicate` returns `false` for every element of
>   ///   `self[startIndex..<i]` and returns `true` for every element
>   ///   of `self[i..<endIndex]`.
>   @warn_unused_result
>   public func binarySearch(
>     predicate: (Self.Generator.Element)->Bool
>   ) -> Index {
>     var len = count
>     var min = startIndex
>     while len > 0 {
>       let half = len/2
>       let middle = min.advancedBy(half)
>
>       if !predicate(self[middle]) {
>         min = middle.successor()
>         len -= half.successor()
>       } else {
>         len = half
>       }
>     }
>     return min
>   }
> }
>
> extension CollectionType where Generator.Element : Comparable {
>   /// Returns the index of the first element greater than or equal to
>   /// `target`, or `endIndex` if no such element exists.
>   ///
>   /// - Requires: `self` is sorted.
>   @warn_unused_result
>   public func lowerBound(target: Self.Generator.Element) -> Index {
>     return binarySearch { $0 >= target }
>   }
>
>   /// Returns the index of the first element greater than
>   /// `target`, or `endIndex` if no such element exists.
>   ///
>   /// - Requires: `self` is sorted.
>   @warn_unused_result
>   public func upperBound(target: Self.Generator.Element) -> Index {
>     return binarySearch { $0 > target }
>   }
> }
>
> //===--- TEST IT
> ----------------------------------------------------------===//
> import Darwin
> for _ in 0..<1000 {
>   // build a sorted array of up to 30 values in the range 0..<10
>   var a : Array<Int> = []
>   for _ in 0..<arc4random_uniform(30) {
>     a.append(Int(arc4random_uniform(10)))
>   }
>   a.sortInPlace()
>
>   print(a)
>
>   for i in -3...14 {
>     let l = a.lowerBound(i)
>     let u = a.upperBound(i)
>     assert(l >= 0)
>     assert(u <= a.count)
>     assert(l <= u)
>     if l > 0 {
>       assert(a[l - 1] < i)
>     }
>     if l < a.count {
>       assert(a[l] >= i)
>     }
>     if u > 0 {
>       assert(a[u - 1] <= i)
>     }
>     if u < a.count {
>       assert(a[u] > i)
>     }
>   }
> }
>
> --
> Dave
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160428/d8dae106/attachment.html>