[Discussion] Binary search, lower bound, upper bound, equal range

Evolution Discussion
1

Hello,

I am working on SR-368 <Issues · apple/swift-issues · GitHub; and am hoping to get some feedback from the community.

Description
Implement analogs to C++’s binary_search, lower_bound, upper_bound, and equal_range algorithms.

Initial Proposal
I propose adding four methods for generic Array and adding four methods for Arrays that conform to Comparable:

Array
@warn_unused_result
func lowerBound(value: Array.Element, @noescape isOrderedBefore: (lhs: Array.Element, rhs: Array.Element) -> Bool) -> Int?

@warn_unused_result
func upperBound(value: Array.Element, @noescape isOrderedBefore: (lhs: Array.Element, rhs: Array.Element) -> Bool) -> Int?

@warn_unused_result
func binarySearch(value: Array.Element, @noescape isOrderedBefore:(lhs: Array.Element, rhs: Array.Element) -> Bool) -> Bool

@warn_unused_result
func equalRange(value: Array.Element, @noescape isOrderedBefore: (lhs: Array.Element, rhs: Array.Element) -> Bool) -> Range<Int>?

Array: Comparable
@warn_unused_result
func lowerBound(value: Array.Element) -> Int?

@warn_unused_result
func upperBound(value: Array.Element) -> Int?

@warn_unused_result
func binarySearch(value: Array.Element) -> Bool

@warn_unused_result
func equalRange(value: Array.Element) -> Range<Int>?

Discussion
The main issue I’d like to discuss is how do we want to add these to Swift? My thoughts are as follows:

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 binarySearch on a set, we would first need to sort the set, which would return an array, and then we would call binarySearch on that array. Similarly, it seems at the SequenceType level the problem ultimately reduces to using Array.
Does it make sense to handle these as public functions? I tend to think not as it seems less idiomatic.
I suggest eight implementations similar to how sort() is handled. If the calling array’s elements conform to Comparable, then no isOrderedBefore 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.
Similar to the C++ implementations, I avoid recursion and favor while-loops
These methods should be preconditioned on the calling array be partitioned with respect to the passed value. 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 value. I favor the preconditioning approach.

Any and all feedback is greatly appreciated!

Thanks
Jeff

2

Hello,

I am working on SR-368 <Issues · apple/swift-issues · GitHub; and am hoping to get some feedback from the community.

Description
Implement analogs to C++’s binary_search, lower_bound, upper_bound, and equal_range algorithms.

Initial Proposal
I propose adding four methods for generic Array and adding four
methods for Arrays that conform to Comparable:

Array
@warn_unused_result
func lowerBound(value: Array.Element, @noescape isOrderedBefore: (lhs:
Array.Element, rhs: Array.Element) -> Bool) -> Int?

@warn_unused_result
func upperBound(value: Array.Element, @noescape isOrderedBefore: (lhs:
Array.Element, rhs: Array.Element) -> Bool) -> Int?

@warn_unused_result
func binarySearch(value: Array.Element, @noescape
isOrderedBefore:(lhs: Array.Element, rhs: Array.Element) -> Bool) ->
Bool

@warn_unused_result
func equalRange(value: Array.Element, @noescape isOrderedBefore: (lhs:
Array.Element, rhs: Array.Element) -> Bool) -> Range<Int>?

Array: Comparable
@warn_unused_result
func lowerBound(value: Array.Element) -> Int?

@warn_unused_result
func upperBound(value: Array.Element) -> Int?

@warn_unused_result
func binarySearch(value: Array.Element) -> Bool

@warn_unused_result
func equalRange(value: Array.Element) -> Range<Int>?

Discussion
The main issue I’d like to discuss is how do we want to add these to Swift? My thoughts are as follows:

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

These should be defined on CollectionType Note that you don't need
random access to get an advantage from binary search if the comparison
is sufficiently expensive.

For example, suppose we implemented these methods as an extension to
CollectionType, if we were to try and call binarySearch on a set, we
would first need to sort the set, which would return an array, and
then we would call binarySearch on that array.

