Experimental implementations of Binary Search in Swift
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
Quaero.xcodeproj
Quaero
QuaeroTests
.gitignore
README.md

README.md

Quaero

Motivation

Quaero (latin, "I search") contains multiple experimental implementations of binary search with the purpose of finding the best API, eventually leading to a Swift Language Proposal.

Summary

Quaero contains three separate implementations of the same four search methods:

  • lowerBound(of:in:at:by:) for finding the lower bound of a value.
  • upperBound(of:in:at:by:) for finding the upper bound of a value.
  • index(of:in:at:by:) for finding the index of a value.
  • range(of:in:at:by:) for finding the range of a value.

The three separate implementations are:

  • An implementation making use of instance methods on BinarySearch.
  • An implementation making use of static methods on BinarySearch.
  • An implementation making use of extension methods on Collection.

Contribution

Please feel free to provide ideas for improvements, alternatives or general critique through either Issues or Pull Requests.

Pros & Cons:

Collection Extension

Pros

  • Allows for non-@escaping closures.
  • Allows for throw-ing closures.

Cons

  • Pollutes Collection with unnecessary bloat.
  • Semantics provided by method name (index(of:) vs. sortedIndex(of:))
  • Method name index(of:) is unavailable due to prior existence.
  • 12 methods overall.

Instance Methods

Pros

  • Keeps Collection as is.
  • Semantics provided by type name, not method name (index(of:) vs. sortedIndex(of:))
  • Method name index(of:) is available.
  • 4 methods overall (+ 3 init(…))

Cons

  • Does not allow for non-@escaping closures.
  • Does not allow for throw-ing closures.

Static Methods

Pros

  • Allows for non-@escaping closures.
  • Allows for throw-ing closures.
  • Method name index(of:) is available.

Cons

  • Keeps Collection as is.
  • 12 methods overall

IdentityProtocol

While this code compiles in Swift 4:

struct Foo {}

let foo = Foo()
let bar = foo.self

This code unfortunately doesn't:

let bar = foo[keypath: \.self]

Nor does this:

let bar = foo[keypath: \Foo.self]

For an ergonomic yet versatile implementation of binary search however we need an identity for KeyPath<T, U>.

This is where IdentityProtocol comes to help us:

public protocol IdentityProtocol {
    var identity: Self { get }
}
extension IdentityProtocol {
    var identity: Self { return self }
}

Until Swift gets native support for foo[keypath: \.self] that is.