<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><br class=""><div><blockquote type="cite" class=""><div class="">On Feb 16, 2016, at 11:58 AM, Pyry Jahkola via swift-evolution <<a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><meta http-equiv="Content-Type" content="text/html charset=utf-8" class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><blockquote type="cite" class="">On 16 Feb 2016, at 17:49, Jeff Hajewski <<a href="mailto:jeff.hajewski@gmail.com" class="">jeff.hajewski@gmail.com</a>> wrote:<br class=""></blockquote><div class=""><blockquote type="cite" class=""><br class="Apple-interchange-newline"><div class=""><span style="font-family: Helvetica; font-size: 13px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class="">I wonder if we can loosen the restriction of conforming to RandomAccessIndexType.</span></div></blockquote><div class=""><br class=""></div><div class="">Yay, it turned out simpler than I thought!</div><div class=""><br class=""></div><div class="">I added a performance test to make sure there's no regression on <span style="font-family: Menlo; font-size: 11px;" class="">RandomAccessIndexType</span>'s performance, then simply downgraded the <span style="font-family: Menlo; font-size: 11px;" class="">RandomAccessIndexType</span> requirement to <span style="font-family: Menlo; font-size: 11px;" class="">ForwardIndexType</span> (and used <span style="font-family: Menlo; font-size: 11px;" class="">!=</span> instead of <span style="font-family: Menlo; font-size: 11px;" class=""><</span> in a few places). The <a href="https://github.com/knomi/Allsorts/commit/52e3d7abee2d01d90ecadea24e00c9067a64a327" class="">updated code</a> is in GitHub.</div><div class=""><br class=""></div><div class="">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;" class="">ForwardIndexType</span>, whenever <span style="color: rgb(112, 61, 170); font-family: Menlo; font-size: 11px;" class="">Index</span> happens to implement O(1) versions of <span style="color: rgb(61, 29, 129); font-family: Menlo; font-size: 11px;" class="">advancedBy(_:)</span> and <span style="color: rgb(61, 29, 129); font-family: Menlo; font-size: 11px;" class="">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" class="">Index.swift</a> on the Swift repository). Cool!</div><div class=""><br class=""></div><div class="">There might still be place for improvement, since the internal use of <span style="font-family: Menlo; font-size: 11px;" class="">midIndex</span> still passes across the same index ranges several times during the search on <span style="font-family: Menlo; font-size: 11px;" class="">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;" class="">ForwardIndexType</span>s, while probably at least 2N can be achieved without much memory use.</div></div></div></div></blockquote><div><br class=""></div><div>I was going to suggest earlier that the algorithms should perhaps switch to an internal representation of ~ `(index: Index, length: Index.Distance)` (instead of `Range<Index>`), which is an unnecessary change for `RandomAccessIndexType` but for a `ForwardIndexType` would eliminate the need to call `distanceTo` more than once.</div><div><br class=""></div><div>The public API could of course stick with Range<Index>, the alternative representation would only be a private implementation detail.</div><div><br class=""></div><div>I have some other thoughts but they’re still in progress.</div><div><br class=""></div><blockquote type="cite" class=""><div class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div class=""><br class=""><blockquote type="cite" class=""><div class=""><span style="font-family: Helvetica; font-size: 13px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class="">I think maybe the<span class="Apple-converted-space"> </span></span><i style="font-family: Helvetica; font-size: 13px; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">Ordering</i><span style="font-family: Helvetica; font-size: 13px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class=""><span class="Apple-converted-space"> </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 class=""></div><div class="">You're absolutely right. I should also paint the bikeshed of naming its cases (<span style="font-family: Menlo; font-size: 11px;" class="">.LT</span>, <span style="font-family: Menlo; font-size: 11px;" class="">.EQ</span>, and <span style="font-family: Menlo; font-size: 11px;" class="">.GT</span>) less obscurely before officially proposing it to swift-evolution. Maybe either <span style="font-family: Menlo; font-size: 11px;" class="">.ascending</span>, <span style="font-family: Menlo; font-size: 11px;" class="">.equivalent</span>, and <span style="font-family: Menlo; font-size: 11px;" class="">.descending</span>, or simply <span style="font-family: Menlo; font-size: 11px;" class="">.less</span>, <span style="font-family: Menlo; font-size: 11px;" class="">.equal</span>, and <span style="font-family: Menlo; font-size: 11px;" class="">.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;" class="">a <=> b</span>" in several other languages.</div><br class=""><div class="">
<span class="Apple-style-span" style="border-collapse: separate; line-height: normal; border-spacing: 0px;"><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><span class="Apple-style-span" style="border-collapse: separate; font-variant: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; border-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-stroke-width: 0px; font-size: 12px;"><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">— Pyry Jahkola</div></span></div></span></div></div>_______________________________________________<br class="">swift-evolution mailing list<br class=""><a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a><br class="">https://lists.swift.org/mailman/listinfo/swift-evolution<br class=""></div></blockquote></div><br class=""></body></html>