Compare commits

..
56 changed files with 878 additions and 5738 deletions

No files matched your search

+5
View File
@@ -0,0 +1,5 @@
<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE plist PUBLIC "-//Apple//DTD PLIST 1.0//EN" "http://www.apple.com/DTDs/PropertyList-1.0.dtd">
<plist version="1.0">
<array/>
</plist>
+2 -68
View File
@@ -16,47 +16,6 @@ package updates, you can specify your package dependency using
---
## [0.0.3] - 2021-02-26
### Additions
An exciting group of new algorithms, contributed by the community:
- `trimming(while:)` returns a subsequence of a bidirectional collection with
the matching elements removed from the start and end. ([#4])
- `min(ofCount:)` and `max(ofCount:)` find the smallest or largest elements in
a collection. ([#9], [#77])
- `windows(ofCount:)` lets you iterate over all the overlapping subsequences of
a particular length. ([#20])
- `striding(by:)` iterates over every *n*th element of a sequence or collection.
([#24])
- `interspersed(with:)` places a new element between every pair of elements in
a sequence or collection. ([#35])
- `chunks(ofCount:)` breaks a collection into subsequences of the given number
of elements. ([#54])
- `suffix(while:)` matches the standard library's `prefix(while:)`, by
returning the suffix of all matching elements from a bidirectional collection.
([#65])
- Variations of `combinations(ofCount:)` and `permutations(ofCount:)` that take
a range expression as a parameter, returning combinations and permutations of
multiple lengths. ([#51], [#56])
### Changes
- The `LazyChunked` type now precomputes its `startIndex`, making performance
more predictable when using the collection.
### Fixes
- `randomSample(count:)` no longer traps in rare circumstances.
- Index calculations have been improved in a variety of collection wrappers.
- A variety of documentation improvements and corrections.
The 0.0.3 release includes contributions from [benrimmington], [danielctull],
[dhruvshah8], [karwa], [LucianoPAlmeida], [markuswntr], [mdznr], [michiboo],
[natecook1000], [ollieatkinson], [rakaramos], [rockbruno], [Roshankumar350],
[sidepelican], and [timvermeulen]. Thank you!
## [0.0.2] - 2020-10-23
### Changes
@@ -73,7 +32,7 @@ The 0.0.3 release includes contributions from [benrimmington], [danielctull],
### Fixes
- `Algorithms` now builds under SwiftPM on Windows.
- Swift Algorithms now builds under SwiftPM on Windows.
- A wide variety of errors, misspellings, and ommissions in the documentation
and guides have been fixed.
- Index/distance calculations for the `Product2` and `Chain` types have been
@@ -85,7 +44,6 @@ The 0.0.2 release includes contributions from [AustinConlon], [egorzhdan],
[IanKeen], [iSame7], [karwa], [kylemacomber], [natecook1000], [nordicio],
[pmtao], [schlagelk], [stephentyrone], and [timvermeulen]. Thank you!
## [0.0.1] - 2020-10-07
- **Swift Algorithms** initial release.
@@ -96,47 +54,23 @@ This changelog's format is based on [Keep a Changelog](https://keepachangelog.co
<!-- Link references for releases -->
[Unreleased]: https://github.com/apple/swift-algorithms/compare/0.0.3...HEAD
[0.0.3]: https://github.com/apple/swift-algorithms/compare/0.0.2...0.0.3
[Unreleased]: https://github.com/apple/swift-algorithms/compare/0.0.2...HEAD
[0.0.2]: https://github.com/apple/swift-algorithms/compare/0.0.1...0.0.2
[0.0.1]: https://github.com/apple/swift-algorithms/releases/tag/0.0.1
<!-- Link references for pull requests -->
[#4]: https://github.com/apple/swift-algorithms/pull/4
[#9]: https://github.com/apple/swift-algorithms/pull/9
[#20]: https://github.com/apple/swift-algorithms/pull/20
[#24]: https://github.com/apple/swift-algorithms/pull/24
[#35]: https://github.com/apple/swift-algorithms/pull/35
[#51]: https://github.com/apple/swift-algorithms/pull/51
[#54]: https://github.com/apple/swift-algorithms/pull/54
[#56]: https://github.com/apple/swift-algorithms/pull/56
[#65]: https://github.com/apple/swift-algorithms/pull/65
[#77]: https://github.com/apple/swift-algorithms/pull/77
<!-- Link references for contributors -->
[AustinConlon]: https://github.com/apple/swift-algorithms/commits?author=AustinConlon
[benrimmington]: https://github.com/apple/swift-algorithms/commits?author=benrimmington
[danielctull]: https://github.com/apple/swift-algorithms/commits?author=danielctull
[dhruvshah8]: https://github.com/apple/swift-algorithms/commits?author=dhruvshah8
[egorzhdan]: https://github.com/apple/swift-algorithms/commits?author=egorzhdan
[IanKeen]: https://github.com/apple/swift-algorithms/commits?author=IanKeen
[iSame7]: https://github.com/apple/swift-algorithms/commits?author=iSame7
[karwa]: https://github.com/apple/swift-algorithms/commits?author=karwa
[kylemacomber]: https://github.com/apple/swift-algorithms/commits?author=kylemacomber
[LucianoPAlmeida]: https://github.com/apple/swift-algorithms/commits?author=LucianoPAlmeida
[markuswntr]: https://github.com/apple/swift-algorithms/commits?author=markuswntr
[mdznr]: https://github.com/apple/swift-algorithms/commits?author=mdznr
[michiboo]: https://github.com/apple/swift-algorithms/commits?author=michiboo
[natecook1000]: https://github.com/apple/swift-algorithms/commits?author=natecook1000
[nordicio]: https://github.com/apple/swift-algorithms/commits?author=nordicio
[ollieatkinson]: https://github.com/apple/swift-algorithms/commits?author=ollieatkinson
[pmtao]: https://github.com/apple/swift-algorithms/commits?author=pmtao
[rakaramos]: https://github.com/apple/swift-algorithms/commits?author=rakaramos
[rockbruno]: https://github.com/apple/swift-algorithms/commits?author=rockbruno
[Roshankumar350]: https://github.com/apple/swift-algorithms/commits?author=Roshankumar350
[schlagelk]: https://github.com/apple/swift-algorithms/commits?author=schlagelk
[sidepelican]: https://github.com/apple/swift-algorithms/commits?author=sidepelican
[stephentyrone]: https://github.com/apple/swift-algorithms/commits?author=stephentyrone
[timvermeulen]: https://github.com/apple/swift-algorithms/commits?author=timvermeulen
+6 -24
View File
@@ -4,10 +4,7 @@
[Tests](https://github.com/apple/swift-algorithms/blob/main/Tests/SwiftAlgorithmsTests/ChunkedTests.swift)]
Break a collection into subsequences where consecutive elements pass a binary
predicate, or where all elements in each chunk project to the same value.
Also, includes a `chunks(ofCount:)` that breaks a collection into subsequences
of a given `count`.
predicate, or where all elements in each chunk project to the same value.
There are two variations of the `chunked` method: `chunked(by:)` and
`chunked(on:)`. `chunked(by:)` uses a binary predicate to test consecutive
@@ -29,32 +26,17 @@ let chunks = names.chunked(on: \.first!)
// [["David"], ["Kyle", "Karoy"], ["Nate"]]
```
The `chunks(ofCount:)` takes a `count` parameter (required to be > 0) and separates
the collection into `n` chunks of this given count. If the `count` parameter is
evenly divided by the count of the base `Collection` all the chunks will have
the count equals to the parameter. Otherwise, the last chunk will contain the
remaining elements.
```swift
let names = ["David", "Kyle", "Karoy", "Nate"]
let evenly = names.chunks(ofCount: 2)
// equivalent to [["David", "Kyle"], ["Karoy", "Nate"]]
let remaining = names.chunks(ofCount: 3)
// equivalent to [["David", "Kyle", "Karoy"], ["Nate"]]
```
The `chunks(ofCount:)` is the method of the [existing SE proposal][proposal].
Unlike the `split` family of methods, the entire collection is included in the
chunked result — joining the resulting chunks recreates the original collection.
These methods are related to the [existing SE proposal][proposal] for chunking a
collection into subsequences of a particular size, potentially named something
like `chunked(length:)`. Unlike the `split` family of methods, the entire
collection is included in the chunked result — joining the resulting chunks
recreates the original collection.
```swift
c.elementsEqual(c.chunked(...).joined())
// true
```
Check the [proposal][proposal] detailed design section for more info.
[proposal]: https://github.com/apple/swift-evolution/pull/935
## Detailed Design
+3 -24
View File
@@ -36,27 +36,6 @@ for combo in numbers2.combinations(ofCount: 2) {
// [10, 10]
```
Given a range, the `combinations(ofCount:)` method returns a sequence of all
the different combinations of the given sizes of a collection’s elements in
increasing order of size.
```swift
let numbers = [10, 20, 30, 40]
for combo in numbers.combinations(ofCount: 2...3) {
print(combo)
}
// [10, 20]
// [10, 30]
// [10, 40]
// [20, 30]
// [20, 40]
// [30, 40]
// [10, 20, 30]
// [10, 20, 40]
// [10, 30, 40]
// [20, 30, 40]
```
## Detailed Design
The `combinations(ofCount:)` method is declared as a `Collection` extension,
@@ -77,9 +56,9 @@ array at every index advancement. `Combinations` does conform to
### Complexity
Calling `combinations(ofCount:)` accesses the count of the collection, so it’s
an O(1) operation for random-access collections, or an O(_n_) operation
otherwise. Creating the iterator for a `Combinations` instance and each call to
Calling `combinations(ofCount:)` accesses the count of the collection, so it’s an
O(1) operation for random-access collections, or an O(_n_) operation otherwise.
Creating the iterator for a `Combinations` instance and each call to
`Combinations.Iterator.next()` is an O(_n_) operation.
### Naming
-43
View File
@@ -1,43 +0,0 @@
# First Non-Nil
[[Source](https://github.com/apple/swift-algorithms/blob/main/Sources/Algorithms/FirstNonNil.swift) |
[Tests](https://github.com/apple/swift-algorithms/blob/main/Tests/SwiftAlgorithmsTests/FirstNonNilTests.swift)]
Retrieves the first `.some` encountered while applying the given transform.
This operation is available through the `firstNonNil(_:)` method on any sequence.
```swift
let value = ["A", "B", "10"].firstNonNil { Int($0) }
// value == .some(10)
//
let noValue = ["A", "B", "C"].firstNonNil { Int($0) }
// noValue == .none
```
This method is analogous to `first(where:)` in how it only consumes values until
a `.some` is found, unlike using lazy operators, which will load any sequence into a collection
before evaluating its transforms lazily.
## Detailed Design
The `firstNonNil(_:)` method is added as an extension method on the `Sequence`
protocol:
```swift
public extension Sequence {
func firstNonNil<Result>(_ transform: (Element) throws -> Result?)
rethrows -> Result?
}
```
### Naming
This method’s name was selected for its comprehensibility.
### Comparison with other languages
**Scala**: Scala provides a `collectFirst` function that finds the first element
in a collection for which a partial function is defined.
+2 -2
View File
@@ -30,6 +30,6 @@ extension Collection {
```
`Indexed` scales from a collection up to a random-access collection, depending on
its base type. `Indexed` also conforms to `LazySequenceProtocol` and
`LazyCollectionProtocol` when the base type conforms.
its base type. `Indexed` also conforms to `LazySequenceProtocol` when the base type
conforms.
-58
View File
@@ -1,58 +0,0 @@
# Intersperse
[[Source](https://github.com/apple/swift-algorithms/blob/main/Sources/Algorithms/Intersperse.swift) |
[Tests](https://github.com/apple/swift-algorithms/blob/main/Tests/SwiftAlgorithmsTests/IntersperseTests.swift)]
Place a given value in between each element of the sequence.
```swift
let numbers = [1, 2, 3].interspersed(with: 0)
// Array(numbers) == [1, 0, 2, 0, 3]
let letters = "ABCDE".interspersed(with: "-")
// String(letters) == "A-B-C-D-E"
let empty = [].interspersed(with: 0)
// Array(empty) == []
```
`interspersed(with:)` takes a separator value and inserts it in between every
element in the sequence.
## Detailed Design
A new method is added to sequence:
```swift
extension Sequence {
func interspersed(with separator: Element) -> Intersperse<Self>
}
```
The new `Intersperse` type represents the sequence when the separator is
inserted between each element. `Intersperse` conforms to `Collection`,
`BidirectionalCollection`, `RandomAccessCollection`, `LazySequenceProtocol` and
`LazyCollectionProtocol` when the base sequence conforms to those respective
protocols.
### Complexity
Calling these methods is O(_1_).
### Naming
This method’s and type’s name match the term of art used in other languages
and libraries.
### Comparison with other languages
**[Haskell][Haskell]:** Has an `intersperse` function which takes an element
and a list and 'intersperses' that element between the elements of the list.
**[Rust][Rust]:** Has a function called `intersperse` to insert a particular
value between each element.
<!-- Link references for other languages -->
[Haskell]: https://hackage.haskell.org/package/base-4.14.0.0/docs/Data-List.html#v:intersperse
[Rust]: https://docs.rs/itertools/0.9.0/itertools/trait.Itertools.html#method.intersperse
-80
View File
@@ -1,80 +0,0 @@
# LazySplit
[[Source](https://github.com/apple/swift-algorithms/blob/main/Sources/Algorithms/LazySplit.swift) |
[Tests](https://github.com/apple/swift-algorithms/blob/main/Tests/SwiftAlgorithmsTests/LazySplitTests.swift)]
Lazily-evaluating versions of
[`split(maxSplits:omittingEmptySubsequences:whereSeparator:)`](https://developer.apple.com/documentation/swift/sequence/3128814-split)
and [`split(separator:maxSplits:omittingEmptySubsequences:)`](https://developer.apple.com/documentation/swift/sequence/3128818-split),
performing the same operation as their counterparts defined on
`Sequence` and `Collection`, are added to `LazySequence` and
`LazyCollection`. The `LazyCollection` methods allow splitting a
collection without allocating additional storage on the heap.
```swift
// Splitting a lazy sequence.
let numbers = stride(from: 1, through: 16, by: 1)
for subsequence in numbers.lazy.split(
whereSeparator: { $0 % 3 == 0 || $0 % 5 == 0 }
) {
print(subsequence)
}
/* Prints:
[1, 2]
[4]
[7, 8]
[11]
[13, 14]
[16]
*/
// Splitting a lazy collection.
let line = "BLANCHE: I don't want realism. I want magic!"
for subsequence in line.lazy.split(separator: " ") {
print(subsequence)
}
/* Prints
BLANCHE:
I
don't
want
realism.
I
want
magic!
*/
```
## Detailed Design
`LazySequence` and `LazyCollection` are each extended with
`split(maxSplits:omittingEmptySubsequences:whereSeparator:)` and
`split(separator:maxSplits:omittingEmptySubsequences:)`.
The `LazySequence` versions of those methods return an instance of
`LazySplitSequence`. The `LazyCollection` versions return an instance of
`LazySplitCollection`.
`LazySplitSequence` wraps the sequence to be split, and provides an
iterator whose `next` method returns a newly-allocated array containing
the elements of each subsequence in the split sequence in turn.
`LazySplitCollection` wraps the collection to be split. Its `Index`
wraps a range of base collection indices. `startIndex` is computed at
initialization. Subscripting a `LazySplitCollection` instance returns
the slice of the original collection which is the subsequence of the
split collection at the given index's position.
### Complexity
Iterating a `LazySplitSequence` instance is O(_n_) in time and space,
since each subsequence returned is a newly-allocated array.
Iterating a `LazySplitCollection` instance is O(_n_) in time and O(1) in
space, since each subsequence returned is a slice of the base
collection. Since `startIndex` is computed at initialization, some or
all of the time cost may be paid at initialization. For example, if the
base collection contains no elements determined to be separators, it
will be iterated entirely on initialization of the split collection, and
all subsequent operations on the split collection, such as
`index(after:)`, will have complexity O(1).
-58
View File
@@ -1,58 +0,0 @@
# Min/Max with Count
[[Source](https://github.com/apple/swift-algorithms/blob/main/Sources/Algorithms/MinMax.swift) |
[Tests](https://github.com/apple/swift-algorithms/blob/main/Tests/SwiftAlgorithmsTests/MinMaxTests.swift)]
Returns the smallest or largest elements of this collection, sorted by a predicate or in the order defined by `Comparable` conformance.
If you need to sort a collection but only need access to a prefix or suffix of the sorted elements, using these methods can give you a performance boost over sorting the entire collection. The order of equal elements is guaranteed to be preserved.
```swift
let numbers = [7, 1, 6, 2, 8, 3, 9]
let smallestThree = numbers.min(count: 3, sortedBy: <)
// [1, 2, 3]
```
## Detailed Design
This adds the `Collection` methods shown below:
```swift
extension Collection {
public func min(
count: Int,
sortedBy areInIncreasingOrder: (Element, Element) throws -> Bool
) rethrows -> [Element]
public func max(
count: Int,
sortedBy areInIncreasingOrder: (Element, Element) throws -> Bool
) rethrows -> [Element]
}
```
Additionally, versions of these methods for `Comparable` types are also provided:
```swift
extension Collection where Element: Comparable {
public func min(count: Int) -> [Element]
public func max(count: Int) -> [Element]
}
```
### Complexity
The algorithm used is based on [Soroush Khanlou's research on this matter](https://khanlou.com/2018/12/analyzing-complexity/). The total complexity is `O(k log k + nk)`, which will result in a runtime close to `O(n)` if *k* is a small amount. If *k* is a large amount (more than 10% of the collection), we fall back to sorting the entire array. Realistically, this means the worst case is actually `O(n log n)`.
Here are some benchmarks we made that demonstrates how this implementation (SmallestM) behaves when *k* increases (before implementing the fallback):
![Benchmark](Resources/SortedPrefix/FewElements.png)
![Benchmark 2](Resources/SortedPrefix/ManyElements.png)
### Comparison with other languages
**C++:** The `<algorithm>` library defines a `partial_sort` function where the entire array is returned using a partial heap sort.
**Python:** Defines a `heapq` priority queue that can be used to manually achieve the same result.
-25
View File
@@ -60,31 +60,6 @@ for perm in numbers2.permutations() {
// [10, 10, 20]
```
Given a range, the `permutations(ofCount:)` method returns a sequence of all the different permutations of the given sizes of a collection’s elements in increasing order of size.
```swift
let numbers = [10, 20, 30]
for perm in numbers.permutations(ofCount: 0...) {
print(perm)
}
// []
// [10]
// [20]
// [30]
// [10, 20]
// [10, 30]
// [20, 10]
// [20, 30]
// [30, 10]
// [30, 20]
// [10, 20, 30]
// [10, 30, 20]
// [20, 10, 30]
// [20, 30, 10]
// [30, 10, 20]
// [30, 20, 10]
```
## Detailed Design
The `permutations(ofCount:)` method is declared as a `Collection` extension,
Binary file not shown.

Before

Width:  |  Height:  |  Size: 74 KiB

Binary file not shown.

Before

Width:  |  Height:  |  Size: 77 KiB

+64
View File
@@ -0,0 +1,64 @@
# SlidingWindows
[[Source](https://github.com/apple/swift-algorithms/blob/main/Sources/Algorithms/SlidingWindows.swift) |
[Tests](https://github.com/apple/swift-algorithms/blob/main/Tests/SwiftAlgorithmsTests/SlidingWindowsTests.swift)]
Break a collection into overlapping contiguous window subsequences where
elements are slices from the original collection.
The `slidingWindows(ofCount:)` method takes in a integer size and returns a collection
of subsequences.
```swift
let swift = "swift"
let windowed = swift.slidingWindows(ofCount: 2)
// windowed == [ "sw", "wi", "if", "ft" ]
```
## Detailed Design
The `slidingWindows(ofCount:)` is added as a method on an extension of `Collection`
```swift
extension Collection {
public func slidingWindows(ofCount count: Int) -> SlidingWindows<Self> {
SlidingWindows(base: self, size: count)
}
}
```
If a size larger than the collection length is specified, an empty collection is returned.
The first upper bound is computed eagerly because it determines if the collection
`startIndex` returns `endIndex`.
```swift
[1, 2, 3].slidingWindows(ofCount: 5).isEmpty // true
```
The resulting `SlidingWindows` type is a collection, with conditional conformance to the
`BidirectionalCollection`, and `RandomAccessCollection` when the base collection
conforms.
### Complexity
The call to `slidingWindows(ofCount: k)` is O(_1_) if the collection conforms to
`RandomAccessCollection`, otherwise O(_k_). Access to the next window is O(_1_).
### Naming
The type `SlidingWindows` takes its name from the algorithm, similarly the method takes
it's name from it too `slidingWindows(ofCount: k)`.
The label on the method `ofCount` was chosen to create a consistent feel to the API
available in swift-algorithms repository. Inspiration was taken from
`combinations(ofCount:)` and `permutations(ofCount:)`.
Previously the name `windows` was considered but was deemed to potentially create
ambiguity with the Windows operating system.
### Comparison with other languages
[rust](https://doc.rust-lang.org/std/slice/struct.Windows.html) has
`std::slice::Windows` which is a method available on slices. It has the same
semantics as described here.
-63
View File
@@ -1,63 +0,0 @@
# Stride
[[Source](https://github.com/apple/swift-algorithms/blob/main/Sources/Algorithms/Stride.swift) |
[Tests](https://github.com/apple/swift-algorithms/blob/main/Tests/SwiftAlgorithmsTests/StrideTests.swift)]
A type that steps over sequence elements by the specified amount.
This is available through the `striding(by:)` method on any `Sequence`.
```swift
(0...10).striding(by: 2) // == [0, 2, 4, 6, 8, 10]
```
If the stride is larger than the count, the resulting wrapper only contains the
first element.
The stride amount must be a positive value.
## Detailed Design
The `striding(by:)` method is declared as a `Sequence` extension, and returns a
`Stride` type:
```swift
extension Sequence {
public func striding(by step: Int) -> Stride<Self>
}
```
A custom `Index` type is defined so that it's not possible to get confused when trying
to access an index of the stride collection.
```swift
[0, 1, 2, 3, 4].striding(by: 2)[1] // == 1
[0, 1, 2, 3, 4].striding(by: 2).map { $0 }[1] // == 2
```
A careful thought was given to the composition of these strides by giving a custom
implementation to `index(_:offsetBy:limitedBy)` which multiplies the offset by the
stride amount.
```swift
base.index(i.base, offsetBy: distance * stride, limitedBy: base.endIndex)
```
The following two lines of code are equivalent, including performance:
```swift
(0...10).striding(by: 6)
(0...10).striding(by: 2).stride(by: 3)
```
### Complexity
The call to `striding(by: k)` is always O(_1_) and access to the next value in the stride
is O(_1_) if the collection conforms to `RandomAccessCollection`, otherwise O(_k_).
### Comparison with other languages
[rust has `Strided`](https://docs.rs/strided/0.2.9/strided/) available in a crate.
[c++ has std::slice::stride](http://www.cplusplus.com/reference/valarray/slice/stride/)
The semantics of `striding` described in this documentation are equivalent.
-39
View File
@@ -1,39 +0,0 @@
# Suffix
[[Source](https://github.com/apple/swift-algorithms/blob/main/Sources/Algorithms/Suffix.swift) |
[Tests](https://github.com/apple/swift-algorithms/blob/main/Tests/SwiftAlgorithmsTests/SuffixTests.swift)]
This function returns a subsequence containing the elements from the end of the collection until predicate returns `false` and skipping the remaining elements.
This example uses `suffix(while: )` to iterate through collection of integers from the end until the predicate returns false, in this case when `$0 <= 5`
```swift
(0...10).suffix(while: { $0 > 5 } // == [6,7,8,9,10]
```
## Detailed Design
The `suffix(while:)` function is added as a method on an extension of `BidirectionalCollection`.
```swift
extension BidirectionalCollection {
public func suffix(while predicate: (Element) throws -> Bool) rethrows -> SubSequence
}
```
This method requires `BidirectionalCollection` for an efficient implementation which visits as few elements as possible. Swift's protocol allows for backward traversal of a collection as well as access to *last* property of a collection.
### Complexity
Calling this method is O(*n*), where *n* is the length of the collection.
### Naming
The function's name resembles that of an existing Swift function `prefix(while:)`, which performs same operation however in the forward direction of the collection. Hence, as this function traverses from the end of the collection, `suffix(while:)` is an appropriate name.
+8 -8
View File
@@ -6,13 +6,13 @@
Returns a `SubSequence` formed by discarding all elements at the start and end of the collection
which satisfy the given predicate.
This example uses `trimming(while:)` to get a substring without the white space at the beginning and end of the string.
This example uses `trimming(where:)` to get a substring without the white space at the beginning and end of the string.
```swift
let myString = " hello, world "
print(myString.trimming(while: \.isWhitespace)) // "hello, world"
print(myString.trimming(where: \.isWhitespace)) // "hello, world"
let results = [2, 10, 11, 15, 20, 21, 100].trimming(while: { $0.isMultiple(of: 2) })
let results = [2, 10, 11, 15, 20, 21, 100].trimming(where: { $0.isMultiple(of: 2) })
print(results) // [11, 15, 20, 21]
```
@@ -23,7 +23,7 @@ A new method is added to `BidirectionalCollection`:
```swift
extension BidirectionalCollection {
public func trimming(while predicate: (Element) throws -> Bool) rethrows -> SubSequence
public func trimming(where predicate: (Element) throws -> Bool) rethrows -> SubSequence
}
```
@@ -36,12 +36,12 @@ to add the `BidirectionalCollection` constraint will receive that inefficient im
```swift
func myAlgorithm<Input>(input: Input) where Input: Collection {
let trimmedInput = input.trimming(while: { ... }) // Uses least-efficient implementation.
let trimmedInput = input.trimming(where: { ... }) // Uses least-efficient implementation.
}
func myAlgorithm2<Input>(input: Input) where Input: BidirectionalCollection {
let trimmedInput = input.trimming(while: { ... }) // Uses most-efficient implementation.
let trimmedInput = input.trimming(where: { ... }) // Uses most-efficient implementation.
}
```
@@ -107,8 +107,8 @@ languages:
```swift
// Does `result` contain the input, trimmed of certain elements?
// Or does this code mutate `input` in-place and return the elements which were dropped?
let result = input.dropFromBothEnds(while: { ... })
let result = input.dropFromBothEnds(where: { ... })
// No such ambiguity here.
let result = input.trimming(while: { ... })
let result = input.trimming(where: { ... })
```
-55
View File
@@ -1,55 +0,0 @@
# Windows
[[Source](https://github.com/apple/swift-algorithms/blob/main/Sources/Algorithms/Windows.swift) |
[Tests](https://github.com/apple/swift-algorithms/blob/main/Tests/SwiftAlgorithmsTests/WindowsTests.swift)]
Break a collection into overlapping subsequences where
elements are slices from the original collection.
The `windows(ofCount:)` method takes a size as a parameter and returns a collection of subsequences. Each element of the returned collection is a successive overlapping slice of the given size.
```swift
let swift = "swift"
let windowed = swift.windows(ofCount: 2)
// Array(windowed) == [ "sw", "wi", "if", "ft" ]
```
## Detailed Design
The `windows(ofCount:)` method is added as an extension `Collection` method:
```swift
extension Collection {
public func windows(ofCount count: Int) -> Windows<Self>
}
```
If a size larger than the collection's length is specified, the returned collection is empty.
```swift
[1, 2, 3].windows(ofCount: 5).isEmpty // true
```
The resulting `Windows` type is a collection, with conditional conformance to the
`BidirectionalCollection`, `RandomAccessCollection`, and
`LazyCollectionProtocol` protocols when the base collection conforms.
### Complexity
The call to `windows(ofCount: k)` is O(1) if the collection conforms to
`RandomAccessCollection`, otherwise O(_k_). Access to each successive window is O(1).
### Naming
The method and type name take their names from the sliding windows algorithm.
The `ofCount` parameter label was chosen to create a consistent feel with other
APIs in the `Algorithms` package, specifically with `combinations(ofCount:)`
and `permutations(ofCount:)`.
### Comparison with other languages
[rust](https://doc.rust-lang.org/std/slice/struct.Windows.html) has
`std::slice::Windows` which is a method available on slices. It has the same
semantics as described here.
-3
View File
@@ -28,9 +28,6 @@ let package = Package(
dependencies: [
.product(name: "RealModule", package: "swift-numerics"),
]),
.target(
name: "Benchmark",
dependencies: ["Algorithms"]),
.testTarget(
name: "SwiftAlgorithmsTests",
dependencies: ["Algorithms"]),
+4 -12
View File
@@ -8,7 +8,7 @@ Read more about the package, and the intent behind it, in the [announcement on s
#### Combinations / permutations
- [`combinations(ofCount:)`](https://github.com/apple/swift-algorithms/blob/main/Guides/Combinations.md): Combinations of particular sizes of the elements in a collection.
- [`combinations(ofCount:)`](https://github.com/apple/swift-algorithms/blob/main/Guides/Combinations.md): Combinations of a particular size of the elements in a collection.
- [`permutations(ofCount:)`](https://github.com/apple/swift-algorithms/blob/main/Guides/Permutations.md): Permutations of a particular size of the elements in a collection, or of the full collection.
#### Mutating algorithms
@@ -26,22 +26,14 @@ Read more about the package, and the intent behind it, in the [announcement on s
- [`randomSample(count:)`, `randomSample(count:using:)`](https://github.com/apple/swift-algorithms/blob/main/Guides/RandomSampling.md): Randomly selects a specific number of elements from a collection.
- [`randomStableSample(count:)`, `randomStableSample(count:using:)`](https://github.com/apple/swift-algorithms/blob/main/Guides/RandomSampling.md): Randomly selects a specific number of elements from a collection, preserving their original relative order.
- [`suffix(while:)`](https://github.com/apple/swift-algorithms/blob/main/Guides/Suffix.md): Returns the suffix of a collection where all element pass a given predicate.
- [`uniqued()`, `uniqued(on:)`](https://github.com/apple/swift-algorithms/blob/main/Guides/Unique.md): The unique elements of a collection, preserving their order.
#### Partial sorting
- [`min(count:)`, `max(count:)`, `min(count:sortedBy:)`, `max(count:sortedBy:)`](https://github.com/apple/swift-algorithms/blob/main/Guides/MinMax.md): Returns the smallest or largest elements of a collection, sorted by a predicate.
#### Other useful operations
- [`chunked(by:)`, `chunked(on:)`, `chunks(ofCount:)`](https://github.com/apple/swift-algorithms/blob/main/Guides/Chunked.md): Eager and lazy operations that break a collection into chunks based on either a binary predicate or when the result of a projection changes or chunks of a given count.
- [`chunked(by:)`, `chunked(on:)`](https://github.com/apple/swift-algorithms/blob/main/Guides/Chunked.md): Eager and lazy operations that break a collection into chunks based on either a binary predicate or when the result of a projection changes.
- [`indexed()`](https://github.com/apple/swift-algorithms/blob/main/Guides/Indexed.md): Iterate over tuples of a collection's indices and elements.
- [`interspersed(with:)`](https://github.com/apple/swift-algorithms/blob/main/Guides/Intersperse.md): Place a value between every two elements of a sequence.
- [`trimming(while:)`](https://github.com/apple/swift-algorithms/blob/main/Guides/Trim.md): Returns a slice by trimming elements from a collection's start and end.
- [`windows(ofCount:)`](https://github.com/apple/swift-algorithms/blob/main/Guides/Windows.md): Breaks a collection into overlapping subsequences where elements are slices from the original collection.
- [`striding(by:)`](https://github.com/apple/swift-algorithms/blob/main/Guides/Stride.md): Returns every nth element of a collection.
- [`split(maxSplits:omittingEmptySubsequences:whereSeparator)`, `split(separator:maxSplits:omittingEmptySubsequences)`](https://github.com/apple/swift-algorithms/blob/main/Guides/LazySplit.md): Lazy versions of the Standard Library's eager operations that split sequences and collections into subsequences separated by the specified separator element.
- [`trimming(where:)`](https://github.com/apple/swift-algorithms/blob/main/Guides/Trim.md): Returns a slice by trimming elements from a collection's start and end.
## Adding Swift Algorithms as a Dependency
+2 -4
View File
@@ -19,7 +19,6 @@ public struct Chain2<Base1: Sequence, Base2: Sequence>
/// The second sequence in this chain.
public let base2: Base2
@usableFromInline
internal init(base1: Base1, base2: Base2) {
self.base1 = base1
self.base2 = base2
@@ -27,7 +26,7 @@ public struct Chain2<Base1: Sequence, Base2: Sequence>
}
extension Chain2: Sequence {
/// The iterator for a `Chain2` sequence.
/// The iterator for a `Chain` sequence.
public struct Iterator: IteratorProtocol {
@usableFromInline
internal var iterator1: Base1.Iterator
@@ -54,7 +53,7 @@ extension Chain2: Sequence {
}
extension Chain2: Collection where Base1: Collection, Base2: Collection {
/// A position in a `Chain2` collection.
/// A position in a `Chain` collection.
public struct Index: Comparable {
// The internal index representation, which can either be an index of the
// first collection or the second. The `endIndex` of the first collection
@@ -307,7 +306,6 @@ extension Chain2: Hashable where Base1: Hashable, Base2: Hashable {}
/// then over the elements of `s2`.
///
/// - Complexity: O(1)
@inlinable
public func chain<S1, S2>(_ s1: S1, _ s2: S2) -> Chain2<S1, S2> {
Chain2(base1: s1, base2: s2)
}
+83 -397
View File
@@ -9,99 +9,92 @@
//
//===----------------------------------------------------------------------===//
/// A collection wrapper that breaks a collection into chunks based on a
/// predicate or projection.
public struct LazyChunked<Base: Collection, Subject> {
public struct LazyChunked<Base: Collection> {
/// The collection that this instance provides a view onto.
public let base: Base
/// The projection function.
@usableFromInline
internal let projection: (Base.Element) -> Subject
/// The predicate.
@usableFromInline
internal let belongInSameGroup: (Subject, Subject) -> Bool
/// The upper bound of the first chunk.
@usableFromInline
internal var firstUpperBound: Base.Index
internal var belongInSameGroup: (Base.Element, Base.Element) -> Bool
@usableFromInline
internal init(
base: Base,
projection: @escaping (Base.Element) -> Subject,
belongInSameGroup: @escaping (Subject, Subject) -> Bool
) {
internal init(base: Base, belongInSameGroup: @escaping (Base.Element, Base.Element) -> Bool) {
self.base = base
self.projection = projection
self.belongInSameGroup = belongInSameGroup
self.firstUpperBound = base.startIndex
if !base.isEmpty {
firstUpperBound = endOfChunk(startingAt: base.startIndex)
}
}
}
extension LazyChunked: LazyCollectionProtocol {
/// A position in a chunked collection.
public struct Index: Comparable {
/// The range corresponding to the chunk at this position.
/// The lower bound of the chunk at this position.
@usableFromInline
internal var baseRange: Range<Base.Index>
internal var lowerBound: Base.Index
/// The upper bound of the chunk at this position.
///
/// `upperBound` is optional so that computing `startIndex` can be an O(1)
/// operation. When `upperBound` is `nil`, the actual upper bound is found
/// when subscripting or calling `index(after:)`.
@usableFromInline
internal var upperBound: Base.Index?
@usableFromInline
internal init(_ baseRange: Range<Base.Index>) {
self.baseRange = baseRange
internal init(lowerBound: Base.Index, upperBound: Base.Index? = nil) {
self.lowerBound = lowerBound
self.upperBound = upperBound
}
@inlinable
public static func == (lhs: Index, rhs: Index) -> Bool {
// Only use the lower bound to test for equality, since sometimes the
// `startIndex` will have an upper bound of `nil` and sometimes it won't,
// such as when retrieved by:
// `c.index(before: c.index(after: c.startIndex))`.
//
// Since each index represents the range of a disparate chunk, no two
// unique indices will have the same lower bound.
lhs.baseRange.lowerBound == rhs.baseRange.lowerBound
lhs.lowerBound == rhs.lowerBound
}
@inlinable
public static func < (lhs: Index, rhs: Index) -> Bool {
// Only use the lower bound to test for ordering, as above.
lhs.baseRange.lowerBound < rhs.baseRange.lowerBound
lhs.lowerBound < rhs.lowerBound
}
}
/// Returns the index in the base collection of the end of the chunk starting
/// at the given index.
/// Returns the index in the base collection for the first element that
/// doesn't match the current chunk.
@usableFromInline
internal func endOfChunk(startingAt start: Base.Index) -> Base.Index {
let subject = projection(base[start])
return base[base.index(after: start)...]
.endOfPrefix(while: { belongInSameGroup(subject, projection($0)) })
internal func endOfChunk(from i: Base.Index) -> Base.Index {
guard i != base.endIndex else { return base.endIndex }
return base[base.index(after: i)...]
.firstIndex(where: { !belongInSameGroup($0, base[i]) }) ?? base.endIndex
}
@inlinable
public var startIndex: Index {
Index(base.startIndex..<firstUpperBound)
Index(lowerBound: base.startIndex)
}
@inlinable
public var endIndex: Index {
Index(base.endIndex..<base.endIndex)
Index(lowerBound: base.endIndex, upperBound: base.endIndex)
}
@inlinable
public func index(after i: Index) -> Index {
precondition(i != endIndex, "Can't advance past endIndex")
let upperBound = i.baseRange.upperBound
guard upperBound != base.endIndex else { return endIndex }
let end = endOfChunk(startingAt: upperBound)
return Index(upperBound..<end)
let upperBound = i.upperBound ?? endOfChunk(from: i.lowerBound)
let end = endOfChunk(from: upperBound)
return Index(lowerBound: upperBound, upperBound: end)
}
@inlinable
public subscript(position: Index) -> Base.SubSequence {
precondition(position != endIndex, "Can't subscript using endIndex")
return base[position.baseRange]
let upperBound = position.upperBound
?? endOfChunk(from: position.lowerBound)
return base[position.lowerBound..<upperBound]
}
}
@@ -110,23 +103,32 @@ extension LazyChunked.Index: Hashable where Base.Index: Hashable {}
extension LazyChunked: BidirectionalCollection
where Base: BidirectionalCollection
{
/// Returns the index in the base collection of the start of the chunk ending
/// at the given index.
/// Returns the index in the base collection for the element that starts
/// the chunk ending at the given index.
@usableFromInline
internal func startOfChunk(endingAt end: Base.Index) -> Base.Index {
let indexBeforeEnd = base.index(before: end)
// Get the projected value of the last element in the range ending at `end`.
let subject = projection(base[indexBeforeEnd])
return base[..<indexBeforeEnd]
.startOfSuffix(while: { belongInSameGroup(projection($0), subject) })
let lastOfPreviousChunk = base[base.index(before: end)]
// Search backward from `end` for the first element whose projection isn't
// equal to `lastOfPreviousChunk`.
if let firstMismatch = base[..<end]
.lastIndex(where: { !belongInSameGroup($0, lastOfPreviousChunk) })
{
// If we found one, that's the last element of the _next_ previous chunk,
// and therefore one position _before_ the start of this chunk.
return base.index(after: firstMismatch)
} else {
// If we didn't find such an element, this chunk extends back to the start
// of the collection.
return base.startIndex
}
}
@inlinable
public func index(before i: Index) -> Index {
precondition(i != startIndex, "Can't advance before startIndex")
let start = startOfChunk(endingAt: i.baseRange.lowerBound)
return Index(start..<i.baseRange.lowerBound)
let start = startOfChunk(endingAt: i.lowerBound)
return Index(lowerBound: start, upperBound: i.lowerBound)
}
}
@@ -138,29 +140,29 @@ extension LazyCollectionProtocol {
/// Returns a lazy collection of subsequences of this collection, chunked by
/// the given predicate.
///
/// - Complexity: O(*n*), because the start index is pre-computed.
/// - Complexity: O(1). When iterating over the resulting collection,
/// accessing each successive chunk has a complexity of O(*m*), where *m*
/// is the length of the chunk.
@inlinable
public func chunked(
by belongInSameGroup: @escaping (Element, Element) -> Bool
) -> LazyChunked<Elements, Element> {
LazyChunked(
base: elements,
projection: { $0 },
belongInSameGroup: belongInSameGroup)
) -> LazyChunked<Elements> {
LazyChunked(base: elements, belongInSameGroup: belongInSameGroup)
}
/// Returns a lazy collection of subsequences of this collection, chunked by
/// grouping elements that project to the same value.
///
/// - Complexity: O(*n*), because the start index is pre-computed.
/// - Complexity: O(1). When iterating over the resulting collection,
/// accessing each successive chunk has a complexity of O(*m*), where *m*
/// is the length of the chunk.
@inlinable
public func chunked<Subject: Equatable>(
on projection: @escaping (Element) -> Subject
) -> LazyChunked<Elements, Subject> {
) -> LazyChunked<Elements> {
LazyChunked(
base: elements,
projection: projection,
belongInSameGroup: ==)
belongInSameGroup: { projection($0) == projection($1) })
}
}
@@ -170,28 +172,27 @@ extension LazyCollectionProtocol {
extension Collection {
/// Returns a collection of subsequences of this collection, chunked by
/// grouping elements that project to the same value according to the given
/// predicate.
/// the given predicate.
///
/// - Complexity: O(*n*), where *n* is the length of this collection.
@usableFromInline
internal func chunked<Subject>(
on projection: (Element) throws -> Subject,
by belongInSameGroup: (Subject, Subject) throws -> Bool
) rethrows -> [SubSequence] {
@inlinable
public func chunked(
by belongInSameGroup: (Element, Element) -> Bool
) -> [SubSequence] {
guard !isEmpty else { return [] }
var result: [SubSequence] = []
var start = startIndex
var subject = try projection(self[start])
for (index, element) in indexed().dropFirst() {
let nextSubject = try projection(element)
if try !belongInSameGroup(subject, nextSubject) {
result.append(self[start..<index])
start = index
subject = nextSubject
var current = startIndex
while true {
let next = index(after: current)
if next == endIndex { break }
if !belongInSameGroup(self[current], self[next]) {
result.append(self[start..<next])
start = next
}
current = next
}
if start != endIndex {
@@ -200,17 +201,6 @@ extension Collection {
return result
}
/// Returns a collection of subsequences of this collection, chunked by
/// the given predicate.
///
/// - Complexity: O(*n*), where *n* is the length of this collection.
@inlinable
public func chunked(
by belongInSameGroup: (Element, Element) throws -> Bool
) rethrows -> [SubSequence] {
try chunked(on: { $0 }, by: belongInSameGroup)
}
/// Returns a collection of subsequences of this collection, chunked by
/// grouping elements that project to the same value.
@@ -218,313 +208,9 @@ extension Collection {
/// - Complexity: O(*n*), where *n* is the length of this collection.
@inlinable
public func chunked<Subject: Equatable>(
on projection: (Element) throws -> Subject
) rethrows -> [SubSequence] {
try chunked(on: projection, by: ==)
on projection: (Element) -> Subject
) -> [SubSequence] {
chunked(by: { projection($0) == projection($1) })
}
}
//===----------------------------------------------------------------------===//
// chunks(ofCount:)
//===----------------------------------------------------------------------===//
/// A collection that presents the elements of its base collection
/// in `SubSequence` chunks of any given count.
///
/// A `ChunkedByCount` is a lazy view on the base Collection, but it does not implicitly confer
/// laziness on algorithms applied to its result. In other words, for ordinary collections `c`:
///
/// * `c.chunks(ofCount: 3)` does not create new storage
/// * `c.chunks(ofCount: 3).map(f)` maps eagerly and returns a new array
/// * `c.lazy.chunks(ofCount: 3).map(f)` maps lazily and returns a `LazyMapCollection`
public struct ChunkedByCount<Base: Collection> {
public typealias Element = Base.SubSequence
@usableFromInline
internal let base: Base
@usableFromInline
internal let chunkCount: Int
@usableFromInline
internal var startUpperBound: Base.Index
/// Creates a view instance that presents the elements of `base`
/// in `SubSequence` chunks of the given count.
///
/// - Complexity: O(*n*), because the start index is pre-computed.
@inlinable
internal init(_base: Base, _chunkCount: Int) {
self.base = _base
self.chunkCount = _chunkCount
// Compute the start index upfront in order to make
// start index a O(1) lookup.
self.startUpperBound = _base.index(
_base.startIndex, offsetBy: _chunkCount,
limitedBy: _base.endIndex
) ?? _base.endIndex
}
}
extension ChunkedByCount: Collection {
public struct Index {
@usableFromInline
internal let baseRange: Range<Base.Index>
@usableFromInline
internal init(_baseRange: Range<Base.Index>) {
self.baseRange = _baseRange
}
}
/// - Complexity: O(1)
@inlinable
public var startIndex: Index {
Index(_baseRange: base.startIndex..<startUpperBound)
}
@inlinable
public var endIndex: Index {
Index(_baseRange: base.endIndex..<base.endIndex)
}
/// - Complexity: O(1)
public subscript(i: Index) -> Element {
precondition(i < endIndex, "Index out of range")
return base[i.baseRange]
}
@inlinable
public func index(after i: Index) -> Index {
precondition(i < endIndex, "Advancing past end index")
let baseIdx = base.index(
i.baseRange.upperBound, offsetBy: chunkCount,
limitedBy: base.endIndex
) ?? base.endIndex
return Index(_baseRange: i.baseRange.upperBound..<baseIdx)
}
}
extension ChunkedByCount.Index: Comparable {
@inlinable
public static func == (lhs: ChunkedByCount.Index,
rhs: ChunkedByCount.Index) -> Bool {
lhs.baseRange.lowerBound == rhs.baseRange.lowerBound
}
@inlinable
public static func < (lhs: ChunkedByCount.Index,
rhs: ChunkedByCount.Index) -> Bool {
lhs.baseRange.lowerBound < rhs.baseRange.lowerBound
}
}
extension ChunkedByCount:
BidirectionalCollection, RandomAccessCollection
where Base: RandomAccessCollection {
@inlinable
public func index(before i: Index) -> Index {
precondition(i > startIndex, "Advancing past start index")
var offset = chunkCount
if i.baseRange.lowerBound == base.endIndex {
let remainder = base.count%chunkCount
if remainder != 0 {
offset = remainder
}
}
let baseIdx = base.index(
i.baseRange.lowerBound, offsetBy: -offset,
limitedBy: base.startIndex
) ?? base.startIndex
return Index(_baseRange: baseIdx..<i.baseRange.lowerBound)
}
}
extension ChunkedByCount {
@inlinable
public func distance(from start: Index, to end: Index) -> Int {
let distance =
base.distance(from: start.baseRange.lowerBound,
to: end.baseRange.lowerBound)
let (quotient, remainder) =
distance.quotientAndRemainder(dividingBy: chunkCount)
return quotient + remainder.signum()
}
@inlinable
public var count: Int {
let (quotient, remainder) =
base.count.quotientAndRemainder(dividingBy: chunkCount)
return quotient + remainder.signum()
}
@inlinable
public func index(
_ i: Index, offsetBy offset: Int, limitedBy limit: Index
) -> Index? {
guard offset != 0 else { return i }
guard limit != i else { return nil }
if offset > 0 {
return limit > i
? offsetForward(i, offsetBy: offset, limit: limit)
: offsetForward(i, offsetBy: offset)
} else {
return limit < i
? offsetBackward(i, offsetBy: offset, limit: limit)
: offsetBackward(i, offsetBy: offset)
}
}
@inlinable
public func index(_ i: Index, offsetBy distance: Int) -> Index {
guard distance != 0 else { return i }
let idx = distance > 0
? offsetForward(i, offsetBy: distance)
: offsetBackward(i, offsetBy: distance)
guard let index = idx else {
fatalError("Out of bounds")
}
return index
}
@usableFromInline
internal func offsetForward(
_ i: Index, offsetBy distance: Int, limit: Index? = nil
) -> Index? {
assert(distance > 0)
return makeOffsetIndex(
from: i, baseBound: base.endIndex,
distance: distance, baseDistance: distance * chunkCount,
limit: limit, by: >
)
}
// Convenience to compute offset backward base distance.
@inline(__always)
private func computeOffsetBackwardBaseDistance(
_ i: Index, _ distance: Int
) -> Int {
if i == endIndex {
let remainder = base.count%chunkCount
// We have to take it into account when calculating offsets.
if remainder != 0 {
// Distance "minus" one(at this point distance is negative)
// because we need to adjust for the last position that have
// a variadic(remainder) number of elements.
return ((distance + 1) * chunkCount) - remainder
}
}
return distance * chunkCount
}
@usableFromInline
internal func offsetBackward(
_ i: Index, offsetBy distance: Int, limit: Index? = nil
) -> Index? {
assert(distance < 0)
let baseDistance =
computeOffsetBackwardBaseDistance(i, distance)
return makeOffsetIndex(
from: i, baseBound: base.startIndex,
distance: distance, baseDistance: baseDistance,
limit: limit, by: <
)
}
// Helper to compute index(offsetBy:) index.
@inline(__always)
private func makeOffsetIndex(
from i: Index, baseBound: Base.Index, distance: Int, baseDistance: Int,
limit: Index?, by limitFn: (Base.Index, Base.Index) -> Bool
) -> Index? {
let baseIdx = base.index(
i.baseRange.lowerBound, offsetBy: baseDistance,
limitedBy: baseBound
)
if let limit = limit {
if baseIdx == nil {
// If we past the bounds while advancing forward and the
// limit is the `endIndex`, since the computation on base
// don't take into account the remainder, we have to make
// sure that passing the bound was because of the distance
// not just because of a remainder. Special casing is less
// expensive than always use count(which could be O(n) for
// non-random access collection base) to compute the base
// distance taking remainder into account.
if baseDistance > 0 && limit == endIndex {
if self.distance(from: i, to: limit) < distance {
return nil
}
} else {
return nil
}
}
// Checks for the limit.
let baseStartIdx = baseIdx ?? baseBound
if limitFn(baseStartIdx, limit.baseRange.lowerBound) {
return nil
}
}
let baseStartIdx = baseIdx ?? baseBound
let baseEndIdx = base.index(
baseStartIdx, offsetBy: chunkCount, limitedBy: base.endIndex
) ?? base.endIndex
return Index(_baseRange: baseStartIdx..<baseEndIdx)
}
}
extension Collection {
/// Returns a `ChunkedCollection<Self>` view presenting the elements
/// in chunks with count of the given count parameter.
///
/// - Parameter size: The size of the chunks. If the count parameter
/// is evenly divided by the count of the base `Collection` all the
/// chunks will have the count equals to size.
/// Otherwise, the last chunk will contain the remaining elements.
///
/// let c = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
/// print(c.chunks(ofCount: 5).map(Array.init))
/// // [[1, 2, 3, 4, 5], [6, 7, 8, 9, 10]]
///
/// print(c.chunks(ofCount: 3).map(Array.init))
/// // [[1, 2, 3], [4, 5, 6], [7, 8, 9], [10]]
///
/// - Complexity: O(*n*), because the start index is pre-computed.
@inlinable
public func chunks(ofCount count: Int) -> ChunkedByCount<Self> {
precondition(count > 0, "Cannot chunk with count <= 0!")
return ChunkedByCount(_base: self, _chunkCount: count)
}
}
// Conditional conformances.
extension ChunkedByCount: Equatable where Base: Equatable {}
// Since we have another stored property of type `Index` on the
// collection, synthesis of `Hashble` conformace would require
// a `Base.Index: Hashable` constraint, so we implement the hasher
// only in terms of `base`. Since the computed index is based on it,
// it should not make a difference here.
extension ChunkedByCount: Hashable where Base: Hashable {
@inlinable
public func hash(into hasher: inout Hasher) {
hasher.combine(base)
}
}
extension ChunkedByCount.Index: Hashable where Base.Index: Hashable {}
// Lazy conditional conformance.
extension ChunkedByCount: LazySequenceProtocol
where Base: LazySequenceProtocol {}
extension ChunkedByCount: LazyCollectionProtocol
where Base: LazyCollectionProtocol {}
+25 -151
View File
@@ -2,64 +2,28 @@
//
// This source file is part of the Swift Algorithms open source project
//
// Copyright (c) 2020-2021 Apple Inc. and the Swift project authors
// Copyright (c) 2020 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
//
//===----------------------------------------------------------------------===//
/// A collection wrapper that generates combinations of a base collection.
public struct Combinations<Base: Collection> {
/// The collection to iterate over for combinations.
public let base: Base
@usableFromInline
internal let baseCount: Int
internal var k: Int
/// The range of accepted sizes of combinations.
/// - Note: This may be `nil` if the attempted range entirely exceeds the
/// upper bounds of the size of the `base` collection.
@usableFromInline
internal let kRange: Range<Int>?
/// Initializes a `Combinations` for all combinations of `base` of size `k`.
/// - Parameters:
/// - base: The collection to iterate over for combinations.
/// - k: The expected size of each combination.
@usableFromInline
internal init(_ base: Base, k: Int) {
self.init(base, kRange: k...k)
}
/// Initializes a `Combinations` for all combinations of `base` of sizes
/// within a given range.
/// - Parameters:
/// - base: The collection to iterate over for combinations.
/// - kRange: The range of accepted sizes of combinations.
@usableFromInline
internal init<R: RangeExpression>(
_ base: Base, kRange: R
) where R.Bound == Int {
let range = kRange.relative(to: 0 ..< .max)
self.base = base
let baseCount = base.count
self.baseCount = baseCount
let upperBound = baseCount + 1
self.kRange = range.lowerBound < upperBound
? range.clamped(to: 0 ..< upperBound)
: nil
self.k = base.count < k ? -1 : k
}
/// The total number of combinations.
@inlinable
public var count: Int {
guard let k = self.kRange else { return 0 }
let n = baseCount
if k == 0 ..< (n + 1) {
return 1 << n
}
func binomial(n: Int, k: Int) -> Int {
switch k {
case n, 0: return 1
@@ -69,38 +33,29 @@ public struct Combinations<Base: Collection> {
}
}
return k.map {
binomial(n: n, k: $0)
}.reduce(0, +)
return k >= 0
? binomial(n: base.count, k: k)
: 0
}
}
extension Combinations: Sequence {
/// The iterator for a `Combinations` instance.
public struct Iterator: IteratorProtocol {
@usableFromInline
internal let base: Base
/// The current range of accepted sizes of combinations.
/// - Note: The range is contracted until empty while iterating over
/// combinations of different sizes. When the range is empty, iteration is
/// finished.
@usableFromInline
internal var kRange: Range<Int>
/// Whether or not iteration is finished (`kRange` is empty)
@usableFromInline
internal var isFinished: Bool {
return kRange.isEmpty
}
@usableFromInline
internal var indexes: [Base.Index]
@usableFromInline
internal var finished: Bool
internal init(_ combinations: Combinations) {
self.base = combinations.base
self.kRange = combinations.kRange ?? 0..<0
self.indexes = Array(combinations.base.indices.prefix(kRange.lowerBound))
self.finished = combinations.k < 0
self.indexes = combinations.k < 0
? []
: Array(combinations.base.indices.prefix(combinations.k))
}
/// Advances the current indices to the next set of combinations. If
@@ -123,35 +78,24 @@ extension Combinations: Sequence {
/// // so the iteration is finished.
@usableFromInline
internal mutating func advance() {
/// Advances `kRange` by incrementing its `lowerBound` until the range is
/// empty, when iteration is finished.
func advanceKRange() {
if kRange.lowerBound < kRange.upperBound {
let advancedLowerBound = kRange.lowerBound + 1
kRange = advancedLowerBound ..< kRange.upperBound
indexes.removeAll(keepingCapacity: true)
indexes.append(contentsOf: base.indices.prefix(kRange.lowerBound))
}
}
guard !indexes.isEmpty else {
// Initial state for combinations of 0 elements is an empty array with
// `finished == false`. Even though no indexes are involved, advancing
// from that state means we are finished with iterating.
advanceKRange()
finished = true
return
}
let i = indexes.count - 1
base.formIndex(after: &indexes[i])
if indexes[i] != base.endIndex { return }
var j = i
while indexes[i] == base.endIndex {
j -= 1
guard j >= 0 else {
// Finished iterating over combinations of this size.
advanceKRange()
// Finished iterating over combinations
finished = true
return
}
@@ -167,7 +111,7 @@ extension Combinations: Sequence {
@inlinable
public mutating func next() -> [Base.Element]? {
guard !isFinished else { return nil }
if finished { return nil }
defer { advance() }
return indexes.map { i in base[i] }
}
@@ -183,86 +127,18 @@ extension Combinations: Equatable where Base: Equatable {}
extension Combinations: Hashable where Base: Hashable {}
//===----------------------------------------------------------------------===//
// combinations(ofCount:)
// combinations(count:)
//===----------------------------------------------------------------------===//
extension Collection {
/// Returns a collection of combinations of this collection's elements, with
/// each combination having the specified number of elements.
///
/// This example prints the different combinations of 1 and 2 from an array of
/// four colors:
///
/// let colors = ["fuchsia", "cyan", "mauve", "magenta"]
/// for combo in colors.combinations(ofCount: 1...2) {
/// print(combo.joined(separator: ", "))
/// }
/// // fuchsia
/// // cyan
/// // mauve
/// // magenta
/// // fuchsia, cyan
/// // fuchsia, mauve
/// // fuchsia, magenta
/// // cyan, mauve
/// // cyan, magenta
/// // mauve, magenta
///
/// The returned collection presents combinations in a consistent order, where
/// the indices in each combination are in ascending lexicographical order.
/// That is, in the example above, the combinations in order are the elements
/// at `[0]`, `[1]`, `[2]`, `[3]`, `[0, 1]`, `[0, 2]`, `[0, 3]`, `[1, 2]`,
/// `[1, 3]`, and finally `[2, 3]`.
///
/// This example prints _all_ the combinations (including an empty array and
/// the original collection) from an array of numbers:
///
/// let numbers = [10, 20, 30, 40]
/// for combo in numbers.combinations(ofCount: 0...) {
/// print(combo)
/// }
/// // []
/// // [10]
/// // [20]
/// // [30]
/// // [40]
/// // [10, 20]
/// // [10, 30]
/// // [10, 40]
/// // [20, 30]
/// // [20, 40]
/// // [30, 40]
/// // [10, 20, 30]
/// // [10, 20, 40]
/// // [10, 30, 40]
/// // [20, 30, 40]
/// // [10, 20, 30, 40]
///
/// If `kRange` is `0...0`, the resulting sequence has exactly one element, an
/// empty array. The given range is limited to `0...base.count`. If the
/// limited range is empty, the resulting sequence has no elements.
///
/// - Parameter kRange: The range of numbers of elements to include in each
/// combination.
///
/// - Complexity: O(1) for random-access base collections. O(*n*) where *n*
/// is the number of elements in the base collection, since `Combinations`
/// accesses the `count` of the base collection.
@inlinable
public func combinations<R: RangeExpression>(
ofCount kRange: R
) -> Combinations<Self> where R.Bound == Int {
return Combinations(self, kRange: kRange)
}
/// Returns a collection of combinations of this collection's elements, with
/// each combination having the specified number of elements.
/// each combination having the specificed number of elements.
///
/// This example prints the different combinations of three from an array of
/// four colors:
///
/// let colors = ["fuchsia", "cyan", "mauve", "magenta"]
/// for combo in colors.combinations(ofCount: 3) {
/// for combo in colors.combinations(ofCount k: 3) {
/// print(combo.joined(separator: ", "))
/// }
/// // fuchsia, cyan, mauve
@@ -281,12 +157,10 @@ extension Collection {
///
/// - Parameter k: The number of elements to include in each combination.
///
/// - Complexity: O(1) for random-access base collections. O(*n*) where *n*
/// is the number of elements in the base collection, since `Combinations`
/// accesses the `count` of the base collection.
/// - Complexity: O(1)
@inlinable
public func combinations(ofCount k: Int) -> Combinations<Self> {
precondition(k >= 0, "Can't have combinations with a negative number of elements.")
assert(k >= 0, "Can't have combinations with a negative number of elements.")
return Combinations(self, k: k)
}
}
-8
View File
@@ -13,11 +13,6 @@
public struct Cycle<Base: Collection> {
/// The collection to repeat.
public let base: Base
@usableFromInline
internal init(base: Base) {
self.base = base
}
}
extension Cycle: Sequence {
@@ -48,7 +43,6 @@ extension Cycle: Sequence {
}
}
@inlinable
public func makeIterator() -> Iterator {
Iterator(base: base)
}
@@ -86,7 +80,6 @@ extension Collection {
/// forever.
///
/// - Complexity: O(1)
@inlinable
public func cycled() -> Cycle<Self> {
Cycle(base: self)
}
@@ -108,7 +101,6 @@ extension Collection {
/// times.
///
/// - Complexity: O(1)
@inlinable
public func cycled(times: Int) -> FlattenSequence<Repeated<Self>> {
repeatElement(self, count: times).joined()
}
+291
View File
@@ -0,0 +1,291 @@
//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift Algorithms open source project
//
// Copyright (c) 2020 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
//
//===----------------------------------------------------------------------===//
public struct SubSequenceFinder<Base: Collection, Other: Collection>
where Base.Element == Other.Element, Base.Element: Equatable
{
internal var base: Base
internal var other: Other
internal var firstRange: Range<Base.Index>?
internal var areEquivalent: (Base.Element, Base.Element) -> Bool
internal init(
base: Base,
other: Other,
by areEquivalent: @escaping (Base.Element, Base.Element) -> Bool)
{
self.base = base
self.other = other
self.areEquivalent = areEquivalent
self.firstRange = base.firstRange(of: other, by: areEquivalent)
}
}
extension SubSequenceFinder: Collection {
public struct Index: Comparable {
internal enum Representation: Comparable {
case match(Range<Base.Index>)
case end
public static func < (lhs: Representation, rhs: Representation) -> Bool {
switch (lhs, rhs) {
case (.match, .end):
return true
case (.end, _):
return false
case (.match(let lhs), .match(let rhs)):
return lhs.lowerBound < rhs.lowerBound
}
}
}
internal var base: Representation
internal static var end: Index {
Index(base: .end)
}
private init(base: Representation) {
self.base = base
}
internal init(_ range: Range<Base.Index>) {
self.base = .match(range)
}
public static func < (lhs: Index, rhs: Index) -> Bool {
lhs.base < rhs.base
}
}
public var startIndex: Index {
firstRange.map { Index($0) } ?? .end
}
public var endIndex: Index {
.end
}
public func index(after i: Index) -> Index {
guard case .match(let range) = i.base else {
preconditionFailure("Can't advance past endIndex")
}
let startingPoint = base.index(after: range.lowerBound)
return base[startingPoint...]
.firstRange(of: other)
.map { Index($0) } ?? .end
}
public subscript(position: Index) -> Range<Base.Index> {
guard case .match(let range) = position.base else {
preconditionFailure("Can't subscript with endIndex")
}
return range
}
}
extension SubSequenceFinder: BidirectionalCollection
where Base: BidirectionalCollection, Other: BidirectionalCollection
{
public func index(before i: Index) -> Index {
let endingPoint: Base.Index
switch i.base {
case .match(let range):
precondition(range != firstRange, "Can't move before startIndex")
endingPoint = base.index(before: range.upperBound)
case .end:
endingPoint = base.endIndex
}
return Index(base[..<endingPoint].lastRange(of: other)!)
}
}
// MARK: allRanges(of:by:) / allRanges(of:)
extension Collection {
public func allRanges<Other: Collection>(
of other: Other,
by areEquivalent: @escaping (Element, Element) -> Bool
)
-> SubSequenceFinder<Self, Other>
{
SubSequenceFinder(base: self, other: other, by: areEquivalent)
}
}
extension Collection where Element: Equatable {
public func allRanges<Other: Collection>(of other: Other) -> SubSequenceFinder<Self, Other>
where Element == Other.Element
{
allRanges(of: other, by: ==)
}
}
// MARK: - firstRange(of:by:) / firstRange(of:)
extension Collection {
public func firstRange<Other: Collection>(
of other: Other,
by areEquivalent: (Element, Element) throws -> Bool
) rethrows -> Range<Index>?
where Other.Element == Element
{
var searchStart = startIndex
guard let needleFirst = other.first else { return nil }
while let matchStart = try self[searchStart...]
.firstIndex(where: { try areEquivalent($0, needleFirst) })
{
var selfPos = index(after: matchStart)
var otherPos = other.index(after: other.startIndex)
while true {
if otherPos == other.endIndex {
return matchStart..<selfPos
}
if selfPos == self.endIndex {
return nil
}
if try !areEquivalent(self[selfPos], other[otherPos]) {
break
}
self.formIndex(after: &selfPos)
other.formIndex(after: &otherPos)
}
searchStart = self.index(after: matchStart)
}
return nil
}
}
extension Collection where Element: Equatable {
public func firstRange<Other: Collection>(of other: Other) -> Range<Index>?
where Element == Other.Element
{
firstRange(of: other, by: ==)
}
}
// MARK: - lastRange(of:by:) / lastRange(of:)
extension BidirectionalCollection where Element: Equatable {
public func lastRange<Other: BidirectionalCollection>(of other: Other) -> Range<Index>?
where Other.Element == Element
{
var searchEnd = endIndex
guard let needleLast = other.last else { return nil }
let otherLastIndex = other.index(before: other.endIndex)
while let matchEnd = self[..<searchEnd].lastIndex(of: needleLast) {
var selfPos = matchEnd
var otherPos = otherLastIndex
while true {
if otherPos == other.startIndex {
return selfPos..<index(after: matchEnd)
}
if selfPos == self.startIndex {
return nil
}
self.formIndex(before: &selfPos)
other.formIndex(before: &otherPos)
if self[selfPos] != other[otherPos] {
break
}
}
searchEnd = matchEnd
}
return nil
}
}
public struct SubSequenceFinderFromEnd<Base: BidirectionalCollection, Other: BidirectionalCollection>
where Base.Element == Other.Element, Base.Element: Equatable
{
internal var base: Base
internal var other: Other
internal var lastRange: Range<Base.Index>?
internal init(base: Base, other: Other, allowingOverlaps: Bool) {
self.base = base
self.other = other
self.lastRange = base.lastRange(of: other)
}
}
extension SubSequenceFinderFromEnd: Collection {
public struct Index: Comparable {
internal enum Representation: Comparable {
case match(Range<Base.Index>)
case end
public static func < (lhs: Representation, rhs: Representation) -> Bool {
switch (lhs, rhs) {
case (.match, .end):
return true
case (.end, _):
return false
case (.match(let lhs), .match(let rhs)):
return lhs.lowerBound > rhs.lowerBound
}
}
}
internal var base: Representation
internal static var end: Index {
Index(base: .end)
}
private init(base: Representation) {
self.base = base
}
internal init(_ range: Range<Base.Index>) {
self.base = .match(range)
}
public static func < (lhs: Index, rhs: Index) -> Bool {
lhs.base < rhs.base
}
}
public var startIndex: Index {
lastRange.map { Index($0) } ?? .end
}
public var endIndex: Index {
.end
}
public func index(after i: Index) -> Index {
guard case .match(let range) = i.base else {
preconditionFailure("Can't advance past endIndex")
}
return base[..<range.lowerBound]
.lastRange(of: other)
.map { Index($0) } ?? .end
}
public subscript(position: Index) -> Range<Base.Index> {
guard case .match(let range) = position.base else {
preconditionFailure("Can't subscript with endIndex")
}
return range
}
}
-28
View File
@@ -1,28 +0,0 @@
//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift Algorithms open source project
//
// Copyright (c) 2020 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
//
//===----------------------------------------------------------------------===//
//===----------------------------------------------------------------------===//
// firstNonNil(_:)
//===----------------------------------------------------------------------===//
public extension Sequence {
/// Returns the first element in `self` that `transform` maps to a `.some`.
func firstNonNil<Result>(
_ transform: (Element) throws -> Result?
) rethrows -> Result? {
for value in self {
if let value = try transform(value) {
return value
}
}
return nil
}
}
-1
View File
@@ -70,7 +70,6 @@ extension Indexed: BidirectionalCollection where Base: BidirectionalCollection {
extension Indexed: RandomAccessCollection where Base: RandomAccessCollection {}
extension Indexed: LazySequenceProtocol where Base: LazySequenceProtocol {}
extension Indexed: LazyCollectionProtocol where Base: LazyCollectionProtocol {}
extension Indexed: Equatable where Base: Equatable {}
extension Indexed: Hashable where Base: Hashable {}
-231
View File
@@ -1,231 +0,0 @@
//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift Algorithms open source project
//
// Copyright (c) 2020 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
//
//===----------------------------------------------------------------------===//
/// A sequence that presents the elements of a base sequence of elements
/// with a separator between each of those elements.
public struct Intersperse<Base: Sequence> {
@usableFromInline
internal let base: Base
@usableFromInline
internal let separator: Base.Element
@usableFromInline
internal init(base: Base, separator: Base.Element) {
self.base = base
self.separator = separator
}
}
extension Intersperse: Sequence {
/// The iterator for an `Intersperse` sequence.
public struct Iterator: IteratorProtocol {
@usableFromInline
internal var iterator: Base.Iterator
@usableFromInline
internal let separator: Base.Element
@usableFromInline
internal var state = State.start
@usableFromInline
internal init(iterator: Base.Iterator, separator: Base.Element) {
self.iterator = iterator
self.separator = separator
}
@usableFromInline
enum State {
case start
case element(Base.Element)
case separator
}
@inlinable
public mutating func next() -> Base.Element? {
// After the start, the state flips between element and separator. Before
// returning a separator, a check is made for the next element as a
// separator is only returned between two elements. The next element is
// stored to allow it to be returned in the next iteration.
switch state {
case .start:
state = .separator
return iterator.next()
case .separator:
guard let next = iterator.next() else { return nil }
state = .element(next)
return separator
case .element(let element):
state = .separator
return element
}
}
}
@inlinable
public func makeIterator() -> Intersperse<Base>.Iterator {
Iterator(iterator: base.makeIterator(), separator: separator)
}
}
extension Intersperse: Collection where Base: Collection {
/// A position in an `Intersperse` collection.
public struct Index: Comparable {
@usableFromInline
enum Representation: Equatable {
case element(Base.Index)
case separator(next: Base.Index)
}
@usableFromInline
internal let representation: Representation
@inlinable
public static func < (lhs: Index, rhs: Index) -> Bool {
switch (lhs.representation, rhs.representation) {
case let (.element(li), .element(ri)),
let (.separator(next: li), .separator(next: ri)),
let (.element(li), .separator(next: ri)):
return li < ri
case let (.separator(next: li), .element(ri)):
return li <= ri
}
}
@usableFromInline
static func element(_ index: Base.Index) -> Self {
Self(representation: .element(index))
}
@usableFromInline
static func separator(next: Base.Index) -> Self {
Self(representation: .separator(next: next))
}
}
@inlinable
public var startIndex: Index {
base.startIndex == base.endIndex ? endIndex : .element(base.startIndex)
}
@inlinable
public var endIndex: Index {
.separator(next: base.endIndex)
}
@inlinable
public func index(after i: Index) -> Index {
precondition(i != endIndex, "Can't advance past endIndex")
switch i.representation {
case let .element(index):
return .separator(next: base.index(after: index))
case let .separator(next):
return .element(next)
}
}
@inlinable
public subscript(position: Index) -> Element {
switch position.representation {
case .element(let index): return base[index]
case .separator: return separator
}
}
@inlinable
public func index(_ i: Index, offsetBy distance: Int) -> Index {
switch (i.representation, distance.isMultiple(of: 2)) {
case (let .element(index), true):
return .element(base.index(index, offsetBy: distance / 2))
case (let .element(index), false):
return .separator(next: base.index(index, offsetBy: (distance + 1) / 2))
case (let .separator(next: index), true):
return .separator(next: base.index(index, offsetBy: distance / 2))
case (let .separator(next: index), false):
return .element(base.index(index, offsetBy: (distance - 1) / 2))
}
}
// TODO: Implement index(_:offsetBy:limitedBy:)
@inlinable
public func distance(from start: Index, to end: Index) -> Int {
switch (start.representation, end.representation) {
case let (.element(element), .separator(next: separator)):
return 2 * base.distance(from: element, to: separator) - 1
case let (.separator(next: separator), .element(element)):
return 2 * base.distance(from: separator, to: element) + 1
case let (.element(start), .element(end)),
let (.separator(start), .separator(end)):
return 2 * base.distance(from: start, to: end)
}
}
}
extension Intersperse: BidirectionalCollection
where Base: BidirectionalCollection
{
@inlinable
public func index(before i: Index) -> Index {
precondition(i != startIndex, "Can't move before startIndex")
switch i.representation {
case let .element(index):
return .separator(next: index)
case let .separator(next):
return .element(base.index(before: next))
}
}
}
extension Intersperse: RandomAccessCollection
where Base: RandomAccessCollection {}
extension Intersperse: LazySequenceProtocol
where Base: LazySequenceProtocol {}
extension Intersperse: LazyCollectionProtocol
where Base: LazyCollectionProtocol {}
extension Sequence {
/// Returns a sequence containing elements of this sequence with the given
/// separator inserted in between each element.
///
/// Any value of the sequence's element type can be used as the separator.
///
/// ```
/// for value in [1,2,3].interspersed(with: 0) {
/// print(value)
/// }
/// // 1
/// // 0
/// // 2
/// // 0
/// // 3
/// ```
///
/// The following shows a String being interspersed with a Character:
/// ```
/// let result = "ABCDE".interspersed(with: "-")
/// print(String(result))
/// // "A-B-C-D-E"
/// ```
///
/// - Parameter separator: Value to insert in between each of this sequence’s
/// elements.
/// - Returns: The interspersed sequence of elements.
///
/// - Complexity: O(1)
@inlinable
public func interspersed(with separator: Element) -> Intersperse<Self> {
Intersperse(base: self, separator: separator)
}
}
-750
View File
@@ -1,750 +0,0 @@
//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift Algorithms open source project
//
// Copyright (c) 2021 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
//
//===----------------------------------------------------------------------===//
//===----------------------------------------------------------------------===//
// LazySplitSequence
//===----------------------------------------------------------------------===//
/// A sequence that lazily splits a base sequence into subsequences separated by
/// elements that satisfy the given `whereSeparator` predicate.
///
/// - Note: This type is the result of
///
/// x.split(maxSplits:omittingEmptySubsequences:whereSeparator)
/// x.split(separator:maxSplits:omittingEmptySubsequences)
///
/// where `x` conforms to `LazySequenceProtocol`.
public struct LazySplitSequence<Base: Sequence> {
@usableFromInline
internal let base: Base
@usableFromInline
internal let isSeparator: (Base.Element) -> Bool
@usableFromInline
internal let maxSplits: Int
@usableFromInline
internal let omittingEmptySubsequences: Bool
@usableFromInline
internal init(
base: Base,
isSeparator: @escaping (Base.Element) -> Bool,
maxSplits: Int,
omittingEmptySubsequences: Bool
) {
self.base = base
self.isSeparator = isSeparator
self.maxSplits = maxSplits
self.omittingEmptySubsequences = omittingEmptySubsequences
}
}
extension LazySplitSequence {
public struct Iterator {
public typealias Element = [Base.Element]
@usableFromInline
internal var base: Base.Iterator
@usableFromInline
internal let isSeparator: (Base.Element) -> Bool
@usableFromInline
internal let maxSplits: Int
@usableFromInline
internal let omittingEmptySubsequences: Bool
/// The number of splits performed.
@usableFromInline
internal var splitCount = 0
/// The number of subsequences returned.
@usableFromInline
internal var sequenceLength = 0
@usableFromInline
internal init(
base: Base.Iterator,
whereSeparator: @escaping (Base.Element) -> Bool,
maxSplits: Int,
omittingEmptySubsequences: Bool
) {
self.base = base
self.isSeparator = whereSeparator
self.maxSplits = maxSplits
self.omittingEmptySubsequences = omittingEmptySubsequences
}
}
}
extension LazySplitSequence.Iterator: IteratorProtocol {
@inlinable
public mutating func next() -> Element? {
var currentElement = base.next()
var subsequence: Element = []
// Add the next elements of the base sequence to this subsequence, until we
// reach a separator, unless we've already split the maximum number of
// times. In all cases, stop at the end of the base sequence.
while currentElement != nil {
if splitCount < maxSplits && isSeparator(currentElement!) {
if omittingEmptySubsequences && subsequence.isEmpty {
// Keep going if we don't want to return an empty subsequence.
currentElement = base.next()
continue
} else {
splitCount += 1
break
}
} else {
subsequence.append(currentElement!)
currentElement = base.next()
}
}
// We're done iterating when we've reached the end of the base sequence,
// and we've either returned the maximum number of subsequences (one more
// than the number of separators), or the only subsequence left to return is
// empty and we're omitting those.
if currentElement == nil
&& (sequenceLength == splitCount + 1
|| omittingEmptySubsequences && subsequence.isEmpty)
{
return nil
} else {
sequenceLength += 1
return subsequence
}
}
}
extension LazySplitSequence: LazySequenceProtocol {
@inlinable
public func makeIterator() -> Iterator {
return Iterator(
base: base.makeIterator(),
whereSeparator: self.isSeparator,
maxSplits: self.maxSplits,
omittingEmptySubsequences: self.omittingEmptySubsequences
)
}
}
extension LazySequenceProtocol {
/// Lazily returns the longest possible subsequences of the sequence, in
/// order, that don't contain elements satisfying the given predicate.
///
/// The resulting lazy sequence consists of at most `maxSplits + 1`
/// subsequences. Elements that are used to split the sequence are not
/// returned as part of any subsequence (except possibly the last one, in the
/// case where `maxSplits` is less than the number of separators in the
/// sequence).
///
/// The following examples show the effects of the `maxSplits` and
/// `omittingEmptySubsequences` parameters when lazily splitting a sequence of
/// integers using a closure that matches numbers evenly divisible by 3 or 5.
/// The first use of `split` returns each subsequence that was originally
/// separated by one or more such numbers.
///
/// let numbers = stride(from: 1, through: 16, by: 1)
/// for subsequence in numbers.lazy.split(
/// whereSeparator: { $0 % 3 == 0 || $0 % 5 == 0 }
/// ) {
/// print(subsequence)
/// }
/// /* Prints:
/// [1, 2]
/// [4]
/// [7, 8]
/// [11]
/// [13, 14]
/// [16]
/// */
///
/// The second example passes `1` for the `maxSplits` parameter, so the
/// original sequence is split just once, into two subsequences.
///
/// for subsequence in numbers.lazy.split(
/// maxSplits: 1,
/// whereSeparator: { $0 % 3 == 0 || $0 % 5 == 0 }
/// ) {
/// print(subsequence)
/// }
/// /* Prints:
/// [1, 2]
/// [4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
/// */
///
/// The final example passes `false` for the `omittingEmptySubsequences`
/// parameter, so the sequence of returned subsequences contains empty
/// subsequences where numbers evenly divisible by 3 or 5 were repeated.
///
/// for subsequence in numbers.lazy.split(
/// omittingEmptySubsequences: false,
/// whereSeparator: { $0 % 3 == 0 || $0 % 5 == 0 }
/// ) {
/// print(subsequence)
/// }
/// /* Prints:
/// [1, 2]
/// [4]
/// []
/// [7, 8]
/// []
/// [11]
/// [13, 14]
/// [16]
/// */
///
/// - Parameters:
/// - maxSplits: The maximum number of times to split the sequence, or
/// one less than the number of subsequences to return. If
/// `maxSplits + 1` subsequences are returned, the last one is a suffix
/// of the original sequence containing the remaining elements.
/// `maxSplits` must be greater than or equal to zero. The default value
/// is `Int.max`.
/// - omittingEmptySubsequences: If `false`, an empty subsequence is
/// returned in the result for each pair of consecutive elements
/// satisfying the `isSeparator` predicate and for each element at the
/// start or end of the sequence satisfying the `isSeparator`
/// predicate. The default value is `true`.
/// - whereSeparator: A closure that takes an element as an argument and
/// returns a Boolean value indicating whether the sequence should be
/// split at that element.
/// - Returns: A lazy sequence of subsequences, split from this sequence's
/// elements.
///
/// - Complexity: O(*n*), where *n* is the length of the sequence.
@inlinable
public func split(
maxSplits: Int = Int.max,
omittingEmptySubsequences: Bool = true,
whereSeparator isSeparator: @escaping (Element) -> Bool
) -> LazySplitSequence<Elements> {
precondition(maxSplits >= 0, "Must take zero or more splits")
return LazySplitSequence(
base: elements,
isSeparator: isSeparator,
maxSplits: maxSplits,
omittingEmptySubsequences: omittingEmptySubsequences
)
}
}
extension LazySequenceProtocol where Element: Equatable {
/// Lazily returns the longest possible subsequences of the sequence, in
/// order, around elements equal to the given element.
///
/// The resulting lazy sequence consists of at most `maxSplits + 1`
/// subsequences. Elements that are used to split the sequence are not
/// returned as part of any subsequence (except possibly the last one, in the
/// case where `maxSplits` is less than the number of separators in the
/// sequence).
///
/// The following examples show the effects of the `maxSplits` and
/// `omittingEmptySubsequences` parameters when splitting a sequence of
/// integers at each zero (`0`). The first use of `split` returns each
/// subsequence that was originally separated by one or more zeros.
///
/// let numbers = AnySequence([1, 2, 0, 3, 4, 0, 0, 5])
/// for subsequence in numbers.lazy.split(separator: 0) {
/// print(subsequence)
/// }
/// /* Prints:
/// [1, 2]
/// [3, 4]
/// [5]
/// */
///
/// The second example passes `1` for the `maxSplits` parameter, so the
/// original sequence is split just once, into two subsequences.
///
/// for subsequence in numbers.lazy.split(
/// separator: 0,
/// maxSplits: 1
/// ) {
/// print(subsequence)
/// }
/// /* Prints:
/// [1, 2]
/// [3, 4, 0, 0, 5]
/// */
///
/// The final example passes `false` for the `omittingEmptySubsequences`
/// parameter, so the sequence of returned subsequences contains empty
/// subsequences where zeros were repeated.
///
/// for subsequence in numbers.lazy.split(
/// separator: 0,
/// omittingEmptySubsequences: false
/// ) {
/// print(subsequence)
/// }
/// /* Prints:
/// [1, 2]
/// [3, 4]
/// []
/// [5]
/// */
///
/// - Parameters:
/// - separator: The element that should be split upon.
/// - maxSplits: The maximum number of times to split the sequence, or
/// one less than the number of subsequences to return. If
/// `maxSplits + 1` subsequences are returned, the last one is a suffix
/// of the original sequence containing the remaining elements.
/// `maxSplits` must be greater than or equal to zero. The default value
/// is `Int.max`.
/// - omittingEmptySubsequences: If `false`, an empty subsequence is
/// returned in the result for each consecutive pair of `separator`
/// elements in the sequence and for each instance of `separator` at
/// the start or end of the sequence. If `true`, only nonempty
/// subsequences are returned. The default value is `true`.
/// - Returns: A lazy sequence of subsequences, split from this sequence's
/// elements.
///
/// - Complexity: O(*n*), where *n* is the length of the sequence.
@inlinable
public func split(
separator: Element,
maxSplits: Int = Int.max,
omittingEmptySubsequences: Bool = true
) -> LazySplitSequence<Elements> {
precondition(maxSplits >= 0, "Must take zero or more splits")
return LazySplitSequence(
base: elements,
isSeparator: { $0 == separator },
maxSplits: maxSplits,
omittingEmptySubsequences: omittingEmptySubsequences
)
}
}
//===----------------------------------------------------------------------===//
// LazySplitCollection
//===----------------------------------------------------------------------===//
/// A collection that lazily splits a base collection into subsequences
/// separated by elements that satisfy the given `whereSeparator` predicate.
///
/// - Note: This type is the result of
///
/// x.split(maxSplits:omittingEmptySubsequences:whereSeparator)
/// x.split(separator:maxSplits:omittingEmptySubsequences)
///
/// where `x` conforms to `LazyCollectionProtocol`.
public struct LazySplitCollection<Base: Collection> {
@usableFromInline
internal let base: Base
@usableFromInline
internal let isSeparator: (Base.Element) -> Bool
@usableFromInline
internal let maxSplits: Int
@usableFromInline
internal let omittingEmptySubsequences: Bool
@usableFromInline
internal var _startIndex: Index
@usableFromInline
internal init(
base: Base,
isSeparator: @escaping (Base.Element) -> Bool,
maxSplits: Int,
omittingEmptySubsequences: Bool
) {
self.base = base
self.isSeparator = isSeparator
self.maxSplits = maxSplits
self.omittingEmptySubsequences = omittingEmptySubsequences
// We precalculate `startIndex`. There are three possibilities:
// 1. `base` is empty and we're _not_ omitting empty subsequences, in which
// case the following index describes the sole element of this collection;
self._startIndex = Index(
baseRange: base.startIndex..<base.startIndex,
sequenceLength: 1,
splitCount: 0
)
if base.isEmpty {
if omittingEmptySubsequences {
// 2. `base` is empty and we _are_ omitting empty subsequences, so this
// collection has no elements;
_startIndex = endIndex
}
} else {
// 3. `base` isn't empty, so we must iterate it to determine the start
// index.
_startIndex = indexForSubsequence(
atOrAfter: base.startIndex,
sequenceLength: 0,
splitCount: 0
)
}
}
}
extension LazySplitCollection: LazyCollectionProtocol {
/// Position of a subsequence in a split collection.
public struct Index: Comparable {
/// The range corresponding to the subsequence at this position.
@usableFromInline
internal let baseRange: Range<Base.Index>
/// The number of subsequences up to and including this position in the
/// collection.
@usableFromInline
internal let sequenceLength: Int
/// The number splits performed up to and including this position in the
/// collection.
@usableFromInline
internal let splitCount: Int
@usableFromInline
internal init(
baseRange: Range<Base.Index>,
sequenceLength: Int,
splitCount: Int
) {
self.baseRange = baseRange
self.sequenceLength = sequenceLength
self.splitCount = splitCount
}
@inlinable
public static func == (lhs: Index, rhs: Index) -> Bool {
// `sequenceLength` is equivalent to the index's 1-based position in the
// collection of indices.
lhs.sequenceLength == rhs.sequenceLength
}
@inlinable
public static func < (lhs: Index, rhs: Index) -> Bool {
lhs.sequenceLength < rhs.sequenceLength
}
}
/// Returns the index of the subsequence starting at or after the given base
/// collection index.
@usableFromInline
internal func indexForSubsequence(
atOrAfter lowerBound: Base.Index,
sequenceLength: Int,
splitCount: Int
) -> Index {
var start = lowerBound
// If we don't have any more splits to do (which we'll determine shortly),
// the end of this subsequence will be the end of the base collection.
var end = base.endIndex
if splitCount < maxSplits {
// The non-inclusive end of this subsequence is marked by the next
// separator, or the end of the base collection.
end =
base[start...].firstIndex(where: isSeparator)
?? base.endIndex
if base[start..<end].isEmpty {
if omittingEmptySubsequences {
// Find the next subsequence of non-separators.
start =
base[end...].firstIndex(where: { !isSeparator($0) })
?? base.endIndex
if start == base.endIndex {
// No non-separators left in the base collection. We're done.
return endIndex
}
end = base[start...].firstIndex(where: isSeparator) ?? base.endIndex
}
}
}
var updatedSplitCount = splitCount
if end < base.endIndex {
// This subsequence ends on a separator (and perhaps includes other
// separators, if we're omitting empty subsequences), so we've performed
// another split.
updatedSplitCount += 1
}
return Index(
baseRange: start..<end,
sequenceLength: sequenceLength + 1,
splitCount: updatedSplitCount
)
}
@inlinable
public var startIndex: Index {
_startIndex
}
@inlinable
public var endIndex: Index {
Index(
baseRange: base.endIndex..<base.endIndex,
sequenceLength: Int.max,
splitCount: Int.max
)
}
@inlinable
public func index(after i: Index) -> Index {
precondition(i != endIndex, "Can't advance past endIndex")
var subsequenceStart = i.baseRange.upperBound
if subsequenceStart < base.endIndex {
// If we're not already at the end of the base collection, the previous
// susequence ended with a separator. Start searching for the next
// subsequence at the following element.
subsequenceStart = base.index(after: i.baseRange.upperBound)
}
guard subsequenceStart != base.endIndex else {
if !omittingEmptySubsequences
&& i.sequenceLength < i.splitCount + 1
{
// The base collection ended with a separator, so we need to emit one
// more empty subsequence. This one differs from `endIndex` in its
// `sequenceLength` (except in an extreme edge case!), which is the
// sole property tested for equality and comparison.
return Index(
baseRange: base.endIndex..<base.endIndex,
sequenceLength: i.sequenceLength + 1,
splitCount: i.splitCount
)
} else {
return endIndex
}
}
return indexForSubsequence(
atOrAfter: subsequenceStart,
sequenceLength: i.sequenceLength,
splitCount: i.splitCount
)
}
@inlinable
public subscript(position: Index) -> Base.SubSequence {
precondition(position != endIndex, "Can't subscript using endIndex")
return base[position.baseRange]
}
}
extension LazySplitCollection.Index: Hashable {
public func hash(into hasher: inout Hasher) {
hasher.combine(sequenceLength)
}
}
extension LazyCollectionProtocol {
/// Lazily returns the longest possible subsequences of the collection, in
/// order, that don't contain elements satisfying the given predicate.
///
/// The resulting lazy collection consists of at most `maxSplits + 1`
/// subsequences. Elements that are used to split the collection are not
/// returned as part of any subsequence (except possibly the last one, in the
/// case where `maxSplits` is less than the number of separators in the
/// collection).
///
/// The following examples show the effects of the `maxSplits` and
/// `omittingEmptySubsequences` parameters when lazily splitting a string
/// using a closure that matches spaces. The first use of `split` returns each
/// word that was originally separated by one or more spaces.
///
/// let line = "BLANCHE: I don't want realism. I want magic!"
/// for spaceless in line.lazy.split(whereSeparator: { $0 == " " }) {
/// print(spaceless)
/// }
/// // Prints
/// // BLANCHE:
/// // I
/// // don't
/// // want
/// // realism.
/// // I
/// // want
/// // magic!
///
/// The second example passes `1` for the `maxSplits` parameter, so the
/// original string is split just once, into two new strings.
///
/// for spaceless in line.lazy.split(
/// maxSplits: 1,
/// whereSeparator: { $0 == " " }
/// ) {
/// print(spaceless)
/// }
/// // Prints
/// // BLANCHE:
/// // I don't want realism. I want magic!
///
/// The final example passes `false` for the `omittingEmptySubsequences`
/// parameter, so the returned array contains empty strings where spaces
/// were repeated.
///
/// for spaceless in line.lazy.split(
/// omittingEmptySubsequences: false,
/// whereSeparator: { $0 == " " }
/// ) {
/// print(spaceless)
/// }
/// // Prints
/// // BLANCHE:
/// //
/// //
/// // I
/// // don't
/// // want
/// // realism.
/// // I
/// // want
/// // magic!
///
/// - Parameters:
/// - maxSplits: The maximum number of times to split the collection, or
/// one less than the number of subsequences to return. If
/// `maxSplits + 1` subsequences are returned, the last one is a suffix
/// of the original collection containing the remaining elements.
/// `maxSplits` must be greater than or equal to zero. The default value
/// is `Int.max`.
/// - omittingEmptySubsequences: If `false`, an empty subsequence is
/// returned in the result for each pair of consecutive elements
/// satisfying the `isSeparator` predicate and for each element at the
/// start or end of the collection satisfying the `isSeparator`
/// predicate. The default value is `true`.
/// - whereSeparator: A closure that takes an element as an argument and
/// returns a Boolean value indicating whether the collection should be
/// split at that element.
/// - Returns: A lazy collection of subsequences, split from this collection's
/// elements.
///
/// - Complexity: O(*n*), where *n* is the length of the collection.
@inlinable
public func split(
maxSplits: Int = Int.max,
omittingEmptySubsequences: Bool = true,
whereSeparator isSeparator: @escaping (Element) -> Bool
) -> LazySplitCollection<Elements> {
precondition(maxSplits >= 0, "Must take zero or more splits")
return LazySplitCollection(
base: elements,
isSeparator: isSeparator,
maxSplits: maxSplits,
omittingEmptySubsequences: omittingEmptySubsequences
)
}
}
extension LazyCollectionProtocol
where Element: Equatable {
/// Lazily returns the longest possible subsequences of the collection, in
/// order, around elements equal to the given element.
///
/// The resulting lazy collection consists of at most `maxSplits + 1`
/// subsequences. Elements that are used to split the collection are not
/// returned as part of any subsequence (except possibly the last one, in the
/// case where `maxSplits` is less than the number of separators in the
/// collection).
///
/// The following examples show the effects of the `maxSplits` and
/// `omittingEmptySubsequences` parameters when splitting a string at each
/// space character (" "). The first use of `split` returns each word that
/// was originally separated by one or more spaces.
///
/// let line = "BLANCHE: I don't want realism. I want magic!"
/// for spaceless in line.lazy.split(separator: " ") {
/// print(spaceless)
/// }
/// // Prints
/// // BLANCHE:
/// // I
/// // don't
/// // want
/// // realism.
/// // I
/// // want
/// // magic!
///
/// The second example passes `1` for the `maxSplits` parameter, so the
/// original string is split just once, into two new strings.
///
/// for spaceless in line.lazy.split(separator: " ", maxSplits: 1) {
/// print(spaceless)
/// }
/// // Prints
/// // BLANCHE:
/// // I don't want realism. I want magic!
///
/// The final example passes `false` for the `omittingEmptySubsequences`
/// parameter, so the returned array contains empty strings where spaces
/// were repeated.
///
/// for spaceless in line.lazy.split(
/// separator: " ",
/// omittingEmptySubsequences: false
/// ) {
/// print(spaceless)
/// }
/// // Prints
/// // BLANCHE:
/// //
/// //
/// // I
/// // don't
/// // want
/// // realism.
/// // I
/// // want
/// // magic!
///
/// - Parameters:
/// - separator: The element that should be split upon.
/// - maxSplits: The maximum number of times to split the collection, or
/// one less than the number of subsequences to return. If
/// `maxSplits + 1` subsequences are returned, the last one is a suffix
/// of the original collection containing the remaining elements.
/// `maxSplits` must be greater than or equal to zero. The default value
/// is `Int.max`.
/// - omittingEmptySubsequences: If `false`, an empty subsequence is
/// returned in the result for each consecutive pair of `separator`
/// elements in the collection and for each instance of `separator` at
/// the start or end of the collection. If `true`, only nonempty
/// subsequences are returned. The default value is `true`.
/// - Returns: A lazy collection of subsequences split from this collection's
/// elements.
///
/// - Complexity: O(*n*), where *n* is the length of the collection.
@inlinable
public func split(
separator: Element,
maxSplits: Int = Int.max,
omittingEmptySubsequences: Bool = true
) -> LazySplitCollection<Elements> {
precondition(maxSplits >= 0, "Must take zero or more splits")
return LazySplitCollection(
base: elements,
isSeparator: { $0 == separator },
maxSplits: maxSplits,
omittingEmptySubsequences: omittingEmptySubsequences
)
}
}
-385
View File
@@ -1,385 +0,0 @@
//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift Algorithms open source project
//
// Copyright (c) 2020 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
//
//===----------------------------------------------------------------------===//
extension Sequence {
/// Implementation for min(count:areInIncreasingOrder:)
@inlinable
internal func _minImplementation(
count: Int,
sortedBy areInIncreasingOrder: (Element, Element) throws -> Bool
) rethrows -> [Element] {
var iterator = makeIterator()
var result: [Element] = []
result.reserveCapacity(count)
while result.count < count, let e = iterator.next() {
result.append(e)
}
try result.sort(by: areInIncreasingOrder)
while let e = iterator.next() {
// To be part of `result`, `e` must be strictly less than `result.last`.
guard try areInIncreasingOrder(e, result.last!) else { continue }
let insertionIndex =
try result.partitioningIndex { try areInIncreasingOrder(e, $0) }
assert(insertionIndex != result.endIndex)
result.removeLast()
result.insert(e, at: insertionIndex)
}
return result
}
/// Implementation for max(count:areInIncreasingOrder:)
@inlinable
internal func _maxImplementation(
count: Int,
sortedBy areInIncreasingOrder: (Element, Element) throws -> Bool
) rethrows -> [Element] {
var iterator = makeIterator()
var result: [Element] = []
result.reserveCapacity(count)
while result.count < count, let e = iterator.next() {
result.append(e)
}
try result.sort(by: areInIncreasingOrder)
while let e = iterator.next() {
// To be part of `result`, `e` must be greater/equal to `result.first`.
guard try !areInIncreasingOrder(e, result.first!) else { continue }
let insertionIndex =
try result.partitioningIndex { try areInIncreasingOrder(e, $0) }
assert(insertionIndex > 0)
// Inserting `e` and then removing the first element (or vice versa)
// would perform a double shift, so we manually shift down the elements
// before dropping `e` in.
var i = 1
while i < insertionIndex {
result[i - 1] = result[i]
i += 1
}
result[insertionIndex - 1] = e
}
return result
}
/// Returns the smallest elements of this sequence, as sorted by the given
/// predicate.
///
/// This example partially sorts an array of integers to retrieve its three
/// smallest values:
///
/// let numbers = [7, 1, 6, 2, 8, 3, 9]
/// let smallestThree = numbers.min(count: 3, sortedBy: <)
/// // [1, 2, 3]
///
/// If you need to sort a sequence but only need to access its smallest
/// elements, using this method can give you a performance boost over sorting
/// the entire sequence. The order of equal elements is guaranteed to be
/// preserved.
///
/// - Parameters:
/// - count: The number of elements to return. If `count` is greater than
/// the number of elements in this sequence, all of the sequence's
/// elements are returned.
/// - areInIncreasingOrder: A predicate that returns `true` if its
/// first argument should be ordered before its second argument;
/// otherwise, `false`.
/// - Returns: An array of the smallest `count` elements of this sequence,
/// sorted according to `areInIncreasingOrder`.
///
/// - Complexity: O(*k* log *k* + *nk*), where *n* is the length of the
/// sequence and *k* is `count`.
@inlinable
public func min(
count: Int,
sortedBy areInIncreasingOrder: (Element, Element) throws -> Bool
) rethrows -> [Element] {
precondition(count >= 0, """
Cannot find a minimum with a negative count of elements!
"""
)
// Do nothing if we're prefixing nothing.
guard count > 0 else {
return []
}
return try _minImplementation(count: count, sortedBy: areInIncreasingOrder)
}
/// Returns the largets elements of this sequence, as sorted by the given
/// predicate.
///
/// This example partially sorts an array of integers to retrieve its three
/// largest values:
///
/// let numbers = [7, 1, 6, 2, 8, 3, 9]
/// let smallestThree = numbers.max(count: 3, sortedBy: <)
/// // [7, 8, 9]
///
/// If you need to sort a sequence but only need to access its largest
/// elements, using this method can give you a performance boost over sorting
/// the entire sequence. The order of equal elements is guaranteed to be
/// preserved.
///
/// - Parameters:
/// - count: The number of elements to return. If `count` is greater than
/// the number of elements in this sequence, all of the sequence's
/// elements are returned.
/// - areInIncreasingOrder: A predicate that returns `true` if its
/// first argument should be ordered before its second argument;
/// otherwise, `false`.
/// - Returns: An array of the largest `count` elements of this sequence,
/// sorted according to `areInIncreasingOrder`.
///
/// - Complexity: O(*k* log *k* + *nk*), where *n* is the length of the
/// sequence and *k* is `count`.
@inlinable
public func max(
count: Int,
sortedBy areInIncreasingOrder: (Element, Element) throws -> Bool
) rethrows -> [Element] {
precondition(count >= 0, """
Cannot find a maximum with a negative count of elements!
"""
)
// Do nothing if we're suffixing nothing.
guard count > 0 else {
return []
}
return try _maxImplementation(count: count, sortedBy: areInIncreasingOrder)
}
}
extension Sequence where Element: Comparable {
/// Returns the smallest elements of this sequence.
///
/// This example partially sorts an array of integers to retrieve its three
/// smallest values:
///
/// let numbers = [7, 1, 6, 2, 8, 3, 9]
/// let smallestThree = numbers.min(count: 3)
/// // [1, 2, 3]
///
/// If you need to sort a sequence but only need to access its smallest
/// elements, using this method can give you a performance boost over sorting
/// the entire sequence. The order of equal elements is guaranteed to be
/// preserved.
///
/// - Parameter count: The number of elements to return. If `count` is greater
/// than the number of elements in this sequence, all of the sequence's
/// elements are returned.
/// - Returns: An array of the smallest `count` elements of this sequence.
///
/// - Complexity: O(*k* log *k* + *nk*), where *n* is the length of the
/// sequence and *k* is `count`.
@inlinable
public func min(count: Int) -> [Element] {
return min(count: count, sortedBy: <)
}
/// Returns the largest elements of this sequence.
///
/// This example partially sorts an array of integers to retrieve its three
/// largest values:
///
/// let numbers = [7, 1, 6, 2, 8, 3, 9]
/// let smallestThree = numbers.max(count: 3)
/// // [7, 8, 9]
///
/// If you need to sort a sequence but only need to access its largest
/// elements, using this method can give you a performance boost over sorting
/// the entire sequence. The order of equal elements is guaranteed to be
/// preserved.
///
/// - Parameter count: The number of elements to return. If `count` is greater
/// than the number of elements in this sequence, all of the sequence's
/// elements are returned.
/// - Returns: An array of the largest `count` elements of this sequence.
///
/// - Complexity: O(*k* log *k* + *nk*), where *n* is the length of the
/// sequence and *k* is `count`.
@inlinable
public func max(count: Int) -> [Element] {
return max(count: count, sortedBy: <)
}
}
extension Collection {
/// Returns the smallest elements of this collection, as sorted by the given
/// predicate.
///
/// This example partially sorts an array of integers to retrieve its three
/// smallest values:
///
/// let numbers = [7, 1, 6, 2, 8, 3, 9]
/// let smallestThree = numbers.min(count: 3, sortedBy: <)
/// // [1, 2, 3]
///
/// If you need to sort a collection but only need to access its smallest
/// elements, using this method can give you a performance boost over sorting
/// the entire collection. The order of equal elements is guaranteed to be
/// preserved.
///
/// - Parameters:
/// - count: The number of elements to return. If `count` is greater than
/// the number of elements in this collection, all of the collection's
/// elements are returned.
/// - areInIncreasingOrder: A predicate that returns `true` if its
/// first argument should be ordered before its second argument;
/// otherwise, `false`.
/// - Returns: An array of the smallest `count` elements of this collection,
/// sorted according to `areInIncreasingOrder`.
///
/// - Complexity: O(*k* log *k* + *nk*), where *n* is the length of the
/// collection and *k* is `count`.
@inlinable
public func min(
count: Int,
sortedBy areInIncreasingOrder: (Element, Element) throws -> Bool
) rethrows -> [Element] {
precondition(count >= 0, """
Cannot find a minimum with a negative count of elements!
"""
)
// Do nothing if we're prefixing nothing.
guard count > 0 else {
return []
}
// Make sure we are within bounds.
let prefixCount = Swift.min(count, self.count)
// If we're attempting to prefix more than 10% of the collection, it's
// faster to sort everything.
guard prefixCount < (self.count / 10) else {
return Array(try sorted(by: areInIncreasingOrder).prefix(prefixCount))
}
return try _minImplementation(count: count, sortedBy: areInIncreasingOrder)
}
/// Returns the largets elements of this collection, as sorted by the given
/// predicate.
///
/// This example partially sorts an array of integers to retrieve its three
/// largest values:
///
/// let numbers = [7, 1, 6, 2, 8, 3, 9]
/// let smallestThree = numbers.max(count: 3, sortedBy: <)
/// // [7, 8, 9]
///
/// If you need to sort a collection but only need to access its largest
/// elements, using this method can give you a performance boost over sorting
/// the entire collection. The order of equal elements is guaranteed to be
/// preserved.
///
/// - Parameters:
/// - count: The number of elements to return. If `count` is greater than
/// the number of elements in this collection, all of the collection's
/// elements are returned.
/// - areInIncreasingOrder: A predicate that returns `true` if its
/// first argument should be ordered before its second argument;
/// otherwise, `false`.
/// - Returns: An array of the largest `count` elements of this collection,
/// sorted according to `areInIncreasingOrder`.
///
/// - Complexity: O(*k* log *k* + *nk*), where *n* is the length of the
/// collection and *k* is `count`.
@inlinable
public func max(
count: Int,
sortedBy areInIncreasingOrder: (Element, Element) throws -> Bool
) rethrows -> [Element] {
precondition(count >= 0, """
Cannot find a maximum with a negative count of elements!
"""
)
// Do nothing if we're suffixing nothing.
guard count > 0 else {
return []
}
// Make sure we are within bounds.
let suffixCount = Swift.min(count, self.count)
// If we're attempting to prefix more than 10% of the collection, it's
// faster to sort everything.
guard suffixCount < (self.count / 10) else {
return Array(try sorted(by: areInIncreasingOrder).suffix(suffixCount))
}
return try _maxImplementation(count: count, sortedBy: areInIncreasingOrder)
}
}
extension Collection where Element: Comparable {
/// Returns the smallest elements of this collection.
///
/// This example partially sorts an array of integers to retrieve its three
/// smallest values:
///
/// let numbers = [7, 1, 6, 2, 8, 3, 9]
/// let smallestThree = numbers.min(count: 3)
/// // [1, 2, 3]
///
/// If you need to sort a collection but only need to access its smallest
/// elements, using this method can give you a performance boost over sorting
/// the entire collection. The order of equal elements is guaranteed to be
/// preserved.
///
/// - Parameter count: The number of elements to return. If `count` is greater
/// than the number of elements in this collection, all of the collection's
/// elements are returned.
/// - Returns: An array of the smallest `count` elements of this collection.
///
/// - Complexity: O(*k* log *k* + *nk*), where *n* is the length of the
/// collection and *k* is `count`.
@inlinable
public func min(count: Int) -> [Element] {
return min(count: count, sortedBy: <)
}
/// Returns the largest elements of this collection.
///
/// This example partially sorts an array of integers to retrieve its three
/// largest values:
///
/// let numbers = [7, 1, 6, 2, 8, 3, 9]
/// let smallestThree = numbers.max(count: 3)
/// // [7, 8, 9]
///
/// If you need to sort a collection but only need to access its largest
/// elements, using this method can give you a performance boost over sorting
/// the entire collection. The order of equal elements is guaranteed to be
/// preserved.
///
/// - Parameter count: The number of elements to return. If `count` is greater
/// than the number of elements in this collection, all of the collection's
/// elements are returned.
/// - Returns: An array of the largest `count` elements of this collection.
///
/// - Complexity: O(*k* log *k* + *nk*), where *n* is the length of the
/// collection and *k* is `count`.
@inlinable
public func max(count: Int) -> [Element] {
return max(count: count, sortedBy: <)
}
}
+56 -168
View File
@@ -11,93 +11,61 @@
/// A sequence of all the permutations of a collection's elements.
public struct Permutations<Base: Collection> {
/// The base collection to iterate over for permutations.
/// The base collection.
public let base: Base
@usableFromInline
internal let baseCount: Int
internal let countToChoose: Int
/// The range of accepted sizes of permutations.
/// - Note: This may be empty if the attempted range entirely exceeds the
/// bounds of the size of the `base` collection.
@usableFromInline
internal let kRange: Range<Int>
/// Initializes a `Permutations` for all permutations of `base` of size `k`.
/// - Parameters:
/// - base: The collection to iterate over for permutations
/// - k: The expected size of each permutation, or `nil` (default) to
/// iterate over all permutations of the same size as the base collection.
@usableFromInline
internal init(_ base: Base, k: Int? = nil) {
let kRange: ClosedRange<Int>?
if let countToChoose = k {
kRange = countToChoose ... countToChoose
} else {
kRange = nil
}
self.init(base, kRange: kRange)
}
/// Initializes a `Permutations` for all combinations of `base` of sizes
/// within a given range.
/// - Parameters:
/// - base: The collection to iterate over for permutations.
/// - kRange: The range of accepted sizes of permutations, or `nil` to
/// iterate over all permutations of the same size as the base collection.
@usableFromInline
internal init<R: RangeExpression>(
_ base: Base, kRange: R?
) where R.Bound == Int {
self.base = base
let baseCount = base.count
self.baseCount = baseCount
let upperBound = baseCount + 1
self.kRange = kRange?.relative(to: 0 ..< .max)
.clamped(to: 0 ..< upperBound) ??
baseCount ..< upperBound
self.countToChoose = k ?? baseCount
}
/// The total number of permutations.
@inlinable
public var count: Int {
return kRange.map {
stride(from: baseCount, to: baseCount - $0, by: -1).reduce(1, *)
}.reduce(0, +)
return baseCount >= countToChoose
? stride(from: baseCount, to: baseCount - countToChoose, by: -1).reduce(1, *)
: 0
}
}
extension Permutations: Sequence {
/// The iterator for a `Permutations` instance.
public struct Iterator: IteratorProtocol {
@usableFromInline
internal var base: Base
@usableFromInline
internal let baseCount: Int
/// The current range of accepted sizes of permutations.
/// - Note: The range is contracted until empty while iterating over
/// permutations of different sizes. When the range is empty, iteration is
/// finished.
internal var indexes: [Base.Index]
@usableFromInline
internal var kRange: Range<Int>
/// Whether or not iteration is finished (`kRange` is empty)
internal var hasMorePermutations: Bool
@usableFromInline
internal var isFinished: Bool {
return kRange.isEmpty
internal var countToChoose: Int = 0
/// `true` if we're generating permutations of the full collection.
@usableFromInline
internal var permutesFullCollection: Bool {
countToChoose == indexes.count
}
@usableFromInline
internal var indexes: [Base.Index]
internal init(_ base: Base) {
self.base = base
self.indexes = Array(base.indices)
self.countToChoose = self.indexes.count
self.hasMorePermutations = true
}
@usableFromInline
internal init(_ permutations: Permutations) {
self.base = permutations.base
self.baseCount = permutations.baseCount
self.kRange = permutations.kRange
self.indexes = Array(permutations.base.indices)
internal init(_ base: Base, count: Int) {
self.base = base
self.countToChoose = count
// Produce exactly one empty permutation when `count == 0`.
self.indexes = count == 0 ? [] : Array(base.indices)
// Can't produce any permutations when `count > base.count`.
self.hasMorePermutations = count <= indexes.count
}
/// Advances the `indexes` array such that the first `countToChoose`
@@ -113,30 +81,29 @@ extension Permutations: Sequence {
/// - Complexity: O(*n*), where *n* is the length of the collection.
@usableFromInline
internal mutating func nextState() -> Bool {
let countToChoose = self.kRange.lowerBound
let edge = countToChoose - 1
// Find first index greater than the one at `edge`.
if let i = indexes[countToChoose...].firstIndex(where: { indexes[edge] < $0 }) {
indexes.swapAt(edge, i)
} else {
indexes.reverse(subrange: countToChoose ..< indexes.endIndex)
indexes.reverse(subrange: countToChoose..<indexes.endIndex)
// Find last increasing pair below `edge`.
// TODO: This could be indexes[..<edge].adjacentPairs().lastIndex(where: ...)
var lastAscent = edge - 1
while (lastAscent >= 0 && indexes[lastAscent] >= indexes[lastAscent + 1]) {
lastAscent -= 1
}
if lastAscent < 0 {
if (lastAscent < 0) {
return false
}
// Find rightmost index less than that at `lastAscent`.
if let i = indexes[lastAscent...].lastIndex(where: { indexes[lastAscent] < $0 }) {
indexes.swapAt(lastAscent, i)
}
indexes.reverse(subrange: (lastAscent + 1) ..< indexes.endIndex)
indexes.reverse(subrange: (lastAscent + 1)..<indexes.endIndex)
}
return true
@@ -144,62 +111,42 @@ extension Permutations: Sequence {
@inlinable
public mutating func next() -> [Base.Element]? {
guard !isFinished else { return nil }
if !hasMorePermutations { return nil }
/// Advances `kRange` by incrementing its `lowerBound` until the range is
/// empty, when iteration is finished.
func advanceKRange() {
kRange.removeFirst()
indexes = Array(base.indices)
}
let countToChoose = self.kRange.lowerBound
if countToChoose == 0 {
defer {
advanceKRange()
}
return []
}
let permutesFullCollection = (countToChoose == baseCount)
if permutesFullCollection {
// If we're permuting the full collection, each iteration is just a
// call to `nextPermutation` on `indexes`.
defer {
let hasMorePermutations = indexes.nextPermutation()
if !hasMorePermutations {
advanceKRange()
}
}
defer { hasMorePermutations = indexes.nextPermutation() }
return indexes.map { base[$0] }
} else {
// Otherwise, return the items at the first `countToChoose` indices and
// advance the state.
defer {
let hasMorePermutations = nextState()
if !hasMorePermutations {
advanceKRange()
}
}
defer { hasMorePermutations = nextState() }
return indexes.prefix(countToChoose).map { base[$0] }
}
}
}
@inlinable
@usableFromInline
internal var permutesFullCollection: Bool {
baseCount == countToChoose
}
public func makeIterator() -> Iterator {
Iterator(self)
permutesFullCollection
? Iterator(base)
: Iterator(base, count: countToChoose)
}
}
extension Permutations: LazySequenceProtocol where Base: LazySequenceProtocol {}
//===----------------------------------------------------------------------===//
// nextPermutation()
// nextPermutation(by:)
//===----------------------------------------------------------------------===//
extension MutableCollection
where Self: BidirectionalCollection, Element: Comparable
where Self: BidirectionalCollection, Element: Comparable
{
/// Permutes this collection's elements through all the lexical orderings.
///
@@ -215,8 +162,8 @@ where Self: BidirectionalCollection, Element: Comparable
/// - Complexity: O(*n*), where *n* is the length of the collection.
@usableFromInline
internal mutating func nextPermutation() -> Bool {
// Ensure we have > 1 element in the collection.
guard !isEmpty else { return false }
// ensure we have > 1 element in the collection
if isEmpty { return false }
var i = index(before: endIndex)
if i == startIndex { return false }
@@ -230,7 +177,7 @@ where Self: BidirectionalCollection, Element: Comparable
formIndex(before: &j)
}
swapAt(i, j)
self.reverse(subrange: ip1 ..< endIndex)
self.reverse(subrange: ip1..<endIndex)
return true
}
@@ -247,62 +194,6 @@ where Self: BidirectionalCollection, Element: Comparable
//===----------------------------------------------------------------------===//
extension Collection {
/// Returns a collection of the permutations of this collection with lengths
/// in the specified range.
///
/// This example prints the different permutations of one to two elements from
/// an array of three names:
///
/// let names = ["Alex", "Celeste", "Davide"]
/// for perm in names.permutations(ofCount: 1...2) {
/// print(perm.joined(separator: ", "))
/// }
/// // Alex
/// // Celeste
/// // Davide
/// // Alex, Celeste
/// // Alex, Davide
/// // Celeste, Alex
/// // Celeste, Davide
/// // Davide, Alex
/// // Davide, Celeste
///
/// This example prints _all_ the permutations (including an empty array) from
/// the an array of numbers:
///
/// let numbers = [10, 20, 30]
/// for perm in numbers.permutations(ofCount: 0...) {
/// print(perm)
/// }
/// // []
/// // [10]
/// // [20]
/// // [30]
/// // [10, 20]
/// // [10, 30]
/// // [20, 10]
/// // [20, 30]
/// // [30, 10]
/// // [30, 20]
/// // [10, 20, 30]
/// // [10, 30, 20]
/// // [20, 10, 30]
/// // [20, 30, 10]
/// // [30, 10, 20]
/// // [30, 20, 10]
///
/// - Parameter kRange: The number of elements to include in each permutation.
///
/// - Complexity: O(1) for random-access base collections. O(*n*) where *n*
/// is the number of elements in the base collection, since `Permutations`
/// accesses the `count` of the base collection.
@inlinable
public func permutations<R: RangeExpression>(
ofCount kRange: R
) -> Permutations<Self> where R.Bound == Int {
return Permutations(self, kRange: kRange)
}
/// Returns a collection of the permutations of this collection of the
/// specified length.
///
@@ -345,15 +236,12 @@ extension Collection {
/// sequence, the resulting sequence has no elements.
///
/// - Parameter k: The number of elements to include in each permutation.
/// If `k` is `nil`, the resulting sequence represents permutations of this
/// entire collection.
/// If `count` is `nil`, the resulting sequence represents permutations
/// of this entire collection.
///
/// - Complexity: O(1) for random-access base collections. O(*n*) where *n*
/// is the number of elements in the base collection, since `Permutations`
/// accesses the `count` of the base collection.
@inlinable
/// - Complexity: O(1)
public func permutations(ofCount k: Int? = nil) -> Permutations<Self> {
precondition(
assert(
k ?? 0 >= 0,
"Can't have permutations with a negative number of elements.")
return Permutations(self, k: k)
+17 -279
View File
@@ -9,14 +9,13 @@
//
//===----------------------------------------------------------------------===//
/// A sequence that represents the product of two sequences' elements.
/// A sequence that represents the product of two sequence's elements.
public struct Product2<Base1: Sequence, Base2: Collection> {
/// The outer sequence in the product.
public let base1: Base1
/// The inner sequence in the product.
public let base2: Base2
@usableFromInline
internal init(_ base1: Base1, _ base2: Base2) {
self.base1 = base1
self.base2 = base2
@@ -120,293 +119,33 @@ extension Product2: Collection where Base1: Collection {
Index(i1: base1.endIndex, i2: base2.startIndex)
}
@inlinable
public subscript(position: Index) -> (Base1.Element, Base2.Element) {
(base1[position.i1], base2[position.i2])
}
/// Forms an index from a pair of base indices, normalizing
/// `(i, base2.endIndex)` to `(base1.index(after: i), base2.startIndex)` if
/// necessary.
@usableFromInline
internal func normalizeIndex(_ i1: Base1.Index, _ i2: Base2.Index) -> Index {
i2 == base2.endIndex
? Index(i1: base1.index(after: i1), i2: base2.startIndex)
: Index(i1: i1, i2: i2)
}
@inlinable
public func index(after i: Index) -> Index {
precondition(i.i1 != base1.endIndex, "Can't advance past endIndex")
return normalizeIndex(i.i1, base2.index(after: i.i2))
let newIndex2 = base2.index(after: i.i2)
return newIndex2 == base2.endIndex
? Index(i1: base1.index(after: i.i1), i2: base2.startIndex)
: Index(i1: i.i1, i2: newIndex2)
}
// TODO: Implement index(_:offsetBy:) and index(_:offsetBy:limitedBy:)
@inlinable
public func distance(from start: Index, to end: Index) -> Int {
guard start.i1 <= end.i1
else { return -distance(from: end, to: start) }
guard start.i1 != end.i1
else { return base2.distance(from: start.i2, to: end.i2) }
// The number of full cycles through `base2` between `start` and `end`,
// excluding the cycles that `start` and `end` are on.
let fullBase2Cycles = base1[start.i1..<end.i1].count - 1
if start.i2 <= end.i2 {
// start.i2
// v
// start.i1 > [l l l|c c c c c c r r r]
// [l l l c c c c c c r r r] >
// ... > `fullBase2Cycles` times
// [l l l c c c c c c r r r] >
// end.i1 > [l l l c c c c c c|r r r]
// ^
// end.i2
let left = base2[..<start.i2].count
let center = base2[start.i2..<end.i2].count
let right = base2[end.i2...].count
return center + right
+ fullBase2Cycles * (left + center + right)
+ left + center
} else {
// start.i2
// v
// start.i1 > [l l l c c c c c c|r r r]
// [l l l c c c c c c r r r] >
// ... > `fullBase2Cycles` times
// [l l l c c c c c c r r r] >
// end.i1 > [l l l|c c c c c c r r r]
// ^
// end.i2
let left = base2[..<end.i2].count
let right = base2[start.i2...].count
// We can avoid traversing `base2[end.i2..<start.i2]` if `start` and `end`
// are on consecutive cycles.
guard fullBase2Cycles > 0 else { return right + left }
let center = base2[end.i2..<start.i2].count
return right
+ fullBase2Cycles * (left + center + right)
+ left
if start > end {
return -distance(from: end, to: start)
}
}
public func index(_ i: Index, offsetBy distance: Int) -> Index {
guard distance != 0 else { return i }
return distance > 0
? offsetForward(i, by: distance)
: offsetBackward(i, by: -distance)
}
public func index(
_ i: Index,
offsetBy distance: Int,
limitedBy limit: Index
) -> Index? {
if distance >= 0 {
return limit >= i
? offsetForward(i, by: distance, limitedBy: limit)
: offsetForward(i, by: distance)
} else {
return limit <= i
? offsetBackward(i, by: -distance, limitedBy: limit)
: offsetBackward(i, by: -distance)
if start.i1 == end.i1 {
return base2[start.i2..<end.i2].count
}
return base2[start.i2...].count + base2[..<end.i2].count
+ base2.count * (base1.distance(from: start.i1, to: end.i1) - 1)
}
@usableFromInline
internal func offsetForward(_ i: Index, by distance: Int) -> Index {
guard let index = offsetForward(i, by: distance, limitedBy: endIndex)
else { fatalError("Index is out of bounds") }
return index
}
@usableFromInline
internal func offsetBackward(_ i: Index, by distance: Int) -> Index {
guard let index = offsetBackward(i, by: distance, limitedBy: startIndex)
else { fatalError("Index is out of bounds") }
return index
}
@usableFromInline
internal func offsetForward(
_ i: Index, by distance: Int, limitedBy limit: Index
) -> Index? {
assert(distance >= 0)
assert(limit >= i)
if limit.i1 == i.i1 {
// Delegate to `base2` if the offset is limited to `i.i1`.
//
// i.i2 limit.i2
// v v
// i.i1 > [x x x|x x x x x x|x x x]
return base2.index(i.i2, offsetBy: distance, limitedBy: limit.i2)
.map { i2 in Index(i1: i.i1, i2: i2) }
}
if let i2 = base2.index(i.i2, offsetBy: distance, limitedBy: base2.endIndex) {
// `distance` does not overflow `base2[i.i2...]`.
//
// i.i2 i2
// v v
// i.i1 > [x x x|x x x x x x|x x x]
// [ |> > > > > >| ] (`distance`)
return normalizeIndex(i.i1, i2)
}
let suffixCount = base2[i.i2...].count
let remaining = distance - suffixCount
let nextI1 = base1.index(after: i.i1)
if limit.i1 == nextI1 {
// Delegate to `base2` if the offset is limited to `nextI1`.
//
// i.i2
// v
// i.i1 > [x x x|x x x x x x x x x]
// nextI1 > [x x x x x x x x x|x x x]
// ^
// limit.i2
return base2.index(base2.startIndex, offsetBy: remaining, limitedBy: limit.i2)
.map { i2 in Index(i1: nextI1, i2: i2) }
}
if let i2 = base2.index(base2.startIndex, offsetBy: remaining, limitedBy: i.i2) {
// `remaining` does not overflow `base2[..<i.i2]`.
//
// i.i2
// v
// i.i1 > [x x x x x x x x x|x x x]
// [ |> > >] (`suffixCount`)
// [> > >| ] (`remaining`)
// nextI1 > [x x x|x x x x x x x x x]
// ^
// i2
return Index(i1: nextI1, i2: i2)
}
let prefixCount = base2[..<i.i2].count
let base2Count = prefixCount + suffixCount
let base1Distance = remaining / base2Count
guard let i1 = base1.index(nextI1, offsetBy: base1Distance, limitedBy: limit.i1)
else { return nil }
// The distance from `base2.startIndex` to the target.
let base2Distance = remaining % base2Count
let base2Limit = limit.i1 == i1 ? limit.i2 : base2.endIndex
return base2.index(base2.startIndex, offsetBy: base2Distance, limitedBy: base2Limit)
.map { i2 in Index(i1: i1, i2: i2) }
}
@usableFromInline
internal func offsetBackward(
_ i: Index, by distance: Int, limitedBy limit: Index
) -> Index? {
assert(distance >= 0)
assert(limit <= i)
if limit.i1 == i.i1 {
// Delegate to `base2` if the offset is limited to `i.i1`.
//
// limit.i2 i.i2
// v v
// i.i1 > [x x x|x x x x x x|x x x]
return base2.index(i.i2, offsetBy: -distance, limitedBy: limit.i2)
.map { i2 in Index(i1: i.i1, i2: i2) }
}
if let i2 = base2.index(i.i2, offsetBy: -distance, limitedBy: base2.startIndex) {
// `distance` does not underflow `base2[..<i.i2]`.
//
// i2 i.i2
// v v
// i.i1 > [x x x|x x x x x x|x x x]
// [ |< < < < < <| ] (`distance`)
return Index(i1: i.i1, i2: i2)
}
let prefixCount = base2[..<i.i2].count
let remaining = distance - prefixCount
let previousI1 = base1.index(i.i1, offsetBy: -1)
if limit.i1 == previousI1 {
// Delegate to `base2` if the offset is limited to `previousI1`.
//
// limit.i2
// v
// previousI1 > [x x x|x x x x x x x x x]
// i.i1 > [x x x x x x x x x|x x x]
// ^
// i.i2
return base2.index(base2.endIndex, offsetBy: -remaining, limitedBy: limit.i2)
.map { i2 in Index(i1: previousI1, i2: i2) }
}
if let i2 = base2.index(base2.endIndex, offsetBy: -remaining, limitedBy: i.i2) {
// `remaining` does not underflow `base2[i.i2...]`.
//
// i2
// v
// previousI1 > [x x x x x x x x x|x x x]
// [ |< < <] (`remaining`)
// [< < <| ] (`prefixCount`)
// i.i1 > [x x x|x x x x x x x x x]
// ^
// i.i2
return Index(i1: previousI1, i2: i2)
}
let suffixCount = base2[i.i2...].count
let base2Count = prefixCount + suffixCount
let base1Distance = remaining / base2Count
// The distance from `base2.endIndex` to the target.
let base2Distance = remaining % base2Count
if base2Distance == 0 {
// We end up exactly between two cycles, so `base1Distance` would
// overshoot the target by 1.
//
// base2.startIndex
// v
// i1 > |x x x x x x x x x x x x] >
// ... > `base1Distance` times
// previousI1 > [x x x x x x x x x x x x] >
// i.i1 > [x x x|x x x x x x x x x]
// ^
// i.i2
if let i1 = base1.index(previousI1, offsetBy: -(base1Distance - 1), limitedBy: limit.i1) {
let index = Index(i1: i1, i2: base2.startIndex)
return index < limit ? nil : index
} else {
return nil
}
}
guard let i1 = base1.index(previousI1, offsetBy: -base1Distance, limitedBy: limit.i1)
else { return nil }
let base2Limit = limit.i1 == i1 ? limit.i2 : base2.startIndex
return base2.index(base2.endIndex, offsetBy: -base2Distance, limitedBy: base2Limit)
.map { i2 in Index(i1: i1, i2: i2) }
@inlinable
public subscript(position: Index) -> (Base1.Element, Base2.Element) {
return (base1[position.i1], base2[position.i2])
}
}
@@ -471,7 +210,6 @@ extension Product2: Hashable where Base1: Hashable, Base2: Hashable {}
/// - s2: The second sequence to iterate over.
///
/// - Complexity: O(1)
@inlinable
public func product<Base1: Sequence, Base2: Collection>(
_ s1: Base1, _ s2: Base2
) -> Product2<Base1, Base2> {
+4 -5
View File
@@ -94,8 +94,7 @@ internal func nextW<G: RandomNumberGenerator>(
internal func nextOffset<G: RandomNumberGenerator>(
w: Double, using rng: inout G
) -> Int {
let offset = Double.log(.random(in: 0..<1, using: &rng)) / .log(onePlus: -w)
return offset < Double(Int.max) ? Int(offset) : Int.max
Int(Double.log(.random(in: 0..<1, using: &rng)) / .log(1 - w))
}
extension Collection {
@@ -202,10 +201,10 @@ extension Sequence {
w *= nextW(k: k, using: &rng)
// Find the offset of the next element to swap into the reservoir.
var offset = nextOffset(w: w, using: &rng)
var offset = nextOffset(w: w, using: &rng) + 1
// Skip over `offset` elements to find the selected element.
while offset > 0, let _ = iterator.next() {
// Skip over `offset - 1` elements to find the selected element.
while offset > 1, let _ = iterator.next() {
offset -= 1
}
guard let nextElement = iterator.next() else { break }
+19 -18
View File
@@ -25,23 +25,23 @@ extension MutableCollection where Self: BidirectionalCollection {
/// Output:
/// [p o n m e f g h i j k l d c b a]
/// ^ ^
/// lower upper
/// f l
///
/// - Postcondition: For returned indices `(lower, upper)`:
/// `lower == limit || upper == limit`
/// - Postcondition: For returned indices `(f, l)`:
/// `f == limit || l == limit`
@usableFromInline
@discardableResult
internal mutating func _reverse(
subrange: Range<Index>, until limit: Index
) -> (Index, Index) {
var lower = subrange.lowerBound
var upper = subrange.upperBound
while lower != limit && upper != limit {
formIndex(before: &upper)
swapAt(lower, upper)
formIndex(after: &lower)
var f = subrange.lowerBound
var l = subrange.upperBound
while f != limit && l != limit {
formIndex(before: &l)
swapAt(f, l)
formIndex(after: &f)
}
return (lower, upper)
return (f, l)
}
/// Reverses the elements within the given subrange.
@@ -59,12 +59,13 @@ extension MutableCollection where Self: BidirectionalCollection {
@inlinable
public mutating func reverse(subrange: Range<Index>) {
if subrange.isEmpty { return }
var lower = subrange.lowerBound
var upper = subrange.upperBound
while lower < upper {
formIndex(before: &upper)
swapAt(lower, upper)
formIndex(after: &lower)
var lo = subrange.lowerBound
var hi = subrange.upperBound
while lo < hi {
formIndex(before: &hi)
swapAt(lo, hi)
formIndex(after: &lo)
}
}
}
@@ -212,7 +213,7 @@ extension MutableCollection {
/// rotating.
/// - Returns: The new index of the element that was first pre-rotation.
///
/// - Complexity: O(*n*), where *n* is the length of the collection.
/// - Complexity: O(*n*)
@inlinable
@discardableResult
public mutating func rotate(toStartAt newStart: Index) -> Index {
@@ -272,7 +273,7 @@ extension MutableCollection where Self: BidirectionalCollection {
/// rotating.
/// - Returns: The new index of the element that was first pre-rotation.
///
/// - Complexity: O(*n*), where *n* is the length of the collection.
/// - Complexity: O(*n*)
@inlinable
@discardableResult
public mutating func rotate(toStartAt newStart: Index) -> Index {
+112
View File
@@ -0,0 +1,112 @@
//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift Algorithms open source project
//
// Copyright (c) 2020 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
//
//===----------------------------------------------------------------------===//
//===----------------------------------------------------------------------===//
// slidingWindows(ofCount:)
//===----------------------------------------------------------------------===//
extension Collection {
/// A collection for all contiguous windows of length size, the
/// windows overlap.
///
/// - Complexity: O(*1*) if the collection conforms to
/// `RandomAccessCollection`, otherwise O(*k*) where `k` is `count`.
/// Access to the next window is O(*1*).
///
/// - Parameter count: The number of elements in each window subsequence.
///
/// - Returns: If the collection is shorter than `size` the resulting
/// SlidingWindows collection will be empty.
public func slidingWindows(ofCount count: Int) -> SlidingWindows<Self> {
SlidingWindows(base: self, size: count)
}
}
public struct SlidingWindows<Base: Collection> {
public let base: Base
public let size: Int
private var firstUpperBound: Base.Index?
init(base: Base, size: Int) {
precondition(size > 0, "SlidingWindows size must be greater than zero")
self.base = base
self.size = size
self.firstUpperBound = base.index(base.startIndex, offsetBy: size, limitedBy: base.endIndex)
}
}
extension SlidingWindows: Collection {
public struct Index: Comparable {
internal var lowerBound: Base.Index
internal var upperBound: Base.Index
public static func == (lhs: Index, rhs: Index) -> Bool {
lhs.lowerBound == rhs.lowerBound
}
public static func < (lhs: Index, rhs: Index) -> Bool {
lhs.lowerBound < rhs.lowerBound
}
}
public var startIndex: Index {
if let upperBound = firstUpperBound {
return Index(lowerBound: base.startIndex, upperBound: upperBound)
} else {
return endIndex
}
}
public var endIndex: Index {
Index(lowerBound: base.endIndex, upperBound: base.endIndex)
}
public subscript(index: Index) -> Base.SubSequence {
precondition(index.lowerBound != index.upperBound, "SlidingWindows index is out of range")
return base[index.lowerBound..<index.upperBound]
}
public func index(after index: Index) -> Index {
precondition(index < endIndex, "Advancing past end index")
guard index.upperBound < base.endIndex else { return endIndex }
return Index(
lowerBound: base.index(after: index.lowerBound),
upperBound: base.index(after: index.upperBound)
)
}
// TODO: Implement distance(from:to:), index(_:offsetBy:) and
// index(_:offsetBy:limitedBy:)
}
extension SlidingWindows: BidirectionalCollection where Base: BidirectionalCollection {
public func index(before index: Index) -> Index {
precondition(index > startIndex, "Incrementing past start index")
if index == endIndex {
return Index(
lowerBound: base.index(index.lowerBound, offsetBy: -size),
upperBound: index.upperBound
)
} else {
return Index(
lowerBound: base.index(before: index.lowerBound),
upperBound: base.index(before: index.upperBound)
)
}
}
}
extension SlidingWindows: RandomAccessCollection where Base: RandomAccessCollection {}
extension SlidingWindows: Equatable where Base: Equatable {}
extension SlidingWindows: Hashable where Base: Hashable, Base.Index: Hashable {}
extension SlidingWindows.Index: Hashable where Base.Index: Hashable {}
-290
View File
@@ -1,290 +0,0 @@
//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift Algorithms open source project
//
// Copyright (c) 2020 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
//
//===----------------------------------------------------------------------===//
//===----------------------------------------------------------------------===//
// striding(by:)
//===----------------------------------------------------------------------===//
extension Sequence {
/// Returns a sequence stepping through the elements every `step` starting
/// at the first value. Any remainders of the stride will be trimmed.
///
/// (0...10).striding(by: 2) // == [0, 2, 4, 6, 8, 10]
/// (0...10).striding(by: 3) // == [0, 3, 6, 9]
///
/// - Complexity: O(1). Access to successive values is O(k) where
/// _k_ is the striding `step`.
///
/// - Parameter step: The amount to step with each iteration.
/// - Returns: Returns a sequence for stepping through the
/// elements by the specified amount.
@inlinable
public func striding(by step: Int) -> StrideSequence<Self> {
StrideSequence(base: self, stride: step)
}
}
extension Collection {
/// Returns a sequence stepping through the elements every `step` starting
/// at the first value. Any remainders of the stride will be trimmed.
///
/// (0...10).striding(by: 2) // == [0, 2, 4, 6, 8, 10]
/// (0...10).striding(by: 3) // == [0, 3, 6, 9]
///
/// - Complexity: O(1). Access to successive values is O(1) if the
/// collection conforms to `RandomAccessCollection`; otherwise,
/// O(_k_), where _k_ is the striding `step`.
///
/// - Parameter step: The amount to step with each iteration.
/// - Returns: Returns a collection for stepping through the
/// elements by the specified amount.
@inlinable
public func striding(by step: Int) -> StrideCollection<Self> {
StrideCollection(base: self, stride: step)
}
}
/// A wrapper that strides over a base sequence.
public struct StrideSequence<Base: Sequence>: Sequence {
@usableFromInline
internal let base: Base
@usableFromInline
internal let stride: Int
@usableFromInline
internal init(base: Base, stride: Int) {
precondition(stride > 0, "striding must be greater than zero")
self.base = base
self.stride = stride
}
}
extension StrideSequence {
/// An iterator over a `Stride` sequence.
public struct Iterator: IteratorProtocol {
@usableFromInline
internal var iterator: Base.Iterator
@usableFromInline
internal let stride: Int
@usableFromInline
internal var striding: Bool = false
@usableFromInline
internal init(iterator: Base.Iterator, stride: Int) {
self.iterator = iterator
self.stride = stride
}
@inlinable
public mutating func next() -> Base.Element? {
guard striding else {
striding = true
return iterator.next()
}
for _ in 0..<stride - 1 {
guard iterator.next() != nil else { break }
}
return iterator.next()
}
}
@inlinable
public func makeIterator() -> Iterator {
Iterator(iterator: base.makeIterator(), stride: stride)
}
}
extension StrideSequence {
@inlinable
public func striding(by step: Int) -> Self {
Self(base: base, stride: stride * step)
}
}
/// A wrapper that strides over a base collection.
public struct StrideCollection<Base: Collection> {
@usableFromInline
internal let base: Base
@usableFromInline
internal let stride: Int
@usableFromInline
internal init(base: Base, stride: Int) {
precondition(stride > 0, "striding must be greater than zero")
self.base = base
self.stride = stride
}
}
extension StrideCollection {
@inlinable
public func striding(by step: Int) -> Self {
Self(base: base, stride: stride * step)
}
}
extension StrideCollection: Collection {
/// A position in a `Stride` collection.
public struct Index: Comparable {
@usableFromInline
internal let base: Base.Index
@usableFromInline
internal init(_ base: Base.Index) {
self.base = base
}
@inlinable
public static func < (lhs: Index, rhs: Index) -> Bool {
lhs.base < rhs.base
}
}
@inlinable
public var startIndex: Index {
Index(base.startIndex)
}
@inlinable
public var endIndex: Index {
Index(base.endIndex)
}
@inlinable
public subscript(i: Index) -> Base.Element {
base[i.base]
}
@inlinable
public func index(after i: Index) -> Index {
precondition(i.base < base.endIndex, "Advancing past end index")
return index(i, offsetBy: 1)
}
@inlinable
public func index(
_ i: Index,
offsetBy n: Int,
limitedBy limit: Index
) -> Index? {
guard n != 0 else { return i }
guard limit != i else { return nil }
return n > 0
? offsetForward(i, offsetBy: n, limitedBy: limit)
: offsetBackward(i, offsetBy: -n, limitedBy: limit)
}
@usableFromInline
internal func offsetForward(
_ i: Index,
offsetBy n: Int,
limitedBy limit: Index
) -> Index? {
if limit < i {
if let idx = base.index(
i.base,
offsetBy: n * stride,
limitedBy: base.endIndex
) {
return Index(idx)
} else {
assert(distance(from: i, to: endIndex) == n, "Advancing past end index")
return endIndex
}
} else if let idx = base.index(
i.base,
offsetBy: n * stride,
limitedBy: limit.base
) {
return Index(idx)
} else {
return distance(from: i, to: limit) == n
? endIndex
: nil
}
}
@usableFromInline
internal func offsetBackward(
_ i: Index,
offsetBy n: Int,
limitedBy limit: Index
) -> Index? {
let distance = i == endIndex
? -((base.count - 1) % stride + 1) + (n - 1) * -stride
: n * -stride
return base.index(
i.base,
offsetBy: distance,
limitedBy: limit.base
).map(Index.init)
}
@inlinable
public var count: Int {
base.isEmpty ? 0 : (base.count - 1) / stride + 1
}
@inlinable
public func distance(from start: Index, to end: Index) -> Int {
let distance = base.distance(from: start.base, to: end.base)
return distance / stride + (distance % stride).signum()
}
@inlinable
public func index(_ i: Index, offsetBy distance: Int) -> Index {
precondition(distance <= 0 || i.base < base.endIndex, "Advancing past end index")
precondition(distance >= 0 || i.base > base.startIndex, "Incrementing past start index")
let limit = distance > 0 ? endIndex : startIndex
let idx = index(i, offsetBy: distance, limitedBy: limit)
precondition(idx != nil, "The distance \(distance) is not valid for this collection")
return idx!
}
}
extension StrideCollection: BidirectionalCollection
where Base: RandomAccessCollection {
@inlinable
public func index(before i: Index) -> Index {
precondition(i.base > base.startIndex, "Incrementing past start index")
return index(i, offsetBy: -1)
}
}
extension StrideCollection: RandomAccessCollection where Base: RandomAccessCollection {}
extension StrideCollection: Equatable where Base.Element: Equatable {
@inlinable
public static func == (lhs: StrideCollection, rhs: StrideCollection) -> Bool {
lhs.elementsEqual(rhs, by: ==)
}
}
extension StrideCollection: Hashable where Base.Element: Hashable {
@inlinable
public func hash(into hasher: inout Hasher) {
hasher.combine(stride)
for element in self {
hasher.combine(element)
}
}
}
extension StrideCollection.Index: Hashable where Base.Index: Hashable {}
-88
View File
@@ -1,88 +0,0 @@
//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift Algorithms open source project
//
// Copyright (c) 2021 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
//
//===----------------------------------------------------------------------===//
//===----------------------------------------------------------------------===//
// suffix(while:)
//===----------------------------------------------------------------------===//
extension BidirectionalCollection {
/// Returns a subsequence containing the elements from the end until
/// `predicate` returns `false` and skipping the remaining elements.
///
/// - Parameter predicate: A closure that takes an element of the
/// sequence as its argument and returns `true` if the element should
/// be included or `false` if it should be excluded. Once the predicate
/// returns `false` it will not be called again.
///
/// - Complexity: O(*n*), where *n* is the length of the collection.
@inlinable
public func suffix(
while predicate: (Element) throws -> Bool
) rethrows -> SubSequence {
try self[startOfSuffix(while: predicate)...]
}
}
//===----------------------------------------------------------------------===//
// endOfPrefix(while:)
//===----------------------------------------------------------------------===//
extension Collection {
/// Returns the exclusive upper bound of the prefix of elements that satisfy
/// the predicate.
///
/// - Parameter predicate: A closure that takes an element of the collection
/// as its argument and returns `true` if the element is part of the prefix
/// or `false` if it is not. Once the predicate returns `false` it will not
/// be called again.
///
/// - Complexity: O(*n*), where *n* is the length of the collection.
@usableFromInline
internal func endOfPrefix(
while predicate: (Element) throws -> Bool
) rethrows -> Index {
var index = startIndex
while try index != endIndex && predicate(self[index]) {
formIndex(after: &index)
}
return index
}
}
//===----------------------------------------------------------------------===//
// startOfSuffix(while:)
//===----------------------------------------------------------------------===//
extension BidirectionalCollection {
/// Returns the inclusive lower bound of the suffix of elements that satisfy
/// the predicate.
///
/// - Parameter predicate: A closure that takes an element of the collection
/// as its argument and returns `true` if the element is part of the suffix
/// or `false` if it is not. Once the predicate returns `false` it will not
/// be called again.
///
/// - Complexity: O(*n*), where *n* is the length of the collection.
@usableFromInline
internal func startOfSuffix(
while predicate: (Element) throws -> Bool
) rethrows -> Index {
var index = endIndex
while index != startIndex {
let after = index
formIndex(before: &index)
if try !predicate(self[index]) {
return after
}
}
return index
}
}
+28 -14
View File
@@ -10,27 +10,41 @@
//===----------------------------------------------------------------------===//
extension BidirectionalCollection {
/// Returns a `SubSequence` formed by discarding all elements at the start and
/// end of the collection which satisfy the given predicate.
/// Returns a `SubSequence` formed by discarding all elements at the start and end of the collection
/// which satisfy the given predicate.
///
/// This example uses `trimming(while:)` to get a substring without the white
/// space at the beginning and end of the string:
/// This example uses `trimming(where:)` to get a substring without the white space at the
/// beginning and end of the string:
///
/// let myString = " hello, world "
/// print(myString.trimming(while: \.isWhitespace)) // "hello, world"
/// ```
/// let myString = " hello, world "
/// print(myString.trimming(where: \.isWhitespace)) // "hello, world"
/// ```
///
/// - Parameters:
/// - predicate: A closure which determines if the element should be
/// omitted from the resulting slice.
/// - parameters:
/// - predicate: A closure which determines if the element should be omitted from the
/// resulting slice.
///
/// - Complexity: O(*n*), where *n* is the length of this collection.
/// - complexity: `O(n)`, where `n` is the length of this collection.
///
@inlinable
public func trimming(
while predicate: (Element) throws -> Bool
where predicate: (Element) throws -> Bool
) rethrows -> SubSequence {
let start = try endOfPrefix(while: predicate)
let end = try self[start...].startOfSuffix(while: predicate)
return self[start..<end]
// Consume elements from the front.
let sliceStart = try firstIndex { try predicate($0) == false } ?? endIndex
// sliceEnd is the index _after_ the last index to match the predicate.
var sliceEnd = endIndex
while sliceStart != sliceEnd {
let idxBeforeSliceEnd = index(before: sliceEnd)
guard try predicate(self[idxBeforeSliceEnd]) else {
return self[sliceStart..<sliceEnd]
}
sliceEnd = idxBeforeSliceEnd
}
// Trimmed everything.
return self[Range(uncheckedBounds: (sliceStart, sliceStart))]
}
}
-352
View File
@@ -1,352 +0,0 @@
//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift Algorithms open source project
//
// Copyright (c) 2020 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
//
//===----------------------------------------------------------------------===//
//===----------------------------------------------------------------------===//
// windows(ofCount:)
//===----------------------------------------------------------------------===//
extension Collection {
/// Returns a collection of all the overlapping slices of a given size.
///
/// Use this method to iterate over overlapping subsequences of this
/// collection. This example prints every five character substring of `str`:
///
/// let str = "Hello, world!"
/// for substring in str.windows(ofCount: 5) {
/// print(substring)
/// }
/// // "Hello"
/// // "ello,"
/// // "llo, "
/// // "lo, W"
/// // ...
/// // "orld!"
///
/// - Parameter count: The number of elements in each window subsequence.
/// - Returns: A collection of subsequences of this collection, each with
/// length `count`. If this collection is shorter than `count`, the
/// resulting collection is empty.
///
/// - Complexity: O(1) if the collection conforms to
/// `RandomAccessCollection`, otherwise O(*k*) where `k` is `count`.
/// Access to successive windows is O(1).
@inlinable
public func windows(ofCount count: Int) -> Windows<Self> {
Windows(base: self, size: count)
}
}
/// A collection wrapper that presents a sliding window over the elements of
/// a collection.
public struct Windows<Base: Collection> {
public let base: Base
public let size: Int
@usableFromInline
internal var firstUpperBound: Base.Index?
@usableFromInline
internal init(base: Base, size: Int) {
precondition(size > 0, "Windows size must be greater than zero")
self.base = base
self.size = size
self.firstUpperBound =
base.index(base.startIndex, offsetBy: size, limitedBy: base.endIndex)
}
}
extension Windows: Collection {
/// A position in a `Windows` collection.
public struct Index: Comparable {
@usableFromInline
internal var lowerBound: Base.Index
@usableFromInline
internal var upperBound: Base.Index
@usableFromInline
internal init(lowerBound: Base.Index, upperBound: Base.Index) {
self.lowerBound = lowerBound
self.upperBound = upperBound
}
@inlinable
public static func == (lhs: Index, rhs: Index) -> Bool {
lhs.lowerBound == rhs.lowerBound
}
@inlinable
public static func < (lhs: Index, rhs: Index) -> Bool {
lhs.lowerBound < rhs.lowerBound
}
}
@inlinable
public var startIndex: Index {
if let upperBound = firstUpperBound {
return Index(lowerBound: base.startIndex, upperBound: upperBound)
} else {
return endIndex
}
}
@inlinable
public var endIndex: Index {
Index(lowerBound: base.endIndex, upperBound: base.endIndex)
}
@inlinable
public subscript(index: Index) -> Base.SubSequence {
precondition(
index.lowerBound != index.upperBound,
"Windows index is out of range")
return base[index.lowerBound..<index.upperBound]
}
@inlinable
public func index(after index: Index) -> Index {
precondition(index < endIndex, "Advancing past end index")
guard index.upperBound < base.endIndex else { return endIndex }
return Index(
lowerBound: base.index(after: index.lowerBound),
upperBound: base.index(after: index.upperBound)
)
}
@inlinable
public func index(_ i: Index, offsetBy distance: Int) -> Index {
guard distance != 0 else { return i }
return distance > 0
? offsetForward(i, by: distance)
: offsetBackward(i, by: -distance)
}
@inlinable
public func index(
_ i: Index,
offsetBy distance: Int,
limitedBy limit: Index
) -> Index? {
guard distance != 0 else { return i }
guard limit != i else { return nil }
if distance > 0 {
return limit > i
? offsetForward(i, by: distance, limitedBy: limit)
: offsetForward(i, by: distance)
} else {
return limit < i
? offsetBackward(i, by: -distance, limitedBy: limit)
: offsetBackward(i, by: -distance)
}
}
@usableFromInline
internal func offsetForward(_ i: Index, by distance: Int) -> Index {
guard let index = offsetForward(i, by: distance, limitedBy: endIndex)
else { fatalError("Index is out of bounds") }
return index
}
@usableFromInline
internal func offsetBackward(_ i: Index, by distance: Int) -> Index {
guard let index = offsetBackward(i, by: distance, limitedBy: startIndex)
else { fatalError("Index is out of bounds") }
return index
}
@usableFromInline
internal func offsetForward(
_ i: Index, by distance: Int, limitedBy limit: Index
) -> Index? {
assert(distance > 0)
assert(limit > i)
// `endIndex` and the index before it both have `base.endIndex` as their
// upper bound, so we first advance to the base index _before_ the upper
// bound of the output, in order to avoid advancing past the end of `base`
// when advancing to `endIndex`.
//
// Advancing by 4:
//
// input: [x|x x x x x|x x x x] [x x|x x x x x|x x x]
// |> > >|>| or |> > >|
// output: [x x x x x|x x x x x] [x x x x x x x x x x] (`endIndex`)
if distance >= size {
// Avoid traversing `self[i.lowerBound..<i.upperBound]` when the lower
// bound of the output is greater than or equal to the upper bound of the
// input.
// input: [x|x x x x|x x x x x x x]
// |> >|> > >|>|
// output: [x x x x x x x|x x x x|x]
guard limit.lowerBound >= i.upperBound,
let lowerBound = base.index(
i.upperBound,
offsetBy: distance - size,
limitedBy: limit.lowerBound),
let indexBeforeUpperBound = base.index(
lowerBound,
offsetBy: size - 1,
limitedBy: limit.upperBound)
else { return nil }
// If `indexBeforeUpperBound` equals `base.endIndex`, we're advancing to
// `endIndex`.
guard indexBeforeUpperBound != base.endIndex else { return endIndex }
return Index(
lowerBound: lowerBound,
upperBound: base.index(after: indexBeforeUpperBound))
} else {
// input: [x|x x x x x x|x x x x x]
// |> > > >| |> > >|>|
// output: [x x x x x|x x x x x x|x]
guard let indexBeforeUpperBound = base.index(
i.upperBound,
offsetBy: distance - 1,
limitedBy: limit.upperBound)
else { return nil }
// If `indexBeforeUpperBound` equals the limit, the upper bound itself
// exceeds it.
guard indexBeforeUpperBound != limit.upperBound || limit == endIndex
else { return nil }
// If `indexBeforeUpperBound` equals `base.endIndex`, we're advancing to
// `endIndex`.
guard indexBeforeUpperBound != base.endIndex else { return endIndex }
return Index(
lowerBound: base.index(i.lowerBound, offsetBy: distance),
upperBound: base.index(after: indexBeforeUpperBound))
}
}
@usableFromInline
internal func offsetBackward(
_ i: Index, by distance: Int, limitedBy limit: Index
) -> Index? {
assert(distance > 0)
assert(limit < i)
if i == endIndex {
// Advance `base.endIndex` by `distance - 1`, because the index before
// `endIndex` also has `base.endIndex` as its upper bound.
//
// Advancing by 4:
//
// input: [x x x x x x x x x x] (`endIndex`)
// |< < < < <|< < <|
// output: [x x|x x x x x|x x x]
guard let upperBound = base.index(
base.endIndex,
offsetBy: -(distance - 1),
limitedBy: limit.upperBound)
else { return nil }
return Index(
lowerBound: base.index(upperBound, offsetBy: -size),
upperBound: upperBound)
} else if distance >= size {
// Avoid traversing `self[i.lowerBound..<i.upperBound]` when the upper
// bound of the output is less than or equal to the lower bound of the
// input.
//
// input: [x x x x x x x|x x x x|x]
// |< < < <|< <|
// output: [x|x x x x|x x x x x x x]
guard limit.upperBound <= i.lowerBound,
let upperBound = base.index(
i.lowerBound,
offsetBy: -(distance - size),
limitedBy: limit.upperBound)
else { return nil }
return Index(
lowerBound: base.index(upperBound, offsetBy: -size),
upperBound: upperBound)
} else {
// input: [x x x x x|x x x x x x|x]
// |< < < <| |< < < <|
// output: [x|x x x x x x|x x x x x]
guard let lowerBound = base.index(
i.lowerBound,
offsetBy: -distance,
limitedBy: limit.lowerBound)
else { return nil }
return Index(
lowerBound: lowerBound,
upperBound: base.index(i.lowerBound, offsetBy: -distance))
}
}
@inlinable
public func distance(from start: Index, to end: Index) -> Int {
guard start <= end else { return -distance(from: end, to: start) }
guard start != end else { return 0 }
guard end < endIndex else {
// We add 1 here because the index before `endIndex` also has
// `base.endIndex` as its upper bound.
return base[start.upperBound...].count + 1
}
if start.upperBound <= end.lowerBound {
// The distance between `start.lowerBound` and `start.upperBound` is
// already known.
//
// start: [x|x x x x|x x x x x x x]
// |- - - -|> >|
// end: [x x x x x x x|x x x x|x]
return size + base[start.upperBound..<end.lowerBound].count
} else {
// start: [x|x x x x x x|x x x x x]
// |> > > >|
// end: [x x x x x|x x x x x x|x]
return base[start.lowerBound..<end.lowerBound].count
}
}
}
extension Windows: BidirectionalCollection where Base: BidirectionalCollection {
@inlinable
public func index(before index: Index) -> Index {
precondition(index > startIndex, "Incrementing past start index")
if index == endIndex {
return Index(
lowerBound: base.index(index.lowerBound, offsetBy: -size),
upperBound: index.upperBound
)
} else {
return Index(
lowerBound: base.index(before: index.lowerBound),
upperBound: base.index(before: index.upperBound)
)
}
}
}
extension Windows: LazySequenceProtocol where Base: LazySequenceProtocol {}
extension Windows: LazyCollectionProtocol where Base: LazyCollectionProtocol {}
extension Windows: RandomAccessCollection where Base: RandomAccessCollection {}
extension Windows: Equatable where Base: Equatable {}
extension Windows: Hashable where Base: Hashable, Base.Index: Hashable {}
extension Windows.Index: Hashable where Base.Index: Hashable {}
-140
View File
@@ -1,140 +0,0 @@
import Darwin
import Algorithms
struct Benchmark {
var name: String
var `default`: Int
var body: (Int) -> Int
}
let benchmarks = [
Benchmark(name: "chain", default: 100) { count in
let x = String(repeating: "_", count: 10_000)
.chained(with: String(repeating: "-", count: 10_000))
.chained(with: "0")
var v = 0
for _ in 0..<count {
let i = x.firstIndex(of: "0")!
let d = x.distance(from: x.startIndex, to: i)
v &+= d
}
return v
},
Benchmark(name: "chunked", default: 1000) { count in
let x = (1...1000).shuffled()
var v = 0
for _ in 0..<count {
let y = x.chunked(by: <=)
v &+= y.count
}
return v
},
Benchmark(name: "lazy chunked", default: 1000) { count in
let x = (1...1000).shuffled()
var v = 0
for _ in 0..<count {
let y = x.lazy.chunked(by: <=)
v &+= y.count
}
return v
},
Benchmark(name: "combinations", default: 100) { count in
let x = 1...30
var v = 0
for _ in 0..<count {
let y = x.combinations(ofCount: 4)
let combo = y.first(where: { combo in combo.allSatisfy { $0.isMultiple(of: 2) }})!
v &+= combo.reduce(0, +)
}
return v
},
Benchmark(name: "stable partition", default: 100) { count in
var v = 0
for _ in 0..<count {
var x = Array(1...10000)
let i = x.stablePartition(by: { $0.isMultiple(of: 3) })
v &+= i
}
return v
},
Benchmark(name: "permutations", default: 10) { count in
let x = 1...20
var v = 0
for _ in 0..<count {
let y = x.permutations(ofCount: 4)
let perm = y.first(where: { perm in perm.allSatisfy { $0.isMultiple(of: 2) }})!
v &+= perm.reduce(0, +)
}
return v
},
Benchmark(name: "product", default: 1000) { count in
let x = product(1...100, "abcdefghijklmnopqrstuvwxyz")
var v = 0
for _ in 0..<count {
let i = x.firstIndex(where: { $0 == 77 && $1 == "m" })!
let d = x.distance(from: x.startIndex, to: i)
v &+= d
}
return v
},
Benchmark(name: "sample", default: 1000) { count in
let x = 1...10000
var v = 0
for _ in 0..<count {
let r = x.randomSample(count: 20)
v &+= r.reduce(0, +)
}
return v
},
Benchmark(name: "stable sample", default: 1000) { count in
let x = 1...10000
var v = 0
for _ in 0..<count {
let r = x.randomStableSample(count: 20)
v &+= r.reduce(0, +)
}
return v
},
Benchmark(name: "uniqued", default: 1000) { count in
let x = repeatElement(1...1000, count: 1000)
var v = 0
for _ in 0..<count {
let r = x.uniqued()
v &+= r.count
}
return v
},
]
func printChoices() -> Never {
print(benchmarks.enumerated().map { "\($0): \($1.name)" }.joined(separator: "\n"))
exit(0)
}
if CommandLine.arguments.count <= 1 {
printChoices()
} else {
guard let choice = Int(CommandLine.arguments[1]), benchmarks.indices.contains(choice) else {
print("Invalid choice:")
printChoices()
}
let bench = benchmarks[choice]
let count: Int
if CommandLine.arguments.count > 2, let c = Int(CommandLine.arguments[2]) {
count = c
} else {
count = bench.default
}
print(bench.body(count))
}
+2 -71
View File
@@ -73,76 +73,7 @@ final class ChunkedTests: XCTestCase {
}
func testChunkedLazy() {
XCTAssertLazySequence(fruits.lazy.chunked(by: { $0.first == $1.first }))
XCTAssertLazySequence(fruits.lazy.chunked(on: { $0.first }))
}
//===----------------------------------------------------------------------===//
// Tests for `chunks(ofCount:)`
//===----------------------------------------------------------------------===//
func testChunksOfCount() {
XCTAssertEqualSequences([Int]().chunks(ofCount: 1), [])
XCTAssertEqualSequences([Int]().chunks(ofCount: 5), [])
let collection1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
XCTAssertEqualSequences(collection1.chunks(ofCount: 1),
[[1], [2], [3], [4], [5], [6], [7], [8], [9], [10]])
XCTAssertEqualSequences(collection1.chunks(ofCount: 3),
[[1, 2, 3], [4, 5, 6], [7, 8, 9], [10]])
XCTAssertEqualSequences(collection1.chunks(ofCount: 5),
[[1, 2, 3, 4, 5], [6, 7, 8, 9, 10]])
XCTAssertEqualSequences(collection1.chunks(ofCount: 11),
[[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]])
let collection2 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
XCTAssertEqualSequences(collection2.chunks(ofCount: 3),
[[1, 2, 3], [4, 5, 6], [7, 8, 9], [10, 11]])
}
func testChunksOfCountBidirectional() {
let collection1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
XCTAssertEqualSequences(collection1.chunks(ofCount: 1).reversed(),
[[10], [9], [8], [7], [6], [5], [4], [3], [2], [1]])
XCTAssertEqualSequences(collection1.chunks(ofCount: 3).reversed(),
[[10], [7, 8, 9], [4, 5, 6], [1, 2, 3]])
XCTAssertEqualSequences(collection1.chunks(ofCount: 5).reversed(),
[[6, 7, 8, 9, 10], [1, 2, 3, 4, 5]])
XCTAssertEqualSequences(collection1.chunks(ofCount: 11).reversed(),
[[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]])
let collection2 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
XCTAssertEqualSequences(collection2.chunks(ofCount: 3).reversed(),
[[10, 11], [7, 8, 9], [4, 5, 6], [1, 2, 3]])
}
func testChunksOfCountCount() {
XCTAssertEqual([Int]().chunks(ofCount: 1).count, 0)
XCTAssertEqual([Int]().chunks(ofCount: 5).count, 0)
let collection1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
XCTAssertEqual(collection1.chunks(ofCount: 1).count, 10)
XCTAssertEqual(collection1.chunks(ofCount: 3).count, 4)
XCTAssertEqual(collection1.chunks(ofCount: 5).count, 2)
XCTAssertEqual(collection1.chunks(ofCount: 11).count, 1)
let collection2 = (1...50).map { $0 }
XCTAssertEqual(collection2.chunks(ofCount: 9).count, 6)
}
func testEmptyChunksOfCountTraversal() {
let emptyChunks = [Int]().chunks(ofCount: 1)
validateIndexTraversals(emptyChunks)
}
func testChunksOfCountTraversal() {
for i in 1..<10 {
let collection = (1...50).map { $0 }
let chunks = collection.chunks(ofCount: i)
validateIndexTraversals(chunks)
}
XCTAssertLazy(fruits.lazy.chunked(by: { $0.first == $1.first }))
XCTAssertLazy(fruits.lazy.chunked(on: { $0.first }))
}
}
@@ -2,7 +2,7 @@
//
// This source file is part of the Swift Algorithms open source project
//
// Copyright (c) 2020-2021 Apple Inc. and the Swift project authors
// Copyright (c) 2020 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
@@ -13,114 +13,33 @@ import XCTest
import Algorithms
final class CombinationsTests: XCTestCase {
func testCount() {
let c = "ABCD"
let c0 = c.combinations(ofCount: 0).count
XCTAssertEqual(c0, 1)
let c1 = c.combinations(ofCount: 1).count
XCTAssertEqual(c1, 4)
let c2 = c.combinations(ofCount: 2).count
XCTAssertEqual(c2, 6)
let c3 = c.combinations(ofCount: 3).count
XCTAssertEqual(c3, 4)
let c4 = c.combinations(ofCount: 4).count
XCTAssertEqual(c4, 1)
let c5 = c.combinations(ofCount: 0...0).count
XCTAssertEqual(c5, 1)
let c6 = c.combinations(ofCount: 1...1).count
XCTAssertEqual(c6, 4)
let c7 = c.combinations(ofCount: 1...2).count
XCTAssertEqual(c7, 10)
let c8 = c.combinations(ofCount: 1...3).count
XCTAssertEqual(c8, 14)
let c9 = c.combinations(ofCount: 2...4).count
XCTAssertEqual(c9, 11)
// `k` greater than element count results in same number of combinations
let c10 = c.combinations(ofCount: 3...10).count
XCTAssertEqual(c10, 5)
// `k` greater than element count results in same number of combinations
let c11 = c.combinations(ofCount: 4...10).count
XCTAssertEqual(c11, 1)
// `k` entirely greater than element count results in no combinations
let c12 = c.combinations(ofCount: 5...10).count
XCTAssertEqual(c12, 0)
let c13 = c.combinations(ofCount: 0...).count
XCTAssertEqual(c13, 16)
let c14 = c.combinations(ofCount: ...3).count
XCTAssertEqual(c14, 15)
let c15 = c.combinations(ofCount: 0...).count
XCTAssertEqual(c15, 16)
}
func testCombinations() {
let c = "ABCD"
let c1 = c.combinations(ofCount: 1)
XCTAssertEqual(["A", "B", "C", "D"], c1.map { String($0) })
let c2 = c.combinations(ofCount: 2)
XCTAssertEqual(["AB", "AC", "AD", "BC", "BD", "CD"], c2.map { String($0) })
let c3 = c.combinations(ofCount: 3)
XCTAssertEqual(["ABC", "ABD", "ACD", "BCD"], c3.map { String($0) })
let c4 = c.combinations(ofCount: 4)
XCTAssertEqual(["ABCD"], c4.map { String($0) })
let c5 = c.combinations(ofCount: 2...4)
XCTAssertEqual(["AB", "AC", "AD", "BC", "BD", "CD", "ABC", "ABD", "ACD", "BCD", "ABCD"], c5.map { String($0) })
let c6 = c.combinations(ofCount: 0...4)
XCTAssertEqual(["", "A", "B", "C", "D", "AB", "AC", "AD", "BC", "BD", "CD", "ABC", "ABD", "ACD", "BCD", "ABCD"], c6.map { String($0) })
let c7 = c.combinations(ofCount: 0...)
XCTAssertEqual(["", "A", "B", "C", "D", "AB", "AC", "AD", "BC", "BD", "CD", "ABC", "ABD", "ACD", "BCD", "ABCD"], c7.map { String($0) })
let c8 = c.combinations(ofCount: ...4)
XCTAssertEqual(["", "A", "B", "C", "D", "AB", "AC", "AD", "BC", "BD", "CD", "ABC", "ABD", "ACD", "BCD", "ABCD"], c8.map { String($0) })
let c9 = c.combinations(ofCount: ...3)
XCTAssertEqual(["", "A", "B", "C", "D", "AB", "AC", "AD", "BC", "BD", "CD", "ABC", "ABD", "ACD", "BCD"], c9.map { String($0) })
let c10 = c.combinations(ofCount: 1...)
XCTAssertEqual(["A", "B", "C", "D", "AB", "AC", "AD", "BC", "BD", "CD", "ABC", "ABD", "ACD", "BCD", "ABCD"], c10.map { String($0) })
}
func testEmpty() {
// `k == 0` results in one zero-length combination
XCTAssertEqualSequences([[]], "".combinations(ofCount: 0))
XCTAssertEqualSequences([[]], "".combinations(ofCount: 0...0))
XCTAssertEqualSequences([[]], "ABCD".combinations(ofCount: 0))
XCTAssertEqualSequences([[]], "ABCD".combinations(ofCount: 0...0))
// `k` greater than element count results in zero combinations
XCTAssertEqualSequences([], "".combinations(ofCount: 5))
XCTAssertEqualSequences([], "".combinations(ofCount: 5...10))
XCTAssertEqualSequences([], "ABCD".combinations(ofCount: 5))
XCTAssertEqualSequences([], "ABCD".combinations(ofCount: 5...10))
}
func testCombinationsLazy() {
XCTAssertLazySequence("ABC".lazy.combinations(ofCount: 1))
XCTAssertLazySequence("ABC".lazy.combinations(ofCount: 1...3))
XCTAssertLazySequence("ABC".lazy.combinations(ofCount: 1...))
XCTAssertLazySequence("ABC".lazy.combinations(ofCount: ...3))
XCTAssertLazySequence("ABC".lazy.combinations(ofCount: 0...))
XCTAssertLazy("ABC".lazy.combinations(ofCount: 1))
}
}
+1 -1
View File
@@ -41,6 +41,6 @@ final class CycleTests: XCTestCase {
}
func testCycleLazy() {
XCTAssertLazySequence((1...4).lazy.cycled())
XCTAssertLazy((1...4).lazy.cycled())
}
}
@@ -0,0 +1,84 @@
//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift Algorithms open source project
//
// Copyright (c) 2020 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
//
//===----------------------------------------------------------------------===//
import XCTest
import Algorithms
extension Collection {
fileprivate func range(at offsets: Range<Int>) -> Range<Index> {
let low = index(startIndex, offsetBy: offsets.lowerBound)
let high = index(low, offsetBy: offsets.count)
return low..<high
}
}
fileprivate let input = "abababaabaaba"
final class FindTests: XCTestCase {
func testFirstRangeOf() {
XCTAssertNil("".firstRange(of: "input"))
XCTAssertNil("".firstRange(of: ""))
XCTAssertNil(input.firstRange(of: ""))
XCTAssertEqual(input.firstRange(of: "ababa"), input.range(at: 0..<5))
XCTAssertEqual(input.firstRange(of: "baba"), input.range(at: 1..<5))
XCTAssertEqual(input.firstRange(of: "abaa"), input.range(at: 4..<8))
XCTAssertEqual(input.firstRange(of: "aabaaba"), input.range(at: 6..<13))
XCTAssertEqual(input.firstRange(of: input), input.range(at: 0..<13))
XCTAssertNil(input.firstRange(of: "aabaabaa"))
XCTAssertNil(input.firstRange(of: "abababab"))
XCTAssertEqual(input.dropFirst().firstRange(of: "ababa"), input.range(at: 2..<7))
XCTAssertEqual(input.dropFirst(5).firstRange(of: "abaa"), input.range(at: 7..<11))
XCTAssertNil(input.dropFirst(7).firstRange(of: "aabaaba"))
}
func testLastRangeOf() {
XCTAssertNil("".lastRange(of: "a"))
XCTAssertNil("".lastRange(of: ""))
XCTAssertNil(input.lastRange(of: ""))
XCTAssertEqual(input.lastRange(of: "ababa"), input.range(at: 2..<7))
XCTAssertEqual(input.lastRange(of: "baba"), input.range(at: 3..<7))
XCTAssertEqual(input.lastRange(of: "abaa"), input.range(at: 7..<11))
XCTAssertEqual(input.lastRange(of: "aabaaba"), input.range(at: 6..<13))
XCTAssertEqual(input.lastRange(of: input), input.range(at: 0..<13))
XCTAssertNil(input.lastRange(of: "aabaabaa"))
XCTAssertNil(input.lastRange(of: "abababab"))
XCTAssertEqual(input.dropLast(7).lastRange(of: "ababa"), input.range(at: 0..<5))
XCTAssertEqual(input.dropLast(3).lastRange(of: "abaa"), input.range(at: 4..<8))
XCTAssertNil(input.dropLast(6).lastRange(of: "abababaa"))
}
func testAllRangesOf() {
XCTAssertEqual("".allRanges(of: "abc").count, 0)
XCTAssertEqual("".allRanges(of: "").count, 0)
XCTAssertEqual(input.allRanges(of: "abc").count, 0)
XCTAssertEqual(input.allRanges(of: "").count, 0)
XCTAssertEqual(input.allRanges(of: "ab").count, 5)
XCTAssertEqual(input.allRanges(of: "ba").count, 5)
XCTAssertEqual(input.allRanges(of: "aba").count, 5)
XCTAssertEqualSequences(
input.allRanges(of: "ababa"),
[input.range(at: 0..<5), input.range(at: 2..<7)])
XCTAssertEqualSequences(
input.allRanges(of: "aaba"),
[input.range(at: 6..<10), input.range(at: 9..<13)])
XCTAssertEqualSequences(
input.allRanges(of: "aaba").reversed(),
[input.range(at: 9..<13), input.range(at: 6..<10)])
print(input.allRanges(of: "aaba").prefix(2))
}
}
@@ -1,23 +0,0 @@
//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift Algorithms open source project
//
// Copyright (c) 2020 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
//
//===----------------------------------------------------------------------===//
import XCTest
import Algorithms
final class FirstNonNilTests: XCTestCase {
func testFirstNonNil() {
XCTAssertNil([].firstNonNil { $0 })
XCTAssertNil(["A", "B", "C"].firstNonNil { Int($0) })
XCTAssertNil(["A", "B", "C"].firstNonNil { _ in nil })
XCTAssertEqual(["A", "B", "10"].firstNonNil { Int($0) }, 10)
XCTAssertEqual(["20", "B", "10"].firstNonNil { Int($0) }, 20)
}
}
@@ -29,6 +29,6 @@ final class IndexedTests: XCTestCase {
}
func testIndexedLazy() {
XCTAssertLazyCollection("ABCD".lazy.indexed())
XCTAssertLazy("ABCD".lazy.indexed())
}
}
@@ -1,65 +0,0 @@
//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift Algorithms open source project
//
// Copyright (c) 2020 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
//
//===----------------------------------------------------------------------===//
import XCTest
import Algorithms
final class IntersperseTests: XCTestCase {
func testSequence() {
let interspersed = (1...).prefix(5).interspersed(with: 0)
XCTAssertEqualSequences(interspersed, [1,0,2,0,3,0,4,0,5])
}
func testSequenceEmpty() {
let interspersed = (1...).prefix(0).interspersed(with: 0)
XCTAssertEqualSequences(interspersed, [])
}
func testString() {
let interspersed = "ABCDE".interspersed(with: "-")
XCTAssertEqualSequences(interspersed, "A-B-C-D-E")
validateIndexTraversals(interspersed)
}
func testStringEmpty() {
let interspersed = "".interspersed(with: "-")
XCTAssertEqualSequences(interspersed, "")
validateIndexTraversals(interspersed)
}
func testArray() {
let interspersed = [1,2,3,4].interspersed(with: 0)
XCTAssertEqualSequences(interspersed, [1,0,2,0,3,0,4])
validateIndexTraversals(interspersed)
}
func testArrayEmpty() {
let interspersed = [].interspersed(with: 0)
XCTAssertEqualSequences(interspersed, [])
validateIndexTraversals(interspersed)
}
func testCollection() {
let interspersed = ["A","B","C","D"].interspersed(with: "-")
XCTAssertEqual(interspersed.count, 7)
}
func testBidirectionalCollection() {
let reversed = "ABCDE".interspersed(with: "-").reversed()
XCTAssertEqualSequences(reversed, "E-D-C-B-A")
validateIndexTraversals(reversed)
}
func testIntersperseLazy() {
XCTAssertLazySequence((1...).prefix(0).lazy.interspersed(with: 0))
XCTAssertLazyCollection("ABCDE".lazy.interspersed(with: "-"))
}
}
@@ -1,840 +0,0 @@
//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift Algorithms open source project
//
// Copyright (c) 2021 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
//
//===----------------------------------------------------------------------===//
import Algorithms
import XCTest
//===----------------------------------------------------------------------===//
// Tests for `LazySplitSequence` and `LazySplitCollection`
//===----------------------------------------------------------------------===//
final class LazySplitTests: XCTestCase {
func testEmpty() {
Validator(
subject: [],
separator: .element(0),
maxSplits: 1
).validate()
}
// The following test names indicate the sequence being split, using the
// notation
// S: Separator
// E: Element
//
// Values of `maxSplit` are interesting when they're less than the number of
// splits that would occur with the default. That varies depending on whether
// empty subsequences are omitted or included. `Validator` tests both the
// default and the value provided, but there are cases below where the
// provided `maxSplit` isn't less than the number of splits when empty
// subsequences are omitted.
//===--------------------------------------------------------------------===//
// Length 1
//===--------------------------------------------------------------------===//
func testE() {
Validator(subject: [1], separator: .element(0), maxSplits: 0).validate()
}
func testS() {
Validator(subject: [0], separator: .element(0), maxSplits: 0).validate()
}
//===--------------------------------------------------------------------===//
// Length 2
//===--------------------------------------------------------------------===//
func testEE() {
Validator(subject: [1, 1], separator: .element(0), maxSplits: 0).validate()
}
func testSS() {
Validator(subject: [0, 0], separator: .element(0), maxSplits: 1).validate()
}
func testES() {
Validator(subject: [1, 0], separator: .element(0), maxSplits: 0).validate()
}
func testSE() {
Validator(subject: [0, 1], separator: .element(0), maxSplits: 0).validate()
}
//===--------------------------------------------------------------------===//
// Length 3
//===--------------------------------------------------------------------===//
func testEEE() {
Validator(subject: [1, 1, 1], separator: .element(0), maxSplits: 0)
.validate()
}
func testSSS() {
Validator(subject: [0, 0, 0], separator: .element(0), maxSplits: 1)
.validate()
}
func testAllEES() {
let permutations = [[1, 1, 0], [1, 0, 1], [0, 1, 1]]
for permutation in permutations {
Validator(subject: permutation, separator: .element(0), maxSplits: 0)
.validate()
}
}
func testAllESS() {
let permutations = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
for permutation in permutations {
Validator(subject: permutation, separator: .element(0), maxSplits: 1)
.validate()
}
}
//===--------------------------------------------------------------------===//
// Length 4 with less than two separators.
//===--------------------------------------------------------------------===//
func testEEEE() {
Validator(subject: [1, 1, 1, 1], separator: .element(0), maxSplits: 0)
.validate()
}
func testAllEEES() {
let permutations = [
[1, 1, 1, 0], [1, 1, 0, 1], [1, 0, 1, 1], [0, 1, 1, 1]
]
for permutation in permutations {
Validator(subject: permutation, separator: .element(0), maxSplits: 0)
.validate()
}
}
//===--------------------------------------------------------------------===//
// Unique permutations of sequences with at least two separators, so there can
// be multiple adjacent separators at the beginning, middle, or end.
//===--------------------------------------------------------------------===//
// All separators.
func testSSSS() {
Validator(subject: [0, 0, 0, 0], separator: .element(0), maxSplits: 1)
.validate()
}
// Equal numbers of elements and separators.
func testAllEESS() {
let permutations = [
[1, 1, 0, 0], [1, 0, 1, 0], [1, 0, 0, 1],
[0, 1, 1, 0], [0, 1, 0, 1], [0, 0, 1, 1],
]
for permutation in permutations {
Validator(subject: permutation, separator: .element(0), maxSplits: 1)
.validate()
}
}
// More separators than elements.
func testAllEESSS() {
let permutations = [
[1, 1, 0, 0, 0], [1, 0, 1, 0, 0], [1, 0, 0, 1, 0], [1, 0, 0, 0, 1],
[0, 1, 1, 0, 0], [0, 1, 0, 1, 0], [0, 1, 0, 0, 1], [0, 0, 1, 1, 0],
[0, 0, 1, 0, 1], [0, 0, 0, 1, 1],
]
for permutation in permutations {
Validator(subject: permutation, separator: .element(0), maxSplits: 1)
.validate()
}
}
// More elements than separators.
func testAllEEESS() {
let permutations = [
[1, 1, 1, 0, 0], [1, 1, 0, 1, 0], [1, 1, 0, 0, 1], [1, 0, 1, 1, 0],
[1, 0, 1, 0, 1], [1, 0, 0, 1, 1], [0, 1, 1, 1, 0], [0, 1, 1, 0, 1],
[0, 1, 0, 1, 1], [0, 0, 1, 1, 1],
]
for permutation in permutations {
Validator(subject: permutation, separator: .element(0), maxSplits: 1)
.validate()
}
}
//===--------------------------------------------------------------------===//
// Unique permutations of sequences with at least three separators.
//===--------------------------------------------------------------------===//
func testAllESSS() {
let permutations = [
[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1],
]
for permutation in permutations {
Validator(subject: permutation, separator: .element(0), maxSplits: 1)
.validate()
}
}
func testAllEEEESSS() {
let permutations = [
[1, 1, 1, 1, 0, 0, 0], [1, 1, 1, 0, 1, 0, 0], [1, 1, 1, 0, 0, 1, 0],
[1, 1, 1, 0, 0, 0, 1], [1, 1, 0, 1, 1, 0, 0], [1, 1, 0, 1, 0, 1, 0],
[1, 1, 0, 1, 0, 0, 1], [1, 1, 0, 0, 1, 1, 0], [1, 1, 0, 0, 1, 0, 1],
[1, 1, 0, 0, 0, 1, 1], [1, 0, 1, 1, 1, 0, 0], [1, 0, 1, 1, 0, 1, 0],
[1, 0, 1, 1, 0, 0, 1], [1, 0, 1, 0, 1, 1, 0], [1, 0, 1, 0, 1, 0, 1],
[1, 0, 1, 0, 0, 1, 1], [1, 0, 0, 1, 1, 1, 0], [1, 0, 0, 1, 1, 0, 1],
[1, 0, 0, 1, 0, 1, 1], [1, 0, 0, 0, 1, 1, 1], [0, 1, 1, 1, 1, 0, 0],
[0, 1, 1, 1, 0, 1, 0], [0, 1, 1, 1, 0, 0, 1], [0, 1, 1, 0, 1, 1, 0],
[0, 1, 1, 0, 1, 0, 1], [0, 1, 1, 0, 0, 1, 1], [0, 1, 0, 1, 1, 1, 0],
[0, 1, 0, 1, 1, 0, 1], [0, 1, 0, 1, 0, 1, 1], [0, 1, 0, 0, 1, 1, 1],
[0, 0, 1, 1, 1, 1, 0], [0, 0, 1, 1, 1, 0, 1], [0, 0, 1, 1, 0, 1, 1],
[0, 0, 1, 0, 1, 1, 1], [0, 0, 0, 1, 1, 1, 1],
]
for permutation in permutations {
Validator(subject: permutation, separator: .element(0), maxSplits: 1)
.validate()
}
}
//===--------------------------------------------------------------------===//
// Unique permutations of sequences with at least four separators, so there
// can be two runs of multiple adjacent separators: beginning and end,
// beginning and middle, or end and middle.
//===--------------------------------------------------------------------===//
// Equal numbers of separators and elements.
func testAllEEEESSSS() {
let permutations = [
[1, 1, 1, 1, 0, 0, 0, 0], [1, 1, 1, 0, 1, 0, 0, 0],
[1, 1, 1, 0, 0, 1, 0, 0], [1, 1, 1, 0, 0, 0, 1, 0],
[1, 1, 1, 0, 0, 0, 0, 1], [1, 1, 0, 1, 1, 0, 0, 0],
[1, 1, 0, 1, 0, 1, 0, 0], [1, 1, 0, 1, 0, 0, 1, 0],
[1, 1, 0, 1, 0, 0, 0, 1], [1, 1, 0, 0, 1, 1, 0, 0],
[1, 1, 0, 0, 1, 0, 1, 0], [1, 1, 0, 0, 1, 0, 0, 1],
[1, 1, 0, 0, 0, 1, 1, 0], [1, 1, 0, 0, 0, 1, 0, 1],
[1, 1, 0, 0, 0, 0, 1, 1], [1, 0, 1, 1, 1, 0, 0, 0],
[1, 0, 1, 1, 0, 1, 0, 0], [1, 0, 1, 1, 0, 0, 1, 0],
[1, 0, 1, 1, 0, 0, 0, 1], [1, 0, 1, 0, 1, 1, 0, 0],
[1, 0, 1, 0, 1, 0, 1, 0], [1, 0, 1, 0, 1, 0, 0, 1],
[1, 0, 1, 0, 0, 1, 1, 0], [1, 0, 1, 0, 0, 1, 0, 1],
[1, 0, 1, 0, 0, 0, 1, 1], [1, 0, 0, 1, 1, 1, 0, 0],
[1, 0, 0, 1, 1, 0, 1, 0], [1, 0, 0, 1, 1, 0, 0, 1],
[1, 0, 0, 1, 0, 1, 1, 0], [1, 0, 0, 1, 0, 1, 0, 1],
[1, 0, 0, 1, 0, 0, 1, 1], [1, 0, 0, 0, 1, 1, 1, 0],
[1, 0, 0, 0, 1, 1, 0, 1], [1, 0, 0, 0, 1, 0, 1, 1],
[1, 0, 0, 0, 0, 1, 1, 1], [0, 1, 1, 1, 1, 0, 0, 0],
[0, 1, 1, 1, 0, 1, 0, 0], [0, 1, 1, 1, 0, 0, 1, 0],
[0, 1, 1, 1, 0, 0, 0, 1], [0, 1, 1, 0, 1, 1, 0, 0],
[0, 1, 1, 0, 1, 0, 1, 0], [0, 1, 1, 0, 1, 0, 0, 1],
[0, 1, 1, 0, 0, 1, 1, 0], [0, 1, 1, 0, 0, 1, 0, 1],
[0, 1, 1, 0, 0, 0, 1, 1], [0, 1, 0, 1, 1, 1, 0, 0],
[0, 1, 0, 1, 1, 0, 1, 0], [0, 1, 0, 1, 1, 0, 0, 1],
[0, 1, 0, 1, 0, 1, 1, 0], [0, 1, 0, 1, 0, 1, 0, 1],
[0, 1, 0, 1, 0, 0, 1, 1], [0, 1, 0, 0, 1, 1, 1, 0],
[0, 1, 0, 0, 1, 1, 0, 1], [0, 1, 0, 0, 1, 0, 1, 1],
[0, 1, 0, 0, 0, 1, 1, 1], [0, 0, 1, 1, 1, 1, 0, 0],
[0, 0, 1, 1, 1, 0, 1, 0], [0, 0, 1, 1, 1, 0, 0, 1],
[0, 0, 1, 1, 0, 1, 1, 0], [0, 0, 1, 1, 0, 1, 0, 1],
[0, 0, 1, 1, 0, 0, 1, 1], [0, 0, 1, 0, 1, 1, 1, 0],
[0, 0, 1, 0, 1, 1, 0, 1], [0, 0, 1, 0, 1, 0, 1, 1],
[0, 0, 1, 0, 0, 1, 1, 1], [0, 0, 0, 1, 1, 1, 1, 0],
[0, 0, 0, 1, 1, 1, 0, 1], [0, 0, 0, 1, 1, 0, 1, 1],
[0, 0, 0, 1, 0, 1, 1, 1], [0, 0, 0, 0, 1, 1, 1, 1],
]
for permutation in permutations {
Validator(subject: permutation, separator: .element(0), maxSplits: 1)
.validate()
}
}
// More separators than elements.
func testAllEEESSSS() {
let permutations = [
[1, 1, 1, 0, 0, 0, 0], [1, 1, 0, 1, 0, 0, 0], [1, 1, 0, 0, 1, 0, 0],
[1, 1, 0, 0, 0, 1, 0], [1, 1, 0, 0, 0, 0, 1], [1, 0, 1, 1, 0, 0, 0],
[1, 0, 1, 0, 1, 0, 0], [1, 0, 1, 0, 0, 1, 0], [1, 0, 1, 0, 0, 0, 1],
[1, 0, 0, 1, 1, 0, 0], [1, 0, 0, 1, 0, 1, 0], [1, 0, 0, 1, 0, 0, 1],
[1, 0, 0, 0, 1, 1, 0], [1, 0, 0, 0, 1, 0, 1], [1, 0, 0, 0, 0, 1, 1],
[0, 1, 1, 1, 0, 0, 0], [0, 1, 1, 0, 1, 0, 0], [0, 1, 1, 0, 0, 1, 0],
[0, 1, 1, 0, 0, 0, 1], [0, 1, 0, 1, 1, 0, 0], [0, 1, 0, 1, 0, 1, 0],
[0, 1, 0, 1, 0, 0, 1], [0, 1, 0, 0, 1, 1, 0], [0, 1, 0, 0, 1, 0, 1],
[0, 1, 0, 0, 0, 1, 1], [0, 0, 1, 1, 1, 0, 0], [0, 0, 1, 1, 0, 1, 0],
[0, 0, 1, 1, 0, 0, 1], [0, 0, 1, 0, 1, 1, 0], [0, 0, 1, 0, 1, 0, 1],
[0, 0, 1, 0, 0, 1, 1], [0, 0, 0, 1, 1, 1, 0], [0, 0, 0, 1, 1, 0, 1],
[0, 0, 0, 1, 0, 1, 1], [0, 0, 0, 0, 1, 1, 1],
]
for permutation in permutations {
Validator(subject: permutation, separator: .element(0), maxSplits: 1)
.validate()
}
}
// More elements than separators.
func testAllEEEEESSSS() {
let permutations = [
[1, 1, 1, 1, 1, 0, 0, 0, 0], [1, 1, 1, 1, 0, 1, 0, 0, 0],
[1, 1, 1, 1, 0, 0, 1, 0, 0], [1, 1, 1, 1, 0, 0, 0, 1, 0],
[1, 1, 1, 1, 0, 0, 0, 0, 1], [1, 1, 1, 0, 1, 1, 0, 0, 0],
[1, 1, 1, 0, 1, 0, 1, 0, 0], [1, 1, 1, 0, 1, 0, 0, 1, 0],
[1, 1, 1, 0, 1, 0, 0, 0, 1], [1, 1, 1, 0, 0, 1, 1, 0, 0],
[1, 1, 1, 0, 0, 1, 0, 1, 0], [1, 1, 1, 0, 0, 1, 0, 0, 1],
[1, 1, 1, 0, 0, 0, 1, 1, 0], [1, 1, 1, 0, 0, 0, 1, 0, 1],
[1, 1, 1, 0, 0, 0, 0, 1, 1], [1, 1, 0, 1, 1, 1, 0, 0, 0],
[1, 1, 0, 1, 1, 0, 1, 0, 0], [1, 1, 0, 1, 1, 0, 0, 1, 0],
[1, 1, 0, 1, 1, 0, 0, 0, 1], [1, 1, 0, 1, 0, 1, 1, 0, 0],
[1, 1, 0, 1, 0, 1, 0, 1, 0], [1, 1, 0, 1, 0, 1, 0, 0, 1],
[1, 1, 0, 1, 0, 0, 1, 1, 0], [1, 1, 0, 1, 0, 0, 1, 0, 1],
[1, 1, 0, 1, 0, 0, 0, 1, 1], [1, 1, 0, 0, 1, 1, 1, 0, 0],
[1, 1, 0, 0, 1, 1, 0, 1, 0], [1, 1, 0, 0, 1, 1, 0, 0, 1],
[1, 1, 0, 0, 1, 0, 1, 1, 0], [1, 1, 0, 0, 1, 0, 1, 0, 1],
[1, 1, 0, 0, 1, 0, 0, 1, 1], [1, 1, 0, 0, 0, 1, 1, 1, 0],
[1, 1, 0, 0, 0, 1, 1, 0, 1], [1, 1, 0, 0, 0, 1, 0, 1, 1],
[1, 1, 0, 0, 0, 0, 1, 1, 1], [1, 0, 1, 1, 1, 1, 0, 0, 0],
[1, 0, 1, 1, 1, 0, 1, 0, 0], [1, 0, 1, 1, 1, 0, 0, 1, 0],
[1, 0, 1, 1, 1, 0, 0, 0, 1], [1, 0, 1, 1, 0, 1, 1, 0, 0],
[1, 0, 1, 1, 0, 1, 0, 1, 0], [1, 0, 1, 1, 0, 1, 0, 0, 1],
[1, 0, 1, 1, 0, 0, 1, 1, 0], [1, 0, 1, 1, 0, 0, 1, 0, 1],
[1, 0, 1, 1, 0, 0, 0, 1, 1], [1, 0, 1, 0, 1, 1, 1, 0, 0],
[1, 0, 1, 0, 1, 1, 0, 1, 0], [1, 0, 1, 0, 1, 1, 0, 0, 1],
[1, 0, 1, 0, 1, 0, 1, 1, 0], [1, 0, 1, 0, 1, 0, 1, 0, 1],
[1, 0, 1, 0, 1, 0, 0, 1, 1], [1, 0, 1, 0, 0, 1, 1, 1, 0],
[1, 0, 1, 0, 0, 1, 1, 0, 1], [1, 0, 1, 0, 0, 1, 0, 1, 1],
[1, 0, 1, 0, 0, 0, 1, 1, 1], [1, 0, 0, 1, 1, 1, 1, 0, 0],
[1, 0, 0, 1, 1, 1, 0, 1, 0], [1, 0, 0, 1, 1, 1, 0, 0, 1],
[1, 0, 0, 1, 1, 0, 1, 1, 0], [1, 0, 0, 1, 1, 0, 1, 0, 1],
[1, 0, 0, 1, 1, 0, 0, 1, 1], [1, 0, 0, 1, 0, 1, 1, 1, 0],
[1, 0, 0, 1, 0, 1, 1, 0, 1], [1, 0, 0, 1, 0, 1, 0, 1, 1],
[1, 0, 0, 1, 0, 0, 1, 1, 1], [1, 0, 0, 0, 1, 1, 1, 1, 0],
[1, 0, 0, 0, 1, 1, 1, 0, 1], [1, 0, 0, 0, 1, 1, 0, 1, 1],
[1, 0, 0, 0, 1, 0, 1, 1, 1], [1, 0, 0, 0, 0, 1, 1, 1, 1],
[0, 1, 1, 1, 1, 1, 0, 0, 0], [0, 1, 1, 1, 1, 0, 1, 0, 0],
[0, 1, 1, 1, 1, 0, 0, 1, 0], [0, 1, 1, 1, 1, 0, 0, 0, 1],
[0, 1, 1, 1, 0, 1, 1, 0, 0], [0, 1, 1, 1, 0, 1, 0, 1, 0],
[0, 1, 1, 1, 0, 1, 0, 0, 1], [0, 1, 1, 1, 0, 0, 1, 1, 0],
[0, 1, 1, 1, 0, 0, 1, 0, 1], [0, 1, 1, 1, 0, 0, 0, 1, 1],
[0, 1, 1, 0, 1, 1, 1, 0, 0], [0, 1, 1, 0, 1, 1, 0, 1, 0],
[0, 1, 1, 0, 1, 1, 0, 0, 1], [0, 1, 1, 0, 1, 0, 1, 1, 0],
[0, 1, 1, 0, 1, 0, 1, 0, 1], [0, 1, 1, 0, 1, 0, 0, 1, 1],
[0, 1, 1, 0, 0, 1, 1, 1, 0], [0, 1, 1, 0, 0, 1, 1, 0, 1],
[0, 1, 1, 0, 0, 1, 0, 1, 1], [0, 1, 1, 0, 0, 0, 1, 1, 1],
[0, 1, 0, 1, 1, 1, 1, 0, 0], [0, 1, 0, 1, 1, 1, 0, 1, 0],
[0, 1, 0, 1, 1, 1, 0, 0, 1], [0, 1, 0, 1, 1, 0, 1, 1, 0],
[0, 1, 0, 1, 1, 0, 1, 0, 1], [0, 1, 0, 1, 1, 0, 0, 1, 1],
[0, 1, 0, 1, 0, 1, 1, 1, 0], [0, 1, 0, 1, 0, 1, 1, 0, 1],
[0, 1, 0, 1, 0, 1, 0, 1, 1], [0, 1, 0, 1, 0, 0, 1, 1, 1],
[0, 1, 0, 0, 1, 1, 1, 1, 0], [0, 1, 0, 0, 1, 1, 1, 0, 1],
[0, 1, 0, 0, 1, 1, 0, 1, 1], [0, 1, 0, 0, 1, 0, 1, 1, 1],
[0, 1, 0, 0, 0, 1, 1, 1, 1], [0, 0, 1, 1, 1, 1, 1, 0, 0],
[0, 0, 1, 1, 1, 1, 0, 1, 0], [0, 0, 1, 1, 1, 1, 0, 0, 1],
[0, 0, 1, 1, 1, 0, 1, 1, 0], [0, 0, 1, 1, 1, 0, 1, 0, 1],
[0, 0, 1, 1, 1, 0, 0, 1, 1], [0, 0, 1, 1, 0, 1, 1, 1, 0],
[0, 0, 1, 1, 0, 1, 1, 0, 1], [0, 0, 1, 1, 0, 1, 0, 1, 1],
[0, 0, 1, 1, 0, 0, 1, 1, 1], [0, 0, 1, 0, 1, 1, 1, 1, 0],
[0, 0, 1, 0, 1, 1, 1, 0, 1], [0, 0, 1, 0, 1, 1, 0, 1, 1],
[0, 0, 1, 0, 1, 0, 1, 1, 1], [0, 0, 1, 0, 0, 1, 1, 1, 1],
[0, 0, 0, 1, 1, 1, 1, 1, 0], [0, 0, 0, 1, 1, 1, 1, 0, 1],
[0, 0, 0, 1, 1, 1, 0, 1, 1], [0, 0, 0, 1, 1, 0, 1, 1, 1],
[0, 0, 0, 1, 0, 1, 1, 1, 1], [0, 0, 0, 0, 1, 1, 1, 1, 1],
]
for permutation in permutations {
Validator(subject: permutation, separator: .element(0), maxSplits: 1)
.validate()
}
}
//===--------------------------------------------------------------------===//
// Permutations of a sequence with six separators, so there can be multiple
// adjacent separators at the beginning, middle, _and_ end.
//===--------------------------------------------------------------------===//
// More separators than elements.
func testAllEEESSSSSS() {
let permutations = [
[1, 1, 1, 0, 0, 0, 0, 0, 0], [1, 1, 0, 1, 0, 0, 0, 0, 0],
[1, 1, 0, 0, 1, 0, 0, 0, 0], [1, 1, 0, 0, 0, 1, 0, 0, 0],
[1, 1, 0, 0, 0, 0, 1, 0, 0], [1, 1, 0, 0, 0, 0, 0, 1, 0],
[1, 1, 0, 0, 0, 0, 0, 0, 1], [1, 0, 1, 1, 0, 0, 0, 0, 0],
[1, 0, 1, 0, 1, 0, 0, 0, 0], [1, 0, 1, 0, 0, 1, 0, 0, 0],
[1, 0, 1, 0, 0, 0, 1, 0, 0], [1, 0, 1, 0, 0, 0, 0, 1, 0],
[1, 0, 1, 0, 0, 0, 0, 0, 1], [1, 0, 0, 1, 1, 0, 0, 0, 0],
[1, 0, 0, 1, 0, 1, 0, 0, 0], [1, 0, 0, 1, 0, 0, 1, 0, 0],
[1, 0, 0, 1, 0, 0, 0, 1, 0], [1, 0, 0, 1, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 1, 1, 0, 0, 0], [1, 0, 0, 0, 1, 0, 1, 0, 0],
[1, 0, 0, 0, 1, 0, 0, 1, 0], [1, 0, 0, 0, 1, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 1, 1, 0, 0], [1, 0, 0, 0, 0, 1, 0, 1, 0],
[1, 0, 0, 0, 0, 1, 0, 0, 1], [1, 0, 0, 0, 0, 0, 1, 1, 0],
[1, 0, 0, 0, 0, 0, 1, 0, 1], [1, 0, 0, 0, 0, 0, 0, 1, 1],
[0, 1, 1, 1, 0, 0, 0, 0, 0], [0, 1, 1, 0, 1, 0, 0, 0, 0],
[0, 1, 1, 0, 0, 1, 0, 0, 0], [0, 1, 1, 0, 0, 0, 1, 0, 0],
[0, 1, 1, 0, 0, 0, 0, 1, 0], [0, 1, 1, 0, 0, 0, 0, 0, 1],
[0, 1, 0, 1, 1, 0, 0, 0, 0], [0, 1, 0, 1, 0, 1, 0, 0, 0],
[0, 1, 0, 1, 0, 0, 1, 0, 0], [0, 1, 0, 1, 0, 0, 0, 1, 0],
[0, 1, 0, 1, 0, 0, 0, 0, 1], [0, 1, 0, 0, 1, 1, 0, 0, 0],
[0, 1, 0, 0, 1, 0, 1, 0, 0], [0, 1, 0, 0, 1, 0, 0, 1, 0],
[0, 1, 0, 0, 1, 0, 0, 0, 1], [0, 1, 0, 0, 0, 1, 1, 0, 0],
[0, 1, 0, 0, 0, 1, 0, 1, 0], [0, 1, 0, 0, 0, 1, 0, 0, 1],
[0, 1, 0, 0, 0, 0, 1, 1, 0], [0, 1, 0, 0, 0, 0, 1, 0, 1],
[0, 1, 0, 0, 0, 0, 0, 1, 1], [0, 0, 1, 1, 1, 0, 0, 0, 0],
[0, 0, 1, 1, 0, 1, 0, 0, 0], [0, 0, 1, 1, 0, 0, 1, 0, 0],
[0, 0, 1, 1, 0, 0, 0, 1, 0], [0, 0, 1, 1, 0, 0, 0, 0, 1],
[0, 0, 1, 0, 1, 1, 0, 0, 0], [0, 0, 1, 0, 1, 0, 1, 0, 0],
[0, 0, 1, 0, 1, 0, 0, 1, 0], [0, 0, 1, 0, 1, 0, 0, 0, 1],
[0, 0, 1, 0, 0, 1, 1, 0, 0], [0, 0, 1, 0, 0, 1, 0, 1, 0],
[0, 0, 1, 0, 0, 1, 0, 0, 1], [0, 0, 1, 0, 0, 0, 1, 1, 0],
[0, 0, 1, 0, 0, 0, 1, 0, 1], [0, 0, 1, 0, 0, 0, 0, 1, 1],
[0, 0, 0, 1, 1, 1, 0, 0, 0], [0, 0, 0, 1, 1, 0, 1, 0, 0],
[0, 0, 0, 1, 1, 0, 0, 1, 0], [0, 0, 0, 1, 1, 0, 0, 0, 1],
[0, 0, 0, 1, 0, 1, 1, 0, 0], [0, 0, 0, 1, 0, 1, 0, 1, 0],
[0, 0, 0, 1, 0, 1, 0, 0, 1], [0, 0, 0, 1, 0, 0, 1, 1, 0],
[0, 0, 0, 1, 0, 0, 1, 0, 1], [0, 0, 0, 1, 0, 0, 0, 1, 1],
[0, 0, 0, 0, 1, 1, 1, 0, 0], [0, 0, 0, 0, 1, 1, 0, 1, 0],
[0, 0, 0, 0, 1, 1, 0, 0, 1], [0, 0, 0, 0, 1, 0, 1, 1, 0],
[0, 0, 0, 0, 1, 0, 1, 0, 1], [0, 0, 0, 0, 1, 0, 0, 1, 1],
[0, 0, 0, 0, 0, 1, 1, 1, 0], [0, 0, 0, 0, 0, 1, 1, 0, 1],
[0, 0, 0, 0, 0, 1, 0, 1, 1], [0, 0, 0, 0, 0, 0, 1, 1, 1],
]
for permutation in permutations {
Validator(subject: permutation, separator: .element(0), maxSplits: 1)
.validate()
}
}
//===--------------------------------------------------------------------===//
// Specific examples of interest.
//===--------------------------------------------------------------------===//
// The motivating example from
// https://github.com/apple/swift-algorithms/issues/59.
func testSplitFilenameComponents() {
Validator(
subject: "archive.tar.gz",
separator: .element("."),
maxSplits: 1
).validate()
}
// Examples from documentation.
func testSequenceDocExamples() {
// Closure version.
let numbers = stride(from: 1, through: 16, by: 1)
Validator(
subject: Array(numbers),
separator: .closure({ $0 % 3 == 0 || $0 % 5 == 0 }),
maxSplits: 1
).validate()
// Equatable element version.
let numbers2 = [1, 2, 0, 3, 4, 0, 0, 5]
Validator(subject: numbers2, separator: .element(0), maxSplits: 1)
.validate()
}
func testCollectionDocExample() {
let line = "BLANCHE: I don't want realism. I want magic!"
Validator(subject: line, separator: .element("."), maxSplits: 1).validate()
}
// Patterns tested in a previous version of this file which aren't tested
// above. Preserved to ensure we're not losing any test coverage.
func testVintagePatterns() {
let pattern1 = [1, 2, 42, 3, 4, 42, 5, 6, 42, 7]
Validator(subject: pattern1, separator: .element(42), maxSplits: 2)
.validate()
Validator(subject: pattern1, separator: .element(42), maxSplits: 0)
.validate()
let pattern2 = [42, 1, 2, 42, 3, 4, 42, 5, 6, 42, 7]
Validator(subject: pattern2, separator: .element(42), maxSplits: 2)
.validate()
let pattern3 = [1, 2, 42, 3, 4, 42, 42, 5, 6, 42, 7]
Validator(subject: pattern3, separator: .element(42), maxSplits: 2)
.validate()
let pattern4 = [1, 2, 42, 3, 4, 42, 42, 5, 6, 42, 7, 42, 42, 42]
Validator(subject: pattern4, separator: .element(42), maxSplits: 1)
.validate()
}
//===--------------------------------------------------------------------===//
// Protocol conformance.
//===--------------------------------------------------------------------===//
func testLaziness() {
let splitSequence = AnySequence([1, 2, 42, 3]).lazy.split(separator: 42)
XCTAssertLazySequence(splitSequence)
let splitCollection = "foo.bar".lazy.split(separator: ".")
XCTAssertLazySequence(splitCollection)
XCTAssertLazyCollection(splitCollection)
}
// TODO: Need a version of `validateIndexTraversals` that doesn't require
// `BidirectionalCollection` conformance.
//===--------------------------------------------------------------------===//
// Validator
//===--------------------------------------------------------------------===//
/// Splits a collection as both a lazy sequence and a lazy collection, using
/// the provided separator, and compares the results to those of the Standard
/// Library's eager splits, which are assumed to be correct.
///
/// Tests all combinations of default and provided `maxSplit` arguments and
/// default (true) and explicit false for `omittingEmptySubsequences`.
///
/// - Parameters:
/// - subject: The collection whose splits will be validated.
/// - separator: The element of the collection--or a predicate function to
/// determine the element--on which to split.
/// - maxSplits: The value to pass for `maxSplits` during validation. The
/// default value is also validated.
fileprivate struct Validator<C: Collection>
where C.Element: Equatable, C.SubSequence: Equatable {
enum Separator {
case element(C.Element)
case closure((C.Element) -> Bool)
}
let subject: C
let separator: Separator
let maxSplits: Int
func validate() {
_validateAsSequence(AnySequence(subject))
_validateAsCollection(subject)
}
private enum MaxSplits: CustomStringConvertible {
case provided(Int)
case defaultValue
var description: String {
switch self {
case .provided(let value):
return "maxSplits: \(value)"
case .defaultValue:
return "maxSplits: default"
}
}
}
private enum OmittingEmptySubsequences: CustomStringConvertible {
case provided(Bool)
case defaultValue
var description: String {
switch self {
case .provided(let value):
return "omittingEmptySubsequences: \(value)"
case .defaultValue:
return "omittingEmptySubsequences: default"
}
}
}
private func failureMessage<L: LazySequenceProtocol, S: Sequence>(
actual: L,
expected: S,
maxSplits: MaxSplits,
omittingEmptySubsequences: OmittingEmptySubsequences
) -> String {
"for \(Array(subject).debugDescription), \(maxSplits), \(omittingEmptySubsequences): \(Array(actual).debugDescription) != \(Array(expected).debugDescription)"
}
private func _validateAsSequence<T: Sequence>(_ s: T)
where T.Element == C.Element {
// Default max splits, omitting empty sequences
switch separator {
case let .element(element):
let expected = s.split(separator: element).map { Array($0) }
let actual = s.lazy.split(separator: element)
XCTAssertEqualSequences(
expected,
actual,
failureMessage(
actual: actual, expected: expected, maxSplits: .defaultValue,
omittingEmptySubsequences: .defaultValue)
)
case let .closure(closure):
let expected = s.split(whereSeparator: closure).map { Array($0) }
let actual = s.lazy.split(whereSeparator: closure)
XCTAssertEqualSequences(
expected,
actual,
failureMessage(
actual: actual, expected: expected, maxSplits: .defaultValue,
omittingEmptySubsequences: .defaultValue)
)
}
// Provided max splits, omitting empty sequences
switch separator {
case let .element(element):
let expected = s.split(
separator: element,
maxSplits: maxSplits
).map { Array($0) }
let actual = s.lazy.split(
separator: element,
maxSplits: maxSplits
)
XCTAssertEqualSequences(
expected,
actual,
failureMessage(
actual: actual, expected: expected, maxSplits: .provided(maxSplits),
omittingEmptySubsequences: .defaultValue)
)
case let .closure(closure):
let expected = s.split(
maxSplits: maxSplits,
whereSeparator: closure
).map { Array($0) }
let actual = s.lazy.split(
maxSplits: maxSplits,
whereSeparator: closure
)
XCTAssertEqualSequences(
expected,
actual,
failureMessage(
actual: actual, expected: expected, maxSplits: .provided(maxSplits),
omittingEmptySubsequences: .defaultValue)
)
}
// Default max splits, including empty sequences
switch separator {
case let .element(element):
let expected = s.split(
separator: element,
omittingEmptySubsequences: false
).map { Array($0) }
let actual = s.lazy.split(
separator: element,
omittingEmptySubsequences: false
)
XCTAssertEqualSequences(
expected,
actual,
failureMessage(
actual: actual, expected: expected, maxSplits: .defaultValue,
omittingEmptySubsequences: .provided(false))
)
case let .closure(closure):
let expected = s.split(
omittingEmptySubsequences: false,
whereSeparator: closure
).map { Array($0) }
let actual = s.lazy.split(
omittingEmptySubsequences: false,
whereSeparator: closure
)
XCTAssertEqualSequences(
expected,
actual,
failureMessage(
actual: actual, expected: expected, maxSplits: .defaultValue,
omittingEmptySubsequences: .provided(false))
)
}
// Provided max splits, including empty sequences
switch separator {
case let .element(element):
let expected = s.split(
separator: element,
maxSplits: maxSplits,
omittingEmptySubsequences: false
).map { Array($0) }
let actual = s.lazy.split(
separator: element,
maxSplits: maxSplits,
omittingEmptySubsequences: false
)
XCTAssertEqualSequences(
expected,
actual,
failureMessage(
actual: actual, expected: expected, maxSplits: .provided(maxSplits),
omittingEmptySubsequences: .provided(false))
)
case let .closure(closure):
let expected = s.split(
maxSplits: maxSplits,
omittingEmptySubsequences: false,
whereSeparator: closure
).map { Array($0) }
let actual = s.lazy.split(
maxSplits: maxSplits,
omittingEmptySubsequences: false,
whereSeparator: closure
)
XCTAssertEqualSequences(
expected,
actual,
failureMessage(
actual: actual, expected: expected, maxSplits: .provided(maxSplits),
omittingEmptySubsequences: .provided(false))
)
}
}
private func _validateAsCollection(_ c: C) {
// Default max splits, omitting empty sequences
switch separator {
case let .element(element):
let expected = c.split(separator: element)
let actual = c.lazy.split(separator: element)
XCTAssertEqualSequences(
expected,
actual,
failureMessage(
actual: actual, expected: expected, maxSplits: .defaultValue,
omittingEmptySubsequences: .defaultValue)
)
case let .closure(closure):
let expected = c.split(whereSeparator: closure)
let actual = c.lazy.split(whereSeparator: closure)
XCTAssertEqualSequences(
expected,
actual,
failureMessage(
actual: actual, expected: expected, maxSplits: .defaultValue,
omittingEmptySubsequences: .defaultValue)
)
}
// Provided max splits, omitting empty sequences
switch separator {
case let .element(element):
let expected = c.split(
separator: element,
maxSplits: maxSplits
)
let actual = c.lazy.split(
separator: element,
maxSplits: maxSplits
)
XCTAssertEqualSequences(
expected,
actual,
failureMessage(
actual: actual, expected: expected, maxSplits: .provided(maxSplits),
omittingEmptySubsequences: .defaultValue)
)
case let .closure(closure):
let expected = c.split(
maxSplits: maxSplits,
whereSeparator: closure
)
let actual = c.lazy.split(
maxSplits: maxSplits,
whereSeparator: closure
)
XCTAssertEqualSequences(
expected,
actual,
failureMessage(
actual: actual, expected: expected, maxSplits: .provided(maxSplits),
omittingEmptySubsequences: .defaultValue)
)
}
// Default max splits, including empty sequences
switch separator {
case let .element(element):
let expected = c.split(
separator: element,
omittingEmptySubsequences: false
)
let actual = c.lazy.split(
separator: element,
omittingEmptySubsequences: false
)
XCTAssertEqualSequences(
expected,
actual,
failureMessage(
actual: actual, expected: expected, maxSplits: .defaultValue,
omittingEmptySubsequences: .provided(false))
)
case let .closure(closure):
let expected = c.split(
omittingEmptySubsequences: false,
whereSeparator: closure
)
let actual = c.lazy.split(
omittingEmptySubsequences: false,
whereSeparator: closure
)
XCTAssertEqualSequences(
expected,
actual,
failureMessage(
actual: actual, expected: expected, maxSplits: .defaultValue,
omittingEmptySubsequences: .provided(false))
)
}
// Provided max splits, including empty sequences
switch separator {
case let .element(element):
let expected = c.split(
separator: element,
maxSplits: maxSplits,
omittingEmptySubsequences: false
)
let actual = c.lazy.split(
separator: element,
maxSplits: maxSplits,
omittingEmptySubsequences: false
)
XCTAssertEqualSequences(
expected,
actual,
failureMessage(
actual: actual, expected: expected, maxSplits: .provided(maxSplits),
omittingEmptySubsequences: .provided(false))
)
case let .closure(closure):
let expected = c.split(
maxSplits: maxSplits,
omittingEmptySubsequences: false,
whereSeparator: closure
)
let actual = c.lazy.split(
maxSplits: maxSplits,
omittingEmptySubsequences: false,
whereSeparator: closure
)
XCTAssertEqualSequences(
expected,
actual,
failureMessage(
actual: actual, expected: expected, maxSplits: .provided(maxSplits),
omittingEmptySubsequences: .provided(false))
)
}
}
}
}
@@ -1,187 +0,0 @@
//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift Algorithms open source project
//
// Copyright (c) 2020 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
//
//===----------------------------------------------------------------------===//
import XCTest
import Algorithms
final class SortedPrefixTests: XCTestCase {
func testMinCount() {
// Replacement at start and end
let input = [10, 11, 12, 1, 13, 2, 14, 3, 4, 5, 6, 0, 7, 8, 9]
let min = input.min(count: 5)
XCTAssertEqualSequences(min, 0..<5)
// Stability with all equal values
let maxZeroes = Array(repeating: 0, count: 100)
.enumerated()
.max(count: 5, sortedBy: { $0.element < $1.element })
XCTAssertEqualSequences(maxZeroes.map { $0.offset }, 95..<100)
}
func testMaxCount() {
// Replacement at start and end
let input = [0, 11, 12, 1, 13, 2, 14, 3, 4, 5, 6, 7, 8, 9, 10]
let max = input.max(count: 5)
XCTAssertEqualSequences(max, 10..<15)
// Stability with all equal values
let maxZeroes = Array(repeating: 0, count: 100)
.enumerated()
.max(count: 5, sortedBy: { $0.element < $1.element })
XCTAssertEqualSequences(maxZeroes.map { $0.offset }, 95..<100)
}
func testEmpty() {
let array = [Int]()
XCTAssertEqual(array.min(count: 0), [])
XCTAssertEqual(array.min(count: 100), [])
XCTAssertEqual(array.max(count: 0), [])
XCTAssertEqual(array.max(count: 100), [])
}
func testMinMaxSequences() {
let input = (1...100).shuffled().interspersed(with: 50)
let seq = AnySequence(input)
XCTAssertEqualSequences(seq.min(count: 0), [])
XCTAssertEqualSequences(seq.min(count: 5), 1...5)
XCTAssertEqualSequences(seq.max(count: 0), [])
XCTAssertEqualSequences(seq.max(count: 5), 96...100)
}
func testSortedPrefixComparable() {
let array: [Int] = [20, 1, 4, 70, 100, 2, 3, 7, 90]
XCTAssertEqual(array.min(count: 0), [])
XCTAssertEqual(array.min(count: 1), [1])
XCTAssertEqualSequences(array.min(count: 5), array.sorted().prefix(5))
XCTAssertEqual(array.min(count: 10), array.sorted())
}
func testMinMaxWithHugeCount() {
XCTAssertEqual([4, 2, 1, 3].min(count: .max), [1, 2, 3, 4])
XCTAssertEqual([4, 2, 1, 3].max(count: .max), [1, 2, 3, 4])
}
func testMinCountWithHugeInput() {
let range = 1...1000
let input = range.shuffled()
XCTAssertEqual(input.min(count: 0, sortedBy: <), [])
XCTAssertEqual(input.min(count: 0, sortedBy: >), [])
XCTAssertEqual(input.min(count: 1, sortedBy: <), [range.lowerBound])
XCTAssertEqual(input.min(count: 1, sortedBy: >), [range.upperBound])
XCTAssertEqualSequences(input.min(count: 5, sortedBy: <), range.prefix(5))
XCTAssertEqualSequences(
input.min(count: 5, sortedBy: >),
range.suffix(5).reversed())
XCTAssertEqualSequences(
input.min(count: 500, sortedBy: <),
range.prefix(500))
XCTAssertEqualSequences(
input.min(count: 500, sortedBy: >),
range.suffix(500).reversed())
XCTAssertEqualSequences(input.min(count: 1000, sortedBy: <), range)
XCTAssertEqualSequences(
input.min(count: 1000, sortedBy: >),
range.reversed())
}
func testMaxCountWithHugeInput() {
let range = 1...1000
let input = range.shuffled()
XCTAssertEqual(input.max(count: 0, sortedBy: <), [])
XCTAssertEqual(input.max(count: 0, sortedBy: >), [])
XCTAssertEqual(input.max(count: 1, sortedBy: <), [range.upperBound])
XCTAssertEqual(input.max(count: 1, sortedBy: >), [range.lowerBound])
XCTAssertEqualSequences(input.max(count: 5, sortedBy: <), range.suffix(5))
XCTAssertEqualSequences(
input.max(count: 5, sortedBy: >),
range.prefix(5).reversed())
XCTAssertEqualSequences(
input.max(count: 500, sortedBy: <),
range.suffix(500))
XCTAssertEqualSequences(
input.max(count: 500, sortedBy: >),
range.prefix(500).reversed())
XCTAssertEqualSequences(input.max(count: 1000, sortedBy: <), range)
XCTAssertEqualSequences(
input.max(count: 1000, sortedBy: >),
range.reversed())
}
func testStability() {
assertStability([1,1,1,2,5,7,3,6,2,5,7,3,6], withCount: 3)
assertStability([1,1,1,2,5,7,3,6,2,5,7,3,6], withCount: 6)
assertStability([1,1,1,2,5,7,3,6,2,5,7,3,6], withCount: 20)
assertStability([1,1,1,2,5,7,3,6,2,5,7,3,6], withCount: 1000)
assertStability(Array(repeating: 0, count: 100), withCount: 0)
assertStability(Array(repeating: 0, count: 100), withCount: 1)
assertStability(Array(repeating: 0, count: 100), withCount: 2)
assertStability(Array(repeating: 0, count: 100), withCount: 5)
assertStability(Array(repeating: 0, count: 100), withCount: 20)
assertStability(Array(repeating: 0, count: 100), withCount: 100)
assertStability(Array(repeating: 1, count: 50) + Array(repeating: 0, count: 50), withCount: 2)
assertStability(Array(repeating: 1, count: 50) + Array(repeating: 0, count: 50), withCount: 5)
assertStability(Array(repeating: 1, count: 50) + Array(repeating: 0, count: 50), withCount: 20)
assertStability(Array(repeating: 1, count: 50) + Array(repeating: 0, count: 50), withCount: 50)
assertStability([0,0], withCount: 1)
assertStability([0,0], withCount: 2)
assertStability([0,1,0,1,0,1], withCount: 2)
assertStability([0,1,0,1,0,1], withCount: 6)
assertStability([0,0,0,1,1,1], withCount: 1)
assertStability([0,0,0,1,1,1], withCount: 3)
assertStability([0,0,0,1,1,1], withCount: 4)
assertStability([0,0,0,1,1,1], withCount: 6)
assertStability([1,1,1,0,0,0], withCount: 1)
assertStability([1,1,1,0,0,0], withCount: 3)
assertStability([1,1,1,0,0,0], withCount: 4)
assertStability([1,1,1,0,0,0], withCount: 6)
assertStability([1,1,1,0,0,0], withCount: 5)
}
func assertStability(
_ actual: [Int],
withCount count: Int
) {
func stableOrder(
a: (offset: Int, element: Int),
b: (offset: Int, element: Int)) -> Bool
{
a.element == b.element
? a.offset < b.offset
: a.element < b.element
}
do {
let sorted = actual.enumerated()
.min(count: count) { $0.element < $1.element }
XCTAssert(sorted.isSorted(by: stableOrder))
}
do {
let sorted = actual.enumerated()
.max(count: count) { $0.element < $1.element }
XCTAssert(sorted.isSorted(by: stableOrder))
}
}
}
@@ -64,17 +64,14 @@ final class PartitionTests: XCTestCase {
func testStablePartitionWithSubrange() {
for length in 10...20 {
let a = Array(0..<length)
for i in 0..<length {
for j in 0...i {
var b = a
let partitionRange = j..<i
let condition = { $0 < i - 1 }
let p = b.stablePartition(subrange: partitionRange, by: condition)
XCTAssertEqual(p, partitionRange.count == 0 ? j : j + 1)
XCTAssertEqualSequences(b[partitionRange.lowerBound..<p], a[partitionRange].filter { !condition($0) })
XCTAssertEqualSequences(b[p..<partitionRange.upperBound], a[partitionRange].filter(condition))
}
for j in 0..<length {
var b = a
let partitionRange = 0..<j
let condition = { $0 < j - 1 }
let p = b.stablePartition(subrange: partitionRange, by: condition)
XCTAssertEqual(p, partitionRange.count > 0 ? 1 : 0)
XCTAssertEqualSequences(b[partitionRange.lowerBound..<p], a[partitionRange].filter { !condition($0) })
XCTAssertEqualSequences(b[p..<partitionRange.upperBound], a[partitionRange].filter(condition))
}
}
}
@@ -91,46 +88,4 @@ final class PartitionTests: XCTestCase {
}
}
}
func testPartitionWithSubrangeBidirectionalCollection() {
for length in 10...20 {
let a = Array(0..<length)
for i in 0..<length {
for j in 0...i {
var b = a
let partitionRange = j..<i
let condition = { $0 < i - 1 }
let p = b.partition(subrange: partitionRange, by: condition)
XCTAssertEqual(p, partitionRange.count == 0 ? j : j + 1)
XCTAssertEqualSequences(b[partitionRange.lowerBound..<p], a[partitionRange].filter { !condition($0) })
XCTAssertUnorderedEqualSequences(b[p..<partitionRange.upperBound], a[partitionRange].filter(condition))
}
}
}
}
func testPartitionWithSubrangeMutableCollection() {
for length in 10...20 {
let a = Array(0..<length)
for i in 0..<length {
for j in 0...i {
var b = a.eraseToAnyMutableCollection()
var bdc = a
let partitionRange = j..<i
let condition = { $0 < i - 1 }
let p = b.partition(subrange: partitionRange, by: condition)
let bdcp = bdc.partition(subrange: partitionRange, by: condition)
XCTAssertEqual(p, partitionRange.count == 0 ? j : j + 1)
XCTAssertEqualSequences(b[partitionRange.lowerBound..<p], a[partitionRange].filter { !condition($0) })
XCTAssertUnorderedEqualSequences(b[p..<partitionRange.upperBound], a[partitionRange].filter(condition))
// Must produce the same result as the `BidirectionalCollection` specialized overload.
XCTAssertEqualSequences(b[partitionRange.lowerBound..<p], bdc[partitionRange.lowerBound..<bdcp])
XCTAssertUnorderedEqualSequences(b[p..<partitionRange.upperBound], bdc[bdcp..<partitionRange.upperBound])
}
}
}
}
}
@@ -26,58 +26,27 @@ final class PermutationsTests: XCTestCase {
XCTAssertTrue(p.allSatisfy { $0.count == count })
XCTAssertTrue(p.isSorted(by: { $0.lexicographicallyPrecedes($1) }))
}
func ts<R: RangeExpression>(count: R) where R.Bound == Int {
let p = count.relative(to: 0 ..< .max)
.clamped(to: 0 ..< c.count + 1)
.flatMap {
c.permutations(ofCount: $0)
}
let p2 = c.permutations(ofCount: count)
XCTAssertEqual(p.count, p2.count)
XCTAssertEqualSequences(p, Array(p2))
}
t(count: 0)
t(count: 1)
t(count: 2)
t(count: 3)
t(count: 4)
t(count: 5)
t(count: nil)
ts(count: 0...0)
ts(count: 1...1)
ts(count: 0...1)
ts(count: 0...2)
ts(count: 0...3)
ts(count: 1...3)
ts(count: 2...3)
ts(count: 0...)
ts(count: ...5)
ts(count: ...4)
ts(count: ...6)
}
func testEmpty() {
// `k == 0` results in one zero-length permutation
XCTAssertEqual(1, "".permutations().count)
XCTAssertEqual(1, "ABCD".permutations(ofCount: 0).count)
XCTAssertEqual(1, "ABCD".permutations(ofCount: 0...0).count)
XCTAssertEqual(Array("".permutations()), [[]])
XCTAssertEqual(Array("".permutations(ofCount: 0)), [[]])
XCTAssertEqual(Array("ABCD".permutations(ofCount: 0)), [[]])
XCTAssertEqual(Array("ABCD".permutations(ofCount: 0...0)), [[]])
// `k` greater than element count results in zero permutations
XCTAssertEqual(0, "".permutations(ofCount: 5).count)
XCTAssertEqual(Array("".permutations(ofCount: 5)), [])
XCTAssertEqual(Array("ABCD".permutations(ofCount: 5)), [])
XCTAssertEqual(Array("ABCD".permutations(ofCount: 5..<6)), [])
XCTAssertEqual(Array("ABCD".permutations(ofCount: 5..<7)), [])
XCTAssertEqual(Array("ABCD".permutations(ofCount: 5...)), [])
}
func testNextPermutation() {
@@ -95,110 +64,13 @@ final class PermutationsTests: XCTestCase {
XCTAssertEqual([1, 2, 3, 4, 7, 6, 5], numbers)
_ = numbers.nextPermutation()
XCTAssertEqual([1, 2, 3, 5, 4, 6, 7], numbers)
// Fast-forward to end of permutations.
while numbers.nextPermutation() {}
XCTAssertEqual([1, 2, 3, 4, 5, 6, 7], numbers)
}
func testPermutationsLazy() {
XCTAssertLazySequence("ABCD".lazy.permutations(ofCount: 2))
}
func testDocumentationExample1() {
// From Guides/Permutations.md
let numbers = [10, 20, 30]
let permutations = numbers.permutations()
XCTAssertEqualSequences(permutations, [
[10, 20, 30],
[10, 30, 20],
[20, 10, 30],
[20, 30, 10],
[30, 10, 20],
[30, 20, 10],
])
}
func testDocumentationExample2() {
// From Guides/Permutations.md
let numbers = [10, 20, 30]
let permutations = numbers.permutations(ofCount: 2)
XCTAssertEqualSequences(permutations, [
[10, 20],
[10, 30],
[20, 10],
[20, 30],
[30, 10],
[30, 20],
])
}
func testDocumentationExample3() {
// From Guides/Permutations.md
let numbers2 = [20, 10, 10]
let permutations = numbers2.permutations()
XCTAssertEqualSequences(permutations, [
[20, 10, 10],
[20, 10, 10],
[10, 20, 10],
[10, 10, 20],
[10, 20, 10],
[10, 10, 20],
])
}
func testDocumentationExample4() {
// From Guides/Permutations.md
let numbers = [10, 20, 30]
let permutations = numbers.permutations(ofCount: 0...)
XCTAssertEqualSequences(permutations, [
[],
[10],
[20],
[30],
[10, 20],
[10, 30],
[20, 10],
[20, 30],
[30, 10],
[30, 20],
[10, 20, 30],
[10, 30, 20],
[20, 10, 30],
[20, 30, 10],
[30, 10, 20],
[30, 20, 10],
])
}
func testDocumentationExample5() {
// From Permutations.swift
let names = ["Alex", "Celeste", "Davide"]
let permutations = names.permutations(ofCount: 2)
XCTAssertEqualSequences(permutations, [
["Alex", "Celeste"],
["Alex", "Davide"],
["Celeste", "Alex"],
["Celeste", "Davide"],
["Davide", "Alex"],
["Davide", "Celeste"],
])
}
func testDocumentationExample6() {
// From Permutations.swift
let names = ["Alex", "Celeste", "Davide"]
let permutations = names.permutations(ofCount: 1...2)
XCTAssertEqualSequences(permutations, [
["Alex"],
["Celeste"],
["Davide"],
["Alex", "Celeste"],
["Alex", "Davide"],
["Celeste", "Alex"],
["Celeste", "Davide"],
["Davide", "Alex"],
["Davide", "Celeste"],
])
XCTAssertLazy("ABCD".lazy.permutations(ofCount: 2))
}
}
@@ -10,7 +10,7 @@
//===----------------------------------------------------------------------===//
import XCTest
@testable import Algorithms
import Algorithms
func validateRandomSamples<S: Sequence>(
_ samples: [Int: Int],
@@ -95,32 +95,4 @@ final class RandomSampleTests: XCTestCase {
let sample2c = c.randomStableSample(count: k, using: &generator)
XCTAssertEqual(sample1c, sample2c)
}
func testRandomSampleRandomEdgeCasesInternal() {
struct ZeroGenerator: RandomNumberGenerator {
mutating func next() -> UInt64 { 0 }
}
var zero = ZeroGenerator()
_ = nextOffset(w: 1, using: &zero) // must not crash
struct AlmostAllZeroGenerator: RandomNumberGenerator {
private var forward: SplitMix64
private var count: Int = 0
init(seed: UInt64) {
forward = SplitMix64(seed: seed)
}
mutating func next() -> UInt64 {
defer { count &+= 1 }
if count % 1000 == 0 { return forward.next() }
return 0
}
}
var almostAllZero = AlmostAllZeroGenerator(seed: 0)
_ = s.randomSample(count: k, using: &almostAllZero) // must not crash
almostAllZero = AlmostAllZeroGenerator(seed: 0)
_ = c.randomSample(count: k, using: &almostAllZero) // must not crash
}
}
+1 -62
View File
@@ -10,70 +10,9 @@
//===----------------------------------------------------------------------===//
import XCTest
@testable import Algorithms
import Algorithms
final class RotateTests: XCTestCase {
/// Tests the example given in `_reverse(subrange:until:)`’s documentation
func testUnderscoreReverse() {
var input = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p"]
let limit: Int = 4
let (lower, upper) = input._reverse(subrange: input.startIndex..<input.endIndex, until: input.startIndex.advanced(by: limit))
let expected = ["p", "o", "n", "m", "e", "f", "g", "h", "i", "j", "k", "l", "d", "c", "b", "a"]
XCTAssertEqual(input, expected)
XCTAssertEqual(lower, input.startIndex.advanced(by: limit))
XCTAssertEqual(upper, input.endIndex.advanced(by: -limit))
}
/// Tests the example given in `reverse(subrange:)`’s documentation
func testReverse() {
var numbers = [10, 20, 30, 40, 50, 60, 70, 80]
numbers.reverse(subrange: 0..<4)
XCTAssertEqual(numbers, [40, 30, 20, 10, 50, 60, 70, 80])
}
/// Tests `rotate(subrange:toStartAt:)` with an empty subrange
/// The order of elements are unchanged
func testRotateEmptySubrange() {
var numbers = [10, 20, 30, 40, 50, 60, 70, 80]
let oldStart = numbers.rotate(subrange: 3..<3, toStartAt: 3)
XCTAssertEqual(numbers, [10, 20, 30, 40, 50, 60, 70, 80])
XCTAssertEqual(numbers[oldStart], 40)
}
/// Tests `rotate(subrange:toStartAt:)` with an empty collection
func testRotateSubrangeOnEmptyCollection() {
var numbers = [Int]()
let oldStart = numbers.rotate(subrange: 0..<0, toStartAt: 0)
XCTAssertEqual(numbers, [])
XCTAssertEqual(oldStart, numbers.startIndex)
}
/// Tests `rotate(subrange:toStartAt:)` with the full range of the collection
func testRotateFullRange() {
var numbers = [10, 20, 30, 40, 50, 60, 70, 80]
let oldStart = numbers.rotate(subrange: 0..<8, toStartAt: 1)
XCTAssertEqual(numbers, [20, 30, 40, 50, 60, 70, 80, 10])
XCTAssertEqual(numbers[oldStart], 10)
}
/// Tests the example given in `rotate(subrange:toStartAt:)`’s documentation
func testRotateSubrange() {
var numbers = [10, 20, 30, 40, 50, 60, 70, 80]
let oldStart = numbers.rotate(subrange: 0..<4, toStartAt: 2)
XCTAssertEqual(numbers, [30, 40, 10, 20, 50, 60, 70, 80])
XCTAssertEqual(numbers[oldStart], 10)
}
/// Tests the example given in `rotate(toStartAt:)`’s documentation
func testRotateExample() {
var numbers = [10, 20, 30, 40, 50, 60, 70, 80]
let oldStart = numbers.rotate(toStartAt: 3)
XCTAssertEqual(numbers, [40, 50, 60, 70, 80, 10, 20, 30])
XCTAssertEqual(numbers[oldStart], 10)
}
/// Tests `rotate(toStartAt:)` on collections of varying lengths, at different
/// starting points
func testRotate() {
for length in 0...15 {
let a = Array(0..<length)
@@ -10,13 +10,14 @@
//===----------------------------------------------------------------------===//
import XCTest
@testable import Algorithms
import Algorithms
final class windowsTests: XCTestCase {
final class SlidingWindowsTests: XCTestCase {
func testWindowsOfString() {
let s = "swift"
let w = s.windows(ofCount: 2)
let w = s.slidingWindows(ofCount: 2)
var i = w.startIndex
XCTAssertEqualSequences(w[i], "sw")
@@ -27,29 +28,30 @@ final class windowsTests: XCTestCase {
w.formIndex(after: &i)
XCTAssertEqualSequences(w[i], "ft")
// w.index(after: w.endIndex) // ← Precondition failed: windows index is out of range
// w.index(before: w.startIndex) // ← Precondition failed: windows index is out of range
// w.formIndex(after: &i); w[i] // ← Precondition failed: windows index is out of range
// w.index(after: w.endIndex) // ← Precondition failed: SlidingWindows index is out of range
// w.index(before: w.startIndex) // ← Precondition failed: SlidingWindows index is out of range
// w.formIndex(after: &i); w[i] // ← Precondition failed: SlidingWindows index is out of range
}
func testWindowsOfRange() {
let a = 0...100
XCTAssertTrue(a.windows(ofCount: 200).isEmpty)
XCTAssertTrue(a.slidingWindows(ofCount: 200).isEmpty)
let w = a.windows(ofCount: 10)
let w = a.slidingWindows(ofCount: 10)
XCTAssertEqualSequences(w.first!, 0..<10)
XCTAssertEqualSequences(w.last!, 91..<101)
}
func testWindowsOfInt() {
let a = [ 0, 1, 0, 1 ].windows(ofCount: 2)
let a = [ 0, 1, 0, 1 ].slidingWindows(ofCount: 2)
XCTAssertEqual(a.count, 3)
XCTAssertEqual(a.map { $0.reduce(0, +) }, [1, 1, 1])
let a2 = [0, 1, 2, 3, 4, 5, 6].windows(ofCount: 3).map {
let a2 = [0, 1, 2, 3, 4, 5, 6].slidingWindows(ofCount: 3).map {
$0.reduce(0, +)
}.reduce(0, +)
@@ -58,27 +60,27 @@ final class windowsTests: XCTestCase {
func testWindowsCount() {
let a = [0, 1, 2, 3, 4, 5]
XCTAssertEqual(a.windows(ofCount: 3).count, 4)
XCTAssertEqual(a.slidingWindows(ofCount: 3).count, 4)
let a2 = [0, 1, 2, 3, 4]
XCTAssertEqual(a2.windows(ofCount: 6).count, 0)
XCTAssertEqual(a2.slidingWindows(ofCount: 6).count, 0)
let a3 = [Int]()
XCTAssertEqual(a3.windows(ofCount: 2).count, 0)
XCTAssertEqual(a3.slidingWindows(ofCount: 2).count, 0)
}
func testWindowsSecondAndLast() {
let a = [0, 1, 2, 3, 4, 5]
let w = a.windows(ofCount: 4)
let w = a.slidingWindows(ofCount: 4)
let snd = w[w.index(after: w.startIndex)]
XCTAssertEqualSequences(snd, [1, 2, 3, 4])
let w2 = a.windows(ofCount: 3)
let w2 = a.slidingWindows(ofCount: 3)
XCTAssertEqualSequences(w2.last!, [3, 4, 5])
}
func testWindowsIndexAfterAndBefore() {
let a = [0, 1, 2, 3, 4, 5].windows(ofCount: 2)
let a = [0, 1, 2, 3, 4, 5].slidingWindows(ofCount: 2)
var i = a.startIndex
a.formIndex(after: &i)
a.formIndex(after: &i)
@@ -86,26 +88,4 @@ final class windowsTests: XCTestCase {
XCTAssertEqualSequences(a[i], [1, 2])
}
func testWindowsIndexTraversals() {
validateIndexTraversals(
"".windows(ofCount: 1),
"a".windows(ofCount: 1),
"ab".windows(ofCount: 1),
"abc".windows(ofCount: 1),
"".windows(ofCount: 3),
"a".windows(ofCount: 3),
"abc".windows(ofCount: 3),
"abcdefgh".windows(ofCount: 3),
indices: { windows in
let endIndex = windows.base.endIndex
let indices = windows.base.indices + [endIndex]
return zip(indices, indices.dropFirst(windows.size))
.map { .init(lowerBound: $0, upperBound: $1) }
+ [.init(lowerBound: endIndex, upperBound: endIndex)]
})
}
func testWindowsLazy() {
XCTAssertLazyCollection([0, 1, 2, 3].lazy.windows(ofCount: 2))
}
}
@@ -1,144 +0,0 @@
//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift Algorithms open source project
//
// Copyright (c) 2020 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
//
//===----------------------------------------------------------------------===//
import XCTest
import Algorithms
final class StridingTests: XCTestCase {
func testStride() {
let a = 0...10
XCTAssertEqualSequences(a.striding(by: 1), (0...10))
XCTAssertEqualSequences(a.striding(by: 2), [0, 2, 4, 6, 8, 10])
XCTAssertEqualSequences(a.striding(by: 3), [0, 3, 6, 9])
XCTAssertEqualSequences(a.striding(by: 4), [0, 4, 8])
XCTAssertEqualSequences(a.striding(by: 5), [0, 5, 10])
XCTAssertEqualSequences(a.striding(by: 10), [0, 10])
XCTAssertEqualSequences(a.striding(by: 11), [0])
let s = (0...).prefix(11)
XCTAssertEqualSequences(s.striding(by: 1), (0...10))
XCTAssertEqualSequences(s.striding(by: 2), [0, 2, 4, 6, 8, 10])
XCTAssertEqualSequences(s.striding(by: 3), [0, 3, 6, 9])
XCTAssertEqualSequences(s.striding(by: 4), [0, 4, 8])
XCTAssertEqualSequences(s.striding(by: 5), [0, 5, 10])
XCTAssertEqualSequences(s.striding(by: 10), [0, 10])
XCTAssertEqualSequences(s.striding(by: 11), [0])
let empty = (0...).prefix(0)
XCTAssertEqualSequences(empty.striding(by: 2), [])
}
func testStrideString() {
let s = "swift"
XCTAssertEqualSequences(s.striding(by: 2), ["s", "i", "t"])
}
func testStrideReversed() {
let a = [0, 1, 2, 3, 4, 5]
XCTAssertEqualSequences(a.striding(by: 3).reversed(), [3, 0])
XCTAssertEqualSequences(a.reversed().striding(by: 2), [5, 3, 1])
}
func testStrideIndexes() {
let a = [0, 1, 2, 3, 4, 5].striding(by: 2)
var i = a.startIndex
XCTAssertEqual(a[i], 0)
a.formIndex(after: &i)
XCTAssertEqual(a[i], 2)
a.formIndex(after: &i)
XCTAssertEqual(a[i], 4)
a.formIndex(before: &i)
XCTAssertEqual(a[i], 2)
a.formIndex(before: &i)
XCTAssertEqual(a[i], 0)
// a.formIndex(before: &i) // Precondition failed: Incrementing past start index
// a.index(after: a.endIndex) // Precondition failed: Advancing past end index
}
func testStrideCompositionEquivalence() {
let a = (0...10)
XCTAssertEqualSequences(a.striding(by: 6), a.striding(by: 2).striding(by: 3))
XCTAssertTrue(a.striding(by: 6) == a.striding(by: 2).striding(by: 3))
XCTAssert(type(of: a.striding(by: 2).striding(by: 3)) == StrideCollection<ClosedRange<Int>>.self)
}
func testEquality() {
let a = [1, 2, 3, 4, 5].striding(by: 2)
let b = [1, 0, 3, 0, 5].striding(by: 2)
XCTAssertEqual(a, b)
}
func testStrideLast() {
XCTAssertEqual((1...10).striding(by: 2).last, 9) // 1, 3, 5, 7, 9
XCTAssertEqual((1...10).striding(by: 3).last, 10) // 1, 4, 7, 10
XCTAssertEqual((1...10).striding(by: 4).last, 9) // 1, 5, 9
XCTAssertEqual((1...10).striding(by: 5).last, 6) // 1, 6
XCTAssertEqual((1...100).striding(by: 50).last, 51) // 1, 51
XCTAssertEqual((1...5).striding(by: 2).last, 5) // 1, 3, 5
XCTAssertEqual([Int]().striding(by: 2).last, nil) // empty
}
func testCount() {
let empty = [Int]().striding(by: 2)
XCTAssertEqual(empty.count, 0)
let a = (0...10)
XCTAssertEqual(a.striding(by: 1).count, (0...10).count)
XCTAssertEqual(a.striding(by: 2).count, [0, 2, 4, 6, 8, 10].count)
XCTAssertEqual(a.striding(by: 3).count, [0, 3, 6, 9].count)
XCTAssertEqual(a.striding(by: 4).count, [0, 4, 8].count)
XCTAssertEqual(a.striding(by: 5).count, [0, 5, 10].count)
XCTAssertEqual(a.striding(by: 10).count, [0, 10].count)
XCTAssertEqual(a.striding(by: 11).count, [0].count)
}
func testIndexTraversals() {
let empty = [Int]()
validateIndexTraversals(
empty.striding(by: 1),
empty.striding(by: 2)
)
let zero_to_one_hundered_range = 0...100
validateIndexTraversals(
zero_to_one_hundered_range.striding(by: 10),
zero_to_one_hundered_range.striding(by: 11),
zero_to_one_hundered_range.striding(by: 101)
)
let zero_to_one_hundered_array = Array(zero_to_one_hundered_range)
validateIndexTraversals(
zero_to_one_hundered_array.striding(by: 10),
zero_to_one_hundered_array.striding(by: 11),
zero_to_one_hundered_array.striding(by: 101)
)
let string = "swift rocks".map(String.init)
validateIndexTraversals(
string.striding(by: 1),
string.striding(by: 2),
string.striding(by: 10)
)
}
func testOffsetBy() {
let a = (0...100).striding(by: 22)
let b = [0, 22, 44, 66, 88]
for i in 0..<a.count {
XCTAssertEqual(a[a.index(a.startIndex, offsetBy: i)], b[i])
}
}
func testOffsetByEndIndex() {
let a = 1...5
let b = a.striding(by: 3) // [1, 4]
let i = b.index(b.startIndex, offsetBy: 2)
XCTAssertEqual(i, b.endIndex)
}
}
@@ -1,50 +0,0 @@
//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift Algorithms open source project
//
// Copyright (c) 2021 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
//
//===----------------------------------------------------------------------===//
import XCTest
@testable import Algorithms
final class SuffixTests: XCTestCase {
func testSuffix() {
let a = 0...10
XCTAssertEqualSequences(a.suffix(while: { $0 > 5 }), (6...10))
XCTAssertEqualSequences(a.suffix(while: { $0 > 10 }), [])
XCTAssertEqualSequences(a.suffix(while: { $0 > 9 }), [10])
XCTAssertEqualSequences(a.suffix(while: { $0 > -1 }), (0...10))
let empty: [Int] = []
XCTAssertEqualSequences(empty.suffix(while: { $0 > 10 }), [])
}
func testEndOfPrefix() {
let array = Array(0..<10)
XCTAssertEqual(array.endOfPrefix(while: { $0 < 3 }), 3)
XCTAssertEqual(array.endOfPrefix(while: { _ in false }), array.startIndex)
XCTAssertEqual(array.endOfPrefix(while: { _ in true }), array.endIndex)
let empty = [Int]()
XCTAssertEqual(empty.endOfPrefix(while: { $0 < 3 }), 0)
XCTAssertEqual(empty.endOfPrefix(while: { _ in false }), empty.startIndex)
XCTAssertEqual(empty.endOfPrefix(while: { _ in true }), empty.endIndex)
}
func testStartOfSuffix() {
let array = Array(0..<10)
XCTAssertEqual(array.startOfSuffix(while: { $0 >= 3 }), 3)
XCTAssertEqual(array.startOfSuffix(while: { _ in false }), array.endIndex)
XCTAssertEqual(array.startOfSuffix(while: { _ in true }), array.startIndex)
let empty = [Int]()
XCTAssertEqual(empty.startOfSuffix(while: { $0 < 3 }), 0)
XCTAssertEqual(empty.startOfSuffix(while: { _ in false }), empty.endIndex)
XCTAssertEqual(empty.startOfSuffix(while: { _ in true }), empty.startIndex)
}
}
+21 -84
View File
@@ -46,69 +46,31 @@ struct SplitMix64: RandomNumberGenerator {
}
}
// An eraser helper to any mutable collection
struct AnyMutableCollection<Base> where Base: MutableCollection {
var base: Base
}
extension AnyMutableCollection: MutableCollection {
typealias Index = Base.Index
typealias Element = Base.Element
var startIndex: Base.Index { base.startIndex }
var endIndex: Base.Index { base.endIndex }
func index(after i: Index) -> Index {
return base.index(after: i)
}
subscript(position: Base.Index) -> Base.Element {
_read { yield base[position] }
set { base[position] = newValue }
}
}
extension MutableCollection {
func eraseToAnyMutableCollection() -> AnyMutableCollection<Self> {
AnyMutableCollection(base: self)
}
}
func XCTAssertEqualSequences<S1: Sequence, S2: Sequence>(
_ expression1: @autoclosure () throws -> S1,
_ expression2: @autoclosure () throws -> S2,
_ message: @autoclosure () -> String = "",
file: StaticString = #file, line: UInt = #line
) rethrows where S1.Element: Equatable, S1.Element == S2.Element {
try XCTAssertEqualSequences(expression1(), expression2(), by: ==,
message(), file: file, line: line)
}
// Two sequences contains exactly the same element but not necessarily in the same order.
func XCTAssertUnorderedEqualSequences<S1: Sequence, S2: Sequence>(
_ expression1: @autoclosure () throws -> S1,
_ expression2: @autoclosure () throws -> S2,
file: StaticString = #file, line: UInt = #line
) rethrows where S1.Element: Equatable, S1.Element == S2.Element {
var s1 = Array(try expression1())
var missing: [S1.Element] = []
for elt in try expression2() {
guard let idx = s1.firstIndex(of: elt) else {
missing.append(elt)
continue
}
s1.remove(at: idx)
}
var iterator1 = try expression1().makeIterator()
var iterator2 = try expression2().makeIterator()
var offset = 0
XCTAssertTrue(
missing.isEmpty, "first sequence missing '\(missing)' elements from second sequence",
file: file, line: line
)
XCTAssertTrue(
s1.isEmpty, "first sequence contains \(s1) missing from second sequence",
file: file, line: line
)
while true {
guard let element1 = iterator1.next() else {
if iterator2.next() != nil {
XCTFail("First sequence had fewer elements than the second", file: file, line: line)
}
return
}
guard let element2 = iterator2.next() else {
XCTFail("First sequence had more elements than the second", file: file, line: line)
return
}
XCTAssertEqual(element1, element2, "Elements not equal at offset \(offset)", file: file, line: line)
offset += 1
}
}
func XCTAssertEqualSequences<S1: Sequence, S2: Sequence>(
@@ -118,35 +80,10 @@ func XCTAssertEqualSequences<S1: Sequence, S2: Sequence>(
_ message: @autoclosure () -> String = "",
file: StaticString = #file, line: UInt = #line
) rethrows where S1.Element == S2.Element {
func fail(_ reason: String) {
let message = message()
XCTFail(message.isEmpty ? reason : "\(message) - \(reason)",
file: file, line: line)
}
var iter1 = try expression1().makeIterator()
var iter2 = try expression2().makeIterator()
var idx = 0
while true {
switch (iter1.next(), iter2.next()) {
case let (e1?, e2?) where areEquivalent(e1, e2):
idx += 1
continue
case let (e1?, e2?):
fail("element \(e1) on first sequence does not match element \(e2) on second sequence at position \(idx)")
case (_?, nil):
fail("second sequence shorter than first")
case (nil, _?):
fail("first sequence shorter than second")
case (nil, nil): break
}
return
}
try XCTAssert(expression1().elementsEqual(expression2(), by: areEquivalent), message(), file: file, line: line)
}
func XCTAssertLazySequence<S: LazySequenceProtocol>(_: S) {}
func XCTAssertLazyCollection<S: LazyCollectionProtocol>(_: S) {}
func XCTAssertLazy<S: LazySequenceProtocol>(_: S) {}
/// Tests that all index traversal methods behave as expected.
///