Compare commits

...
65 Commits
Author SHA1 Message Date
Nate Cook 1e761dd787 Update changelog for 0.0.3 release (#86) 2021-02-26 14:03:33 -06:00
Nate Cook bd64bef3d2 Rename sortedPrefix methods (#77)
This renames sortedPrefix to min(count:), adds max(count:),
and moves both methods down to Sequence.

In order to still provide the optimization when `count` is close to
a collection's length, we include a Collection-specific overload of
all methods. These won't be accessed when in a Sequence-generic context,
but it's the best we can do without adding these methods as protocol
requirements.
2021-02-26 13:57:55 -06:00
Ben Rimmington 32837b9ad6 Rename trimming(where:) to trimming(while:) 2021-02-26 10:38:50 -06:00
Nate Cook f91638bba6 Add new methods to the README 2021-02-23 17:18:33 -06:00
Luciano Almeida 914e626e23 Audit public functions and properties that could be inlinable (#83) 2021-02-23 11:48:57 -06:00
Dhruv Shah d91723bd4b Create Suffix.md (#82)
Guide for suffix(while: ) function
2021-02-22 01:07:41 -06:00
Nate Cook 63311ae0ab Merge pull request #79 from apple/nate/just_windows
Rename slidingWindows back to windows(ofCount:)
2021-02-18 17:07:27 -06:00
Nate Cook cc20b55cc6 Rename slidingWindows back to windows(ofCount:) 2021-02-18 12:31:58 -06:00
Nate Cook 5be792abcf Add additional tests to rotate functions, clarify variable names (#75)
* Avoid ambiguous single-letter variable names
* Use consistent variable names
* Add unit tests for documented examples of rotate functions
* Add unit tests for reverse functions
2021-02-16 09:11:19 -06:00
Matt Zanchelli bf1de3240d Add unit tests for reverse functions 2021-02-15 13:31:34 -08:00
Matt Zanchelli dd564ca517 Add unit tests for documented examples of rotate functions 2021-02-15 13:31:22 -08:00
Matt Zanchelli 44d359b429 Use consistent variable names 2021-02-15 13:29:43 -08:00
Matt Zanchelli bdf36ad23d Avoid ambiguous single-letter variable names 2021-02-15 13:29:41 -08:00
Tim Vermeulen 7ca12bed60 Precompute LazyChunked's startIndex (#68) 2021-02-12 07:02:26 -08:00
Tim Vermeulen 4f7cd340cd Index offsetting for Product2 (#66) 2021-02-12 06:48:40 -08:00
Iceman 1a3c7061de Fix RandomSample crash when 0 was out from random. (#70) 2021-02-12 06:41:26 -08:00
Matt Zanchelli d8a11e0d51 All permutations (#56)
Adds the ability to easily get permutations of a range of sizes, like #51 did for Combinations.
2021-02-12 06:32:32 -08:00
Matt Zanchelli d2a1ca5f7b Lowercase suffix(while:) to match the case of the actual function name (#76) 2021-02-10 20:45:56 -06:00
Nate Cook 52e1e0e45a add suffix:while method (#65) 2021-02-09 13:00:17 -06:00
michiboo 3b511072a6 Fix suffix tests 2021-02-09 12:56:08 -06:00
Nate Cook cda6fddada Merge pull request #61 from LucianoPAlmeida/normalizing-assert
[NFC] Using precondition instead of assert in calls that do not allow negative values
2021-01-28 10:08:09 -06:00
michibooandXiaodi Wu f9a4f79027 Update Sources/Algorithms/Suffix.swift
Co-authored-by: Xiaodi Wu <13952+xwu@users.noreply.github.com>
2021-01-28 15:22:18 +02:00
michibooandXiaodi Wu 2f8f798d0c Update Sources/Algorithms/Suffix.swift
Co-authored-by: Xiaodi Wu <13952+xwu@users.noreply.github.com>
2021-01-24 21:54:14 +08:00
michibooandXiaodi Wu 60bad3bbf4 Update Sources/Algorithms/Suffix.swift
Co-authored-by: Xiaodi Wu <13952+xwu@users.noreply.github.com>
2021-01-23 14:39:02 +08:00
michiboo 08e424ea07 add doc on suffix method 2021-01-23 08:38:12 +02:00
michiboo 813ea7905e add more test for suffix Tests 2021-01-22 16:17:28 +02:00
michiboo 1acc2136d9 add test for suffix 2021-01-20 15:23:38 +02:00
michiboo 9ef531f23f add suffix while method 2021-01-20 15:16:25 +02:00
Nate Cook d872b648f4 Merge pull request #57 from ollieatkinson/patch-1
Update README.md to add slidingWindows(ofCount:) and striding(by:)
2021-01-15 22:49:04 -06:00
Nate Cook 9836a4f80b [Chunked] Add chunks(of:) variant that divides a collection in chunks of a given size (#54) 2021-01-15 22:43:13 -06:00
Luciano Almeida 34d7a55d1a [NFC] Using precondition instead of assert in calls that do not allow negative values 2021-01-15 20:15:52 -03:00
Luciano Almeida ad8d6ed7a1 [Chunks] Add chunks(ofCount:) in the readme 2021-01-15 07:53:21 -03:00
Luciano Almeida 14f09e4228 [Chunked] Improving index(offset:limit:) to avoid distance call 2021-01-15 07:48:11 -03:00
Luciano Almeida 622703b97f [Chunked] Improve tests for ChunksOfCount traversal 2021-01-14 22:56:28 -03:00
Matt Zanchelli 5b7993ca8d All combinations (#51)
Add an overload of combinations(ofCount:) that accepts a range.
2021-01-14 13:32:47 -06:00
Oliver AtkinsonandXiaodi Wu b18a659ab5 Update README.md
Co-authored-by: Xiaodi Wu <13952+xwu@users.noreply.github.com>
2021-01-14 17:26:41 +00:00
Luciano Almeida f89fe8fad1 [Chunked] Code review adjustments 2021-01-13 23:06:19 -03:00
Oliver Atkinson f0dba1433f Update README.md
Adds `slidingWindows(ofCount:)` and `striding(by:)` to README.md
2021-01-12 20:07:01 +00:00
Luciano Almeida 05df988369 [Chunked] Minor adjustments on tests 2021-01-10 17:18:49 -03:00
Luciano Almeida afac704540 [Chunked] Implemeting of ChunkedByCount index(offsetBy:) 2021-01-09 00:17:49 -03:00
Luciano Almeida 79aeb24e9d Fixing review comments 2021-01-08 08:21:01 -03:00
Luciano Almeida 3092eb1304 [Chucked] Add chunks(ofCount:) information on the Chunked guides 2021-01-08 00:09:07 -03:00
Luciano Almeida e0fed41419 [Chunked] Adding tests for chunks of count collection implementation 2021-01-08 00:08:21 -03:00
Luciano Almeida 505b57369f [Chunked] Implementing chunked collection by a given count 2021-01-08 00:07:46 -03:00
Rafael Machado 3864606e00 Add "sortedPrefix(_:by)" to Collection (#9) 2020-12-04 10:20:28 -06:00
Nate Cook e1c421c568 Fix typo 2020-12-04 10:16:09 -06:00
Nate Cook 638869256a Add a few missing doc comments. 2020-12-02 16:28:23 -06:00
Tim Vermeulen 99152ecc68 Unify chunked(by:) and chunked(on:) (#44)
* Unify the eager `chunked(on:)` and `chunked(by:)`

* Unify the lazy `chunked(on:)` and `chunked(by:)`

* Trap when going past the end

* Add preconditions in `index(before:)`/`index(after:)`
2020-12-02 15:25:50 -06:00
Markus Winter 7af7ac2599 Clean up some comments (#49) 2020-12-02 10:21:06 -06:00
Nate Cook ff01a02c07 Add Stride for Collection (#24) 2020-12-01 17:54:00 -06:00
Daniel Tull 93c8724c72 Add conformances to LazySequenceProtocol and LazyCollectionProtocol (#47)
* Conform Intersperse to LazySequenceProtocol when the base sequence does

* Add conformance to LazyCollectionProtocol

* Conform Indexed to LazyCollectionProtocol when Base conforms

* Rename XCTAssertLazy to XCTAssertLazySequence

* Add XCTAssertLazyCollection

* Add lazy test for Intersperse

* Update Indexed guide

* Add lazy conformances to SlidingWindows

* Update SlidingWindows guide
2020-12-01 15:47:13 -06:00
Tim Vermeulen ad6dc7a143 Add random-access methods to SlidingWindows (#42) 2020-11-12 11:30:32 -06:00
Daniel Tull fd189aa078 Add interspersed(with:) (#35) 2020-11-09 09:44:23 -06:00
Tim Vermeulen 6933a3157b Avoid unnecessary computations in Product.distance(from:to:) (#40) 2020-11-06 15:06:23 -06:00
Oliver Atkinson dfcc611e1d consistant negative stride 2020-11-06 15:52:42 +00:00
Oliver Atkinson 3669ff0c11 offsetBackward n is positive and remove init? from Index 2020-11-06 15:33:03 +00:00
Oliver Atkinson 0a6bcc3c68 compute the stride only when the next element is requested 2020-11-06 15:25:34 +00:00
Oliver Atkinson 92b2846345 Add unbounded striding tests to check empty and sequence implementation 2020-11-06 10:42:38 +00:00
Oliver Atkinson 377bb72f0a small documentation tweek collection -> sequence 2020-11-06 10:31:40 +00:00
Oliver Atkinson 28bbed8776 Add implementation for Sequence iterator 2020-11-06 10:13:29 +00:00
Oliver Atkinson 6f7148d966 Implementation of feedback from @timvermeulen 2020-11-06 09:46:06 +00:00
Oliver Atkinson dcdef508c0 make base and stride internal 2020-11-02 10:02:17 +00:00
Oliver Atkinson 4a194ca811 remove redundant limit 2020-11-01 20:39:18 +00:00
Oliver Atkinson 6df6133ab7 Refactor to index(_:offsetBy:limitedBy:) and utilise the new test utilities for validateIndexTraversals 2020-11-01 20:30:17 +00:00
Oliver Atkinson 17cb07e38f Add Stride for Collection 2020-11-01 20:30:10 +00:00
44 changed files with 3585 additions and 453 deletions

No files matched your search

+68 -2
View File
@@ -16,6 +16,47 @@ 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
@@ -32,7 +73,7 @@ package updates, you can specify your package dependency using
### Fixes
- Swift Algorithms now builds under SwiftPM on Windows.
- `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
@@ -44,6 +85,7 @@ 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.
@@ -54,23 +96,47 @@ 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.2...HEAD
[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
[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
+24 -6
View File
@@ -4,7 +4,10 @@
[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.
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`.
There are two variations of the `chunked` method: `chunked(by:)` and
`chunked(on:)`. `chunked(by:)` uses a binary predicate to test consecutive
@@ -26,17 +29,32 @@ let chunks = names.chunked(on: \.first!)
// [["David"], ["Kyle", "Karoy"], ["Nate"]]
```
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.
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.
```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
+24 -3
View File
@@ -36,6 +36,27 @@ 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,
@@ -56,9 +77,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
+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` when the base type
conforms.
its base type. `Indexed` also conforms to `LazySequenceProtocol` and
`LazyCollectionProtocol` when the base type conforms.
+58
View File
@@ -0,0 +1,58 @@
# 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
+58
View File
@@ -0,0 +1,58 @@
# 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,6 +60,31 @@ 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.

After

Width:  |  Height:  |  Size: 74 KiB

Binary file not shown.

After

Width:  |  Height:  |  Size: 77 KiB

-64
View File
@@ -1,64 +0,0 @@
# 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
@@ -0,0 +1,63 @@
# 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
@@ -0,0 +1,39 @@
# 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(where:)` to get a substring without the white space at the beginning and end of the string.
This example uses `trimming(while:)` to get a substring without the white space at the beginning and end of the string.
```swift
let myString = " hello, world "
print(myString.trimming(where: \.isWhitespace)) // "hello, world"
print(myString.trimming(while: \.isWhitespace)) // "hello, world"
let results = [2, 10, 11, 15, 20, 21, 100].trimming(where: { $0.isMultiple(of: 2) })
let results = [2, 10, 11, 15, 20, 21, 100].trimming(while: { $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(where predicate: (Element) throws -> Bool) rethrows -> SubSequence
public func trimming(while 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(where: { ... }) // Uses least-efficient implementation.
let trimmedInput = input.trimming(while: { ... }) // Uses least-efficient implementation.
}
func myAlgorithm2<Input>(input: Input) where Input: BidirectionalCollection {
let trimmedInput = input.trimming(where: { ... }) // Uses most-efficient implementation.
let trimmedInput = input.trimming(while: { ... }) // 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(where: { ... })
let result = input.dropFromBothEnds(while: { ... })
// No such ambiguity here.
let result = input.trimming(where: { ... })
let result = input.trimming(while: { ... })
```
+55
View File
@@ -0,0 +1,55 @@
# 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.
+11 -4
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 a particular size of the elements in a collection.
- [`combinations(ofCount:)`](https://github.com/apple/swift-algorithms/blob/main/Guides/Combinations.md): Combinations of particular sizes 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,14 +26,21 @@ 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:)`](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.
- [`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.
- [`indexed()`](https://github.com/apple/swift-algorithms/blob/main/Guides/Indexed.md): Iterate over tuples of a collection's indices and elements.
- [`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.
- [`interspersed(with:)`](https://github.com/apple/swift-algorithms/blob/main/Guides/Interspersed.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/SlidingWindows.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.
## Adding Swift Algorithms as a Dependency
+4 -2
View File
@@ -19,6 +19,7 @@ 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
@@ -26,7 +27,7 @@ public struct Chain2<Base1: Sequence, Base2: Sequence>
}
extension Chain2: Sequence {
/// The iterator for a `Chain` sequence.
/// The iterator for a `Chain2` sequence.
public struct Iterator: IteratorProtocol {
@usableFromInline
internal var iterator1: Base1.Iterator
@@ -53,7 +54,7 @@ extension Chain2: Sequence {
}
extension Chain2: Collection where Base1: Collection, Base2: Collection {
/// A position in a `Chain` collection.
/// A position in a `Chain2` 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
@@ -306,6 +307,7 @@ 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)
}
+399 -72
View File
@@ -9,92 +9,100 @@
//
//===----------------------------------------------------------------------===//
public struct LazyChunked<Base: Collection> {
/// A collection wrapper that breaks a collection into chunks based on a
/// predicate or projection.
public struct LazyChunked<Base: Collection, Subject> {
/// The collection that this instance provides a view onto.
public let base: Base
/// The projection function.
@usableFromInline
internal var belongInSameGroup: (Base.Element, Base.Element) -> Bool
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
@usableFromInline
internal init(base: Base, belongInSameGroup: @escaping (Base.Element, Base.Element) -> Bool) {
internal init(
base: Base,
projection: @escaping (Base.Element) -> Subject,
belongInSameGroup: @escaping (Subject, Subject) -> 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 lower bound of the chunk at this position.
/// The range corresponding to the chunk at this position.
@usableFromInline
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?
internal var baseRange: Range<Base.Index>
@usableFromInline
internal init(lowerBound: Base.Index, upperBound: Base.Index? = nil) {
self.lowerBound = lowerBound
self.upperBound = upperBound
internal init(_ baseRange: Range<Base.Index>) {
self.baseRange = baseRange
}
@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.lowerBound == rhs.lowerBound
lhs.baseRange.lowerBound == rhs.baseRange.lowerBound
}
@inlinable
public static func < (lhs: Index, rhs: Index) -> Bool {
// Only use the lower bound to test for ordering, as above.
lhs.lowerBound < rhs.lowerBound
lhs.baseRange.lowerBound < rhs.baseRange.lowerBound
}
}
/// Returns the index in the base collection for the first element that
/// doesn't match the current chunk.
/// Returns the index in the base collection of the end of the chunk starting
/// at the given index.
@usableFromInline
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
internal func endOfChunk(startingAt start: Base.Index) -> Base.Index {
let subject = projection(base[start])
return base[base.index(after: start)...]
.firstIndex(where: { !belongInSameGroup(subject, projection($0)) })
?? base.endIndex
}
@inlinable
public var startIndex: Index {
Index(lowerBound: base.startIndex)
Index(base.startIndex..<firstUpperBound)
}
@inlinable
public var endIndex: Index {
Index(lowerBound: base.endIndex, upperBound: base.endIndex)
Index(base.endIndex..<base.endIndex)
}
@inlinable
public func index(after i: Index) -> Index {
let upperBound = i.upperBound ?? endOfChunk(from: i.lowerBound)
let end = endOfChunk(from: upperBound)
return Index(lowerBound: upperBound, upperBound: end)
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)
}
@inlinable
public subscript(position: Index) -> Base.SubSequence {
let upperBound = position.upperBound
?? endOfChunk(from: position.lowerBound)
return base[position.lowerBound..<upperBound]
precondition(position != endIndex, "Can't subscript using endIndex")
return base[position.baseRange]
}
}
@@ -103,17 +111,19 @@ extension LazyChunked.Index: Hashable where Base.Index: Hashable {}
extension LazyChunked: BidirectionalCollection
where Base: BidirectionalCollection
{
/// Returns the index in the base collection for the element that starts
/// the chunk ending at the given index.
/// Returns the index in the base collection of the start of 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 lastOfPreviousChunk = base[base.index(before: end)]
let subject = projection(base[indexBeforeEnd])
// 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) })
// equal to `subject`.
if let firstMismatch = base[..<indexBeforeEnd]
.lastIndex(where: { !belongInSameGroup(projection($0), subject) })
{
// If we found one, that's the last element of the _next_ previous chunk,
// and therefore one position _before_ the start of this chunk.
@@ -127,8 +137,9 @@ extension LazyChunked: BidirectionalCollection
@inlinable
public func index(before i: Index) -> Index {
let start = startOfChunk(endingAt: i.lowerBound)
return Index(lowerBound: start, upperBound: i.lowerBound)
precondition(i != startIndex, "Can't advance before startIndex")
let start = startOfChunk(endingAt: i.baseRange.lowerBound)
return Index(start..<i.baseRange.lowerBound)
}
}
@@ -140,29 +151,29 @@ extension LazyCollectionProtocol {
/// Returns a lazy collection of subsequences of this collection, chunked by
/// the given predicate.
///
/// - 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.
/// - Complexity: O(*n*), because the start index is pre-computed.
@inlinable
public func chunked(
by belongInSameGroup: @escaping (Element, Element) -> Bool
) -> LazyChunked<Elements> {
LazyChunked(base: elements, belongInSameGroup: belongInSameGroup)
) -> LazyChunked<Elements, Element> {
LazyChunked(
base: elements,
projection: { $0 },
belongInSameGroup: belongInSameGroup)
}
/// Returns a lazy collection of subsequences of this collection, chunked by
/// grouping elements that project to the same value.
///
/// - 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.
/// - Complexity: O(*n*), because the start index is pre-computed.
@inlinable
public func chunked<Subject: Equatable>(
on projection: @escaping (Element) -> Subject
) -> LazyChunked<Elements> {
) -> LazyChunked<Elements, Subject> {
LazyChunked(
base: elements,
belongInSameGroup: { projection($0) == projection($1) })
projection: projection,
belongInSameGroup: ==)
}
}
@@ -172,27 +183,28 @@ extension LazyCollectionProtocol {
extension Collection {
/// Returns a collection of subsequences of this collection, chunked by
/// the given predicate.
/// grouping elements that project to the same value according to the given
/// predicate.
///
/// - Complexity: O(*n*), where *n* is the length of this collection.
@inlinable
public func chunked(
by belongInSameGroup: (Element, Element) -> Bool
) -> [SubSequence] {
@usableFromInline
internal func chunked<Subject>(
on projection: (Element) throws -> Subject,
by belongInSameGroup: (Subject, Subject) throws -> Bool
) rethrows -> [SubSequence] {
guard !isEmpty else { return [] }
var result: [SubSequence] = []
var start = startIndex
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
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
}
current = next
}
if start != endIndex {
@@ -201,6 +213,17 @@ 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.
@@ -208,9 +231,313 @@ extension Collection {
/// - Complexity: O(*n*), where *n* is the length of this collection.
@inlinable
public func chunked<Subject: Equatable>(
on projection: (Element) -> Subject
) -> [SubSequence] {
chunked(by: { projection($0) == projection($1) })
on projection: (Element) throws -> Subject
) rethrows -> [SubSequence] {
try chunked(on: projection, by: ==)
}
}
//===----------------------------------------------------------------------===//
// 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 {}
+152 -26
View File
@@ -2,28 +2,64 @@
//
// This source file is part of the Swift Algorithms open source project
//
// Copyright (c) 2020 Apple Inc. and the Swift project authors
// Copyright (c) 2020-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
//
//===----------------------------------------------------------------------===//
/// 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 var k: Int
internal let baseCount: 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.base = base
self.k = base.count < k ? -1 : k
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
}
/// 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
@@ -33,29 +69,38 @@ public struct Combinations<Base: Collection> {
}
}
return k >= 0
? binomial(n: base.count, k: k)
: 0
return k.map {
binomial(n: n, k: $0)
}.reduce(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.finished = combinations.k < 0
self.indexes = combinations.k < 0
? []
: Array(combinations.base.indices.prefix(combinations.k))
self.kRange = combinations.kRange ?? 0..<0
self.indexes = Array(combinations.base.indices.prefix(kRange.lowerBound))
}
/// Advances the current indices to the next set of combinations. If
@@ -78,24 +123,35 @@ 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.
finished = true
advanceKRange()
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
finished = true
// Finished iterating over combinations of this size.
advanceKRange()
return
}
@@ -111,7 +167,7 @@ extension Combinations: Sequence {
@inlinable
public mutating func next() -> [Base.Element]? {
if finished { return nil }
guard !isFinished else { return nil }
defer { advance() }
return indexes.map { i in base[i] }
}
@@ -127,18 +183,86 @@ extension Combinations: Equatable where Base: Equatable {}
extension Combinations: Hashable where Base: Hashable {}
//===----------------------------------------------------------------------===//
// combinations(count:)
// combinations(ofCount:)
//===----------------------------------------------------------------------===//
extension Collection {
/// Returns a collection of combinations of this collection's elements, with
/// each combination having the specificed number of elements.
/// 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.
///
/// 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 k: 3) {
/// for combo in colors.combinations(ofCount: 3) {
/// print(combo.joined(separator: ", "))
/// }
/// // fuchsia, cyan, mauve
@@ -157,10 +281,12 @@ extension Collection {
///
/// - Parameter k: The number of elements to include in each combination.
///
/// - Complexity: O(1)
/// - 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(ofCount k: Int) -> Combinations<Self> {
assert(k >= 0, "Can't have combinations with a negative number of elements.")
precondition(k >= 0, "Can't have combinations with a negative number of elements.")
return Combinations(self, k: k)
}
}
+8
View File
@@ -13,6 +13,11 @@
public struct Cycle<Base: Collection> {
/// The collection to repeat.
public let base: Base
@usableFromInline
internal init(base: Base) {
self.base = base
}
}
extension Cycle: Sequence {
@@ -43,6 +48,7 @@ extension Cycle: Sequence {
}
}
@inlinable
public func makeIterator() -> Iterator {
Iterator(base: base)
}
@@ -80,6 +86,7 @@ extension Collection {
/// forever.
///
/// - Complexity: O(1)
@inlinable
public func cycled() -> Cycle<Self> {
Cycle(base: self)
}
@@ -101,6 +108,7 @@ extension Collection {
/// times.
///
/// - Complexity: O(1)
@inlinable
public func cycled(times: Int) -> FlattenSequence<Repeated<Self>> {
repeatElement(self, count: times).joined()
}
+1
View File
@@ -70,6 +70,7 @@ 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
@@ -0,0 +1,231 @@
//===----------------------------------------------------------------------===//
//
// 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)
}
}
+385
View File
@@ -0,0 +1,385 @@
//===----------------------------------------------------------------------===//
//
// 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: <)
}
}
+172 -60
View File
@@ -11,61 +11,93 @@
/// A sequence of all the permutations of a collection's elements.
public struct Permutations<Base: Collection> {
/// The base collection.
/// The base collection to iterate over for permutations.
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
self.countToChoose = k ?? baseCount
let upperBound = baseCount + 1
self.kRange = kRange?.relative(to: 0 ..< .max)
.clamped(to: 0 ..< upperBound) ??
baseCount ..< upperBound
}
/// The total number of permutations.
@inlinable
public var count: Int {
return baseCount >= countToChoose
? stride(from: baseCount, to: baseCount - countToChoose, by: -1).reduce(1, *)
: 0
return kRange.map {
stride(from: baseCount, to: baseCount - $0, by: -1).reduce(1, *)
}.reduce(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.
@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 hasMorePermutations: Bool
@usableFromInline
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 init(_ base: Base) {
self.base = base
self.indexes = Array(base.indices)
self.countToChoose = self.indexes.count
self.hasMorePermutations = true
}
@usableFromInline
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
internal init(_ permutations: Permutations) {
self.base = permutations.base
self.baseCount = permutations.baseCount
self.kRange = permutations.kRange
self.indexes = Array(permutations.base.indices)
}
/// Advances the `indexes` array such that the first `countToChoose`
@@ -81,29 +113,30 @@ 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
@@ -111,42 +144,62 @@ extension Permutations: Sequence {
@inlinable
public mutating func next() -> [Base.Element]? {
if !hasMorePermutations { return nil }
guard !isFinished else { 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 { hasMorePermutations = indexes.nextPermutation() }
defer {
let hasMorePermutations = indexes.nextPermutation()
if !hasMorePermutations {
advanceKRange()
}
}
return indexes.map { base[$0] }
} else {
// Otherwise, return the items at the first `countToChoose` indices and
// advance the state.
defer { hasMorePermutations = nextState() }
defer {
let hasMorePermutations = nextState()
if !hasMorePermutations {
advanceKRange()
}
}
return indexes.prefix(countToChoose).map { base[$0] }
}
}
}
@usableFromInline
internal var permutesFullCollection: Bool {
baseCount == countToChoose
}
@inlinable
public func makeIterator() -> Iterator {
permutesFullCollection
? Iterator(base)
: Iterator(base, count: countToChoose)
Iterator(self)
}
}
extension Permutations: LazySequenceProtocol where Base: LazySequenceProtocol {}
//===----------------------------------------------------------------------===//
// nextPermutation(by:)
// nextPermutation()
//===----------------------------------------------------------------------===//
extension MutableCollection
where Self: BidirectionalCollection, Element: Comparable
where Self: BidirectionalCollection, Element: Comparable
{
/// Permutes this collection's elements through all the lexical orderings.
///
@@ -162,8 +215,8 @@ extension MutableCollection
/// - 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
if isEmpty { return false }
// Ensure we have > 1 element in the collection.
guard !isEmpty else { return false }
var i = index(before: endIndex)
if i == startIndex { return false }
@@ -177,7 +230,7 @@ extension MutableCollection
formIndex(before: &j)
}
swapAt(i, j)
self.reverse(subrange: ip1..<endIndex)
self.reverse(subrange: ip1 ..< endIndex)
return true
}
@@ -194,6 +247,62 @@ extension MutableCollection
//===----------------------------------------------------------------------===//
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.
///
@@ -236,12 +345,15 @@ extension Collection {
/// sequence, the resulting sequence has no elements.
///
/// - Parameter k: The number of elements to include in each permutation.
/// If `count` is `nil`, the resulting sequence represents permutations
/// of this entire collection.
/// If `k` is `nil`, the resulting sequence represents permutations of this
/// entire collection.
///
/// - Complexity: O(1)
/// - 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(ofCount k: Int? = nil) -> Permutations<Self> {
assert(
precondition(
k ?? 0 >= 0,
"Can't have permutations with a negative number of elements.")
return Permutations(self, k: k)
+281 -19
View File
@@ -9,13 +9,14 @@
//
//===----------------------------------------------------------------------===//
/// A sequence that represents the product of two sequence's elements.
/// A sequence that represents the product of two sequences' 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,32 +121,292 @@ extension Product2: Collection where Base1: Collection {
}
@inlinable
public func index(after i: Index) -> Index {
precondition(i.i1 != base1.endIndex, "Can't advance past endIndex")
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)
public subscript(position: Index) -> (Base1.Element, Base2.Element) {
(base1[position.i1], base2[position.i2])
}
// TODO: Implement index(_:offsetBy:) and index(_:offsetBy:limitedBy:)
/// 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))
}
@inlinable
public func distance(from start: Index, to end: Index) -> Int {
if start > end {
return -distance(from: end, to: start)
}
if start.i1 == end.i1 {
return base2[start.i2..<end.i2].count
}
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) }
return base2[start.i2...].count + base2[..<end.i2].count
+ base2.count * (base1.distance(from: start.i1, to: end.i1) - 1)
// 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
}
}
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)
}
}
@inlinable
public subscript(position: Index) -> (Base1.Element, Base2.Element) {
return (base1[position.i1], base2[position.i2])
@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) }
}
}
@@ -210,6 +471,7 @@ 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> {
+5 -4
View File
@@ -94,7 +94,8 @@ internal func nextW<G: RandomNumberGenerator>(
internal func nextOffset<G: RandomNumberGenerator>(
w: Double, using rng: inout G
) -> Int {
Int(Double.log(.random(in: 0..<1, using: &rng)) / .log(1 - w))
let offset = Double.log(.random(in: 0..<1, using: &rng)) / .log(onePlus: -w)
return offset < Double(Int.max) ? Int(offset) : Int.max
}
extension Collection {
@@ -201,10 +202,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) + 1
var offset = nextOffset(w: w, using: &rng)
// Skip over `offset - 1` elements to find the selected element.
while offset > 1, let _ = iterator.next() {
// Skip over `offset` elements to find the selected element.
while offset > 0, let _ = iterator.next() {
offset -= 1
}
guard let nextElement = iterator.next() else { break }
+18 -19
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]
/// ^ ^
/// f l
/// lower upper
///
/// - Postcondition: For returned indices `(f, l)`:
/// `f == limit || l == limit`
/// - Postcondition: For returned indices `(lower, upper)`:
/// `lower == limit || upper == limit`
@usableFromInline
@discardableResult
internal mutating func _reverse(
subrange: Range<Index>, until limit: Index
) -> (Index, Index) {
var f = subrange.lowerBound
var l = subrange.upperBound
while f != limit && l != limit {
formIndex(before: &l)
swapAt(f, l)
formIndex(after: &f)
var lower = subrange.lowerBound
var upper = subrange.upperBound
while lower != limit && upper != limit {
formIndex(before: &upper)
swapAt(lower, upper)
formIndex(after: &lower)
}
return (f, l)
return (lower, upper)
}
/// Reverses the elements within the given subrange.
@@ -59,13 +59,12 @@ extension MutableCollection where Self: BidirectionalCollection {
@inlinable
public mutating func reverse(subrange: Range<Index>) {
if subrange.isEmpty { return }
var lo = subrange.lowerBound
var hi = subrange.upperBound
while lo < hi {
formIndex(before: &hi)
swapAt(lo, hi)
formIndex(after: &lo)
var lower = subrange.lowerBound
var upper = subrange.upperBound
while lower < upper {
formIndex(before: &upper)
swapAt(lower, upper)
formIndex(after: &lower)
}
}
}
@@ -213,7 +212,7 @@ extension MutableCollection {
/// rotating.
/// - Returns: The new index of the element that was first pre-rotation.
///
/// - Complexity: O(*n*)
/// - Complexity: O(*n*), where *n* is the length of the collection.
@inlinable
@discardableResult
public mutating func rotate(toStartAt newStart: Index) -> Index {
@@ -273,7 +272,7 @@ extension MutableCollection where Self: BidirectionalCollection {
/// rotating.
/// - Returns: The new index of the element that was first pre-rotation.
///
/// - Complexity: O(*n*)
/// - Complexity: O(*n*), where *n* is the length of the collection.
@inlinable
@discardableResult
public mutating func rotate(toStartAt newStart: Index) -> Index {
-112
View File
@@ -1,112 +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
//
//===----------------------------------------------------------------------===//
//===----------------------------------------------------------------------===//
// 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 {}
+245
View File
@@ -0,0 +1,245 @@
//===----------------------------------------------------------------------===//
//
// 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(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 sequence or collection for stepping through the
/// elements by the specified amount.
@inlinable
public func striding(by step: Int) -> Stride<Self> {
Stride(base: self, stride: step)
}
}
/// A wrapper that strides over a base sequence or collection.
public struct Stride<Base: 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 Stride {
@inlinable
public func striding(by step: Int) -> Self {
Stride(base: base, stride: stride * step)
}
}
extension Stride: Sequence {
/// 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() -> Stride<Base>.Iterator {
Iterator(iterator: base.makeIterator(), stride: stride)
}
}
extension Stride: Collection where Base: 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 Stride: 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 Stride: RandomAccessCollection where Base: RandomAccessCollection {}
extension Stride: Equatable where Base.Element: Equatable {
@inlinable
public static func == (lhs: Stride, rhs: Stride) -> Bool {
lhs.elementsEqual(rhs, by: ==)
}
}
extension Stride: Hashable where Base.Element: Hashable {
@inlinable
public func hash(into hasher: inout Hasher) {
hasher.combine(stride)
for element in self {
hasher.combine(element)
}
}
}
extension Stride.Index: Hashable where Base.Index: Hashable {}
+39
View File
@@ -0,0 +1,39 @@
//===----------------------------------------------------------------------===//
//
// 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 {
let start = startIndex
var result = endIndex
while result != start {
let previous = index(before: result)
guard try predicate(self[previous]) else { break }
result = previous
}
return self[result...]
}
}
+13 -15
View File
@@ -10,33 +10,30 @@
//===----------------------------------------------------------------------===//
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(where:)` to get a substring without the white space at the
/// beginning and end of the string:
/// This example uses `trimming(while:)` to get a substring without the white
/// space at the beginning and end of the string:
///
/// ```
/// let myString = " hello, world "
/// print(myString.trimming(where: \.isWhitespace)) // "hello, world"
/// ```
/// let myString = " hello, world "
/// print(myString.trimming(while: \.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(
where predicate: (Element) throws -> Bool
while predicate: (Element) throws -> Bool
) rethrows -> SubSequence {
// 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 {
@@ -44,6 +41,7 @@ extension BidirectionalCollection {
}
sliceEnd = idxBeforeSliceEnd
}
// Trimmed everything.
return self[Range(uncheckedBounds: (sliceStart, sliceStart))]
}
+352
View File
@@ -0,0 +1,352 @@
//===----------------------------------------------------------------------===//
//
// 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 {}
+71 -2
View File
@@ -73,7 +73,76 @@ final class ChunkedTests: XCTestCase {
}
func testChunkedLazy() {
XCTAssertLazy(fruits.lazy.chunked(by: { $0.first == $1.first }))
XCTAssertLazy(fruits.lazy.chunked(on: { $0.first }))
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)
}
}
}
@@ -2,7 +2,7 @@
//
// This source file is part of the Swift Algorithms open source project
//
// Copyright (c) 2020 Apple Inc. and the Swift project authors
// Copyright (c) 2020-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
@@ -13,33 +13,114 @@ 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() {
XCTAssertLazy("ABC".lazy.combinations(ofCount: 1))
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...))
}
}
+1 -1
View File
@@ -41,6 +41,6 @@ final class CycleTests: XCTestCase {
}
func testCycleLazy() {
XCTAssertLazy((1...4).lazy.cycled())
XCTAssertLazySequence((1...4).lazy.cycled())
}
}
@@ -29,6 +29,6 @@ final class IndexedTests: XCTestCase {
}
func testIndexedLazy() {
XCTAssertLazy("ABCD".lazy.indexed())
XCTAssertLazyCollection("ABCD".lazy.indexed())
}
}
@@ -0,0 +1,65 @@
//===----------------------------------------------------------------------===//
//
// 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: "-"))
}
}
@@ -0,0 +1,187 @@
//===----------------------------------------------------------------------===//
//
// 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))
}
}
}
@@ -26,27 +26,58 @@ 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() {
@@ -64,13 +95,110 @@ 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() {
XCTAssertLazy("ABCD".lazy.permutations(ofCount: 2))
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"],
])
}
}
@@ -10,7 +10,7 @@
//===----------------------------------------------------------------------===//
import XCTest
import Algorithms
@testable import Algorithms
func validateRandomSamples<S: Sequence>(
_ samples: [Int: Int],
@@ -95,4 +95,32 @@ 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
}
}
+62 -1
View File
@@ -10,9 +10,70 @@
//===----------------------------------------------------------------------===//
import XCTest
import Algorithms
@testable 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)
@@ -0,0 +1,144 @@
//===----------------------------------------------------------------------===//
//
// 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)) == Stride<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)
}
}
@@ -0,0 +1,26 @@
//===----------------------------------------------------------------------===//
//
// 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
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 }), [])
}
}
@@ -65,7 +65,8 @@ func XCTAssertEqualSequences<S1: Sequence, S2: Sequence>(
try XCTAssert(expression1().elementsEqual(expression2(), by: areEquivalent), message(), file: file, line: line)
}
func XCTAssertLazy<S: LazySequenceProtocol>(_: S) {}
func XCTAssertLazySequence<S: LazySequenceProtocol>(_: S) {}
func XCTAssertLazyCollection<S: LazyCollectionProtocol>(_: S) {}
/// Tests that all index traversal methods behave as expected.
///
@@ -10,14 +10,13 @@
//===----------------------------------------------------------------------===//
import XCTest
import Algorithms
@testable import Algorithms
final class SlidingWindowsTests: XCTestCase {
final class windowsTests: XCTestCase {
func testWindowsOfString() {
let s = "swift"
let w = s.slidingWindows(ofCount: 2)
let w = s.windows(ofCount: 2)
var i = w.startIndex
XCTAssertEqualSequences(w[i], "sw")
@@ -28,30 +27,29 @@ final class SlidingWindowsTests: XCTestCase {
w.formIndex(after: &i)
XCTAssertEqualSequences(w[i], "ft")
// 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
// 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
}
func testWindowsOfRange() {
let a = 0...100
XCTAssertTrue(a.slidingWindows(ofCount: 200).isEmpty)
XCTAssertTrue(a.windows(ofCount: 200).isEmpty)
let w = a.slidingWindows(ofCount: 10)
let w = a.windows(ofCount: 10)
XCTAssertEqualSequences(w.first!, 0..<10)
XCTAssertEqualSequences(w.last!, 91..<101)
}
func testWindowsOfInt() {
let a = [ 0, 1, 0, 1 ].slidingWindows(ofCount: 2)
let a = [ 0, 1, 0, 1 ].windows(ofCount: 2)
XCTAssertEqual(a.count, 3)
XCTAssertEqual(a.map { $0.reduce(0, +) }, [1, 1, 1])
let a2 = [0, 1, 2, 3, 4, 5, 6].slidingWindows(ofCount: 3).map {
let a2 = [0, 1, 2, 3, 4, 5, 6].windows(ofCount: 3).map {
$0.reduce(0, +)
}.reduce(0, +)
@@ -60,27 +58,27 @@ final class SlidingWindowsTests: XCTestCase {
func testWindowsCount() {
let a = [0, 1, 2, 3, 4, 5]
XCTAssertEqual(a.slidingWindows(ofCount: 3).count, 4)
XCTAssertEqual(a.windows(ofCount: 3).count, 4)
let a2 = [0, 1, 2, 3, 4]
XCTAssertEqual(a2.slidingWindows(ofCount: 6).count, 0)
XCTAssertEqual(a2.windows(ofCount: 6).count, 0)
let a3 = [Int]()
XCTAssertEqual(a3.slidingWindows(ofCount: 2).count, 0)
XCTAssertEqual(a3.windows(ofCount: 2).count, 0)
}
func testWindowsSecondAndLast() {
let a = [0, 1, 2, 3, 4, 5]
let w = a.slidingWindows(ofCount: 4)
let w = a.windows(ofCount: 4)
let snd = w[w.index(after: w.startIndex)]
XCTAssertEqualSequences(snd, [1, 2, 3, 4])
let w2 = a.slidingWindows(ofCount: 3)
let w2 = a.windows(ofCount: 3)
XCTAssertEqualSequences(w2.last!, [3, 4, 5])
}
func testWindowsIndexAfterAndBefore() {
let a = [0, 1, 2, 3, 4, 5].slidingWindows(ofCount: 2)
let a = [0, 1, 2, 3, 4, 5].windows(ofCount: 2)
var i = a.startIndex
a.formIndex(after: &i)
a.formIndex(after: &i)
@@ -88,4 +86,26 @@ final class SlidingWindowsTests: 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))
}
}