<div dir="ltr">According to the aforementioned thread on the &lt;=&gt; 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&#39;ve thus assumed there&#39;s no need to turn it into a formal proposal with a review. I&#39;ve not seen any opposition to the idea yet.<div>If it does make it to a review I&#39;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">&lt;<a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a>&gt;</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 &lt;<a href="mailto:jeff.hajewski@gmail.com" target="_blank">jeff.hajewski@gmail.com</a>&gt; 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&#39;s no regression on <span style="font-family:Menlo;font-size:11px">RandomAccessIndexType</span>&#39;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">&lt;</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&#39;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&#39;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&#39;s precedent on the use of something like &quot;<span style="font-family:Menlo;font-size:11px">a &lt;=&gt; b</span>&quot; 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>