It should work on any arbitrary collection. The collections you know
are not the only ones that matter. For examples, consider binary
searching the result of applying a lazy map or filter to some sorted
array.

Similarly, it seems at the SequenceType level the problem ultimately
reduces to using Array.

Sequences don't have indices; you can't binary search them.

Does it make sense to handle these as public functions? I tend to
think not as it seems less idiomatic. I suggest eight implementations
similar to how sort() is handled. If the calling array’s elements
conform to Comparable, then no isOrderedBefore 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.

The general form takes a closure that partitions the collection; see
Binary Search with Heterogeneous Comparison and
Issue 270: Binary search requirements overly strict - WG21 LWG Issues

I would suggest avoiding the API choice that requires both a comparison
closure *and* an element against which to compare, as a unary
partitioning predicate is much simpler.

Similar to the C++ implementations, I avoid recursion and favor
while-loops.

Have an implementation is important as proof-of-concept and for
performance testing, but I don't consider the details important at this
stage.

These methods should be preconditioned on the calling
array be partitioned with respect to the passed value.
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?

Seems like a separable proposal.

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 value.

That *is* a precondition. Not all preconditions can or should be
verfied at runtime. We would never make the caller pay to actually
verify at runtime that the collection is partitioned w.r.t. the closure;
that would make the whole operation O(N) and effectively discard any
benefit of binary-searching.

I favor the preconditioning approach.

Any and all feedback is greatly appreciated!

HTH,
Dave

···

on Mon Feb 15 2016, Jeff Hajewski <swift-evolution@swift.org> wrote:

--
-Dave

3

Dave,

Thanks a lot for the feedback - it is greatly appreciated. With respect to your comment about the unary partitioning predicate, I really like that idea and hadn’t thought of the problem like that. Excellent suggestion!

Thanks
Jeff

···

On Feb 15, 2016, at 4:34 PM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:

on Mon Feb 15 2016, Jeff Hajewski <swift-evolution@swift.org> wrote:

Hello,

I am working on SR-368 <Issues · apple/swift-issues · GitHub; and am hoping to get some feedback from the community.

Description
Implement analogs to C++’s binary_search, lower_bound, upper_bound, and equal_range algorithms.

Initial Proposal
I propose adding four methods for generic Array and adding four
methods for Arrays that conform to Comparable:

Array
@warn_unused_result
func lowerBound(value: Array.Element, @noescape isOrderedBefore: (lhs:
Array.Element, rhs: Array.Element) -> Bool) -> Int?

@warn_unused_result
func upperBound(value: Array.Element, @noescape isOrderedBefore: (lhs:
Array.Element, rhs: Array.Element) -> Bool) -> Int?

@warn_unused_result
func binarySearch(value: Array.Element, @noescape
isOrderedBefore:(lhs: Array.Element, rhs: Array.Element) -> Bool) ->
Bool

@warn_unused_result
func equalRange(value: Array.Element, @noescape isOrderedBefore: (lhs:
Array.Element, rhs: Array.Element) -> Bool) -> Range<Int>?

Array: Comparable
@warn_unused_result
func lowerBound(value: Array.Element) -> Int?

@warn_unused_result
func upperBound(value: Array.Element) -> Int?

@warn_unused_result
func binarySearch(value: Array.Element) -> Bool

@warn_unused_result
func equalRange(value: Array.Element) -> Range<Int>?

Discussion
The main issue I’d like to discuss is how do we want to add these to Swift? My thoughts are as follows:

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

These should be defined on CollectionType Note that you don't need
random access to get an advantage from binary search if the comparison
is sufficiently expensive.

For example, suppose we implemented these methods as an extension to
CollectionType, if we were to try and call binarySearch on a set, we
would first need to sort the set, which would return an array, and
then we would call binarySearch on that array.

It should work on any arbitrary collection. The collections you know
are not the only ones that matter. For examples, consider binary
searching the result of applying a lazy map or filter to some sorted
array.

