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
> <[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
<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
