[Proposal] Add Binary Search functions to SequenceType

Lorenzo_Racca · 2016-03-15T14:28:42.000Z

Hi all,

Using the library for an app with wide sorted arrays I’ve found out that Swift doesn’t (yet) have binary search functions.
Standing on the fact that C++, Java and .NET all have Binary Search functions in their standard libs, and given the notorious difficulty to create the algorithm (hence the need of developers to trust the library function) I’m proposing to adopt these.
I worked out some code, recalling the C++ functions binary_search, lower_bound and upper_bound.
I’ve tested them and they seem all right.

Also, they all return the `Index` of a found element (say, in an Array), so that they can be implemented to return either a boolean value, or the element itself. They either return nil or -1 if not any or if the predicate isn’t matched, but they all could surely be arranged to return nil.
The code for binarySearch is :

extension CollectionType where Generator.Element : Comparable {
    /// Returns `element.Index` if `element` is in `self`.
    /// If `element` is not in `self`, returns nil.
    @warn_unused_result
    public func binarySearch(element: Generator.Element) -> Index? {

        var left = startIndex
        var right = endIndex

        while (left != right) {
            let mid = left.advancedBy(left.distanceTo(right) / 2)
            let value = self[mid]

            if (value == element) {
                return mid
            }
            if (value < element) {
                left = mid.advancedBy(1)
            }
            if (value > element) {
                right = mid
            }
        }
        return nil
    }
}

lowerBound and upperBound:

extension CollectionType where Generator.Element : Comparable {
    /// Returns the Index of the smallest element in collection matching `predicate`.
    /// If none, returns -1.
    @warn_unused_result
    func lowerBound(predicate: Generator.Element -> Bool) -> Index {
        var result = self.startIndex.advancedBy(-1)
        var low = self.startIndex
        var hi = self.endIndex

        while low != hi {
            let mid = low.advancedBy(low.distanceTo(hi) / 2)

            if predicate(self[mid]) {
                result = mid
                hi = mid
            } else {
                low = mid.advancedBy(1)
            }
        }
        return result
    }
}

extension CollectionType where Generator.Element : Comparable {
    /// Returns the Index of the biggest element in collection matching `predicate`.
    /// If none, returns -1.
    func upperBound(predicate: Generator.Element -> Bool) -> Index {
        var result = startIndex.advancedBy(-1)
        var low = startIndex
        var hi = endIndex

        while low != hi {
            let mid = low.advancedBy(low.distanceTo(hi) / 2)

            if predicate(self[mid]) {
                result = mid
                low = mid.advancedBy(1)
            } else {
                hi = mid
            }
        }
        return result
    }
}

If you wish to try them, usage is :
var array : Array = [1,2,3,4,5]

let a = array.upperBound{$0 < 3} //array[a] = 2
let b = array.lowerBound{$0 > 3} //array[b] = 4

What do you think? Should I commit a new file to proposals?
Should they be added to CollectionType or SequenceType?
It’s obviously open to discussion and change.

Thank you.

Best,

Lorenzo Racca
+39 345 9294756
lorenzo.racca@live.it

Haravikk3 · 2016-03-15T15:37:35.000Z

I’m not sure the documentation matches the .lowerBound() and .upperBound() behaviours accurately enough; it suggests that a bound will be found for a predicate “match”, however if my predicate is { $0 == foo } then these won’t actually work at all unless I get lucky and the middle element is a match, to me this means that they will only work with comparison predicates such as { $0 > foo }, but in that case the lower bound is for the first element that is not greater than foo, but I wouldn’t call it a “match” until I can also test it for equality.

I’ve been doing some work recently on a sorted collection and I implemented a binary search a bit differently. My method returns the nearest index given an isOrderedBefore predicate, returning .endIndex if nothing matches. Implementation below:

  @warn_unused_result
  public func binarySearch(withinRange theRange:Range<Index>?=nil, isOrderedBefore:(Generator.Element) -> Bool) -> Index {
    var low:Index, high:Index
    if let theSpecifiedRange = theRange { low = theSpecifiedRange.startIndex; high = theSpecifiedRange.endIndex }
    else { low = self.startIndex; high = self.endIndex }

    while low != high {
      let mid = low.advancedBy(low.distanceTo(high) / 2)
      if isOrderedBefore(self[mid]) { low = mid.successor() }
      else { high = mid }
    }
    return low
  }

What this gives me is really an insertion index, however I can implement searching for a specific element like so:

    let isOrderedBefore:(Generator.Element, Generator.Element) -> Bool
    func indexOf(theElement:Equatable) -> Index? {
        let theNearestIndex = self.binarySearch(){ self.isOrderedBefore($0, theElement) }
        if theNearestIndex < self.endIndex && self[theNearestIndex] == theElement { return theNearestIndex }
        return nil
    }

I can also do things like a generic insert() method like so:

func insert(theElement:Comparable) { self.insert(theElement, atIndex: self.binarySearch(){ self.isOrderedBefore($0, theElement) }) }

(note I’ve simplified these as examples as they won’t go into CollectionType as-is, it’s just to give you the idea).

Anyway, it seems to me that this enables simple matching of both an exact element and the lower bound (this is what the .indexOf() above should return), while also giving a useful value if the element isn’t found, though it does require testing the result to be sure. When it comes to matching a specific element, the above actually eliminates tests for equality during the search, only having to test once at the end to confirm the result is a match.

I also added a variable starting range, as I had to handle merging two sorted collections, in which case it’s useful to restrict the search range as you go since there’s no point revisiting indices that you’ve passed already if the elements are sorted properly.

The above can also perform an upper bound search by passing in a predicate such as { $0 <= foo }, though in that case you’re performing all the extra comparisons plus a check at the end, so there might still be an argument for two methods, e.g nearestLowerBound() and nearestUpperBound().

Lastly, in my case I’ve defined the above method on CollectionType directly, rather than requiring Comparable; since it takes a predicate its only requirement is the collection is sorted prior to search it. In fact, constraining the method to Comparable doesn’t guarantee that the collection is sorted, only that its elements can be compared in isolation.

···

On 15 Mar 2016, at 14:28, Lorenzo Racca via swift-evolution <swift-evolution@swift.org> wrote:

Hi all,

Using the library for an app with wide sorted arrays I’ve found out that Swift doesn’t (yet) have binary search functions.
Standing on the fact that C++, Java and .NET all have Binary Search functions in their standard libs, and given the notorious difficulty to create the algorithm (hence the need of developers to trust the library function) I’m proposing to adopt these.
I worked out some code, recalling the C++ functions binary_search, lower_bound and upper_bound.
I’ve tested them and they seem all right.

Also, they all return the `Index` of a found element (say, in an Array), so that they can be implemented to return either a boolean value, or the element itself. They either return nil or -1 if not any or if the predicate isn’t matched, but they all could surely be arranged to return nil.
The code for binarySearch is :

