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

[Ross O'Brien]

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/277a3568/attachment.html>