on Fri Apr 29 2016, Haravikk <[email protected]> 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 > <[email protected]> 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 > <[email protected]> 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 > <[email protected]> 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 > [email protected] > https://lists.swift.org/mailman/listinfo/swift-evolution > > _______________________________________________ > swift-evolution mailing list > [email protected] > https://lists.swift.org/mailman/listinfo/swift-evolution -- Dave _______________________________________________ swift-evolution mailing list [email protected] https://lists.swift.org/mailman/listinfo/swift-evolution
