[swift-evolution] [Discussion] Binary search, lower bound, upper bound, equal range

[Jeff Hajewski]

Thanks for adding that info regarding <=> and Swift 3 - sounds like we
should include it in the proposal. Keeping up with all these
swift-evolution threads could be a full-time job!

Jeff

On Tue, Feb 16, 2016 at 1:26 PM, Ross O'Brien <narrativium+swift at gmail.com>
wrote:

> According to the aforementioned thread on the <=> operator (inclusive of
> its addition to Comparable with the Ordered(Ascending|Descending|Equal)
> enum), Dave Abrahams mentioned it was already slated for inclusion in Swift
> 3, and that sorting algorithms using it would be nifty. I've thus assumed
> there's no need to turn it into a formal proposal with a review. I've not
> seen any opposition to the idea yet.
> If it does make it to a review I'll add my +1 though.
>
> On Tue, Feb 16, 2016 at 5:58 PM, Pyry Jahkola via swift-evolution <
> swift-evolution at swift.org> wrote:
>
>> On 16 Feb 2016, at 17:49, Jeff Hajewski <jeff.hajewski at gmail.com> wrote:
>>
>>
>> I wonder if we can loosen the restriction of conforming to
>> RandomAccessIndexType.
>>
>>
>> Yay, it turned out simpler than I thought!
>>
>> I added a performance test to make sure there's no regression on
>> RandomAccessIndexType's performance, then simply downgraded the
>> RandomAccessIndexType requirement to ForwardIndexType (and used != instead
>> of < in a few places). The updated code
>> <https://github.com/knomi/Allsorts/commit/52e3d7abee2d01d90ecadea24e00c9067a64a327> is
>> in GitHub.
>>
>> That appears to work because of protocol inheritance magic in the
>> standard library. So, even though my search algorithm only knows about
>> ForwardIndexType, whenever Index happens to implement O(1) versions of
>> advancedBy(_:) and distanceTo(_:), then those get used instead of the
>> O(N) default implementations (Index.swift
>> <https://github.com/apple/swift/blob/de253d9b6f21498704f96aac712cf1b02e612255/stdlib/public/core/Index.swift#L243-L262> on
>> the Swift repository). Cool!
>>
>> There might still be place for improvement, since the internal use of
>> midIndex still passes across the same index ranges several times during
>> the search on ForwardIndexType. If I did my math right, the current
>> implementation makes something like 3N index increments on
>> ForwardIndexTypes, while probably at least 2N can be achieved without
>> much memory use.
>>
>> I think maybe the *Ordering* enum should be broken out into a separate
>> proposal since it's not currently part of the standard lib. That being
>> said, it does make for a clean implementation.
>>
>>
>> You're absolutely right. I should also paint the bikeshed of naming its
>> cases (.LT, .EQ, and .GT) less obscurely before officially proposing it
>> to swift-evolution. Maybe either  .ascending, .equivalent, and
>> .descending, or simply .less, .equal, and .greater. And I expect there
>> to be resistance against adding yet another comparison operator, even if
>> there's precedent on the use of something like "a <=> b" in several
>> other languages.
>>
>> — Pyry Jahkola
>>
>> _______________________________________________
>> 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/20160216/dd904732/attachment.html>