<div dir="ltr">Pyry - this is great work! I wonder if we can loosen the restriction of conforming to RandomAccessIndexType. I will play around with this. I think maybe the <i>Ordering</i> 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.<div><br></div><div>Thanks</div><div>Jeff</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Feb 16, 2016 at 7:12 AM, 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"><div><blockquote type="cite"></blockquote><blockquote type="cite"></blockquote><blockquote type="cite"><blockquote type="cite">On Mon Feb 15 2016, Jeff Hajewski <<a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a>> wrote:</blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite"><div>I am working on SR-368 <<a href="https://bugs.swift.org/browse/SR-368" target="_blank">https://bugs.swift.org/browse/SR-368</a>> and am hoping to get some feedback from the community.</div></blockquote></blockquote></div><div><br></div><div>Definitely +1!</div><div><br></div>Shameless plug:<div><br></div><div>I've played with this idea in the past, implementing all of the four suggested binary searches as generic functions over index ranges or collections, using a custom 3-way comparator. The commented code and unit tests are found in <a href="https://github.com/knomi/Allsorts" target="_blank">https://github.com/knomi/Allsorts</a>. The library is also somewhat tested in production.</div><div><br></div><div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><div style="margin:0px;line-height:normal"><span style="color:rgb(187,44,162)">let</span> i: <span style="color:rgb(112,61,170)">Int</span> = [<span style="color:rgb(209,47,27)">"a"</span>,<span style="color:rgb(209,47,27)">"b"</span>,<span style="color:rgb(209,47,27)">"c"</span>,<span style="color:rgb(209,47,27)">"c"</span>,<span style="color:rgb(209,47,27)">"c"</span>,<span style="color:rgb(209,47,27)">"d"</span>,<span style="color:rgb(209,47,27)">"f"</span>,<span style="color:rgb(209,47,27)">"f"</span>].binarySearch(<span style="color:rgb(209,47,27)">"c"</span>) <span style="color:rgb(0,132,0)">//=> 2, 3 or 4</span></div><div style="margin:0px;line-height:normal"><span style="color:#bb2ca2">let</span> j: <span style="color:#703daa">Int</span>? = [<span style="color:#d12f1b">"a"</span>,<span style="color:#d12f1b">"b"</span>,<span style="color:#d12f1b">"c"</span>,<span style="color:#d12f1b">"c"</span>,<span style="color:#d12f1b">"c"</span>,<span style="color:#d12f1b">"d"</span>,<span style="color:#d12f1b">"f"</span>,<span style="color:#d12f1b">"f"</span>].binaryFind(<span style="color:#d12f1b">"e"</span>) <span style="color:rgb(0,132,0)">//=> nil</span></div><div style="margin:0px;line-height:normal"><span style="color:rgb(0,132,0)">// C</span><span style="color:rgb(0,132,0)">ompare values to "e". `a <=> b` performs a 3-way comparison, returning .LT, .EQ or .GT</span></div><div style="margin:0px;line-height:normal"><span style="color:#bb2ca2">let</span> k: <span style="color:#703daa">Int</span> = [<span style="color:#d12f1b">"a"</span>,<span style="color:#d12f1b">"b"</span>,<span style="color:#d12f1b">"c"</span>,<span style="color:#d12f1b">"c"</span>,<span style="color:#d12f1b">"c"</span>,<span style="color:#d12f1b">"d"</span>,<span style="color:#d12f1b">"f"</span>,<span style="color:#d12f1b">"f"</span>].lowerBound {x <span style="color:#bb2ca2">in</span> x <=> <span style="color:#d12f1b">"e"</span>} <span style="color:rgb(0,132,0)">//=> 6</span></div><div style="margin:0px;line-height:normal"><span style="color:rgb(0,132,0)">// </span><span style="color:rgb(0,132,0)">Reverse order (the arguments of <=> are flipped):</span></div><div style="margin:0px;line-height:normal"><span style="color:#bb2ca2">let</span> r: <span style="color:#703daa">Range</span><<span style="color:#703daa">Int</span>> = [<span style="color:#d12f1b">"e"</span>,<span style="color:#d12f1b">"e"</span>,<span style="color:#d12f1b">"d"</span>,<span style="color:#d12f1b">"c"</span>,<span style="color:#d12f1b">"c"</span>,<span style="color:#d12f1b">"c"</span>,<span style="color:#d12f1b">"b"</span>,<span style="color:#d12f1b">"a"</span>].equalRange {x <span style="color:#bb2ca2">in</span> <span style="color:#d12f1b">"c"</span> <=> x} <span style="color:rgb(0,132,0)">//=> 3 ..< 6</span></div><div><br></div></div></div><div>I'd be happy to join forces in making the algorithms available in the standard library.</div><div><br></div><div>I believe that my code tackles many points Dave mentioned:</div><div><br></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div>(1) You don't need to construct an element just to perform the search. You only need a function to tell if the search should proceed to the left or right, or if there's a match.</div><div><br></div><div>(2) You don't really need to a concrete collection either. A <span style="font-family:Menlo;font-size:11px;color:rgb(112,61,170)">Range</span><span style="font-family:Menlo;font-size:11px"><</span><span style="font-family:Menlo;font-size:11px;color:rgb(112,61,170)">Int</span><span style="font-family:Menlo;font-size:11px">></span> will do just as fine, as long as you're able to say how those indices should be compared to each other (usually by looking up somewhere else).</div><div><br></div><div>(3) The collection can be sorted by any comparator (which I call an "<span style="font-family:Menlo;font-size:11px">ordering</span>"), as long as you pass that information along as the closure (the <span style="font-family:Menlo;font-size:11px">ordering</span>).</div><div><br></div><div>(4) I use three-way comparisons to avoid extra work comparing e.g. strings.</div></blockquote><div><ul><ul><li>Turns out comparisons defined that way also compose amazingly well, see first examples in README.</li><li>There's an operator "<span style="font-family:Menlo;font-size:11px">x <=> y</span>" returning <span style="font-family:Menlo;font-size:11px">Ordering.LT</span>, <span style="font-family:Menlo;font-size:11px">.EQ</span>, or <span style="font-family:Menlo;font-size:11px">.GT</span> instead of just <span style="color:rgb(112,61,170);font-family:Menlo;font-size:11px">Bool</span>. However, that operator has little to do with the implementation of binary search.</li><li>(The topic of three-way comparisons <a href="https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20160201/009127.html" target="_blank">was discussed earlier</a> in swift-evolution. I think it should find its way into the <span style="color:rgb(112,61,170);font-family:Menlo;font-size:11px">Comparable</span> protocol directly, as an alternative to defining "<span style="font-family:Menlo;font-size:11px"><</span>".)</li></ul></ul></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div>(5) By convention, I <b>do not</b> return <span style="font-family:Menlo;font-size:11px">nil</span> just because an index wasn't found. You might still want to use the index for the insertion of new elements. For convenience, there's <span style="font-family:Menlo;font-size:11px">binaryFind</span> which is guaranteed to return an index exactly when there's a match, otherwise <span style="font-family:Menlo;font-size:11px">nil</span>.</div><div><br></div><div>(6) There are convenience overloads for sorted collections of <span style="font-family:Menlo;font-size:11px">Generator.Element : </span><span style="color:rgb(112,61,170);font-family:Menlo;font-size:11px">Comparable</span> so that you can give a <span style="font-family:Menlo;font-size:11px">value</span> to look up.</div><div><br></div><div>(7) The project also contains more experimental stuff like a working (but slow?) port of libc++'s binary heap algorithms. Over time, those would be nice to port to Swift standard library as well.</div></blockquote><div><br></div><div>The existing interface on GitHub is still preferring top-level functions. I'm modernising the interface into the following (plus the usual <span style="color:rgb(187,44,162);font-family:Menlo;font-size:11px">public</span>, <span style="color:rgb(187,44,162);font-family:Menlo;font-size:11px">@warn_unused_result</span>, <span style="color:rgb(187,44,162);font-family:Menlo;font-size:11px">@noescape</span>, <span style="color:rgb(187,44,162);font-family:Menlo;font-size:11px">throws</span> and <span style="color:rgb(187,44,162);font-family:Menlo;font-size:11px">rethrows</span> dance). An already working implementation can be found in the <a href="https://github.com/knomi/Allsorts/blob/protocol-extensions/Allsorts/BinarySearch.swift" target="_blank">protocol-extensions branch</a>:</div><div><div><br></div></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div><div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><span style="color:#bb2ca2">enum</span> Ordering : <span style="color:#703daa">Int</span> { <span style="color:rgb(187,44,162)">case</span> LT = -1, EQ, GT } <span style="color:rgb(0,132,0)">// NSComparisonResult, basically</span></div></div></div><div><div><br></div></div><div><div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;color:rgb(112,61,170)"><span style="color:#bb2ca2">extension</span><span style="color:#000000"> </span>CollectionType<span style="color:#000000"> </span><span style="color:#bb2ca2">where</span><span style="color:#000000"> Index : </span>RandomAccessIndexType<span style="color:#000000"> {</span></div></div></div><div><div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;min-height:13px"> <span style="color:rgb(187,44,162)">func</span> binaryFind(ordering: Generator.Element -> <span style="color:rgb(79,129,135)">Ordering</span>) -> <span style="color:rgb(112,61,170)">Self</span>.<span style="color:rgb(112,61,170)">Index</span>?</div></div></div><div><div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;min-height:13px"> <span style="color:rgb(187,44,162)">func</span> binarySearch(ordering: Generator.Element -> <span style="color:rgb(79,129,135)">Ordering</span>) -> <span style="color:rgb(112,61,170)">Self</span>.<span style="color:rgb(112,61,170)">Index</span></div></div></div><div><div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;min-height:13px"> <span style="color:rgb(187,44,162)">func</span> lowerBound(ordering: Generator.Element -> <span style="color:rgb(79,129,135)">Ordering</span>) -> <span style="color:rgb(112,61,170)">Self</span>.<span style="color:rgb(112,61,170)">Index</span></div></div></div><div><div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;min-height:13px"> <span style="color:rgb(187,44,162)">func</span> upperBound(ordering: Generator.Element -> <span style="color:rgb(79,129,135)">Ordering</span>) -> <span style="color:rgb(112,61,170)">Self</span>.<span style="color:rgb(112,61,170)">Index</span></div></div></div><div><div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;min-height:13px"> <span style="color:rgb(187,44,162)">func</span> equalRange(ordering: Generator.Element -> <span style="color:rgb(79,129,135)">Ordering</span>) -> <span style="color:rgb(112,61,170)">Range</span><<span style="color:rgb(112,61,170)">Self</span>.<span style="color:rgb(112,61,170)">Index</span>></div></div></div><div><div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo">}</div></div></div><div><div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;min-height:13px"><br></div></div></div><div><div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;color:rgb(112,61,170)"><span style="color:#bb2ca2">extension</span><span style="color:#000000"> </span>CollectionType<span style="color:#000000"> </span><span style="color:#bb2ca2">where</span><span style="color:#000000"> Index : </span>RandomAccessIndexType<span style="color:#000000">, Generator.Element : </span>Comparable<span style="color:#000000"> {</span></div></div></div><div><div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;min-height:13px"> <span style="color:rgb(187,44,162)">func</span> binaryFind(value: <span style="color:rgb(112,61,170)">Generator</span>.<span style="color:rgb(112,61,170)">Element</span>) -> <span style="color:rgb(112,61,170)">Self</span>.<span style="color:rgb(112,61,170)">Index</span>?</div></div></div><div><div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;min-height:13px"> <span style="color:rgb(187,44,162)">func</span> binarySearch(value: <span style="color:rgb(112,61,170)">Generator</span>.<span style="color:rgb(112,61,170)">Element</span>) -> <span style="color:rgb(112,61,170)">Self</span>.<span style="color:rgb(112,61,170)">Index</span></div></div></div><div><div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;min-height:13px"> <span style="color:rgb(187,44,162)">func</span> lowerBound(value: <span style="color:rgb(112,61,170)">Generator</span>.<span style="color:rgb(112,61,170)">Element</span>) -> <span style="color:rgb(112,61,170)">Self</span>.<span style="color:rgb(112,61,170)">Index</span></div></div></div><div><div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;min-height:13px"> <span style="color:rgb(187,44,162)">func</span> upperBound(value: <span style="color:rgb(112,61,170)">Generator</span>.<span style="color:rgb(112,61,170)">Element</span>) -> <span style="color:rgb(112,61,170)">Self</span>.<span style="color:rgb(112,61,170)">Index</span></div></div></div><div><div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;min-height:13px"> <span style="color:rgb(187,44,162)">func</span> equalRange(value: <span style="color:rgb(112,61,170)">Generator</span>.<span style="color:rgb(112,61,170)">Element</span>) -> <span style="color:rgb(112,61,170)">Range</span><<span style="color:rgb(112,61,170)">Self</span>.<span style="color:rgb(112,61,170)">Index</span>></div></div></div><div><div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo">}</div></div></div></blockquote><div><div><br></div><div><blockquote type="cite">On 15 Feb 2016, at 23:34, Dave Abrahams via swift-evolution <<a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a>> wrote:</blockquote></div><div><blockquote type="cite"><span></span><br></blockquote><blockquote type="cite">Note that you don't need random access to get an advantage from binary search if the comparison is sufficiently expensive.</blockquote></div><div><div><br></div><div>One current restriction is that I only define these functions over collections with random access. What it boils down to is the implementation of <span style="font-family:Menlo;font-size:11px">midIndex</span>:</div><div><br></div></div></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div><div><div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><span style="color:rgb(187,44,162)">internal</span> <span style="color:rgb(187,44,162)">func</span> midIndex<Ix : <span style="color:rgb(112,61,170)">RandomAccessIndexType</span>>(range: <span style="color:rgb(112,61,170)">Range</span><<span style="color:rgb(112,61,170)">Ix</span>>) -> <span style="color:rgb(112,61,170)">Ix</span> {</div></div></div></div><div><div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:rgb(187,44,162)">let</span> fullDistance = range.<span style="color:rgb(112,61,170)">startIndex</span>.<span style="color:rgb(61,29,129)">distanceTo</span>(range.<span style="color:rgb(112,61,170)">endIndex</span>)</div></div></div><div><div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:rgb(187,44,162)">return</span> range.<span style="color:rgb(112,61,170)">startIndex</span>.<span style="color:rgb(61,29,129)">advancedBy</span>(fullDistance <span style="color:rgb(61,29,129)">/</span> <span style="color:rgb(39,42,216)">2</span>)</div></div></div><div><div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo">}</div></div></div></blockquote><div><div><br></div><div>That could certainly be written with weaker constraints as well; I just haven't checked how it affects to the interface in terms of duplication of code, and to the performance of the random access version.</div><span class="HOEnZb"><font color="#888888"><div><br></div><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><div style="word-wrap:break-word"><br></div></span></div></span></div></font></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>