<div dir="ltr">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.<div>If it does make it to a review I'll add my +1 though.</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Feb 16, 2016 at 5:58 PM, Pyry Jahkola via swift-evolution <span dir="ltr"><<a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word"><span class=""><blockquote type="cite">On 16 Feb 2016, at 17:49, Jeff Hajewski <<a href="mailto:jeff.hajewski@gmail.com" target="_blank">jeff.hajewski@gmail.com</a>> wrote:<br></blockquote></span><div><span class=""><blockquote type="cite"><br><div><span style="font-family:Helvetica;font-size:13px;font-style:normal;font-variant:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;float:none;display:inline!important">I wonder if we can loosen the restriction of conforming to RandomAccessIndexType.</span></div></blockquote><div><br></div></span><div>Yay, it turned out simpler than I thought!</div><div><br></div><div>I added a performance test to make sure there's no regression on <span style="font-family:Menlo;font-size:11px">RandomAccessIndexType</span>'s performance, then simply downgraded the <span style="font-family:Menlo;font-size:11px">RandomAccessIndexType</span> requirement to <span style="font-family:Menlo;font-size:11px">ForwardIndexType</span> (and used <span style="font-family:Menlo;font-size:11px">!=</span> instead of <span style="font-family:Menlo;font-size:11px"><</span> in a few places). The <a href="https://github.com/knomi/Allsorts/commit/52e3d7abee2d01d90ecadea24e00c9067a64a327" target="_blank">updated code</a> is in GitHub.</div><div><br></div><div>That appears to work because of protocol inheritance magic in the standard library. So, even though my search algorithm only knows about <span style="font-family:Menlo;font-size:11px">ForwardIndexType</span>, whenever <span style="color:rgb(112,61,170);font-family:Menlo;font-size:11px">Index</span> happens to implement O(1) versions of <span style="color:rgb(61,29,129);font-family:Menlo;font-size:11px">advancedBy(_:)</span> and <span style="color:rgb(61,29,129);font-family:Menlo;font-size:11px">distanceTo(_:)</span>, then those get used instead of the O(N) default implementations (<a href="https://github.com/apple/swift/blob/de253d9b6f21498704f96aac712cf1b02e612255/stdlib/public/core/Index.swift#L243-L262" target="_blank">Index.swift</a> on the Swift repository). Cool!</div><div><br></div><div>There might still be place for improvement, since the internal use of <span style="font-family:Menlo;font-size:11px">midIndex</span> still passes across the same index ranges several times during the search on <span style="font-family:Menlo;font-size:11px">ForwardIndexType</span>. If I did my math right, the current implementation makes something like 3N index increments on <span style="font-family:Menlo;font-size:11px">ForwardIndexType</span>s, while probably at least 2N can be achieved without much memory use.</div><span class=""><br><blockquote type="cite"><div><span style="font-family:Helvetica;font-size:13px;font-style:normal;font-variant:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;float:none;display:inline!important">I think maybe the<span> </span></span><i style="font-family:Helvetica;font-size:13px;font-variant:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px">Ordering</i><span style="font-family:Helvetica;font-size:13px;font-style:normal;font-variant:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;float:none;display:inline!important"><span> </span>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.</span></div></blockquote><br></span></div><div>You're absolutely right. I should also paint the bikeshed of naming its cases (<span style="font-family:Menlo;font-size:11px">.LT</span>, <span style="font-family:Menlo;font-size:11px">.EQ</span>, and <span style="font-family:Menlo;font-size:11px">.GT</span>) less obscurely before officially proposing it to swift-evolution. Maybe either <span style="font-family:Menlo;font-size:11px">.ascending</span>, <span style="font-family:Menlo;font-size:11px">.equivalent</span>, and <span style="font-family:Menlo;font-size:11px">.descending</span>, or simply <span style="font-family:Menlo;font-size:11px">.less</span>, <span style="font-family:Menlo;font-size:11px">.equal</span>, and <span style="font-family:Menlo;font-size:11px">.greater</span>. And I expect there to be resistance against adding yet another comparison operator, even if there's precedent on the use of something like "<span style="font-family:Menlo;font-size:11px">a <=> b</span>" in several other languages.</div><br><div>
<span style="border-collapse:separate;line-height:normal;border-spacing:0px"><div style="word-wrap:break-word"><span style="border-collapse:separate;color:rgb(0,0,0);font-variant:normal;letter-spacing:normal;line-height:normal;text-align:-webkit-auto;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;border-spacing:0px;font-size:12px"><div style="word-wrap:break-word">— Pyry Jahkola</div></span></div></span></div></div><br>_______________________________________________<br>
swift-evolution mailing list<br>
<a href="mailto:swift-evolution@swift.org">swift-evolution@swift.org</a><br>
<a href="https://lists.swift.org/mailman/listinfo/swift-evolution" rel="noreferrer" target="_blank">https://lists.swift.org/mailman/listinfo/swift-evolution</a><br>
<br></blockquote></div><br></div>