search

lorenzoracca / Swift-binary-search

Binary search imply that will presented as proposal to swift-evolution
2 stars 2 forks source link

Revise proposal to describe new APIs #8

Closed natecook1000 closed 8 years ago

natecook1000 commented 8 years ago

This is a big revision to the proposal that describes the APIs discussed in #5 in detail. The names are still totally up in the air, but I've used my suggestions:

I think these have internal consistency and comport well with existing methods of the Swift 3 standard library, most notably index(of:) and index(where:). What do you think? I think there's some danger in users thinking that a method like sortedIndex(of:) sorts the collection before finding the index, but I'm not sure of how else to distinguish these methods from the standard index(of:).

natecook1000 commented 8 years ago

cc @j-haj @lorenzoracca @Haravikk

j-haj commented 8 years ago

@natecook1000 I think this looks really good! I agree with your comment on sortedIndex and to add to that, I imagine there will be some resistance, at least initially, from the core team since this is such a departure from the original ask.

I received a response from Dave Abrahams yesterday and sent him a message back regarding the issues we are seeing with using a unary predicate. I'll add any pertinent info to the discussion here as it comes in.

Haravikk commented 8 years ago

Looks good! I mentioned it in the other thread, so it should be no surprise I'm in favour of this, since these names should place no restrictions on how the actual search/partitioning works. It also has the benefit that .sortedIndex(of:) will be grouped lexically with .sort().

While I can see the possibility for .sortedIndex(of:) to be misleading, I think most people will lean towards .index(of:) first (which is correct for unsorted collections) so it should be fine so long as .sortedIndex(of:) has a requirement that self is sorted, and we could maybe have a link from .index(of:) to .sortedIndex(of:) (e.g- "If self is sorted consider .sortedIndex(of:) instead).

Also, I assume there will still be sortedIndex(of:where:) and sortedRange(of:where:) variants for non-Comparable elements?

natecook1000 commented 8 years ago

@Haravikk I called the binary predicate isOrderedBefore in the proposal, since it has the same requirements and semantics as the one used in sort(isOrderedBefore:), min(isOrderedBefore:), and other existing stdlib methods.

Also, is it okay to add you to the proposal?

lorenzoracca commented 8 years ago

Looks good! As Jeff said, we did change this a lot since the beginning, but as long as the core team gives us a go, I'm totally fine with this. Besides, I think the problem with .sortedIndex(of:) isn't a big one. The API will be documented, users will be thoroughly informed about the use of the function, and maybe even a help page on binary search could be put within the Apple Swift website.

Also, I think we should still try and make a version of .sortedIndex(of: where:) and .sortedRange(of:where:), as it remains consistent with .index(where:). What do you think?

natecook1000 commented 8 years ago

What would the where parameter be in that variation? Both of those methods need to test for equivalence.

lorenzoracca commented 8 years ago

Oh, I just noticed the mistake. Who knows what I was thinking. Obviously they test for equivalence, partitionedIndex(where:) and partition(where:) are for predicate-based searches. Sorry :)

This looks all good, and I think we could start working on it!

EDIT: That's where I saw it. On the proposal document, SE-0047.md, in the examples for .sortedIndex(of:), there's the function performing a binary search using the value itself and a binary predicate. Should I delete that then? Also because I believe that our attempts to create a binarySearch() function taking a predicate were all vain, we couldn't manage to get one.

natecook1000 commented 8 years ago

Right—it's not clearly called out in the Proposed Solution section that there will be two versions of sortedIndex and sortedRange: