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

Jeff Hajewski jeff.hajewski at gmail.com
Tue Feb 16 12:37:54 CST 2016

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!


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

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

More information about the swift-evolution mailing list