<div dir="ltr"><div style="font-size:12.8px">Hey Vincent,</div><span style="font-size:12.8px">good proposal, love to see this in production. Better collection search would become quite handy :-)</span><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">regards,</div><div style="font-size:12.8px">Flori</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Jan 4, 2016 at 4:13 PM, Vincent Esche via swift-evolution <span dir="ltr"><<a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word"><div>After having had this code laying around on my Mac since 6/26/15 (waiting for Swift to go open source)</div><div>I figured it’s about damn time I submit the actual RFC for it. So without further ado…</div><div><br></div><div>One of the areas where Swift’s stdlib is still quite lacking is searching.</div><div>Which is a shame as searching (along with indexing) might be among</div><div>the most important tasks of computer science/software development.</div><div>One might not need fast collection searches for writing a banal fart or flashlight app,</div><div>but almost every other app is likely to benefit from having a proper searching API.</div><div><br></div><div>So I’d like to fix that.</div><div><br></div><div>Attached you find a full RFC along with the full and functional source code to make it happen.</div><div><br></div><div>I’d love to hear your opinion on this and will be more than happy to answer questions.</div><div><br></div><div>Rendered Version + Full Implementation: <a href="https://gist.github.com/regexident/2b7531bd748f57679671" target="_blank">https://gist.github.com/regexident/2b7531bd748f57679671</a></div><div>(The code is tested using Quick/Nimble. Tests would thus have to be ported to Swift’s XCTest.)</div><div><br></div><div>- Vincent</div><div><br></div><div></div><blockquote type="cite"><div>Markdown-dump for</div><div><br></div><div># Improved Collection Search</div><div><br></div><div>* Proposal: [SE-NNNN](<a href="https://github.com/apple/swift-evolution/blob/master/proposals/NNNN-name.md" target="_blank">https://github.com/apple/swift-evolution/blob/master/proposals/NNNN-name.md</a>)</div><div>* Author(s): [Vincent Esche](<a href="https://github.com/regexident" target="_blank">https://github.com/regexident</a>)</div><div>* Status: **Review**</div><div>* Review manager: TBD</div><div><br></div><div>## Introduction</div><div><br></div><div>This RFC proposes an extension to the currently rather limited and linear searching API of `CollectionType`, that is `indexOf(element:)` and `indexOf(predicate:)`.</div><div>It proposes the backwards-compatible refactoring of those existing methods as well as the introduction of a view-based ensemble of methods for efficient binary-search.</div><div><br></div><div>Swift-evolution thread: [link to the discussion thread for that proposal](<a href="https://lists.swift.org/pipermail/swift-evolution" target="_blank">https://lists.swift.org/pipermail/swift-evolution</a>)</div><div><br></div><div>## Motivation</div><div><br></div><div>Indexing of and searching in data is a big deal in software development. As such it is crucial to have capable means of doing so in a language that aspires to be a highly performant programming language.</div><div><br></div><div>Swift's current API for searching is basically limited to these two methods on `CollectionType`:</div><div><br></div><div>> ```swift</div><div>> func indexOf(element: Self.Generator.Element) -> Self.Index?</div><div>> ```</div><div>> Returns the first index where value appears in self or nil if value is not found.</div><div>></div><div>> **Complexity**: `O(self.count)`.</div><div><br></div><div>and:</div><div><br></div><div>> ```swift</div><div>> func indexOf(@noescape predicate: (Self.Generator.Element) throws -> Bool) rethrows -> Self.Index?</div><div>> ```</div><div>> Returns the first index where predicate returns true for the corresponding value, or nil if such value is not found.</div><div>> </div><div>> **Complexity**: `O(self.count)`.</div><div><br></div><div>The author sees a couple of issue with these two methods:</div><div><br></div><div>1. They do not provide an option for restricting the "haystack" to a certain `range` of `self`.</div><div>2. They do not provide a fast (`O(log2(self.count))`) path for sorted collections.</div><div>3. They should not be limited to `CollectionType` but instead be moved to `Indexable`.</div><div><br></div><div>In many situations it is desirable to perform fast searches on sorted collections instead of having to fall back to naïve linear searches.</div><div><br></div><div>Further more while a single `index` might be the most common subject of interest, there are many scenarios where a `range` or `count` of matches are of more use.</div><div><br></div><div>And anyone who is writing a custom ordered collection type will eventually want to find the insertion index for a given element and will thus end up writing some variant of `lowerBoundOf(…)` or `upperBoundOf(…)` (upon which all the other methods can be implemented, actually).</div><div><br></div><div>## Proposed solution</div><div><br></div><div>The author proposes:</div><div><br></div><div>1. A backwards-compatible refactoring of `CollectionType.indices`, moving it to `Indexable`.</div><div><br></div><div>2. A backwards-compatible refactoring of `indexOf(…)` (adding optional `range:` and moving it to `Indexable`).</div><div><br></div><div>3. The addition of `rangeOf(…)`, `countOf(…)` and `isSorted(…)` to `Indexable` with a TIME complexity of `O(self.count)`.</div><div><br></div><div>4. The introduction of a `BinarySearchView` on `Indexable`, allowing for fast (`O(log2(self.count))`) searches on `Indexable` via `indexOf(…)`, `rangeOf(…)`, `countOf(…)`, `lowerBoundOf(…)`, `upperBoundOf(…)` without cluttering `Indexable`'s interface.</div><div><br></div><div>## Detailed design</div><div><br></div><div>### `CollectionType.indices`:</div><div><br></div><div>The author proposes the relocation of `.indices` from `CollectionType` to `Indexable`:</div><div><br></div><div>```swift</div><div>extension Indexable {</div><div> /// Return the range of valid index values.</div><div> ///</div><div> /// The result's `endIndex` is the same as that of `self`. Because</div><div> /// `Range` is half-open, iterating the values of the result produces</div><div> /// all valid subscript arguments for `self`, omitting its `endIndex`.</div><div> public var indices: Range<Self.Index> { get }</div><div>}</div><div>```</div><div><br></div><div>After all all it does is provide a convenience method for generating a Range from its `startIndex` and `endIndex`. There is no need for `self` to be a `CollectionType` for this.</div><div><br></div><div>This change should not break any existing code as it generalizes the property.</div><div><br></div><div>### `Indexable` of `Comparable` elements:</div><div><br></div><div>The author proposes the addition of the following method on `Indexable where Element : Comparable`:</div><div><br></div><div>```swift</div><div>extension Indexable where Index: RandomAccessIndexType, _Element: Comparable {</div><div><span style="white-space:pre-wrap"> </span>/// Return true iff all elements in `self` within `range` are sorted according to `isOrderedBefore`.</div><div><span style="white-space:pre-wrap"> </span>///</div><div><span style="white-space:pre-wrap"> </span>/// - Complexity: O(`self.count`)</div><div><span style="white-space:pre-wrap"> </span>public func isSorted(range: Range<Index>? = nil) -> Bool</div><div>}</div><div>```</div><div><br></div><div>This method would perform a linear scan of the `Indexable` with a TIME complexity of `O(self.count)`.</div><div><br></div><div>An actual implementation of these methods can be found in `Indexable.swift`.</div><div><br></div><div>### `Indexable` of `Equatable ` elements:</div><div><br></div><div>The author proposes the addition of the following method on `Indexable where Element : Equatable`:</div><div><br></div><div>```swift</div><div>extension Indexable where Index : RandomAccessIndexType, _Element : Equatable {</div><div><br></div><div> /// Returns the first index where `element` appears in `self`</div><div> /// within range `range` or `nil` if `element` is not found.</div><div> ///</div><div> /// - Complexity: O(`self.count`)</div><div> public func indexOf(element: _Element, range: Range<Index>? = default) -> Self.Index?</div><div><br></div><div> /// Returns the first range where `element` appears in `self`</div><div> /// within range `range` or `nil` if `element` is not found.</div><div> ///</div><div> /// - Complexity: O(`self.count`)</div><div> public func rangeOf(element: _Element, range: Range<Index>? = default) -> Range<Self.Index>?</div><div><br></div><div> /// Returns the number of `element`s that appear in `self`</div><div> /// within range `range` or `nil` if such an element is not found.</div><div> ///</div><div> /// - Complexity: O(`self.count`)</div><div> public func countOf(element: _Element, range: Range<Index>? = default) -> Int</div><div>}</div><div>```</div><div><br></div><div>These methods would perform a linear scan of the `Indexable` with a TIME complexity of `O(self.count)`.</div><div><br></div><div>An actual implementation of these methods can be found in `Indexable.swift`.</div><div><br></div><div>### `Indexable` of any elements:</div><div><br></div><div>The author proposes the addition of the following methods on `Indexable`:</div><div><br></div><div>```swift</div><div>extension Indexable where Index : RandomAccessIndexType {</div><div><br></div><div> /// Returns the first index where an element appears in `self`</div><div> /// within range `range` for which `lensView(element) == value` or `nil` if such an element is not found.</div><div> ///</div><div> /// - Complexity: O(`self.count`)</div><div> public func indexOf(range: Range<Index>? = default, @noescape predicate: (_Element) throws -> Bool) rethrows -> Self.Index?</div><div><br></div><div> /// Returns the first range where an element appears in `self`</div><div> /// within range `range` for which `lensView(element) == value` or `nil` if such an element is not found.</div><div> ///</div><div> /// - Complexity: O(`self.count`)</div><div> public func rangeOf(range: Range<Index>? = default, @noescape predicate: (_Element) throws -> Bool) rethrows -> Range<Self.Index>?</div><div><br></div><div> /// Returns the number of `element`s that appear in `self`</div><div> /// within range `range` or `nil` if `element` is not found.</div><div> ///</div><div> /// - Complexity: O(`self.count`)</div><div> public func countOf(range: Range<Index>? = default, @noescape predicate: (_Element) throws -> Bool) rethrows -> Int</div><div><br></div><div> /// Return true iff all elements in `self` within `range` are sorted according to `isOrderedBefore`.</div><div> /// </div><div> /// - Complexity: O(`self.count`)</div><div> public func isSorted(range: Range<Index>? = default, @noescape isOrderedBefore: (_Element, _Element) throws -> Bool) rethrows -> Bool</div><div>}</div><div>```</div><div><br></div><div>These methods would perform a linear scan of the `Indexable` with a TIME complexity of `O(self.count)`.</div><div><br></div><div>An actual implementation of these methods can be found in `Indexable.swift`.</div><div><br></div><div>**Note**: For explanation of and reasoning behind the `lensView:` argument as well as the distinction between `T` and `Base._Element`, see below.</div><div><br></div><div>### `Indexable.binarySearchView(validateAgainst:?)`:</div><div><br></div><div>The author proposes the addition of a `binarySearchView(validateAgainst:?)` method on `Indexable` for obtaining a specialized search view for performing searches with O(`log2(self.count)`) complexity:</div><div><br></div><div>```swift</div><div>extension Indexable where Index: RandomAccessIndexType {</div><div><span style="white-space:pre-wrap"> </span>/// Create a view into a sorted indexable that allows access within `bounds`.</div><div><span style="white-space:pre-wrap"> </span>///</div><div><span style="white-space:pre-wrap"> </span>/// - Complexity: O(`self.count`) if a validation closure is provided, otherwise O(`1`).</div><div><span style="white-space:pre-wrap"> </span>public func binarySearchView(validateAgainst isOrderedBefore: ((_Element, _Element) -> Bool)? = nil) -> BinarySearchView<Self></div><div>}</div><div>```</div><div><br></div><div>### `BinarySearchView<T: Indexable>`:</div><div><br></div><div>The author proposes the introduction of a `BinarySearchView` struct with the following interface:</div><div><br></div><div>```swift</div><div>public struct BinarySearchView<Base : Indexable where Base.Index : RandomAccessIndexType> : Indexable {</div><div> public typealias Index = Base.Index</div><div><br></div><div> public var startIndex: Base.Index { get }</div><div><br></div><div> public var endIndex: Base.Index { get }</div><div><br></div><div> public subscript (position: Index) -> Base._Element { get }</div><div><br></div><div> /// Create a view into a sorted collection `base` that allows access within `bounds`.</div><div> ///</div><div> /// - Complexity: O(1).</div><div> public init(base: Base, validateAgainst isOrderedBefore: ((Base._Element, Base._Element) -> Bool)? = default)</div><div><br></div><div> /// Returns first index of the first `element` in `self` within range `range` for which</div><div> /// `lensView(element) < value` evaluates to false or `nil` if `element` is not found.</div><div> ///</div><div> /// - Complexity: O(`log2(self.count)`).</div><div> public func lowerBoundOf<T : Comparable>(value: T, range: Range<Index>? = default, @noescape isOrderedBefore: (T, T) -> Bool = default, @noescape lensView: Base._Element -> T) -> Base.Index</div><div><br></div><div> /// Returns first index of the first `element` in `self` within range `range` for which</div><div> /// `value < lensView(element)` evaluates to true or `nil` if `element` is not found.</div><div> ///</div><div> /// - Complexity: O(`log2(self.count)`).</div><div> public func upperBoundOf<T : Comparable>(value: T, range: Range<Index>? = default, @noescape isOrderedBefore: ((T, T) -> Bool) = default, @noescape lensView: Base._Element -> T) -> Base.Index</div><div><br></div><div> /// Returns the first index where an element appears in `self`</div><div> /// within range `range` for which `lensView(element) == value` or `nil` if such an element is not found.</div><div> ///</div><div> /// - Complexity: O(`log2(self.count)`).</div><div> public func indexOf<T : Comparable>(value: T, range: Range<Index>? = default, @noescape isOrderedBefore: (T, T) -> Bool = default, @noescape lensView: Base._Element -> T) -> Base.Index?</div><div><br></div><div> /// Returns the range where an element appears in `self`</div><div> /// within range `range` for which `lensView(element) == value` or `nil` if such an element is not found.</div><div> ///</div><div> /// - Complexity: O(`log2(self.count)`).</div><div> public func rangeOf<T : Comparable>(value: T, range: Range<Index>? = default, @noescape isOrderedBefore: (T, T) -> Bool = default, @noescape lensView: Base._Element -> T) -> Range<Base.Index>?</div><div><br></div><div> /// Returns the number of `element`s that appear in `self`</div><div> /// within range `range` for which `lensView(element) == value` or `nil` if such an element is not found.</div><div> ///</div><div> /// - Complexity: O(`log2(self.count)`).</div><div> public func countOf<T : Comparable>(value: T, range: Range<Index>? = default, @noescape isOrderedBefore: (T, T) -> Bool = default, @noescape lensView: Base._Element -> T) -> Int</div><div><br></div><div> internal let _base: Base</div><div>}</div><div>```</div><div><br></div><div>As well as the following extension for `Indexable where Element: Comparable`:</div><div><br></div><div>```swift</div><div>extension BinarySearchView where Base._Element : Comparable {</div><div> /// Returns first index of the first `element` in `self` within range `range` for which</div><div> /// `… < element` evaluates to false or `nil` if `element` is not found.</div><div> ///</div><div> /// - Complexity: O(`log2(self.count)`).</div><div> public func lowerBoundOf(element: Base._Element, range: Range<Index>? = default, @noescape isOrderedBefore: (Base._Element, Base._Element) -> Bool = default) -> Base.Index</div><div><br></div><div> /// Returns first index of the first `element` in `self` within range `range` for which</div><div> /// `element < …` evaluates to true or `nil` if `element` is not found.</div><div> ///</div><div> /// - Complexity: O(`log2(self.count)`).</div><div> public func upperBoundOf(element: Base._Element, range: Range<Index>? = default, @noescape isOrderedBefore: (Base._Element, Base._Element) -> Bool = default) -> Base.Index</div><div><br></div><div> /// Returns the first index where `element` appears in `self`</div><div> /// within range `range` or `nil` if `element` is not found.</div><div> ///</div><div> /// - Complexity: O(`log2(self.count)`).</div><div> public func indexOf(element: Base._Element, range: Range<Index>? = default, @noescape isOrderedBefore: (Base._Element, Base._Element) -> Bool = default) -> Base.Index?</div><div><br></div><div> /// Returns the range where `element` appears in `self`</div><div> /// within range `range` or `nil` if `element` is not found.</div><div> ///</div><div> /// - Complexity: O(`log2(self.count)`).</div><div> public func rangeOf(element: Base._Element, range: Range<Index>? = default, @noescape isOrderedBefore: (Base._Element, Base._Element) -> Bool = default) -> Range<Base.Index>?</div><div><br></div><div> /// Returns the number of `element`s that appear in `self`</div><div> /// within range `range` or `nil` if `element` is not found.</div><div> ///</div><div> /// - Complexity: O(`log2(self.count)`).</div><div> public func countOf(element: Base._Element, range: Range<Index>? = default, @noescape isOrderedBefore: (Base._Element, Base._Element) -> Bool = default) -> Int</div><div>}</div><div>```</div><div><br></div><div>These methods would perform a linear scan of the `Indexable` with a TIME complexity of `O(log2(self.count))`.</div><div><br></div><div>An actual implementation of these methods can be found in `BinarySearchView.swift`.</div><div><br></div><div>### Why `lensView`?</div><div><br></div><div>Let's assume one had a collection of Persons like this:</div><div><br></div><div>```swift</div><div>struct Person {</div><div> let name: String</div><div> let age: Int</div><div>}</div><div><br></div><div>let persons: [Person] = [ … ]</div><div>```</div><div><br></div><div>Now let's assume one wanted to find the first person that's called `John Doe`. One could either change `Person` to conform to `Equatable`, allowing `indexOf(element:)` to be called on `persons`. Now that was easy, wasn't it?</div><div><br></div><div>Fine, but what if one wanted to search `Person`s by both their `name` or their `age` depending on the given use case? You're out of luck now.</div><div><br></div><div>Luckily there is a variant of `indexOf(…)` called `indexOf(predicate:)` that is available for any type of `Element` regardless of its conformance to `Equatable`:</div><div><br></div><div>```swift</div><div>let searchView = persons.binarySearchView()</div><div>let index = persons.indexOf { $<a href="http://0.name" target="_blank">0.name</a> == "John Doe" }</div><div>```</div><div><br></div><div>Unfortunately however such a `predicate` cannot be used when searching for an element's property in a sorted(!) collection or a collection of non-`Comparable` elements within a TIME complexity of `O(log2(self.count))` as binary search uses `<` instead of `==` internally and as the "needle" gets passed as both the first (in `indexOf(…)` itself) and second argument (in `lowerBoundOf(…)` which gets called by `indexOf(…)`) to the operator, one cannot simply change `predicate: (E) -> Bool` to `isOrderedBefore: (V, E) -> Bool` as that would result in a type mismatch (`(V, E)` vs. `(E, V)`).</div><div><br></div><div>The use of `lensView` however allows one to do just that without making a mess.</div><div><br></div><div>```swift</div><div>let searchView = persons.binarySearchView() // sorted!</div><div>let index = searchView.indexOf("John Doe") { $<a href="http://0.name" target="_blank">0.name</a> }</div><div>```</div><div><br></div><div>The `lensView` works similarly to how keypaths work in Objective-C, just type-safe.</div><div><br></div><div>## Impact on existing code</div><div><br></div><div>The author proposes:</div><div><br></div><div>1. Moving `CollectionType.indices` to `Indexable` should not cause any issues with existing code.</div><div><br></div><div>2. Changing `indexOf(element:)` to `indexOf(element:range:?)` should not cause any issues with existing code as the `range` argument is optional and the default behaves like it used to.</div><div><br></div><div>2. Changing `indexOf(predicate:)` to `indexOf(range:?predicate:)` should not cause any issues with existing code either, as the `range` argument is optional and the default behaves like it used to. Swift's trailing-closure magic allows `indexOf(predicate: …)` to still properly map to `indexOf(range: nil, predicate: …)`.</div><div><br></div><div>3. The addition of `rangeOf(…)`, `countOf(…)` and `isSorted(…)` to `Indexable` do not conflict with any existing API.</div><div><br></div><div>4. The introduction of a `BinarySearchView` on `Indexable` does not conflict with any existing API.</div><div><br></div><div>## Alternatives considered</div><div><br></div><div>The author's initial approach was to implement all methods on Indexable. This however required all methods to either be provided in two variants (one for unsorted, one for sorted `Indexable`s):</div><div><br></div><div>```swift</div><div>final public func indexOf(element: _Element, range: Range<Index>? = nil) -> Index? {</div><div><span style="white-space:pre-wrap"> </span>return …</div><div>}</div><div><br></div><div>final public func sortedIndexOf(element: _Element, range: Range<Index>? = nil) -> Index? {</div><div><span style="white-space:pre-wrap"> </span>return …</div><div>}</div><div>```</div><div><br></div><div>Or require the introduction of an additional argument:</div><div><br></div><div>```swift</div><div>final public func indexOf(element: _Element, range: Range<Index>? = nil, isSorted: Bool = true) -> Index? {</div><div> if isSorted {</div><div> return …</div><div> } else {</div><div> return …</div><div> }</div><div>}</div><div>```</div><div><br></div><div>It also would have cluttered `Indexable` with methods such as `lowerBoundOf` and `upperBoundOf`, which are only ever applicable when `self` is sorted accordingly. The introduction of a dedicated BinarySearchView fixes these issues.</div><div><br></div><div>One also would have had to switch from `predicate: (T) -> Bool` to `isOrderedBefore: (T, T) -> Bool` for all methods for the second unified API alternative.</div></blockquote><div><br></div>
<img src="https://u2002410.ct.sendgrid.net/wf/open?upn=060Ny-2BAgNfmOIXBwq-2FuGydbbLmCTrZEOO-2Fgo-2FfX4XSapRLw9Y0YDfAAILF2-2FAYlquRKcCFd29-2BM2JquZUrD0J6iLIhLgtj1rTc0MysQLhdq7H9uktlImyNBx-2FHPl-2FRgHaJTVVnz96iyBmb0HtrlESlhcMKVz-2FDOBYfINaMoS54mQjc45Gbh1eFlbx3-2FRb4oaWunHXGBcBz2GQsbWIdnlLl20H7OeQ1dVQpz1IlEwn28-3D" alt="" width="1" height="1" border="0" style="min-height:1px!important;width:1px!important;border-width:0!important;margin-top:0!important;margin-bottom:0!important;margin-right:0!important;margin-left:0!important;padding-top:0!important;padding-bottom:0!important;padding-right:0!important;padding-left:0!important">
</div>
<br>_______________________________________________<br>
swift-evolution mailing list<br>
<a href="mailto:swift-evolution@swift.org">swift-evolution@swift.org</a><br>
<a href="https://lists.swift.org/mailman/listinfo/swift-evolution" rel="noreferrer" target="_blank">https://lists.swift.org/mailman/listinfo/swift-evolution</a><br>
<br></blockquote></div><br></div>