<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=""><div class="">Actually, the binary search proposal settled on a definition of a partition point method (and probably a partition method as well) that provides the real implementation details anyway, so these could go ahead as-is. You’re right that the search methods themselves may prefer to wait, since .sort() will likely change to reflect the new strict ordering operator, in which case it makes sense to delay those to be consistent, but partitioning should be unaffected.</div><br class=""><div><blockquote type="cite" class=""><div class="">On 28 Apr 2016, at 13:03, Jeff Hajewski 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=""><div dir="ltr" class="">Thanks for bringing this back into the spotlight Pyry. A few of us have been working on this issue here:<div class=""><br class=""></div><div class=""><a href="https://github.com/lorenzoracca/Swift-binary-search" class="">https://github.com/lorenzoracca/Swift-binary-search</a><br class=""></div><div class=""><br class=""></div><div class="">However we have sort of stalled as we have been unable to come up with a unary approach that Dave suggested using just Bool return values. And of course, as you say, the three case order enum would make this a trivial problem.</div><div class=""><br class=""></div><div class="">I guess the question is, do we move forward without a unary implementation and update if/when we get a three case Order enum or do we wait on a three case Order enum and implement a fully generic version once?</div><div class=""><br class=""></div><div class=""> Jeff</div></div><div class="gmail_extra"><br class=""><div class="gmail_quote">On Thu, Apr 28, 2016 at 7:36 AM, Pyry Jahkola <span dir="ltr" class=""><<a href="mailto:pyry.jahkola@iki.fi" target="_blank" class="">pyry.jahkola@iki.fi</a>></span> wrote:<br class=""><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word" class="">Bringing up this topic because it became relevant with Brent Royal-Gordon's "<a href="http://thread.gmane.org/gmane.comp.lang.swift.evolution/15180" target="_blank" class="">[Idea] Bringing the partial/total ordering distinction into Comparable</a><span style="font-family:'Helvetica Neue'" class="">".</span><div class=""><font face="Helvetica Neue" class=""><br class=""></font></div><div class=""><font face="Helvetica Neue" class="">If the `</font><font face="Menlo" class=""><span style="font-size:11px" class=""><=></span></font><font face="Helvetica Neue" class="">` operator with a return type of a three-case `</font><font face="Menlo" class=""><span style="font-size:11px" class=""><b class="">enum</b> Order</span></font><font face="Helvetica Neue" class="">`, you can fully define the most generic versions of binary searches as:</font></div><div class=""><font face="Helvetica Neue" class=""><br class=""></font></div><div class=""><font face="Menlo" class=""><span style="font-size:11px" class=""> lowerBound(compare: Self.Collection.Element -> Order) -> Index</span></font></div><div class=""><font face="Helvetica Neue" class=""><br class=""></font></div><div class=""><font face="Helvetica Neue" class="">etc.<br class=""></font><div class=""><br class=""><div class=""><blockquote type="cite" class=""><div class="">On 29 Mar 2016, at 13:43, Jeff Hajewski via swift-evolution <<a href="mailto:swift-evolution@swift.org" target="_blank" class="">swift-evolution@swift.org</a>> wrote:</div><br class=""><div class=""><div dir="ltr" style="font-family:Helvetica;font-size:13px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px" class=""><div class="">I've responded below, but just for the sake of being explicit, this is roughly </div><div class="">the signature for lowerBound, upperBound, and binarySearch I have in </div><div class="">mind based on your comments of a unary predicate:</div><div class=""><br class=""></div><div class="">lowerBound(isOrderedBelow: Self.Collection.Element -> Bool) -> Index</div><div class="">upperBound(isOrderedBelow: Self.Collection.Element -> Bool) -> Index</div><div class="">binarySearch(isOrderedBelow: Self.Collection.Element -> Bool) -> Bool<br class=""><div class="gmail_extra"><br class=""></div><div class="gmail_extra">That's the general structure - the key is that the exact same predicate is</div><div class="gmail_extra">used in all signatures. The predicate would be defined along the lines of</div><div class="gmail_extra">a binary predicate where one of the parameters is fixed as the search value.</div><div class="gmail_extra">The unary predicate could be formed along the lines of:</div><div class="gmail_extra"><br class=""></div><div class="gmail_extra">let binaryPred = { $0 < $1 }</div><div class="gmail_extra">let unnaryPred = binaryPred($0, value)</div><div class="gmail_extra"><br class=""></div><div class="gmail_extra">where value is the search value. The main point of illustrating that is that</div><div class="gmail_extra">once the unary predicate is defined, we can't change the position of the</div><div class="gmail_extra">search value within the predicate like they do in the C++ implementation.</div></div></div></div></blockquote></div><br class=""></div></div><div class="">You're right, there's no way a <font face="Menlo" class=""><span style="font-size:11px" class="">Bool</span></font>-returning unary comparator could allow you to implement anything but lowerBound. With a three-value result, however, you've got all you need.</div><div class=""><br class=""></div><div class="">I've shamelessly plugged before but for the sake of proving a point, I'll do it once more: I think this little library we did works as a good starting point for a stdlib binary search API: <a href="https://github.com/knomi/Allsorts/blob/master/Allsorts/BinarySearch.swift" target="_blank" class="">https://github.com/knomi/Allsorts/blob/master/Allsorts/BinarySearch.swift</a></div><span class="HOEnZb"><font color="#888888" class=""><div class=""><br class=""></div><div class="">— Pyry</div></font></span></div></blockquote></div><br class=""></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>