Similarly, it seems at the SequenceType level the problem ultimately
reduces to using Array.

Sequences don't have indices; you can't binary search them.

Does it make sense to handle these as public functions? I tend to
think not as it seems less idiomatic. I suggest eight implementations
similar to how sort() is handled. If the calling array’s elements
conform to Comparable, then no isOrderedBefore 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.

The general form takes a closure that partitions the collection; see
Binary Search with Heterogeneous Comparison and
http://wg21.cmeerw.net/lwg/issue270

I would suggest avoiding the API choice that requires both a comparison
closure *and* an element against which to compare, as a unary
partitioning predicate is much simpler.

Similar to the C++ implementations, I avoid recursion and favor
while-loops.

Have an implementation is important as proof-of-concept and for
performance testing, but I don't consider the details important at this
stage.

These methods should be preconditioned on the calling
array be partitioned with respect to the passed value.
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?

Seems like a separable proposal.

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 value.

That *is* a precondition. Not all preconditions can or should be
verfied at runtime. We would never make the caller pay to actually
verify at runtime that the collection is partitioned w.r.t. the closure;
that would make the whole operation O(N) and effectively discard any
benefit of binary-searching.

I favor the preconditioning approach.

Any and all feedback is greatly appreciated!

HTH,
Dave

--
-Dave

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

4

Over the weekend, I looked at what I would require for porting a simple kd-tree from C++ to Swift, and other than stable sort I was also lacking equal_range. But I think that defining the interface for these methods on Array would be a mistake: One thing the STL got very right is that the caller gets to pick the iterators (ranges) for the algorithm. For the kd-tree, I would want to stable_sort and apply equal_range to recursively smaller segments (slices?) of an Array, and not always the complete one.

  Daniel.

···

On 15 Feb 2016, at 21:35, Jeff Hajewski via swift-evolution <swift-evolution@swift.org> wrote:

Hello,

Description
Implement analogs to C++’s binary_search, lower_bound, upper_bound, and equal_range algorithms.

Initial Proposal
I propose adding four methods for generic Array and adding four methods for Arrays that conform to Comparable:

5

I am working on SR-368 <Issues · apple/swift-issues · GitHub; and am hoping to get some feedback from the community.

Definitely +1!

Shameless plug:

I've played with this idea in the past, implementing all of the four suggested binary searches as generic functions over index ranges or collections, using a custom 3-way comparator. The commented code and unit tests are found in https://github.com/knomi/Allsorts\. The library is also somewhat tested in production.

let i: Int = ["a","b","c","c","c","d","f","f"].binarySearch("c") //=> 2, 3 or 4
let j: Int? = ["a","b","c","c","c","d","f","f"].binaryFind("e") //=> nil
// Compare values to "e". `a <=> b` performs a 3-way comparison, returning .LT, .EQ or .GT
let k: Int = ["a","b","c","c","c","d","f","f"].lowerBound {x in x <=> "e"} //=> 6
// Reverse order (the arguments of <=> are flipped):
let r: Range<Int> = ["e","e","d","c","c","c","b","a"].equalRange {x in "c" <=> x} //=> 3 ..< 6

I'd be happy to join forces in making the algorithms available in the standard library.

I believe that my code tackles many points Dave mentioned:

(1) You don't need to construct an element just to perform the search. You only need a function to tell if the search should proceed to the left or right, or if there's a match.

(2) You don't really need to a concrete collection either. A Range<Int> will do just as fine, as long as you're able to say how those indices should be compared to each other (usually by looking up somewhere else).

(3) The collection can be sorted by any comparator (which I call an "ordering"), as long as you pass that information along as the closure (the ordering).

