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

[Jeff Hajewski]

Nate - I suppose that's really the crux of the matter here. I agree a
binary predicate solves the problem, but is that the route we want to go? I
think it makes sense, but is there a reason we should stick with a unary
predicate? For some reason I had it in my mind that there was mention of
preferring a unary predicate but now that I'm looking back I can't find
anything to that end.

I'll work on a binary predicate implementation and see what the group
thinks.

Thanks!
Jeff

On Wed, Mar 16, 2016 at 2:17 AM, Nate Cook via swift-evolution <
swift-evolution at swift.org> wrote:

> On Mar 15, 2016, at 1:58 PM, Lorenzo Racca via swift-evolution <
> swift-evolution at swift.org> wrote:
>
> On Mar 15, 2016, at 6:49 PM, Haravikk <swift-evolution at haravikk.me> wrote:
>
> On 15 Mar 2016, at 15:48, Lorenzo Racca <lorenzo.racca at live.it> wrote:
>
> I already knew the impossibility of applying such a predicate as “$0 == 3”
> and I actually couldn’t quite figure out a solution.
>
>
> I thought so, and I don’t think there is a way to do it, my point was
> really just that your swift doc comments weren’t clear on that point, then
> I went off at a bit of a tangent ;)
>
> No problem! What I am trying to figure out here is how we should implement
> the lowerBound and upperBound functions. Should they exactly reflect their
> C++ counterparts?
> Anyway, it seems all of our implementations have the same problem, that
> they cannot be univocally called with any predicate whatsoever, (or at
> least it seemed to me during some tests with the implementations :) ), so I
> don’t really know how we should act. I am a little blocked.
> Does anyone have ideas on how that could work no matter what predicate is
> given? Especially, an upperBound() function, which is a little trickier.
>
>
> The key is to use a binary predicate (as used in sort and partition)
> instead of a unary predicate. Then you can use the predicate as is for
> lowerBound or with the arguments "reversed" for upperBound. The methods
> would have a similar signature to indexOf—one that just takes a value for
> comparable collections and one that takes a value and a predicate.
>
> The binary search method can be implemented by finding the lower bound,
> which is by definition not less than the given value, then using the same
> predicate to check whether the value is not less than the lower bound. If
> neither is less than the other, you've found the value.
>
> Nate
>
> On Mar 15, 2016, at 6:07 PM, Jeff Hajewski  <jeff.hajewski at gmail.come>
> wrote:
>
> I suspect there is an easy solution here and I'm just having a mental
> block...
>
>
> Jeff, I really do feel you, I’m in the same situation!
> I think your solution could be applicable though, just in a little more
> complicated way than C++ did, which is to extract the complement of the
> predicate and act differently upon that.
> As of now I don’t have the time to put down some code (time zone sucks)
> but will try asap.
>
> Lorenzo
>
>
>
> _______________________________________________
> 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/20160316/8ae0ab79/attachment.html>