extension CollectionType where Generator.Element : Comparable {
    /// Returns `element.Index` if `element` is in `self`.
    /// If `element` is not in `self`, returns nil.
    @warn_unused_result
    public func binarySearch(element: Generator.Element) -> Index? {

        var left = startIndex
        var right = endIndex

        while (left != right) {
            let mid = left.advancedBy(left.distanceTo(right) / 2)
            let value = self[mid]

            if (value == element) {
                return mid
            }
            if (value < element) {
                left = mid.advancedBy(1)
            }
            if (value > element) {
                right = mid
            }
        }
        return nil
    }
}

lowerBound and upperBound:

extension CollectionType where Generator.Element : Comparable {
    /// Returns the Index of the smallest element in collection matching `predicate`.
    /// If none, returns -1.
    @warn_unused_result
    func lowerBound(predicate: Generator.Element -> Bool) -> Index {
        var result = self.startIndex.advancedBy(-1)
        var low = self.startIndex
        var hi = self.endIndex

        while low != hi {
            let mid = low.advancedBy(low.distanceTo(hi) / 2)

            if predicate(self[mid]) {
                result = mid
                hi = mid
            } else {
                low = mid.advancedBy(1)
            }
        }
        return result
    }
}

extension CollectionType where Generator.Element : Comparable {
    /// Returns the Index of the biggest element in collection matching `predicate`.
    /// If none, returns -1.
    func upperBound(predicate: Generator.Element -> Bool) -> Index {
        var result = startIndex.advancedBy(-1)
        var low = startIndex
        var hi = endIndex

        while low != hi {
            let mid = low.advancedBy(low.distanceTo(hi) / 2)

            if predicate(self[mid]) {
                result = mid
                low = mid.advancedBy(1)
            } else {
                hi = mid
            }
        }
        return result
    }
}

If you wish to try them, usage is :
var array : Array = [1,2,3,4,5]

let a = array.upperBound{$0 < 3} //array[a] = 2
let b = array.lowerBound{$0 > 3} //array[b] = 4

What do you think? Should I commit a new file to proposals?
Should they be added to CollectionType or SequenceType?
It’s obviously open to discussion and change.

Thank you.

Best,

Lorenzo Racca
+39 345 9294756
lorenzo.racca@live.it <mailto:lorenzo.racca@live.it>

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Jeff_Hajewski · 2016-03-15T17:07:21.000Z

This is something I've been working on as well. The issue I've been stuck
on is how we define the predicate and match the definitions of lower_bound
and upper_bound from C++. It seems to me that the focus should be on these
implementations, since once we have these a simple binary_search follows.
Specifically, the issue I'm encountering at the moment is handling
`!predicate`. If `predicate` is sorting on a rule like $0 < 3, for example,
then the complement is $0 >= 3, which has the effect of creating an upper
bound inclusive of 3. To be consistent with the C++ implementation, the
upper bound should be strictly greater than 3. In C++ they are able to get
around this issue by swapping the indices within the `comp` function (our
`predicate`) to eliminate the equality case (e.g., looking at `comp(i,j)`
and `comp(j,i)`). I don't see a way to easily do this in our case if we
want keep `predicate` of the form `Generator.Element -> Bool`.

The following implementations are as far as I've gotten so far.

