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

[Dave Abrahams]

on Fri Apr 29 2016, Haravikk <swift-evolution at swift.org> wrote:

> Actually, the binary search proposal settled on a definition of a partition
> point method (and probably a partition method as well) that provides the real
> implementation details anyway, so these could go ahead as-is. 

That's what I had in mind.

> You’re right that the search methods themselves may prefer to wait,
> since .sort() will likely change to reflect the new strict ordering
> operator, in which case it makes sense to delay those to be
> consistent, but partitioning should be unaffected.
>
>     On 28 Apr 2016, at 13:03, Jeff Hajewski via swift-evolution
>     <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?
>
>     Jeff
>
>     On Thu, Apr 28, 2016 at 7:36 AM, Pyry Jahkola
>     <pyry.jahkola at iki.fi> wrote:
>
>         Bringing up this topic because it became relevant with Brent
>         Royal-Gordon's "[Idea] Bringing the partial/total ordering distinction
>         into Comparable".
>
>         If the `<=>` operator with a return type of a three-case `enum Order`,
>         you can fully define the most generic versions of binary searches as:
>
>         lowerBound(compare: Self.Collection.Element -> Order) -> Index
>
>         etc.
>
>             On 29 Mar 2016, at 13:43, Jeff Hajewski via swift-evolution
>             <swift-evolution at swift.org> wrote:
>
>             I've responded below, but just for the sake of being explicit, this
>             is roughly 
>             the signature for lowerBound, upperBound, and binarySearch I have in 
>             mind based on your comments of a unary predicate:
>
>             lowerBound(isOrderedBelow: Self.Collection.Element -> Bool) -> Index
>             upperBound(isOrderedBelow: Self.Collection.Element -> Bool) -> Index
>             binarySearch(isOrderedBelow: Self.Collection.Element -> Bool) ->
>             Bool
>
>             That's the general structure - the key is that the exact same
>             predicate is
>             used in all signatures. The predicate would be defined along the
>             lines of
>             a binary predicate where one of the parameters is fixed as the
>             search value.
>             The unary predicate could be formed along the lines of:
>
>             let binaryPred = { $0 < $1 }
>             let unnaryPred = binaryPred($0, value)
>
>             where value is the search value. The main point of illustrating that
>             is that
>             once the unary predicate is defined, we can't change the position of
>             the
>             search value within the predicate like they do in the C++
>             implementation.
>
>         You're right, there's no way a Bool-returning unary comparator could
>         allow you to implement anything but lowerBound. With a three-value
>         result, however, you've got all you need.
>
>         I've shamelessly plugged before but for the sake of proving a point,
>         I'll do it once more: I think this little library we did works as a good
>         starting point for a stdlib binary search API:
>         https://github.com/knomi/Allsorts/blob/master/Allsorts/BinarySearch.swift
>
>         — Pyry
>
>     _______________________________________________
>     swift-evolution mailing list
>     swift-evolution at swift.org
>     https://lists.swift.org/mailman/listinfo/swift-evolution
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution

-- 
Dave