(4) I use three-way comparisons to avoid extra work comparing e.g. strings.
Turns out comparisons defined that way also compose amazingly well, see first examples in README.
There's an operator "x <=> y" returning Ordering.LT, .EQ, or .GT instead of just Bool. However, that operator has little to do with the implementation of binary search.
(The topic of three-way comparisons was discussed earlier <https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20160201/009127.html&gt; in swift-evolution. I think it should find its way into the Comparable protocol directly, as an alternative to defining "<".)
(5) By convention, I do not return nil just because an index wasn't found. You might still want to use the index for the insertion of new elements. For convenience, there's binaryFind which is guaranteed to return an index exactly when there's a match, otherwise nil.

(6) There are convenience overloads for sorted collections of Generator.Element : Comparable so that you can give a value to look up.

(7) The project also contains more experimental stuff like a working (but slow?) port of libc++'s binary heap algorithms. Over time, those would be nice to port to Swift standard library as well.

The existing interface on GitHub is still preferring top-level functions. I'm modernising the interface into the following (plus the usual public, @warn_unused_result, @noescape, throws and rethrows dance). An already working implementation can be found in the protocol-extensions branch <https://github.com/knomi/Allsorts/blob/protocol-extensions/Allsorts/BinarySearch.swift&gt;:

enum Ordering : Int { case LT = -1, EQ, GT } // NSComparisonResult, basically

extension CollectionType where Index : RandomAccessIndexType {
    func binaryFind(ordering: Generator.Element -> Ordering) -> Self.Index?
    func binarySearch(ordering: Generator.Element -> Ordering) -> Self.Index
    func lowerBound(ordering: Generator.Element -> Ordering) -> Self.Index
    func upperBound(ordering: Generator.Element -> Ordering) -> Self.Index
    func equalRange(ordering: Generator.Element -> Ordering) -> Range<Self.Index>
}

extension CollectionType where Index : RandomAccessIndexType, Generator.Element : Comparable {
    func binaryFind(value: Generator.Element) -> Self.Index?
    func binarySearch(value: Generator.Element) -> Self.Index
    func lowerBound(value: Generator.Element) -> Self.Index
    func upperBound(value: Generator.Element) -> Self.Index
    func equalRange(value: Generator.Element) -> Range<Self.Index>
}

Note that you don't need random access to get an advantage from binary search if the comparison is sufficiently expensive.

One current restriction is that I only define these functions over collections with random access. What it boils down to is the implementation of midIndex:

internal func midIndex<Ix : RandomAccessIndexType>(range: Range<Ix>) -> Ix {
    let fullDistance = range.startIndex.distanceTo(range.endIndex)
    return range.startIndex.advancedBy(fullDistance / 2)
}

That could certainly be written with weaker constraints as well; I just haven't checked how it affects to the interface in terms of duplication of code, and to the performance of the random access version.

— Pyry Jahkola

···

On Mon Feb 15 2016, Jeff Hajewski <swift-evolution@swift.org> wrote:

On 15 Feb 2016, at 23:34, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:

6

Thanks Daniel - comments regarding Array vs CollectionType are duly noted. Stable sort is next on my list unless someone else tackles it before I finish this work. I suppose I’ll be adding isPartitioned as well at some point.

Thanks again for the comments
Jeff

···

On Feb 15, 2016, at 5:45 PM, Daniel Vollmer via swift-evolution <swift-evolution@swift.org> wrote:

On 15 Feb 2016, at 21:35, Jeff Hajewski via swift-evolution <swift-evolution@swift.org> wrote:

Hello,

Description
Implement analogs to C++’s binary_search, lower_bound, upper_bound, and equal_range algorithms.

Initial Proposal
I propose adding four methods for generic Array and adding four methods for Arrays that conform to Comparable:

Over the weekend, I looked at what I would require for porting a simple kd-tree from C++ to Swift, and other than stable sort I was also lacking equal_range. But I think that defining the interface for these methods on Array would be a mistake: One thing the STL got very right is that the caller gets to pick the iterators (ranges) for the algorithm. For the kd-tree, I would want to stable_sort and apply equal_range to recursively smaller segments (slices?) of an Array, and not always the complete one.

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

7