extension CollectionType {

/// Returns an index such that each element at or above the index is
partitioned from below by the partition predicate

///

/// - Parameter partitionPredicate: The partioning predicate returns
`true` for elements in the collection that are

/// ordered below, with respet to the
partitioning predicate.

/// - Complexity: O(lg(n))

///

/// - Returns: An index such that each element at or above the returned
index evaluates as `false` with respect to `partitionPredicate(_:)`

@warn_unused_result

func lowerBound(@noescape partitionPredicate: Self.Generator.Element ->
Bool) -> Index {

var len = self.startIndex.distanceTo(self.endIndex)

var firstIndex = self.startIndex

while len > 0 {

let half = len/2

let middle = firstIndex.advancedBy(half)

if partitionPredicate(self[middle]) {

firstIndex = middle.advancedBy(1)

len -= half + 1

} else {

len = half

}

return firstIndex

}

/// Returns an index such that each element below the index is strictly
less than the partition predicate

///

/// - Parameter partitionPredicate: The partioning predicate. Returns
`true` for elements in the collection that are

/// ordered below, with respet to the
partitioning predicate.

/// - Complexity: O(lg(n))

///

/// - Returns: An index such that each element evaluates as `false` with
respect to `partitionPredicate(_:)`

@warn_unused_result

func upperBound(@noescape partitionPredicate:Self.Generator.Element ->
Bool) -> Index {

var len = self.startIndex.distanceTo(self.endIndex)

var firstIndex = self.startIndex

while len > 0 {

let half = len/2

let middle = firstIndex.advancedBy(half)

if !partitionPredicate(self[middle]) {

len = half

} else {

firstIndex = middle.advancedBy(1)

len -= half + 1

}

return firstIndex

}

/// Returns `true` if element is in Collection, `false` otherwise

@warn_unused_result

func binarySearch(@noescape partitionPredicate:Self.Generator.Element
-> Bool) -> Bool {

let lb = lowerBound(partitionPredicate)

return (lb != self.endIndex) && !partitionPredicate(self[lb])

}

Again, `upperBound` isn't working like it should, mainly because I'm
looking at the complement of `predicate`. The only way I see getting around
this is making `predicate` take the form `(Generator.Element,
Generator.Element) -> Bool`, but this comes at the cost of some added
complexity on the user end as you can't simply pass a closure like `{ $0 <
3 }`. I suspect there is an easy solution here and I'm just having a mental
block...

Jeff

···

On Tue, Mar 15, 2016 at 11:37 AM, Haravikk via swift-evolution < swift-evolution@swift.org> wrote:

I’m not sure the documentation matches the .lowerBound() and .upperBound()
behaviours accurately enough; it suggests that a bound will be found for a
predicate “match”, however if my predicate is { $0 == foo } then these
won’t actually work at all unless I get lucky and the middle element is a
match, to me this means that they will only work with comparison predicates
such as { $0 > foo }, but in that case the lower bound is for the first
element that is not greater than foo, but I wouldn’t call it a “match”
until I can also test it for equality.

I’ve been doing some work recently on a sorted collection and I
implemented a binary search a bit differently. My method returns the
nearest index given an isOrderedBefore predicate, returning .endIndex if
nothing matches. Implementation below:

@warn_unused_result
public func binarySearch(withinRange theRange:Range<Index>?=nil,
isOrderedBefore:(Generator.Element) -> Bool) -> Index {
var low:Index, high:Index
if let theSpecifiedRange = theRange { low = theSpecifiedRange.startIndex;
high = theSpecifiedRange.endIndex }
else { low = self.startIndex; high = self.endIndex }

while low != high {
let mid = low.advancedBy(low.distanceTo(high) / 2)
if isOrderedBefore(self[mid]) { low = mid.successor() }
else { high = mid }
}
return low
}

What this gives me is really an insertion index, however I can implement
searching for a specific element like so:

    let isOrderedBefore:(Generator.Element, Generator.Element) -> Bool
    func indexOf(theElement:Equatable) -> Index? {
        let theNearestIndex = self.binarySearch(){ self.isOrderedBefore($0,
theElement) }
        if theNearestIndex < self.endIndex && self[theNearestIndex] ==
theElement { return theNearestIndex }
        return nil
    }

I can also do things like a generic insert() method like so:

    func insert(theElement:Comparable) { self.insert(theElement, atIndex:
self.binarySearch(){ self.isOrderedBefore($0, theElement) }) }

(note I’ve simplified these as examples as they won’t go into
CollectionType as-is, it’s just to give you the idea).

Anyway, it seems to me that this enables simple matching of both an exact
element and the lower bound (this is what the .indexOf() above should
return), while also giving a useful value if the element isn’t found,
though it does require testing the result to be sure. When it comes to
matching a specific element, the above actually eliminates tests for
equality during the search, only having to test once at the end to confirm
the result is a match.

I also added a variable starting range, as I had to handle merging two
sorted collections, in which case it’s useful to restrict the search range
as you go since there’s no point revisiting indices that you’ve passed
already if the elements are sorted properly.

The above can also perform an upper bound search by passing in a predicate
such as { $0 <= foo }, though in that case you’re performing all the extra
comparisons *plus* a check at the end, so there might still be an
argument for two methods, e.g nearestLowerBound() and nearestUpperBound().

Lastly, in my case I’ve defined the above method on CollectionType
directly, rather than requiring Comparable; since it takes a predicate its
only requirement is the collection is sorted prior to search it. In fact,
constraining the method to Comparable doesn’t guarantee that the collection
is sorted, only that its elements can be compared in isolation.

On 15 Mar 2016, at 14:28, Lorenzo Racca via swift-evolution < > swift-evolution@swift.org> wrote:

Hi all,

Using the library for an app with wide sorted arrays I’ve found out that
Swift doesn’t (yet) have binary search functions.
Standing on the fact that C++, Java and .NET all have Binary Search
functions in their standard libs, and given the notorious difficulty to
create the algorithm (hence the need of developers to trust the library
function) I’m proposing to adopt these.
I worked out some code, recalling the C++ functions binary_search,
lower_bound and upper_bound.
I’ve tested them and they seem all right.

Also, they all return the `Index` of a found element (say, in an Array),
so that they can be implemented to return either a boolean value, or the
element itself. They either return nil or -1 if not any or if the predicate
isn’t matched, but they all could surely be arranged to return nil.
The code for binarySearch is :

extension CollectionType where Generator.Element : Comparable {
    /// Returns `element.Index` if `element` is in `self`.
    /// If `element` is not in `self`, returns nil.
    @warn_unused_result
    public func binarySearch(element: Generator.Element) -> Index? {

        var left = startIndex
        var right = endIndex

        while (left != right) {
            let mid = left.advancedBy(left.distanceTo(right) / 2)
            let value = self[mid]

            if (value == element) {
                return mid
            }
            if (value < element) {
                left = mid.advancedBy(1)
            }
            if (value > element) {
                right = mid
            }
        }
        return nil
    }
}

lowerBound and upperBound:

extension CollectionType where Generator.Element : Comparable {
    /// Returns the Index of the smallest element in collection matching
`predicate`.
    /// If none, returns -1.
    @warn_unused_result
    func lowerBound(predicate: Generator.Element -> Bool) -> Index {
        var result = self.startIndex.advancedBy(-1)
        var low = self.startIndex
        var hi = self.endIndex

        while low != hi {
            let mid = low.advancedBy(low.distanceTo(hi) / 2)

            if predicate(self[mid]) {
                result = mid
                hi = mid
            } else {
                low = mid.advancedBy(1)
            }
        }
        return result
    }
}

extension CollectionType where Generator.Element : Comparable {
    /// Returns the Index of the biggest element in collection matching
`predicate`.
    /// If none, returns -1.
    func upperBound(predicate: Generator.Element -> Bool) -> Index {
        var result = startIndex.advancedBy(-1)
        var low = startIndex
        var hi = endIndex

        while low != hi {
            let mid = low.advancedBy(low.distanceTo(hi) / 2)

            if predicate(self[mid]) {
                result = mid
                low = mid.advancedBy(1)
            } else {
                hi = mid
            }
        }
        return result
    }
}

If you wish to try them, usage is :
var array : Array = [1,2,3,4,5]

let a = array.upperBound{$0 < 3} //array[a] = 2
let b = array.lowerBound{$0 > 3} //array[b] = 4

What do you think? Should I commit a new file to proposals?
Should they be added to CollectionType or SequenceType?
It’s obviously open to discussion and change.

Thank you.

Best,

Lorenzo Racca
+39 345 9294756
lorenzo.racca@live.it

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Lorenzo_Racca · 2016-03-15T15:48:58.000Z

Thank you Haraviik,

I already knew the impossibility of applying such a predicate as “$0 == 3” and I actually couldn’t quite figure out a solution. Honestly, I’m quite new to Swift :)

Actually at first I thought that no one would use it, as the same result could be achieved using the main binarySearch function.
If the elements to be matched have to be equal it makes no difference whether we retrieve the smallest or greatest, unless the array had multiple entries with same value.
In that case, you are right, my functions do not work properly, but your code seems to be working fine in these situations!
Would you want to cooperate for the proposal?

Lorenzo Racca
+39 345 9294756
lorenzo.racca@live.it

Haravikk3 · 2016-03-15T17:49:58.000Z

I already knew the impossibility of applying such a predicate as “$0 == 3” and I actually couldn’t quite figure out a solution.

I thought so, and I don’t think there is a way to do it, my point was really just that your swift doc comments weren’t clear on that point, then I went off at a bit of a tangent ;)

    /// Returns an index such that each element at or above the index is partitioned from below by the partition predicate
    ///
    /// - Parameter partitionPredicate: The partioning predicate returns `true` for elements in the collection that are
    /// ordered below, with respet to the partitioning predicate.
    /// - Complexity: O(lg(n))
    ///
    /// - Returns: An index such that each element at or above the returned index evaluates as `false` with respect to `partitionPredicate(_:)`
    @warn_unused_result
    func lowerBound(@noescape partitionPredicate: Self.Generator.Element -> Bool) -> Index {

Should probably have "requires: Collection is sorted" or such, as a binary search can’t really guarantee correct behaviour otherwise, no matter what your predicate is. I also kind of prefer a name of isOrderedBefore for the predicate; it matches .sort() and is very specific about what it does.

    /// Returns an index such that each element below the index is strictly less than the partition predicate
    ///
    /// - Parameter partitionPredicate: The partioning predicate. Returns `true` for elements in the collection that are
    /// ordered below, with respet to the partitioning predicate.
    /// - Complexity: O(lg(n))
    ///
    /// - Returns: An index such that each element evaluates as `false` with respect to `partitionPredicate(_:)`
    @warn_unused_result
    func upperBound(@noescape partitionPredicate:Self.Generator.Element -> Bool) -> Index {

Did you mean “each element above the returned index evaluates as false"?

Implementation wise they seem fine, but I think that for correctness you should be using .successor() and .advancedBy(), as not all indexes are numeric.

···

On 15 Mar 2016, at 15:48, Lorenzo Racca <lorenzo.racca@live.it> wrote:
On 15 Mar 2016, at 17:07, Jeff Hajewski <jeff.hajewski@gmail.com> wrote:

Lorenzo_Racca · 2016-03-15T18:58:07.000Z

I already knew the impossibility of applying such a predicate as “$0 == 3” and I actually couldn’t quite figure out a solution.

I thought so, and I don’t think there is a way to do it, my point was really just that your swift doc comments weren’t clear on that point, then I went off at a bit of a tangent ;)

No problem! What I am trying to figure out here is how we should implement the lowerBound and upperBound functions. Should they exactly reflect their C++ counterparts?
Anyway, it seems all of our implementations have the same problem, that they cannot be univocally called with any predicate whatsoever, (or at least it seemed to me during some tests with the implementations :) ), so I don’t really know how we should act. I am a little blocked.
Does anyone have ideas on how that could work no matter what predicate is given? Especially, an upperBound() function, which is a little trickier.

I suspect there is an easy solution here and I'm just having a mental block...

Jeff, I really do feel you, I’m in the same situation!
I think your solution could be applicable though, just in a little more complicated way than C++ did, which is to extract the complement of the predicate and act differently upon that.
As of now I don’t have the time to put down some code (time zone sucks) but will try asap.

Lorenzo

Lorenzo Racca
+39 345 9294756
lorenzo.racca@live.it

···

On Mar 15, 2016, at 6:49 PM, Haravikk <swift-evolution@haravikk.me> wrote:

On 15 Mar 2016, at 15:48, Lorenzo Racca <lorenzo.racca@live.it <mailto:lorenzo.racca@live.it>> wrote:
On Mar 15, 2016, at 6:07 PM, Jeff Hajewski <jeff.hajewski@gmail.come> wrote:

nnnnnnnn · 2016-03-16T06:17:32.000Z

I already knew the impossibility of applying such a predicate as “$0 == 3” and I actually couldn’t quite figure out a solution.

I thought so, and I don’t think there is a way to do it, my point was really just that your swift doc comments weren’t clear on that point, then I went off at a bit of a tangent ;)

No problem! What I am trying to figure out here is how we should implement the lowerBound and upperBound functions. Should they exactly reflect their C++ counterparts?
Anyway, it seems all of our implementations have the same problem, that they cannot be univocally called with any predicate whatsoever, (or at least it seemed to me during some tests with the implementations :) ), so I don’t really know how we should act. I am a little blocked.
Does anyone have ideas on how that could work no matter what predicate is given? Especially, an upperBound() function, which is a little trickier.

The key is to use a binary predicate (as used in sort and partition) instead of a unary predicate. Then you can use the predicate as is for lowerBound or with the arguments "reversed" for upperBound. The methods would have a similar signature to indexOf—one that just takes a value for comparable collections and one that takes a value and a predicate.

The binary search method can be implemented by finding the lower bound, which is by definition not less than the given value, then using the same predicate to check whether the value is not less than the lower bound. If neither is less than the other, you've found the value.

Nate

···

On Mar 15, 2016, at 1:58 PM, Lorenzo Racca via swift-evolution <swift-evolution@swift.org> wrote:

On Mar 15, 2016, at 6:49 PM, Haravikk <swift-evolution@haravikk.me <mailto:swift-evolution@haravikk.me>> wrote:

On 15 Mar 2016, at 15:48, Lorenzo Racca <lorenzo.racca@live.it <mailto:lorenzo.racca@live.it>> wrote:

On Mar 15, 2016, at 6:07 PM, Jeff Hajewski <jeff.hajewski@gmail.come <mailto:jeff.hajewski@gmail.come>> wrote:
I suspect there is an easy solution here and I'm just having a mental block...

Jeff, I really do feel you, I’m in the same situation!
I think your solution could be applicable though, just in a little more complicated way than C++ did, which is to extract the complement of the predicate and act differently upon that.
As of now I don’t have the time to put down some code (time zone sucks) but will try asap.

Lorenzo

Jeff_Hajewski · 2016-03-16T17:27:23.000Z

Nate - I suppose that's really the crux of the matter here. I agree a
binary predicate solves the problem, but is that the route we want to go? I
think it makes sense, but is there a reason we should stick with a unary
predicate? For some reason I had it in my mind that there was mention of
preferring a unary predicate but now that I'm looking back I can't find
anything to that end.

I'll work on a binary predicate implementation and see what the group
thinks.

Thanks!
Jeff

···

On Wed, Mar 16, 2016 at 2:17 AM, Nate Cook via swift-evolution < swift-evolution@swift.org> wrote:

On Mar 15, 2016, at 1:58 PM, Lorenzo Racca via swift-evolution < > swift-evolution@swift.org> wrote:

On Mar 15, 2016, at 6:49 PM, Haravikk <swift-evolution@haravikk.me> wrote:

On 15 Mar 2016, at 15:48, Lorenzo Racca <lorenzo.racca@live.it> wrote:

I already knew the impossibility of applying such a predicate as “$0 == 3”
and I actually couldn’t quite figure out a solution.

I thought so, and I don’t think there is a way to do it, my point was
really just that your swift doc comments weren’t clear on that point, then
I went off at a bit of a tangent ;)

No problem! What I am trying to figure out here is how we should implement
the lowerBound and upperBound functions. Should they exactly reflect their
C++ counterparts?
Anyway, it seems all of our implementations have the same problem, that
they cannot be univocally called with any predicate whatsoever, (or at
least it seemed to me during some tests with the implementations :) ), so I
don’t really know how we should act. I am a little blocked.
Does anyone have ideas on how that could work no matter what predicate is
given? Especially, an upperBound() function, which is a little trickier.

The key is to use a binary predicate (as used in sort and partition)
instead of a unary predicate. Then you can use the predicate as is for
lowerBound or with the arguments "reversed" for upperBound. The methods
would have a similar signature to indexOf—one that just takes a value for
comparable collections and one that takes a value and a predicate.

The binary search method can be implemented by finding the lower bound,
which is by definition not less than the given value, then using the same
predicate to check whether the value is not less than the lower bound. If
neither is less than the other, you've found the value.

Nate

On Mar 15, 2016, at 6:07 PM, Jeff Hajewski <jeff.hajewski@gmail.come> > wrote:

I suspect there is an easy solution here and I'm just having a mental
block...

Jeff, I really do feel you, I’m in the same situation!
I think your solution could be applicable though, just in a little more
complicated way than C++ did, which is to extract the complement of the
predicate and act differently upon that.
As of now I don’t have the time to put down some code (time zone sucks)
but will try asap.

Lorenzo

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

dabrahams · 2016-03-24T20:52:12.000Z

Having an overload that accepts a binary predicate is certainly a nice
convenience, but the most general formulation takes a unary predicate
that “partitions” the collection, i.e. returns false for the first N
elements of the collection and returns true for the rest.

IMO it's important to expose the unary predicate version. Lots of
times, the thing you want to compare against doesn't have the same type
as the elements of the collection. For example, you might have a
collection of key-value pairs where you just want to compare against the
keys, and you may not even be able to create an instance of the whole
element. For more on this, see
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2001/n1313.html

···

on Tue Mar 15 2016, Nate Cook <swift-evolution@swift.org> wrote:

On Mar 15, 2016, at 1:58 PM, Lorenzo Racca via swift-evolution <swift-evolution@swift.org> wrote:

On Mar 15, 2016, at 6:49 PM, Haravikk >>> <swift-evolution@haravikk.me >>> <mailto:swift-evolution@haravikk.me>> > >>> wrote:

On 15 Mar 2016, at 15:48, Lorenzo Racca <lorenzo.racca@live.it <mailto:lorenzo.racca@live.it>> wrote:

I already knew the impossibility of applying such a predicate as “$0 == 3” and I actually couldn’t quite figure out a solution.

I thought so, and I don’t think there is a way to do it, my point
was really just that your swift doc comments weren’t clear on that
point, then I went off at a bit of a tangent ;)

No problem! What I am trying to figure out here is how we should
implement the lowerBound and upperBound functions. Should they
exactly reflect their C++ counterparts?
Anyway, it seems all of our implementations have the same problem,
that they cannot be univocally called with any predicate whatsoever,
(or at least it seemed to me during some tests with the
implementations :) ), so I don’t really know how we should act. I am
a little blocked.
Does anyone have ideas on how that could work no matter what predicate is given? Especially, an upperBound() function, which is a little trickier.

The key is to use a binary predicate (as used in sort and partition)
instead of a unary predicate. Then you can use the predicate as is for
lowerBound or with the arguments "reversed" for upperBound. The
methods would have a similar signature to indexOf—one that just takes
a value for comparable collections and one that takes a value and a
predicate.

--
Dave

Jeff_Hajewski · 2016-03-25T13:48:37.000Z

Dave,

I've been giving this approach a lot of thought (and have read everything
I've been able to find that you've written on the matter several times) and
am not convinced it will work. Implementing a lowerBound function is
trivial with a unary operator. However, implementing an upperBound or
binarySearch function is, at least in my mind, a bit more difficult. The
reason is because with the unary predicate we only know if an element is
strictly less than the search value or greater than or equal to the search
value, whereas in the standard approach we can determine strictly greater
than as well as equivalence by swapping the inputs to the comp function.

For example, consider the set [2, 1, 5, 4]. If we want to search the set
using a unary predicate for 3, we would pass in the closure { $0 < 3 }. I
don't see how we can test for equivalence when all we know is "<" or ">=".
With the standard approach using a binary predicate of `{ $0 < $1 }` we can
use `{ $0 < 3 }` to get the lower bound and then `!{ 3 < $0 }` to get us to
equivalence (or in this case, to return `false`).

Of course, an easy solution around this is to change the definition of the
unary predicate to return a triple of values less/equal/greater. However,
this would either require an additional datatype to the library (which I
don't think is appropriate) OR require the user to increase the complexity
of their predicate function to return -1/0/1. I don't think either of these
are ideal or necessarily better than the standard approach of a value and a
binary predicate.

I really like the idea of the unary predicate approach, I just can't seem
to understand how it will work in practice. What am I missing here?
(hopefully not something completely obvious!)

Thanks!
Jeff

···

On Thu, Mar 24, 2016 at 4:52 PM, Dave Abrahams via swift-evolution < swift-evolution@swift.org> wrote:

on Tue Mar 15 2016, Nate Cook <swift-evolution@swift.org> wrote:

>> On Mar 15, 2016, at 1:58 PM, Lorenzo Racca via swift-evolution < > swift-evolution@swift.org> wrote:
>>
>>> On Mar 15, 2016, at 6:49 PM, Haravikk > >>> <swift-evolution@haravikk.me > >>> <mailto:swift-evolution@haravikk.me>> > > > >>> wrote:
>>>
>>>> On 15 Mar 2016, at 15:48, Lorenzo Racca <lorenzo.racca@live.it > <mailto:lorenzo.racca@live.it>> wrote:
>>>>
>>>> I already knew the impossibility of applying such a predicate as “$0
== 3” and I actually couldn’t quite figure out a solution.
>>>
>>> I thought so, and I don’t think there is a way to do it, my point
>>> was really just that your swift doc comments weren’t clear on that
>>> point, then I went off at a bit of a tangent ;)
>>>
>> No problem! What I am trying to figure out here is how we should
>> implement the lowerBound and upperBound functions. Should they
>> exactly reflect their C++ counterparts?
>> Anyway, it seems all of our implementations have the same problem,
>> that they cannot be univocally called with any predicate whatsoever,
>> (or at least it seemed to me during some tests with the
>> implementations :) ), so I don’t really know how we should act. I am
>> a little blocked.
>> Does anyone have ideas on how that could work no matter what predicate
is given? Especially, an upperBound() function, which is a little trickier.
>
> The key is to use a binary predicate (as used in sort and partition)
> instead of a unary predicate. Then you can use the predicate as is for
> lowerBound or with the arguments "reversed" for upperBound. The
> methods would have a similar signature to indexOf—one that just takes
> a value for comparable collections and one that takes a value and a
> predicate.

Having an overload that accepts a binary predicate is certainly a nice
convenience, but the most general formulation takes a unary predicate
that “partitions” the collection, i.e. returns false for the first N
elements of the collection and returns true for the rest.

IMO it's important to expose the unary predicate version. Lots of
times, the thing you want to compare against doesn't have the same type
as the elements of the collection. For example, you might have a
collection of key-value pairs where you just want to compare against the
keys, and you may not even be able to create an instance of the whole
element. For more on this, see
Binary Search with Heterogeneous Comparison

--
Dave

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

dabrahams · 2016-03-28T19:39:44.000Z

Dave,

I've been giving this approach a lot of thought (and have read everything
I've been able to find that you've written on the matter several times) and
am not convinced it will work. Implementing a lowerBound function is
trivial with a unary operator. However, implementing an upperBound or
binarySearch function is, at least in my mind, a bit more difficult.

upperBound is just lowerBound with an inverted predicate. You can prove
this to yourself by looking at the implementation of any C++ standard
library.

The reason is because with the unary predicate we only know if an
element is strictly less than the search value or greater than or
equal to the search value, whereas in the standard approach we can
determine strictly greater than as well as equivalence by swapping the
inputs to the comp function.

For example, consider the set [2, 1, 5, 4]. If we want to search the set
using a unary predicate for 3, we would pass in the closure { $0 < 3 }. I
don't see how we can test for equivalence when all we know is "<" or ">=".
With the standard approach using a binary predicate of `{ $0 < $1 }` we can
use `{ $0 < 3 }` to get the lower bound and then `!{ 3 < $0 }` to get us to
equivalence (or in this case, to return `false`).

Of course, an easy solution around this is to change the definition of the
unary predicate to return a triple of values less/equal/greater. However,
this would either require an additional datatype to the library (which I
don't think is appropriate) OR require the user to increase the complexity
of their predicate function to return -1/0/1. I don't think either of these
are ideal or necessarily better than the standard approach of a value and a
binary predicate.

I really like the idea of the unary predicate approach, I just can't seem
to understand how it will work in practice. What am I missing here?
(hopefully not something completely obvious!)

This works; when I get some more time I might code it up for you, if
nobody has done it by then.

···

on Fri Mar 25 2016, Jeff Hajewski <swift-evolution@swift.org> wrote:

Thanks!
Jeff

On Thu, Mar 24, 2016 at 4:52 PM, Dave Abrahams via swift-evolution < > swift-evolution@swift.org> wrote:

on Tue Mar 15 2016, Nate Cook <swift-evolution@swift.org> wrote:

>> On Mar 15, 2016, at 1:58 PM, Lorenzo Racca via swift-evolution < >> swift-evolution@swift.org> wrote:
>>
>>> On Mar 15, 2016, at 6:49 PM, Haravikk >> >>> <swift-evolution@haravikk.me >> >>> <mailto:swift-evolution@haravikk.me>> >> > >> >>> wrote:
>>>
>>>> On 15 Mar 2016, at 15:48, Lorenzo Racca <lorenzo.racca@live.it >> <mailto:lorenzo.racca@live.it>> wrote:
>>>>
>>>> I already knew the impossibility of applying such a predicate as “$0
== 3” and I actually couldn’t quite figure out a solution.
>>>
>>> I thought so, and I don’t think there is a way to do it, my point
>>> was really just that your swift doc comments weren’t clear on that
>>> point, then I went off at a bit of a tangent ;)
>>>
>> No problem! What I am trying to figure out here is how we should
>> implement the lowerBound and upperBound functions. Should they
>> exactly reflect their C++ counterparts?
>> Anyway, it seems all of our implementations have the same problem,
>> that they cannot be univocally called with any predicate whatsoever,
>> (or at least it seemed to me during some tests with the
>> implementations :) ), so I don’t really know how we should act. I am
>> a little blocked.
>> Does anyone have ideas on how that could work no matter what predicate
is given? Especially, an upperBound() function, which is a little trickier.
>
> The key is to use a binary predicate (as used in sort and partition)
> instead of a unary predicate. Then you can use the predicate as is for
> lowerBound or with the arguments "reversed" for upperBound. The
> methods would have a similar signature to indexOf—one that just takes
> a value for comparable collections and one that takes a value and a
> predicate.

Having an overload that accepts a binary predicate is certainly a nice
convenience, but the most general formulation takes a unary predicate
that “partitions” the collection, i.e. returns false for the first N
elements of the collection and returns true for the rest.

IMO it's important to expose the unary predicate version. Lots of
times, the thing you want to compare against doesn't have the same type
as the elements of the collection. For example, you might have a
collection of key-value pairs where you just want to compare against the
keys, and you may not even be able to create an instance of the whole
element. For more on this, see
Binary Search with Heterogeneous Comparison

--
Dave

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

--
Dave

Jeff_Hajewski · 2016-03-29T10:43:47.000Z

Dave,

I've responded below, but just for the sake of being explicit, this is
roughly
the signature for lowerBound, upperBound, and binarySearch I have in
mind based on your comments of a unary predicate:

lowerBound(isOrderedBelow: Self.Collection.Element -> Bool) -> Index
upperBound(isOrderedBelow: Self.Collection.Element -> Bool) -> Index
binarySearch(isOrderedBelow: Self.Collection.Element -> Bool) -> Bool

That's the general structure - the key is that the exact same predicate is
used in all signatures. The predicate would be defined along the lines of
a binary predicate where one of the parameters is fixed as the search value.
The unary predicate could be formed along the lines of:

let binaryPred = { $0 < $1 }
let unnaryPred = binaryPred($0, value)

where value is the search value. The main point of illustrating that is that
once the unary predicate is defined, we can't change the position of the
search value within the predicate like they do in the C++ implementation.

Additional comments below..

Thanks for your input on this! It is greatly appreciated!
Jeff

> Dave,
>
> I've been giving this approach a lot of thought (and have read everything
> I've been able to find that you've written on the matter several times)
and
> am not convinced it will work. Implementing a lowerBound function is
> trivial with a unary operator. However, implementing an upperBound or
> binarySearch function is, at least in my mind, a bit more difficult.

upperBound is just lowerBound with an inverted predicate. You can prove
this to yourself by looking at the implementation of any C++ standard
library.

I've spent a decent amount of time looking at the implementation in C++, but
the caveat is that the operator is binary, and that is used in the
upperBound
implementation. For upperBound we need the position of the first element
that is strictly great than the partition point, and we can't get this by
simply
taking the complement of the unary predicate. In C++ they swap the order
of the parameters in the comp method to achieve this, but this isn't
possible
in the unary case or, if it is, no one I have spoken with (including the
four
of us discussing and working on this fix) can figure out how.

It occurs to me that this could be a communication issue. What I presume
you are suggesting is using a unary predicate such that the same predicate
is interchangeable amongst lowerBound, upperBound, and binarySearch.
Of course, if lowerBound and upperBound take different partition predicates
then the problem is trivial, but it also doesn't help you in implementing a
binary search.

> The reason is because with the unary predicate we only know if an
> element is strictly less than the search value or greater than or
> equal to the search value, whereas in the standard approach we can
> determine strictly greater than as well as equivalence by swapping the
> inputs to the comp function.
>
> For example, consider the set [2, 1, 5, 4]. If we want to search the set
> using a unary predicate for 3, we would pass in the closure { $0 < 3 }.
I
> don't see how we can test for equivalence when all we know is "<" or
">=".
> With the standard approach using a binary predicate of `{ $0 < $1 }` we
can
> use `{ $0 < 3 }` to get the lower bound and then `!{ 3 < $0 }` to get us
to
> equivalence (or in this case, to return `false`).
>
> Of course, an easy solution around this is to change the definition of
the
> unary predicate to return a triple of values less/equal/greater. However,
> this would either require an additional datatype to the library (which I
> don't think is appropriate) OR require the user to increase the
complexity
> of their predicate function to return -1/0/1. I don't think either of
these
> are ideal or necessarily better than the standard approach of a value
and a
> binary predicate.
>
> I really like the idea of the unary predicate approach, I just can't seem
> to understand how it will work in practice. What am I missing here?
> (hopefully not something completely obvious!)

This works; when I get some more time I might code it up for you, if
nobody has done it by then.

Even just the logic for upperBound would be an immense help to us. As
I stated above, our issue is that the complement of the unary predicate
function gives us the equivalent of "greater than or equal".

···

On Mon, Mar 28, 2016 at 3:39 PM, Dave Abrahams via swift-evolution < swift-evolution@swift.org> wrote:

on Fri Mar 25 2016, Jeff Hajewski <swift-evolution@swift.org> wrote:

> Thanks!
> Jeff
>
> On Thu, Mar 24, 2016 at 4:52 PM, Dave Abrahams via swift-evolution < > > swift-evolution@swift.org> wrote:
>
>>
>> on Tue Mar 15 2016, Nate Cook <swift-evolution@swift.org> wrote:
>>
>> >> On Mar 15, 2016, at 1:58 PM, Lorenzo Racca via swift-evolution < > >> swift-evolution@swift.org> wrote:
>> >>
>> >>> On Mar 15, 2016, at 6:49 PM, Haravikk > >> >>> <swift-evolution@haravikk.me > >> >>> <mailto:swift-evolution@haravikk.me>> > >> > > >> >>> wrote:
>> >>>
>> >>>> On 15 Mar 2016, at 15:48, Lorenzo Racca <lorenzo.racca@live.it > >> <mailto:lorenzo.racca@live.it>> wrote:
>> >>>>
>> >>>> I already knew the impossibility of applying such a predicate as
“$0
>> == 3” and I actually couldn’t quite figure out a solution.
>> >>>
>> >>> I thought so, and I don’t think there is a way to do it, my point
>> >>> was really just that your swift doc comments weren’t clear on that
>> >>> point, then I went off at a bit of a tangent ;)
>> >>>
>> >> No problem! What I am trying to figure out here is how we should
>> >> implement the lowerBound and upperBound functions. Should they
>> >> exactly reflect their C++ counterparts?
>> >> Anyway, it seems all of our implementations have the same problem,
>> >> that they cannot be univocally called with any predicate whatsoever,
>> >> (or at least it seemed to me during some tests with the
>> >> implementations :) ), so I don’t really know how we should act. I am
>> >> a little blocked.
>> >> Does anyone have ideas on how that could work no matter what
predicate
>> is given? Especially, an upperBound() function, which is a little
trickier.
>> >
>> > The key is to use a binary predicate (as used in sort and partition)
>> > instead of a unary predicate. Then you can use the predicate as is for
>> > lowerBound or with the arguments "reversed" for upperBound. The
>> > methods would have a similar signature to indexOf—one that just takes
>> > a value for comparable collections and one that takes a value and a
>> > predicate.
>>
>> Having an overload that accepts a binary predicate is certainly a nice
>> convenience, but the most general formulation takes a unary predicate
>> that “partitions” the collection, i.e. returns false for the first N
>> elements of the collection and returns true for the rest.
>>
>> IMO it's important to expose the unary predicate version. Lots of
>> times, the thing you want to compare against doesn't have the same type
>> as the elements of the collection. For example, you might have a
>> collection of key-value pairs where you just want to compare against the
>> keys, and you may not even be able to create an instance of the whole
>> element. For more on this, see
>> Binary Search with Heterogeneous Comparison
>>
>> --
>> Dave
>>
>> _______________________________________________
>> swift-evolution mailing list
>> swift-evolution@swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution

--
Dave

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

pyrtsa · 2016-04-28T11:36:55.000Z

Bringing up this topic because it became relevant with Brent Royal-Gordon's "[Idea] Bringing the partial/total ordering distinction into Comparable <http://thread.gmane.org/gmane.comp.lang.swift.evolution/15180>"\.

If the `<=>` operator with a return type of a three-case `enum Order`, you can fully define the most generic versions of binary searches as:

lowerBound(compare: Self.Collection.Element -> Order) -> Index

etc.

···

On 29 Mar 2016, at 13:43, Jeff Hajewski via swift-evolution <swift-evolution@swift.org> wrote:

I've responded below, but just for the sake of being explicit, this is roughly
the signature for lowerBound, upperBound, and binarySearch I have in
mind based on your comments of a unary predicate:

lowerBound(isOrderedBelow: Self.Collection.Element -> Bool) -> Index
upperBound(isOrderedBelow: Self.Collection.Element -> Bool) -> Index
binarySearch(isOrderedBelow: Self.Collection.Element -> Bool) -> Bool

That's the general structure - the key is that the exact same predicate is
used in all signatures. The predicate would be defined along the lines of
a binary predicate where one of the parameters is fixed as the search value.
The unary predicate could be formed along the lines of:

let binaryPred = { $0 < $1 }
let unnaryPred = binaryPred($0, value)

where value is the search value. The main point of illustrating that is that
once the unary predicate is defined, we can't change the position of the
search value within the predicate like they do in the C++ implementation.

You're right, there's no way a Bool-returning unary comparator could allow you to implement anything but lowerBound. With a three-value result, however, you've got all you need.

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: https://github.com/knomi/Allsorts/blob/master/Allsorts/BinarySearch.swift

— Pyry

Jeff_Hajewski · 2016-04-28T12:03:56.000Z

Thanks for bringing this back into the spotlight Pyry. A few of us have
been working on this issue here:

GitHub

GitHub - lorenzoracca/Swift-binary-search: Binary search imply that will...

Binary search imply that will presented as proposal to swift-evolution - GitHub - lorenzoracca/Swift-binary-search: Binary search imply that will presented as proposal to swift-evolution

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?

Jeff

···

On Thu, Apr 28, 2016 at 7:36 AM, Pyry Jahkola <pyry.jahkola@iki.fi> wrote:

Bringing up this topic because it became relevant with Brent
Royal-Gordon's "[Idea] Bringing the partial/total ordering distinction
into Comparable
<http://thread.gmane.org/gmane.comp.lang.swift.evolution/15180>"\.

If the `<=>` operator with a return type of a three-case `*enum* Order`,
you can fully define the most generic versions of binary searches as:

lowerBound(compare: Self.Collection.Element -> Order) -> Index

etc.

On 29 Mar 2016, at 13:43, Jeff Hajewski via swift-evolution < > swift-evolution@swift.org> wrote:

I've responded below, but just for the sake of being explicit, this is
roughly
the signature for lowerBound, upperBound, and binarySearch I have in
mind based on your comments of a unary predicate:

lowerBound(isOrderedBelow: Self.Collection.Element -> Bool) -> Index
upperBound(isOrderedBelow: Self.Collection.Element -> Bool) -> Index
binarySearch(isOrderedBelow: Self.Collection.Element -> Bool) -> Bool

That's the general structure - the key is that the exact same predicate is
used in all signatures. The predicate would be defined along the lines of
a binary predicate where one of the parameters is fixed as the search
value.
The unary predicate could be formed along the lines of:

let binaryPred = { $0 < $1 }
let unnaryPred = binaryPred($0, value)

where value is the search value. The main point of illustrating that is
that
once the unary predicate is defined, we can't change the position of the
search value within the predicate like they do in the C++ implementation.

You're right, there's no way a Bool-returning unary comparator could
allow you to implement anything but lowerBound. With a three-value result,
however, you've got all you need.

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:
https://github.com/knomi/Allsorts/blob/master/Allsorts/BinarySearch.swift

— Pyry

dabrahams · 2016-04-28T21:06:32.000Z

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)
    }
  }
}

···

on Thu Apr 28 2016, Jeff Hajewski <swift-evolution@swift.org> wrote:

Thanks for bringing this back into the spotlight Pyry. A few of us have been
working on this issue here:

GitHub - lorenzoracca/Swift-binary-search: Binary search imply that will presented as proposal to swift-evolution

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?

--
Dave

Jeff_Hajewski · 2016-04-28T23:51:27.000Z

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.
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 < swift-evolution@swift.org> wrote:

on Thu Apr 28 2016, Jeff Hajewski <swift-evolution@swift.org> wrote:

> Thanks for bringing this back into the spotlight Pyry. A few of us have
been
> working on this issue here:
>
> GitHub - lorenzoracca/Swift-binary-search: Binary search imply that will presented as proposal to swift-evolution
>
> 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
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Haravikk3 · 2016-04-29T10:38:24.000Z

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.

···

On 28 Apr 2016, at 13:03, Jeff Hajewski via swift-evolution <swift-evolution@swift.org> wrote:

Thanks for bringing this back into the spotlight Pyry. A few of us have been working on this issue here:

GitHub - lorenzoracca/Swift-binary-search: Binary search imply that will presented as proposal to swift-evolution

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?

Jeff

On Thu, Apr 28, 2016 at 7:36 AM, Pyry Jahkola <pyry.jahkola@iki.fi <mailto:pyry.jahkola@iki.fi>> wrote:
Bringing up this topic because it became relevant with Brent Royal-Gordon's "[Idea] Bringing the partial/total ordering distinction into Comparable <http://thread.gmane.org/gmane.comp.lang.swift.evolution/15180>"\.

If the `<=>` operator with a return type of a three-case `enum Order`, you can fully define the most generic versions of binary searches as:

lowerBound(compare: Self.Collection.Element -> Order) -> Index

etc.

On 29 Mar 2016, at 13:43, Jeff Hajewski via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

I've responded below, but just for the sake of being explicit, this is roughly
the signature for lowerBound, upperBound, and binarySearch I have in
mind based on your comments of a unary predicate:

lowerBound(isOrderedBelow: Self.Collection.Element -> Bool) -> Index
upperBound(isOrderedBelow: Self.Collection.Element -> Bool) -> Index
binarySearch(isOrderedBelow: Self.Collection.Element -> Bool) -> Bool

That's the general structure - the key is that the exact same predicate is
used in all signatures. The predicate would be defined along the lines of
a binary predicate where one of the parameters is fixed as the search value.
The unary predicate could be formed along the lines of:

let binaryPred = { $0 < $1 }
let unnaryPred = binaryPred($0, value)

where value is the search value. The main point of illustrating that is that
once the unary predicate is defined, we can't change the position of the
search value within the predicate like they do in the C++ implementation.

You're right, there's no way a Bool-returning unary comparator could allow you to implement anything but lowerBound. With a three-value result, however, you've got all you need.

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: https://github.com/knomi/Allsorts/blob/master/Allsorts/BinarySearch.swift

— Pyry

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

dabrahams · 2016-04-29T21:26:03.000Z

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.

···

on Thu Apr 28 2016, Jeff Hajewski <swift-evolution@swift.org> wrote:

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 > <swift-evolution@swift.org> wrote:

    on Thu Apr 28 2016, Jeff Hajewski > <swift-evolution@swift.org> wrote:

    > Thanks for bringing this back into the spotlight Pyry. A few of us have
    been
    > working on this issue here:
    >
    > GitHub - lorenzoracca/Swift-binary-search: Binary search imply that will presented as proposal to swift-evolution
    >
    > 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
    swift-evolution@swift.org
    https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

--
Dave

dabrahams · 2016-04-29T21:26:51.000Z

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.

That's what I had in mind.

···

on Fri Apr 29 2016, Haravikk <swift-evolution@swift.org> wrote:

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.

    On 28 Apr 2016, at 13:03, Jeff Hajewski via swift-evolution > <swift-evolution@swift.org> wrote:

    Thanks for bringing this back into the spotlight Pyry. A few of us have been
    working on this issue here:

    GitHub - lorenzoracca/Swift-binary-search: Binary search imply that will presented as proposal to swift-evolution

    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?

    Jeff

    On Thu, Apr 28, 2016 at 7:36 AM, Pyry Jahkola > <pyry.jahkola@iki.fi> wrote:

        Bringing up this topic because it became relevant with Brent
        Royal-Gordon's "[Idea] Bringing the partial/total ordering distinction
        into Comparable".

        If the `<=>` operator with a return type of a three-case `enum Order`,
        you can fully define the most generic versions of binary searches as:

        lowerBound(compare: Self.Collection.Element -> Order) -> Index

        etc.

            On 29 Mar 2016, at 13:43, Jeff Hajewski via swift-evolution > <swift-evolution@swift.org> wrote:

            I've responded below, but just for the sake of being explicit, this
            is roughly
            the signature for lowerBound, upperBound, and binarySearch I have in
            mind based on your comments of a unary predicate:

            lowerBound(isOrderedBelow: Self.Collection.Element -> Bool) -> Index
            upperBound(isOrderedBelow: Self.Collection.Element -> Bool) -> Index
            binarySearch(isOrderedBelow: Self.Collection.Element -> Bool) ->
            Bool

            That's the general structure - the key is that the exact same
            predicate is
            used in all signatures. The predicate would be defined along the
            lines of
            a binary predicate where one of the parameters is fixed as the
            search value.
            The unary predicate could be formed along the lines of:

            let binaryPred = { $0 < $1 }
            let unnaryPred = binaryPred($0, value)

            where value is the search value. The main point of illustrating that
            is that
            once the unary predicate is defined, we can't change the position of
            the
            search value within the predicate like they do in the C++
            implementation.

        You're right, there's no way a Bool-returning unary comparator could
        allow you to implement anything but lowerBound. With a three-value
        result, however, you've got all you need.

        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:
        https://github.com/knomi/Allsorts/blob/master/Allsorts/BinarySearch.swift

        — Pyry

    _______________________________________________
    swift-evolution mailing list
    swift-evolution@swift.org
    https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

--
Dave