<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="">Hello,<div class=""><br class=""></div><div class="">I am working on <a href="https://bugs.swift.org/browse/SR-368" class="">SR-368</a> and am hoping to get some feedback from the community.</div><div class=""><br class=""></div><div class=""><b class="">Description</b></div><div class="">Implement analogs to C++’s binary_search, lower_bound, upper_bound, and equal_range algorithms.</div><div class=""><br class=""></div><div class=""><b class="">Initial Proposal</b></div><div class="">I propose adding four methods for generic <i class="">Array</i> and adding four methods for <i class="">Array</i>s that conform to <i class="">Comparable</i>:</div><div class=""><br class=""></div><div class=""><br class=""></div><div class=""><span style="color: rgb(112, 61, 170); font-family: Menlo; font-size: 10px;" class=""><b class="">Array</b></span></div><div class=""><div style="margin: 0px; font-size: 10px; line-height: normal; font-family: Menlo; color: rgb(187, 44, 162);" class="">@warn_unused_result</div><div style="margin: 0px; font-size: 10px; line-height: normal; font-family: Menlo;" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">func</span> lowerBound(value: <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Array</span>.<span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Element</span>, <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">@noescape</span> isOrderedBefore: (lhs: <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Array</span>.<span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Element</span>, rhs: <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Array</span>.<span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Element</span>) -> <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Bool</span>) -> <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Int</span>?</div></div><div style="margin: 0px; font-size: 10px; line-height: normal; font-family: Menlo;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class=""><div style="font-family: Menlo; font-size: 10px; margin: 0px; line-height: normal; color: rgb(187, 44, 162);" class="">@warn_unused_result</div><div style="font-family: Menlo; font-size: 10px; margin: 0px; line-height: normal;" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">func</span> upperBound(value: <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Array</span>.<span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Element</span>, <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">@noescape</span> isOrderedBefore: (lhs: <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Array</span>.<span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Element</span>, rhs: <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Array</span>.<span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Element</span>) -> <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Bool</span>) -> <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Int</span>?</div><div style="font-family: Menlo; font-size: 10px; margin: 0px; line-height: normal;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class=""><div style="font-family: Menlo; font-size: 10px; margin: 0px; line-height: normal; color: rgb(187, 44, 162);" class="">@warn_unused_result</div><div style="font-family: Menlo; font-size: 10px; margin: 0px; line-height: normal;" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">func</span> binarySearch(value: <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Array</span>.<span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Element</span>, <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">@noescape</span> isOrderedBefore:(lhs: <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Array</span>.<span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Element</span>, rhs: <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Array</span>.<span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Element</span>) -> <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Bool</span>) -> <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Bool</span></div><div style="font-family: Menlo; font-size: 10px; margin: 0px; line-height: normal;" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class=""><br class=""></span></div><div style="font-family: Menlo; font-size: 10px; margin: 0px; line-height: normal;" class=""><div style="margin: 0px; line-height: normal; color: rgb(187, 44, 162);" class="">@warn_unused_result</div><div style="margin: 0px; line-height: normal;" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">func</span> equalRange(value: <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Array</span>.<span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Element</span>, <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">@noescape</span> isOrderedBefore: (lhs: <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Array</span>.<span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Element</span>, rhs: <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Array</span>.<span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Element</span>) -> <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Bool</span>) -> <span style="color: rgb(112, 61, 170);" class="">Range</span><<span style="color: rgb(112, 61, 170);" class="">Int</span>>?</div></div><div style="font-family: Menlo; font-size: 10px; margin: 0px; line-height: normal;" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class=""><br class=""></span></div><div style="font-family: Menlo; font-size: 10px; margin: 0px; line-height: normal;" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class=""><br class=""></span></div><div style="font-family: Menlo; font-size: 10px; margin: 0px; line-height: normal;" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class=""><b class="">Array: Comparable</b></span></div><div style="margin: 0px; line-height: normal;" class=""><div style="font-family: Helvetica; font-size: 12px;" class=""><div style="margin: 0px; font-size: 10px; line-height: normal; font-family: Menlo; color: rgb(187, 44, 162);" class="">@warn_unused_result</div><div style="margin: 0px; font-size: 10px; line-height: normal; font-family: Menlo;" class=""><span style="color: rgb(187, 44, 162);" class="">func</span> lowerBound(value: <span style="color: rgb(112, 61, 170);" class="">Array</span>.<span style="color: rgb(112, 61, 170);" class="">Element</span>) -> <span style="color: rgb(112, 61, 170);" class="">Int</span>?</div></div><div style="font-family: Menlo; font-size: 10px; margin: 0px; line-height: normal;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class=""><div style="font-family: Menlo; font-size: 10px; margin: 0px; line-height: normal; color: rgb(187, 44, 162);" class="">@warn_unused_result</div><div style="font-family: Menlo; font-size: 10px; margin: 0px; line-height: normal;" class=""><span style="color: rgb(187, 44, 162);" class="">func</span> upperBound(value: <span style="color: rgb(112, 61, 170);" class="">Array</span>.<span style="color: rgb(112, 61, 170);" class="">Element</span>) -> <span style="color: rgb(112, 61, 170);" class="">Int</span>?</div><div style="font-family: Menlo; font-size: 10px; margin: 0px; line-height: normal;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class=""><div style="font-family: Menlo; font-size: 10px; margin: 0px; line-height: normal; color: rgb(187, 44, 162);" class="">@warn_unused_result</div><div style="font-family: Menlo; font-size: 10px; margin: 0px; line-height: normal;" class=""><span style="color: rgb(187, 44, 162);" class="">func</span> binarySearch(value: <span style="color: rgb(112, 61, 170);" class="">Array</span>.<span style="color: rgb(112, 61, 170);" class="">Element</span>) -> <span style="color: rgb(112, 61, 170);" class="">Bool</span></div><div style="font-family: Menlo; font-size: 10px; margin: 0px; line-height: normal;" class=""><span style="color: rgb(112, 61, 170);" class=""><br class=""></span></div><div style="margin: 0px; line-height: normal;" class=""><div style="font-family: Menlo; font-size: 10px; margin: 0px; line-height: normal; color: rgb(187, 44, 162);" class="">@warn_unused_result</div><div style="font-family: Menlo; font-size: 10px; margin: 0px; line-height: normal;" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">func</span> equalRange(value: <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Array</span>.<span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Element</span>) -> <span style="color: rgb(112, 61, 170);" class="">Range</span><<span style="color: rgb(112, 61, 170);" class="">Int</span>>?</div><div style="font-family: Menlo; font-size: 10px; margin: 0px; line-height: normal;" class=""><br class=""></div><div style="font-family: Menlo; font-size: 10px; margin: 0px; line-height: normal;" class=""><span style="font-family: Helvetica; font-size: 12px;" class=""><b class="">Discussion</b></span></div><div style="margin: 0px; line-height: normal;" class="">The main issue I’d like to discuss is how do we want to add these to Swift? My thoughts are as follows:</div><div style="margin: 0px; line-height: normal;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class=""><ul class="MailOutline"><li class="">These should be as generic as possible. I initially started at the CollectionType level but it seemed that the problem was ultimately reduced to an Array (through the use of various protocols, etc.). For example, suppose we implemented these methods as an extension to CollectionType, if we were to try and call <i class="">binarySearch</i> on a set, we would first need to sort the set, which would return an array, and then we would call <i class="">binarySearch</i> on that array. Similarly, it seems at the SequenceType level the problem ultimately reduces to using Array.</li><li class="">Does it make sense to handle these as public functions? I tend to think not as it seems less idiomatic.</li><li class="">I suggest eight implementations similar to how sort() is handled. If the calling array’s elements conform to Comparable, then no <i class="">isOrderedBefore</i> closure is required since we can use “<“, otherwise the user should supply a closure to allow the algorithm determine how the array elements are ordered.</li><li class="">Similar to the C++ implementations, I avoid recursion and favor while-loops</li><li class="">These methods should be preconditioned on the calling array be partitioned with respect to the passed <i class="">value</i>. As far as I’m aware, there is no “isPartitioned(value:)” method currently available. Should we add this as well? We could use this functionality and not add a isPartitioned method but if we are adding this functionality is there a good reason not to give the public access? The alternative is to not set a precondition and document that the results may not be valid if the calling array is not partitioned with respect to <i class="">value</i>. I favor the preconditioning approach.</li></ul><div class=""><br class=""></div><div class="">Any and all feedback is greatly appreciated!</div><div class=""><br class=""></div><div class="">Thanks</div><div class="">Jeff</div></div></div></div></div></div></div></div></body></html>