Pyry - this is great work! I wonder if we can loosen the restriction of
conforming to RandomAccessIndexType. I will play around with this. I think
maybe the *Ordering* enum should be broken out into a separate proposal
since it's not currently part of the standard lib. That being said, it does
make for a clean implementation.

Thanks
Jeff

···

On Tue, Feb 16, 2016 at 7:12 AM, Pyry Jahkola via swift-evolution < swift-evolution@swift.org> wrote:

On Mon Feb 15 2016, Jeff Hajewski <swift-evolution@swift.org> wrote:

I am working on SR-368 <Issues · apple/swift-issues · GitHub; and am
hoping to get some feedback from the community.

Definitely +1!

Shameless plug:

I've played with this idea in the past, implementing all of the four
suggested binary searches as generic functions over index ranges or
collections, using a custom 3-way comparator. The commented code and unit
tests are found in https://github.com/knomi/Allsorts\. The library is also
somewhat tested in production.

let i: Int = ["a","b","c","c","c","d","f","f"].binarySearch("c")
        //=> 2, 3 or 4
let j: Int? = ["a","b","c","c","c","d","f","f"].binaryFind("e")
        //=> nil
// Compare values to "e". `a <=> b` performs a 3-way comparison,
returning .LT, .EQ or .GT
let k: Int = ["a","b","c","c","c","d","f","f"].lowerBound {x in x
<=> "e"} //=> 6
// Reverse order (the arguments of <=> are flipped):
let r: Range<Int> = ["e","e","d","c","c","c","b","a"].equalRange {x in "c"
<=> x} //=> 3 ..< 6

I'd be happy to join forces in making the algorithms available in the
standard library.

I believe that my code tackles many points Dave mentioned:

(1) You don't need to construct an element just to perform the search. You
only need a function to tell if the search should proceed to the left or
right, or if there's a match.

(2) You don't really need to a concrete collection either. A Range<Int> will
do just as fine, as long as you're able to say how those indices should be
compared to each other (usually by looking up somewhere else).

(3) The collection can be sorted by any comparator (which I call an "
ordering"), as long as you pass that information along as the closure
(the ordering).

(4) I use three-way comparisons to avoid extra work comparing e.g. strings.

   - Turns out comparisons defined that way also compose amazingly well,
      see first examples in README.
      - There's an operator "x <=> y" returning Ordering.LT, .EQ, or .GT instead
      of just Bool. However, that operator has little to do with the
      implementation of binary search.
      - (The topic of three-way comparisons was discussed earlier
      <https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20160201/009127.html&gt; in
      swift-evolution. I think it should find its way into the Comparable protocol
      directly, as an alternative to defining "<".)

(5) By convention, I *do not* return nil just because an index wasn't
found. You might still want to use the index for the insertion of new
elements. For convenience, there's binaryFind which is guaranteed to
return an index exactly when there's a match, otherwise nil.

(6) There are convenience overloads for sorted collections of Generator.Element
: Comparable so that you can give a value to look up.

(7) The project also contains more experimental stuff like a working (but
slow?) port of libc++'s binary heap algorithms. Over time, those would be
nice to port to Swift standard library as well.

The existing interface on GitHub is still preferring top-level functions.
I'm modernising the interface into the following (plus the usual public,
@warn_unused_result, @noescape, throws and rethrows dance). An already
working implementation can be found in the protocol-extensions branch
<https://github.com/knomi/Allsorts/blob/protocol-extensions/Allsorts/BinarySearch.swift&gt;
:

enum Ordering : Int { case LT = -1, EQ, GT } // NSComparisonResult,
basically

extension CollectionType where Index : RandomAccessIndexType {
    func binaryFind(ordering: Generator.Element -> Ordering) -> Self.Index
?
    func binarySearch(ordering: Generator.Element -> Ordering) -> Self.
Index
    func lowerBound(ordering: Generator.Element -> Ordering) -> Self.Index
    func upperBound(ordering: Generator.Element -> Ordering) -> Self.Index
    func equalRange(ordering: Generator.Element -> Ordering) -> Range<Self
.Index>
}

