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

[Haravikk]

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. 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 <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 <mailto: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 <http://thread.gmane.org/gmane.comp.lang.swift.evolution/15180>".
> 
> 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 <mailto: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 <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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160429/7032a37a/attachment.html>