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.jahk...@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@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@swift.org https://lists.swift.org/mailman/listinfo/swift-evolution