extension CollectionType where Index : RandomAccessIndexType,
Generator.Element : Comparable {
    func binaryFind(value: Generator.Element) -> Self.Index?
    func binarySearch(value: Generator.Element) -> Self.Index
    func lowerBound(value: Generator.Element) -> Self.Index
    func upperBound(value: Generator.Element) -> Self.Index
    func equalRange(value: Generator.Element) -> Range<Self.Index>
}

On 15 Feb 2016, at 23:34, Dave Abrahams via swift-evolution < > swift-evolution@swift.org> wrote:

Note that you don't need random access to get an advantage from binary
search if the comparison is sufficiently expensive.

One current restriction is that I only define these functions over
collections with random access. What it boils down to is the implementation
of midIndex:

internal func midIndex<Ix : RandomAccessIndexType>(range: Range<Ix>) -> Ix
{
    let fullDistance = range.startIndex.distanceTo(range.endIndex)
    return range.startIndex.advancedBy(fullDistance / 2)
}

That could certainly be written with weaker constraints as well; I just
haven't checked how it affects to the interface in terms of duplication of
code, and to the performance of the random access version.

— Pyry Jahkola

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

8

I wonder if we can loosen the restriction of conforming to RandomAccessIndexType.

Yay, it turned out simpler than I thought!

I added a performance test to make sure there's no regression on RandomAccessIndexType's performance, then simply downgraded the RandomAccessIndexType requirement to ForwardIndexType (and used != instead of < in a few places). The updated code <https://github.com/knomi/Allsorts/commit/52e3d7abee2d01d90ecadea24e00c9067a64a327&gt; is in GitHub.

