on Thu Apr 28 2016, Jeff Hajewski <[email protected]> wrote:
> Dave - I think it boils down to a gap in communication. We were under the > impression that the goal was a pure extension of CollectionType, without > making > any requirements on Generator.Element (i.e., your requiring it to be > comparable), where binary search, lower bound, and upper bound all work with > the > same unary predicate. > Of course, as you demonstrated, it is trivial to implement when > Generator.Element is Comparable, but if you relax that requirement it > is not possible to create a set of functions (binary search, lower > bound, upper bound) that all take the same unary predicate. I'm sorry if I gave you the wrong impression. What I posted was exactly what I had in mind. > We ultimately came up with a slightly different approach, implementing > binary search similar to your example, but a different take on lower > bound, upper bound, and range. I suppose we should just send out our > proposal and get everyone's take on it. > > Jeff > > On Thu, Apr 28, 2016 at 5:06 PM, Dave Abrahams via swift-evolution > <[email protected]> wrote: > > on Thu Apr 28 2016, Jeff Hajewski > <[email protected]> wrote: > > > Thanks for bringing this back into the spotlight Pyry. A few of us have > been > > working on this issue here: > > > > https://github.com/lorenzoracca/Swift-binary-search > > > > 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. > > > > 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? > > Or you could just do it like this (Swift 2.2-compatible). Am I missing > something? > > extension CollectionType { > /// Returns the index of the first element satisfying `predicate`, > /// or `endIndex` if no such element exists. > /// > /// - Requires: `self` is partitioned with respect to `predicate`; > /// that is, there exists an index `i` in `startIndex...endIndex` > /// such that `predicate` returns `false` for every element of > /// `self[startIndex..<i]` and returns `true` for every element > /// of `self[i..<endIndex]`. > @warn_unused_result > public func binarySearch( > predicate: (Self.Generator.Element)->Bool > ) -> Index { > var len = count > var min = startIndex > while len > 0 { > let half = len/2 > let middle = min.advancedBy(half) > > if !predicate(self[middle]) { > min = middle.successor() > len -= half.successor() > } else { > len = half > } > } > return min > } > } > > extension CollectionType where Generator.Element : Comparable { > /// Returns the index of the first element greater than or equal to > /// `target`, or `endIndex` if no such element exists. > /// > /// - Requires: `self` is sorted. > @warn_unused_result > public func lowerBound(target: Self.Generator.Element) -> Index { > return binarySearch { $0 >= target } > } > > /// Returns the index of the first element greater than > /// `target`, or `endIndex` if no such element exists. > /// > /// - Requires: `self` is sorted. > @warn_unused_result > public func upperBound(target: Self.Generator.Element) -> Index { > return binarySearch { $0 > target } > } > } > > //===--- TEST IT - > ---------------------------------------------------------===// > import Darwin > for _ in 0..<1000 { > // build a sorted array of up to 30 values in the range 0..<10 > var a : Array<Int> = [] > for _ in 0..<arc4random_uniform(30) { > a.append(Int(arc4random_uniform(10))) > } > a.sortInPlace() > > print(a) > > for i in -3...14 { > let l = a.lowerBound(i) > let u = a.upperBound(i) > assert(l >= 0) > assert(u <= a.count) > assert(l <= u) > if l > 0 { > assert(a[l - 1] < i) > } > if l < a.count { > assert(a[l] >= i) > } > if u > 0 { > assert(a[u - 1] <= i) > } > if u < a.count { > assert(a[u] > i) > } > } > } > > -- > Dave > > _______________________________________________ > swift-evolution mailing list > [email protected] > https://lists.swift.org/mailman/listinfo/swift-evolution > > _______________________________________________ > swift-evolution mailing list > [email protected] > https://lists.swift.org/mailman/listinfo/swift-evolution -- Dave _______________________________________________ swift-evolution mailing list [email protected] https://lists.swift.org/mailman/listinfo/swift-evolution