That appears to work because of protocol inheritance magic in the standard library. So, even though my search algorithm only knows about ForwardIndexType, whenever Index happens to implement O(1) versions of advancedBy(_:) and distanceTo(_:), then those get used instead of the O(N) default implementations (Index.swift <https://github.com/apple/swift/blob/de253d9b6f21498704f96aac712cf1b02e612255/stdlib/public/core/Index.swift#L243-L262&gt; on the Swift repository). Cool!

There might still be place for improvement, since the internal use of midIndex still passes across the same index ranges several times during the search on ForwardIndexType. If I did my math right, the current implementation makes something like 3N index increments on ForwardIndexTypes, while probably at least 2N can be achieved without much memory use.

I think maybe the Ordering enum should be broken out into a separate proposal since it's not currently part of the standard lib. That being said, it does make for a clean implementation.

You're absolutely right. I should also paint the bikeshed of naming its cases (.LT, .EQ, and .GT) less obscurely before officially proposing it to swift-evolution. Maybe either .ascending, .equivalent, and .descending, or simply .less, .equal, and .greater. And I expect there to be resistance against adding yet another comparison operator, even if there's precedent on the use of something like "a <=> b" in several other languages.

— Pyry Jahkola

···

On 16 Feb 2016, at 17:49, Jeff Hajewski <jeff.hajewski@gmail.com> wrote:

9

No love though for the X-wing/Cat variation. >=<

-- E

···

On Feb 16, 2016, at 11:26 AM, Ross O'Brien via swift-evolution <swift-evolution@swift.org> wrote:

According to the aforementioned thread on the <=> operator (inclusive of its addition to Comparable with the Ordered(Ascending|Descending|Equal) enum), Dave Abrahams mentioned it was already slated for inclusion in Swift 3, and that sorting algorithms using it would be nifty. I've thus assumed there's no need to turn it into a formal proposal with a review. I've not seen any opposition to the idea yet.
If it does make it to a review I'll add my +1 though.

10

I wonder if we can loosen the restriction of conforming to RandomAccessIndexType.

Yay, it turned out simpler than I thought!

I added a performance test to make sure there's no regression on RandomAccessIndexType's performance, then simply downgraded the RandomAccessIndexType requirement to ForwardIndexType (and used != instead of < in a few places). The updated code <https://github.com/knomi/Allsorts/commit/52e3d7abee2d01d90ecadea24e00c9067a64a327&gt; is in GitHub.

That appears to work because of protocol inheritance magic in the standard library. So, even though my search algorithm only knows about ForwardIndexType, whenever Index happens to implement O(1) versions of advancedBy(_:) and distanceTo(_:), then those get used instead of the O(N) default implementations (Index.swift <https://github.com/apple/swift/blob/de253d9b6f21498704f96aac712cf1b02e612255/stdlib/public/core/Index.swift#L243-L262&gt; on the Swift repository). Cool!

There might still be place for improvement, since the internal use of midIndex still passes across the same index ranges several times during the search on ForwardIndexType. If I did my math right, the current implementation makes something like 3N index increments on ForwardIndexTypes, while probably at least 2N can be achieved without much memory use.

I was going to suggest earlier that the algorithms should perhaps switch to an internal representation of ~ `(index: Index, length: Index.Distance)` (instead of `Range<Index>`), which is an unnecessary change for `RandomAccessIndexType` but for a `ForwardIndexType` would eliminate the need to call `distanceTo` more than once.

The public API could of course stick with Range<Index>, the alternative representation would only be a private implementation detail.

I have some other thoughts but they’re still in progress.

···

On Feb 16, 2016, at 11:58 AM, Pyry Jahkola via swift-evolution <swift-evolution@swift.org> wrote:

On 16 Feb 2016, at 17:49, Jeff Hajewski <jeff.hajewski@gmail.com <mailto:jeff.hajewski@gmail.com>> wrote:

I think maybe the Ordering enum should be broken out into a separate proposal since it's not currently part of the standard lib. That being said, it does make for a clean implementation.

You're absolutely right. I should also paint the bikeshed of naming its cases (.LT, .EQ, and .GT) less obscurely before officially proposing it to swift-evolution. Maybe either .ascending, .equivalent, and .descending, or simply .less, .equal, and .greater. And I expect there to be resistance against adding yet another comparison operator, even if there's precedent on the use of something like "a <=> b" in several other languages.

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

11

Thanks for adding that info regarding <=> and Swift 3 - sounds like we
should include it in the proposal. Keeping up with all these
swift-evolution threads could be a full-time job!

Jeff

···

On Tue, Feb 16, 2016 at 1:26 PM, Ross O'Brien <narrativium+swift@gmail.com> wrote:

According to the aforementioned thread on the <=> operator (inclusive of
its addition to Comparable with the Ordered(Ascending|Descending|Equal)
enum), Dave Abrahams mentioned it was already slated for inclusion in Swift
3, and that sorting algorithms using it would be nifty. I've thus assumed
there's no need to turn it into a formal proposal with a review. I've not
seen any opposition to the idea yet.
If it does make it to a review I'll add my +1 though.

On Tue, Feb 16, 2016 at 5:58 PM, Pyry Jahkola via swift-evolution < > swift-evolution@swift.org> wrote:

On 16 Feb 2016, at 17:49, Jeff Hajewski <jeff.hajewski@gmail.com> wrote:

I wonder if we can loosen the restriction of conforming to
RandomAccessIndexType.

Yay, it turned out simpler than I thought!

I added a performance test to make sure there's no regression on
RandomAccessIndexType's performance, then simply downgraded the
RandomAccessIndexType requirement to ForwardIndexType (and used != instead
of < in a few places). The updated code
<https://github.com/knomi/Allsorts/commit/52e3d7abee2d01d90ecadea24e00c9067a64a327&gt; is
in GitHub.

That appears to work because of protocol inheritance magic in the
standard library. So, even though my search algorithm only knows about
ForwardIndexType, whenever Index happens to implement O(1) versions of
advancedBy(_:) and distanceTo(_:), then those get used instead of the
O(N) default implementations (Index.swift
<https://github.com/apple/swift/blob/de253d9b6f21498704f96aac712cf1b02e612255/stdlib/public/core/Index.swift#L243-L262&gt; on
the Swift repository). Cool!

There might still be place for improvement, since the internal use of
midIndex still passes across the same index ranges several times during
the search on ForwardIndexType. If I did my math right, the current
implementation makes something like 3N index increments on
ForwardIndexTypes, while probably at least 2N can be achieved without
much memory use.

I think maybe the *Ordering* enum should be broken out into a separate
proposal since it's not currently part of the standard lib. That being
said, it does make for a clean implementation.

You're absolutely right. I should also paint the bikeshed of naming its
cases (.LT, .EQ, and .GT) less obscurely before officially proposing it
to swift-evolution. Maybe either .ascending, .equivalent, and
.descending, or simply .less, .equal, and .greater. And I expect there
to be resistance against adding yet another comparison operator, even if
there's precedent on the use of something like "a <=> b" in several
other languages.

— Pyry Jahkola

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

12

You're absolutely right. I should also paint the bikeshed of naming its cases (.LT, .EQ, and .GT) less obscurely before officially proposing it to swift-evolution. Maybe either .ascending, .equivalent, and .descending, or simply .less, .equal, and .greater.

How exciting, another bikeshed! My color:

  enum Ordering {
    case leftSmaller, bothEqual, rightSmaller
  }

I always have trouble tying the case names back to the original expression; I *think* this might help me with that.

···

--
Brent Royal-Gordon
Architechies

13

According to the aforementioned thread on the <=> operator (inclusive of
its addition to Comparable with the Ordered(Ascending|Descending|Equal)
enum), Dave Abrahams mentioned it was already slated for inclusion in Swift
3, and that sorting algorithms using it would be nifty. I've thus assumed
there's no need to turn it into a formal proposal with a review. I've not
seen any opposition to the idea yet.
If it does make it to a review I'll add my +1 though.

···

On Tue, Feb 16, 2016 at 5:58 PM, Pyry Jahkola via swift-evolution < swift-evolution@swift.org> wrote:

On 16 Feb 2016, at 17:49, Jeff Hajewski <jeff.hajewski@gmail.com> wrote:

I wonder if we can loosen the restriction of conforming to
RandomAccessIndexType.

Yay, it turned out simpler than I thought!

I added a performance test to make sure there's no regression on
RandomAccessIndexType's performance, then simply downgraded the
RandomAccessIndexType requirement to ForwardIndexType (and used != instead
of < in a few places). The updated code
<https://github.com/knomi/Allsorts/commit/52e3d7abee2d01d90ecadea24e00c9067a64a327&gt; is
in GitHub.

That appears to work because of protocol inheritance magic in the standard
library. So, even though my search algorithm only knows about
ForwardIndexType, whenever Index happens to implement O(1) versions of
advancedBy(_:) and distanceTo(_:), then those get used instead of the
O(N) default implementations (Index.swift
<https://github.com/apple/swift/blob/de253d9b6f21498704f96aac712cf1b02e612255/stdlib/public/core/Index.swift#L243-L262&gt; on
the Swift repository). Cool!

There might still be place for improvement, since the internal use of
midIndex still passes across the same index ranges several times during
the search on ForwardIndexType. If I did my math right, the current
implementation makes something like 3N index increments on
ForwardIndexTypes, while probably at least 2N can be achieved without
much memory use.

I think maybe the *Ordering* enum should be broken out into a separate
proposal since it's not currently part of the standard lib. That being
said, it does make for a clean implementation.

You're absolutely right. I should also paint the bikeshed of naming its
cases (.LT, .EQ, and .GT) less obscurely before officially proposing it
to swift-evolution. Maybe either .ascending, .equivalent, and .descending,
or simply .less, .equal, and .greater. And I expect there to be
resistance against adding yet another comparison operator, even if there's
precedent on the use of something like "a <=> b" in several other
languages.

— Pyry Jahkola

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