mirror of
https://github.com/apple/swift-algorithms
synced 2026-11-22 04:10:39 +00:00
Compare commits
6
Commits
| Author | SHA1 | Date | |
|---|---|---|---|
|
|
f0df883f88 | ||
|
|
5cde0b1b67 | ||
|
|
220649e999 | ||
|
|
b171b81577 | ||
|
|
e652f01949 | ||
|
|
9783c1be91 |
No files matched your search
+35
-13
@@ -3,7 +3,7 @@
|
||||
[[Source](https://github.com/apple/swift-algorithms/blob/main/Sources/Algorithms/Permutations.swift) |
|
||||
[Tests](https://github.com/apple/swift-algorithms/blob/main/Tests/SwiftAlgorithmsTests/PermutationsTests.swift)]
|
||||
|
||||
A type that computes permutations of a collection’s elements, or of a subset of
|
||||
Methods that compute permutations of a collection’s elements, or of a subset of
|
||||
those elements.
|
||||
|
||||
The `permutations(ofCount:)` method, when called without the `ofCount`
|
||||
@@ -60,7 +60,18 @@ 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.
|
||||
To generate only unique permutations, use the `uniquePermutations(ofCount:)` method:
|
||||
|
||||
```swift
|
||||
for perm in numbers2.uniquePermutations() {
|
||||
print(perm)
|
||||
}
|
||||
// [20, 10, 10]
|
||||
// [10, 20, 10]
|
||||
// [10, 10, 20]
|
||||
```
|
||||
|
||||
Given a range, the methods return 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]
|
||||
@@ -87,21 +98,29 @@ for perm in numbers.permutations(ofCount: 0...) {
|
||||
|
||||
## Detailed Design
|
||||
|
||||
The `permutations(ofCount:)` method is declared as a `Collection` extension,
|
||||
and returns a `Permutations` type:
|
||||
The `permutations(ofCount:)` and `uniquePermutations(ofCount:)` methods are declared as `Collection` extensions,
|
||||
and return `Permutations` and `UniquePermutations` instances, respectively:
|
||||
|
||||
```swift
|
||||
extension Collection {
|
||||
public func permutations(ofCount k: Int? = nil) -> Permutations<Self>
|
||||
public func permutations<R>(ofCount kRange: R) -> Permutations<Self>
|
||||
where R: RangeExpression, R.Bound == Int
|
||||
}
|
||||
|
||||
extension Collection where Element: Hashable {
|
||||
public func uniquePermutations(ofCount k: Int? = nil) -> UniquePermutations<Self>
|
||||
public func uniquePermutations<R>(ofCount kRange: R) -> UniquePermutations<Self>
|
||||
where R: RangeExpression, R.Bound == Int
|
||||
}
|
||||
```
|
||||
|
||||
Since the `Permutations` type needs to store an array of the collection’s
|
||||
indices and mutate the array to generate each permutation, `Permutations` only
|
||||
has `Sequence` conformance. Adding `Collection` conformance would require
|
||||
Since both result types need to store an array of the collection’s
|
||||
indices and mutate the array to generate each permutation, they only
|
||||
have `Sequence` conformance. Adding `Collection` conformance would require
|
||||
storing the array in the index type, which would in turn lead to copying the
|
||||
array at every index advancement. `Combinations` does conform to
|
||||
`LazySequenceProtocol` when the base type conforms.
|
||||
array at every index advancement. The `Permutations` type
|
||||
conforms to `LazySequenceProtocol` when its base type conforms.
|
||||
|
||||
### Complexity
|
||||
|
||||
@@ -109,6 +128,10 @@ Calling `permutations()` is an O(1) operation. Creating the iterator for a
|
||||
`Permutations` instance and each call to `Permutations.Iterator.next()` is an
|
||||
O(_n_) operation.
|
||||
|
||||
Calling `uniquePermutations()` is an O(_n_) operation, because it preprocesses the
|
||||
collection to find duplicate elements. Creating the iterator for and each call to
|
||||
`next()` is also an O(_n_) operation.
|
||||
|
||||
### Naming
|
||||
|
||||
See the ["Naming" section for `combinations(ofCount:)`](Combinations.md#naming) for detail.
|
||||
@@ -117,9 +140,8 @@ See the ["Naming" section for `combinations(ofCount:)`](Combinations.md#naming)
|
||||
|
||||
**C++:** The `<algorithm>` library defines a `next_permutation` function that
|
||||
advances an array of comparable values through their lexicographic orderings.
|
||||
This function is tricky to use and understand, so while it’s included in
|
||||
`swift-algorithms` as an implementation detail of the `Permutations` type, it
|
||||
isn’t public.
|
||||
This function is very similar to the `uniquePermutations(ofCount:)` method.
|
||||
|
||||
**Rust/Ruby/Python:** Rust, Ruby, and Python all define functions with
|
||||
essentially the same semantics as the method described here.
|
||||
essentially the same semantics as the `permutations(ofCount:)` method
|
||||
described here.
|
||||
@@ -0,0 +1,136 @@
|
||||
# Reductions
|
||||
|
||||
[[Source](https://github.com/apple/swift-algorithms/blob/main/Sources/Algorithms/Reductions.swift) |
|
||||
[Tests](https://github.com/apple/swift-algorithms/blob/main/Tests/SwiftAlgorithmsTests/ReductionsTests.swift)]
|
||||
|
||||
Produces a sequence of values.
|
||||
|
||||
This has the behaviour of reduce, but also returns all intermediate results.
|
||||
|
||||
```swift
|
||||
let exclusiveRunningTotal = (1...5).reductions(0, +)
|
||||
print(exclusiveRunningTotal)
|
||||
// prints [0, 1, 3, 6, 10, 15]
|
||||
|
||||
let intoRunningTotal = (1...5).reductions(into: 0, +=)
|
||||
print(intoRunningTotal)
|
||||
// prints [0, 1, 3, 6, 10, 15]
|
||||
|
||||
let inclusiveRunningTotal = (1...5).reductions(+)
|
||||
print(inclusiveRunningTotal)
|
||||
// prints [1, 3, 6, 10, 15]
|
||||
```
|
||||
|
||||
## Detailed Design
|
||||
|
||||
One trio of methods are added to `LazySequenceProtocol` for a lazily evaluated
|
||||
sequence and another trio are added to `Sequence` which are eagerly evaluated.
|
||||
|
||||
```swift
|
||||
extension LazySequenceProtocol {
|
||||
|
||||
public func reductions<Result>(
|
||||
_ initial: Result,
|
||||
_ transform: @escaping (Result, Element) -> Result
|
||||
) -> ExclusiveReductions<Result, Self>
|
||||
|
||||
public func reductions<Result>(
|
||||
into initial: Result,
|
||||
_ transform: @escaping (inout Result, Element) -> Void
|
||||
) -> ExclusiveReductions<Result, Self>
|
||||
|
||||
public func reductions(
|
||||
_ transform: @escaping (Element, Element) -> Element
|
||||
) -> InclusiveReductions<Self>
|
||||
}
|
||||
```
|
||||
|
||||
```swift
|
||||
extension Sequence {
|
||||
|
||||
public func reductions<Result>(
|
||||
_ initial: Result,
|
||||
_ transform: (Result, Element) throws -> Result
|
||||
) rethrows -> [Result]
|
||||
|
||||
public func reductions<Result>(
|
||||
into initial: Result,
|
||||
_ transform: (inout Result, Element) throws -> Void
|
||||
) rethrows -> [Result]
|
||||
|
||||
public func reductions(
|
||||
_ transform: (Element, Element) throws -> Element
|
||||
) rethrows -> [Element]
|
||||
}
|
||||
```
|
||||
|
||||
### Complexity
|
||||
|
||||
Calling the lazy methods, those defined on `LazySequenceProtocol`, is O(_1_).
|
||||
Calling the eager methods, those returning an array, is O(_n_).
|
||||
|
||||
### Naming
|
||||
|
||||
While the name `scan` is the term of art for this function, it has been
|
||||
discussed that `reductions` aligns better with the existing `reduce` function
|
||||
and will aid newcomers that might not know the existing `scan` term.
|
||||
|
||||
Deprecated `scan` methods have been added for people who are familiar with the
|
||||
term, so they can easily discover the `reductions` methods via compiler
|
||||
deprecation warnings.
|
||||
|
||||
Below are two quotes from the Swift forum [discussion about SE-0045][SE-0045]
|
||||
which proposed adding `scan` to the standard library and one from
|
||||
[issue #25][Issue 25] on the swift-algorithms GitHub project. These provide
|
||||
the reasoning to use the name `reductions`.
|
||||
|
||||
[Brent Royal-Gordon][Brent_Royal-Gordon]:
|
||||
> I really like the `reduce`/`reductions` pairing instead of `reduce`/`scan`;
|
||||
it does a really good job of explaining the relationship between the two
|
||||
functions.
|
||||
|
||||
[David Rönnqvist][David Rönnqvist]:
|
||||
> As other have already pointed out, I also feel that `scan` is the least
|
||||
intuitive name among these and that the `reduce`/`reductions` pairing would do
|
||||
a good job at explaining the relation between the two.
|
||||
|
||||
[Kyle Macomber][Kyle Macomber]:
|
||||
> As someone unfamiliar with the prior art, `reductions` strikes me as very
|
||||
approachable—I feel like I can extrapolate the expected behavior purely from my
|
||||
familiarity with `reduce`.
|
||||
|
||||
As part of early discussions, it was decided to have two variants, one which
|
||||
takes an initial value to use for the first element in the returned sequence,
|
||||
and another which uses the first value of the base sequence as the initial
|
||||
value. C++ calls these variants exclusive and inclusive respectively and so
|
||||
these terms carry through as the name for the lazy sequences;
|
||||
`ExclusiveReductions` and `InclusiveReductions`.
|
||||
|
||||
[SE-0045]: https://forums.swift.org/t/review-se-0045-add-scan-prefix-while-drop-while-and-iterate-to-the-stdlib/2382
|
||||
[Issue 25]: https://github.com/apple/swift-algorithms/issues/25
|
||||
[Brent_Royal-Gordon]: https://forums.swift.org/t/review-se-0045-add-scan-prefix-while-drop-while-and-iterate-to-the-stdlib/2382/6
|
||||
[David Rönnqvist]: https://forums.swift.org/t/review-se-0045-add-scan-prefix-while-drop-while-and-iterate-to-the-stdlib/2382/8
|
||||
[Kyle Macomber]: https://github.com/apple/swift-algorithms/issues/25#issuecomment-709317894
|
||||
|
||||
### Comparison with other langauges
|
||||
|
||||
**C++:** As of C++17, the `<algorithm>` library includes both
|
||||
[`exclusive_scan`][C++ Exclusive] and [`inclusive_scan`][C++ Inclusive]
|
||||
functions.
|
||||
|
||||
**[Clojure][Clojure]:** Clojure 1.2 added a `reductions` function.
|
||||
|
||||
**[Haskell][Haskell]:** Haskell includes a `scan` function for its
|
||||
`Traversable` type, which is akin to Swift's `Sequence`.
|
||||
|
||||
**Python:** Python’s `itertools` includes an `accumulate` method. In version
|
||||
3.3, a function paramenter was added. Version 3.8 added the optional initial
|
||||
parameter.
|
||||
|
||||
**[Rust][Rust]:** Rust provides a `scan` function.
|
||||
|
||||
[C++ Exclusive]: https://en.cppreference.com/w/cpp/algorithm/exclusive_scan
|
||||
[C++ Inclusive]: https://en.cppreference.com/w/cpp/algorithm/inclusive_scan
|
||||
[Clojure]: http://clojure.github.io/clojure/clojure.core-api.html#clojure.core/reductions
|
||||
[Haskell]: http://hackage.haskell.org/package/base-4.8.2.0/docs/Prelude.html#v:scanl
|
||||
[Rust]: https://doc.rust-lang.org/std/iter/trait.Iterator.html#method.scan
|
||||
@@ -10,6 +10,7 @@ Read more about the package, and the intent behind it, in the [announcement on s
|
||||
|
||||
- [`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.
|
||||
- [`uniquePermutations(ofCount:)`](https://github.com/apple/swift-algorithms/blob/main/Guides/Permutations.md): Permutations of a collection's elements, skipping any duplicate permutations.
|
||||
|
||||
#### Mutating algorithms
|
||||
|
||||
|
||||
@@ -19,7 +19,7 @@ public struct Chain2<Base1: Sequence, Base2: Sequence>
|
||||
/// The second sequence in this chain.
|
||||
public let base2: Base2
|
||||
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal init(base1: Base1, base2: Base2) {
|
||||
self.base1 = base1
|
||||
self.base2 = base2
|
||||
@@ -35,7 +35,7 @@ extension Chain2: Sequence {
|
||||
@usableFromInline
|
||||
internal var iterator2: Base2.Iterator
|
||||
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal init(_ concatenation: Chain2) {
|
||||
iterator1 = concatenation.base1.makeIterator()
|
||||
iterator2 = concatenation.base2.makeIterator()
|
||||
@@ -71,13 +71,13 @@ extension Chain2: Collection where Base1: Collection, Base2: Collection {
|
||||
internal let position: Representation
|
||||
|
||||
/// Creates a new index into the first underlying collection.
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal init(first i: Base1.Index) {
|
||||
position = .first(i)
|
||||
}
|
||||
|
||||
/// Creates a new index into the second underlying collection.
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal init(second i: Base2.Index) {
|
||||
position = .second(i)
|
||||
}
|
||||
@@ -99,7 +99,7 @@ extension Chain2: Collection where Base1: Collection, Base2: Collection {
|
||||
|
||||
/// Converts an index of `Base1` to the corresponding `Index` by mapping
|
||||
/// `base1.endIndex` to `base2.startIndex`.
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal func convertIndex(_ i: Base1.Index) -> Index {
|
||||
i == base1.endIndex ? Index(second: base2.startIndex) : Index(first: i)
|
||||
}
|
||||
@@ -157,7 +157,7 @@ extension Chain2: Collection where Base1: Collection, Base2: Collection {
|
||||
: offsetBackward(i, by: -n, limitedBy: limit)
|
||||
}
|
||||
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal func offsetForward(
|
||||
_ i: Index, by n: Int, limitedBy limit: Index
|
||||
) -> Index? {
|
||||
@@ -197,7 +197,7 @@ extension Chain2: Collection where Base1: Collection, Base2: Collection {
|
||||
}
|
||||
}
|
||||
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal func offsetBackward(
|
||||
_ i: Index, by n: Int, limitedBy limit: Index
|
||||
) -> Index? {
|
||||
|
||||
@@ -27,7 +27,7 @@ public struct LazyChunked<Base: Collection, Subject> {
|
||||
@usableFromInline
|
||||
internal var firstUpperBound: Base.Index
|
||||
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal init(
|
||||
base: Base,
|
||||
projection: @escaping (Base.Element) -> Subject,
|
||||
@@ -51,7 +51,7 @@ extension LazyChunked: LazyCollectionProtocol {
|
||||
@usableFromInline
|
||||
internal var baseRange: Range<Base.Index>
|
||||
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal init(_ baseRange: Range<Base.Index>) {
|
||||
self.baseRange = baseRange
|
||||
}
|
||||
@@ -72,7 +72,7 @@ extension LazyChunked: LazyCollectionProtocol {
|
||||
|
||||
/// Returns the index in the base collection of the end of the chunk starting
|
||||
/// at the given index.
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal func endOfChunk(startingAt start: Base.Index) -> Base.Index {
|
||||
let subject = projection(base[start])
|
||||
return base[base.index(after: start)...]
|
||||
@@ -112,7 +112,7 @@ extension LazyChunked: BidirectionalCollection
|
||||
{
|
||||
/// Returns the index in the base collection of the start of the chunk ending
|
||||
/// at the given index.
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal func startOfChunk(endingAt end: Base.Index) -> Base.Index {
|
||||
let indexBeforeEnd = base.index(before: end)
|
||||
|
||||
@@ -174,7 +174,7 @@ extension Collection {
|
||||
/// predicate.
|
||||
///
|
||||
/// - Complexity: O(*n*), where *n* is the length of this collection.
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal func chunked<Subject>(
|
||||
on projection: (Element) throws -> Subject,
|
||||
by belongInSameGroup: (Subject, Subject) throws -> Bool
|
||||
@@ -273,7 +273,7 @@ extension ChunkedByCount: Collection {
|
||||
@usableFromInline
|
||||
internal let baseRange: Range<Base.Index>
|
||||
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal init(_baseRange: Range<Base.Index>) {
|
||||
self.baseRange = _baseRange
|
||||
}
|
||||
@@ -290,6 +290,7 @@ extension ChunkedByCount: Collection {
|
||||
}
|
||||
|
||||
/// - Complexity: O(1)
|
||||
@inlinable
|
||||
public subscript(i: Index) -> Element {
|
||||
precondition(i < endIndex, "Index out of range")
|
||||
return base[i.baseRange]
|
||||
@@ -392,7 +393,7 @@ extension ChunkedByCount {
|
||||
return index
|
||||
}
|
||||
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal func offsetForward(
|
||||
_ i: Index, offsetBy distance: Int, limit: Index? = nil
|
||||
) -> Index? {
|
||||
@@ -406,8 +407,8 @@ extension ChunkedByCount {
|
||||
}
|
||||
|
||||
// Convenience to compute offset backward base distance.
|
||||
@inline(__always)
|
||||
private func computeOffsetBackwardBaseDistance(
|
||||
@inlinable
|
||||
internal func computeOffsetBackwardBaseDistance(
|
||||
_ i: Index, _ distance: Int
|
||||
) -> Int {
|
||||
if i == endIndex {
|
||||
@@ -423,7 +424,7 @@ extension ChunkedByCount {
|
||||
return distance * chunkCount
|
||||
}
|
||||
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal func offsetBackward(
|
||||
_ i: Index, offsetBy distance: Int, limit: Index? = nil
|
||||
) -> Index? {
|
||||
@@ -438,8 +439,8 @@ extension ChunkedByCount {
|
||||
}
|
||||
|
||||
// Helper to compute index(offsetBy:) index.
|
||||
@inline(__always)
|
||||
private func makeOffsetIndex(
|
||||
@inlinable
|
||||
internal func makeOffsetIndex(
|
||||
from i: Index, baseBound: Base.Index, distance: Int, baseDistance: Int,
|
||||
limit: Index?, by limitFn: (Base.Index, Base.Index) -> Bool
|
||||
) -> Index? {
|
||||
|
||||
@@ -27,7 +27,7 @@ public struct Combinations<Base: Collection> {
|
||||
/// - Parameters:
|
||||
/// - base: The collection to iterate over for combinations.
|
||||
/// - k: The expected size of each combination.
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal init(_ base: Base, k: Int) {
|
||||
self.init(base, kRange: k...k)
|
||||
}
|
||||
@@ -37,7 +37,7 @@ public struct Combinations<Base: Collection> {
|
||||
/// - Parameters:
|
||||
/// - base: The collection to iterate over for combinations.
|
||||
/// - kRange: The range of accepted sizes of combinations.
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal init<R: RangeExpression>(
|
||||
_ base: Base, kRange: R
|
||||
) where R.Bound == Int {
|
||||
@@ -89,7 +89,7 @@ extension Combinations: Sequence {
|
||||
internal var kRange: Range<Int>
|
||||
|
||||
/// Whether or not iteration is finished (`kRange` is empty)
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal var isFinished: Bool {
|
||||
return kRange.isEmpty
|
||||
}
|
||||
@@ -97,6 +97,7 @@ extension Combinations: Sequence {
|
||||
@usableFromInline
|
||||
internal var indexes: [Base.Index]
|
||||
|
||||
@inlinable
|
||||
internal init(_ combinations: Combinations) {
|
||||
self.base = combinations.base
|
||||
self.kRange = combinations.kRange ?? 0..<0
|
||||
@@ -121,7 +122,7 @@ extension Combinations: Sequence {
|
||||
/// [2, 3, 4] *
|
||||
/// // Can't advance without needing to go past `base.endIndex`,
|
||||
/// // so the iteration is finished.
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal mutating func advance() {
|
||||
/// Advances `kRange` by incrementing its `lowerBound` until the range is
|
||||
/// empty, when iteration is finished.
|
||||
|
||||
@@ -14,7 +14,7 @@ public struct Cycle<Base: Collection> {
|
||||
/// The collection to repeat.
|
||||
public let base: Base
|
||||
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal init(base: Base) {
|
||||
self.base = base
|
||||
}
|
||||
@@ -29,7 +29,7 @@ extension Cycle: Sequence {
|
||||
@usableFromInline
|
||||
var current: Base.Index
|
||||
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal init(base: Base) {
|
||||
self.base = base
|
||||
self.current = base.startIndex
|
||||
|
||||
@@ -18,7 +18,7 @@ public struct Indexed<Base: Collection> {
|
||||
/// The base collection.
|
||||
public let base: Base
|
||||
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal init(base: Base) {
|
||||
self.base = base
|
||||
}
|
||||
|
||||
@@ -18,7 +18,7 @@ public struct Intersperse<Base: Sequence> {
|
||||
@usableFromInline
|
||||
internal let separator: Base.Element
|
||||
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal init(base: Base, separator: Base.Element) {
|
||||
self.base = base
|
||||
self.separator = separator
|
||||
@@ -37,7 +37,7 @@ extension Intersperse: Sequence {
|
||||
@usableFromInline
|
||||
internal var state = State.start
|
||||
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal init(iterator: Base.Iterator, separator: Base.Element) {
|
||||
self.iterator = iterator
|
||||
self.separator = separator
|
||||
@@ -89,6 +89,11 @@ extension Intersperse: Collection where Base: Collection {
|
||||
@usableFromInline
|
||||
internal let representation: Representation
|
||||
|
||||
@inlinable
|
||||
init(representation: Representation) {
|
||||
self.representation = representation
|
||||
}
|
||||
|
||||
@inlinable
|
||||
public static func < (lhs: Index, rhs: Index) -> Bool {
|
||||
switch (lhs.representation, rhs.representation) {
|
||||
@@ -101,12 +106,12 @@ extension Intersperse: Collection where Base: Collection {
|
||||
}
|
||||
}
|
||||
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
static func element(_ index: Base.Index) -> Self {
|
||||
Self(representation: .element(index))
|
||||
}
|
||||
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
static func separator(next: Base.Index) -> Self {
|
||||
Self(representation: .separator(next: next))
|
||||
}
|
||||
|
||||
@@ -34,7 +34,7 @@ public struct LazySplitSequence<Base: Sequence> {
|
||||
@usableFromInline
|
||||
internal let omittingEmptySubsequences: Bool
|
||||
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal init(
|
||||
base: Base,
|
||||
isSeparator: @escaping (Base.Element) -> Bool,
|
||||
@@ -72,7 +72,7 @@ extension LazySplitSequence {
|
||||
@usableFromInline
|
||||
internal var sequenceLength = 0
|
||||
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal init(
|
||||
base: Base.Iterator,
|
||||
whereSeparator: @escaping (Base.Element) -> Bool,
|
||||
@@ -360,7 +360,7 @@ public struct LazySplitCollection<Base: Collection> {
|
||||
@usableFromInline
|
||||
internal var _startIndex: Index
|
||||
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal init(
|
||||
base: Base,
|
||||
isSeparator: @escaping (Base.Element) -> Bool,
|
||||
@@ -415,7 +415,7 @@ extension LazySplitCollection: LazyCollectionProtocol {
|
||||
@usableFromInline
|
||||
internal let splitCount: Int
|
||||
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal init(
|
||||
baseRange: Range<Base.Index>,
|
||||
sequenceLength: Int,
|
||||
@@ -441,7 +441,7 @@ extension LazySplitCollection: LazyCollectionProtocol {
|
||||
|
||||
/// Returns the index of the subsequence starting at or after the given base
|
||||
/// collection index.
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal func indexForSubsequence(
|
||||
atOrAfter lowerBound: Base.Index,
|
||||
sequenceLength: Int,
|
||||
|
||||
@@ -120,7 +120,7 @@ extension Sequence {
|
||||
return try _minImplementation(count: count, sortedBy: areInIncreasingOrder)
|
||||
}
|
||||
|
||||
/// Returns the largets elements of this sequence, as sorted by the given
|
||||
/// Returns the largest elements of this sequence, as sorted by the given
|
||||
/// predicate.
|
||||
///
|
||||
/// This example partially sorts an array of integers to retrieve its three
|
||||
@@ -275,7 +275,7 @@ extension Collection {
|
||||
return try _minImplementation(count: count, sortedBy: areInIncreasingOrder)
|
||||
}
|
||||
|
||||
/// Returns the largets elements of this collection, as sorted by the given
|
||||
/// Returns the largest elements of this collection, as sorted by the given
|
||||
/// predicate.
|
||||
///
|
||||
/// This example partially sorts an array of integers to retrieve its three
|
||||
|
||||
@@ -21,7 +21,7 @@ extension MutableCollection {
|
||||
/// - Complexity: O(*n* log *n*), where *n* is the number of elements.
|
||||
/// - Precondition:
|
||||
/// `n == distance(from: range.lowerBound, to: range.upperBound)`
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal mutating func stablePartition(
|
||||
count n: Int,
|
||||
subrange: Range<Index>,
|
||||
|
||||
@@ -9,6 +9,72 @@
|
||||
//
|
||||
//===----------------------------------------------------------------------===//
|
||||
|
||||
//===----------------------------------------------------------------------===//
|
||||
// nextPermutation()
|
||||
//===----------------------------------------------------------------------===//
|
||||
|
||||
extension MutableCollection
|
||||
where Self: BidirectionalCollection, Element: Comparable
|
||||
{
|
||||
/// Permutes this collection's elements through all the lexical orderings.
|
||||
///
|
||||
/// Call `nextPermutation()` repeatedly starting with the collection in
|
||||
/// sorted order. When the full cycle of all permutations has been completed,
|
||||
/// the collection will be back in sorted order and this method will return
|
||||
/// `false`.
|
||||
///
|
||||
/// - Returns: A Boolean value indicating whether the collection still has
|
||||
/// remaining permutations. When this method returns `false`, the collection
|
||||
/// is in ascending order according to `areInIncreasingOrder`.
|
||||
///
|
||||
/// - Complexity: O(*n*), where *n* is the length of the collection.
|
||||
@inlinable
|
||||
internal mutating func nextPermutation(upperBound: Index? = nil) -> Bool {
|
||||
// Ensure we have > 1 element in the collection.
|
||||
guard !isEmpty else { return false }
|
||||
var i = index(before: endIndex)
|
||||
if i == startIndex { return false }
|
||||
|
||||
let upperBound = upperBound ?? endIndex
|
||||
|
||||
while true {
|
||||
let ip1 = i
|
||||
formIndex(before: &i)
|
||||
|
||||
// Find the last ascending pair (ie. ..., a, b, ... where a < b)
|
||||
if self[i] < self[ip1] {
|
||||
// Find the last element greater than self[i]
|
||||
// This is _always_ at most `ip1` due to if statement above
|
||||
let j = lastIndex(where: { self[i] < $0 })!
|
||||
|
||||
// At this point we have something like this:
|
||||
// 0, 1, 4, 3, 2
|
||||
// ^ ^
|
||||
// i j
|
||||
swapAt(i, j)
|
||||
self.reverse(subrange: ip1 ..< endIndex)
|
||||
|
||||
// Only return if we've made a change within ..<upperBound region
|
||||
if i < upperBound {
|
||||
return true
|
||||
} else {
|
||||
i = index(before: endIndex)
|
||||
continue
|
||||
}
|
||||
}
|
||||
|
||||
if i == startIndex {
|
||||
self.reverse()
|
||||
return false
|
||||
}
|
||||
}
|
||||
}
|
||||
}
|
||||
|
||||
//===----------------------------------------------------------------------===//
|
||||
// struct Permutations<Base>
|
||||
//===----------------------------------------------------------------------===//
|
||||
|
||||
/// A sequence of all the permutations of a collection's elements.
|
||||
public struct Permutations<Base: Collection> {
|
||||
/// The base collection to iterate over for permutations.
|
||||
@@ -28,7 +94,7 @@ public struct Permutations<Base: Collection> {
|
||||
/// - 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
|
||||
@inlinable
|
||||
internal init(_ base: Base, k: Int? = nil) {
|
||||
let kRange: ClosedRange<Int>?
|
||||
if let countToChoose = k {
|
||||
@@ -45,7 +111,7 @@ public struct Permutations<Base: Collection> {
|
||||
/// - 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
|
||||
@inlinable
|
||||
internal init<R: RangeExpression>(
|
||||
_ base: Base, kRange: R?
|
||||
) where R.Bound == Int {
|
||||
@@ -84,7 +150,7 @@ extension Permutations: Sequence {
|
||||
internal var kRange: Range<Int>
|
||||
|
||||
/// Whether or not iteration is finished (`kRange` is empty)
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal var isFinished: Bool {
|
||||
return kRange.isEmpty
|
||||
}
|
||||
@@ -92,7 +158,7 @@ extension Permutations: Sequence {
|
||||
@usableFromInline
|
||||
internal var indexes: [Base.Index]
|
||||
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal init(_ permutations: Permutations) {
|
||||
self.base = permutations.base
|
||||
self.baseCount = permutations.baseCount
|
||||
@@ -111,7 +177,7 @@ extension Permutations: Sequence {
|
||||
/// is in ascending order.
|
||||
///
|
||||
/// - Complexity: O(*n*), where *n* is the length of the collection.
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal mutating func nextState() -> Bool {
|
||||
let countToChoose = self.kRange.lowerBound
|
||||
let edge = countToChoose - 1
|
||||
@@ -194,54 +260,6 @@ extension Permutations: Sequence {
|
||||
|
||||
extension Permutations: LazySequenceProtocol where Base: LazySequenceProtocol {}
|
||||
|
||||
//===----------------------------------------------------------------------===//
|
||||
// nextPermutation()
|
||||
//===----------------------------------------------------------------------===//
|
||||
|
||||
extension MutableCollection
|
||||
where Self: BidirectionalCollection, Element: Comparable
|
||||
{
|
||||
/// Permutes this collection's elements through all the lexical orderings.
|
||||
///
|
||||
/// Call `nextPermutation()` repeatedly starting with the collection in
|
||||
/// sorted order. When the full cycle of all permutations has been completed,
|
||||
/// the collection will be back in sorted order and this method will return
|
||||
/// `false`.
|
||||
///
|
||||
/// - Returns: A Boolean value indicating whether the collection still has
|
||||
/// remaining permutations. When this method returns `false`, the collection
|
||||
/// is in ascending order according to `areInIncreasingOrder`.
|
||||
///
|
||||
/// - Complexity: O(*n*), where *n* is the length of the collection.
|
||||
@usableFromInline
|
||||
internal mutating func nextPermutation() -> Bool {
|
||||
// Ensure we have > 1 element in the collection.
|
||||
guard !isEmpty else { return false }
|
||||
var i = index(before: endIndex)
|
||||
if i == startIndex { return false }
|
||||
|
||||
while true {
|
||||
let ip1 = i
|
||||
formIndex(before: &i)
|
||||
|
||||
if self[i] < self[ip1] {
|
||||
var j = index(before: endIndex)
|
||||
while self[i] >= self[j] {
|
||||
formIndex(before: &j)
|
||||
}
|
||||
swapAt(i, j)
|
||||
self.reverse(subrange: ip1 ..< endIndex)
|
||||
return true
|
||||
}
|
||||
|
||||
if i == startIndex {
|
||||
self.reverse()
|
||||
return false
|
||||
}
|
||||
}
|
||||
}
|
||||
}
|
||||
|
||||
//===----------------------------------------------------------------------===//
|
||||
// permutations(ofCount:)
|
||||
//===----------------------------------------------------------------------===//
|
||||
@@ -268,34 +286,41 @@ extension Collection {
|
||||
/// // Davide, Celeste
|
||||
///
|
||||
/// This example prints _all_ the permutations (including an empty array) from
|
||||
/// the an array of numbers:
|
||||
/// 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]
|
||||
/// 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.
|
||||
/// The returned permutations are in ascending order by length, and then
|
||||
/// lexicographically within each group of the same length.
|
||||
///
|
||||
/// - Parameter kRange: A range of the number of elements to include in each
|
||||
/// permutation. `kRange` can be any integer range expression, and is
|
||||
/// clamped to the number of elements in this collection. Passing a range
|
||||
/// covering sizes greater than the number of elements in this collection
|
||||
/// results in an empty sequence.
|
||||
///
|
||||
/// - 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.
|
||||
/// 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
|
||||
@@ -346,11 +371,12 @@ extension Collection {
|
||||
///
|
||||
/// - Parameter k: The number of elements to include in each permutation.
|
||||
/// If `k` is `nil`, the resulting sequence represents permutations of this
|
||||
/// entire collection.
|
||||
/// entire collection. If `k` is greater than the number of elements in
|
||||
/// this collection, the resulting sequence is empty.
|
||||
///
|
||||
/// - 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.
|
||||
/// 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> {
|
||||
precondition(
|
||||
@@ -359,3 +385,196 @@ extension Collection {
|
||||
return Permutations(self, k: k)
|
||||
}
|
||||
}
|
||||
|
||||
//===----------------------------------------------------------------------===//
|
||||
// uniquePermutations()
|
||||
//===----------------------------------------------------------------------===//
|
||||
|
||||
/// A sequence of the unique permutations of the elements of a sequence or
|
||||
/// collection.
|
||||
///
|
||||
/// To create a `UniquePermutations` instance, call one of the
|
||||
/// `uniquePermutations` methods on your collection.
|
||||
public struct UniquePermutations<Base: Collection> {
|
||||
/// The base collection to iterate over for permutations.
|
||||
public let base: Base
|
||||
|
||||
@usableFromInline
|
||||
internal var indexes: [Base.Index]
|
||||
|
||||
@usableFromInline
|
||||
internal let kRange: Range<Int>
|
||||
}
|
||||
|
||||
extension UniquePermutations where Base.Element: Hashable {
|
||||
@inlinable
|
||||
internal static func _indexes(_ base: Base) -> [Base.Index] {
|
||||
let firstIndexesAndCountsByElement = Dictionary(
|
||||
base.indices.lazy.map { (base[$0], ($0, 1)) },
|
||||
uniquingKeysWith: { indexAndCount, _ in (indexAndCount.0, indexAndCount.1 + 1) })
|
||||
|
||||
return firstIndexesAndCountsByElement
|
||||
.values.sorted(by: { $0.0 < $1.0 })
|
||||
.flatMap { index, count in repeatElement(index, count: count) }
|
||||
}
|
||||
|
||||
@inlinable
|
||||
internal init(_ elements: Base) {
|
||||
self.indexes = Self._indexes(elements)
|
||||
self.base = elements
|
||||
self.kRange = self.indexes.count ..< (self.indexes.count + 1)
|
||||
}
|
||||
|
||||
@inlinable
|
||||
internal init<R: RangeExpression>(_ base: Base, _ range: R)
|
||||
where R.Bound == Int
|
||||
{
|
||||
self.indexes = Self._indexes(base)
|
||||
self.base = base
|
||||
|
||||
let upperBound = self.indexes.count + 1
|
||||
self.kRange = range.relative(to: 0 ..< .max)
|
||||
.clamped(to: 0 ..< upperBound)
|
||||
}
|
||||
}
|
||||
|
||||
extension UniquePermutations: Sequence {
|
||||
/// The iterator for a `UniquePermutations` instance.
|
||||
public struct Iterator: IteratorProtocol {
|
||||
@usableFromInline
|
||||
internal let base: Base
|
||||
|
||||
@usableFromInline
|
||||
internal var indexes: [Base.Index]
|
||||
|
||||
@usableFromInline
|
||||
internal var lengths: Range<Int>
|
||||
|
||||
@usableFromInline
|
||||
internal var initial = true
|
||||
|
||||
@inlinable
|
||||
internal init(_ elements: Base, indexes: [Base.Index], lengths: Range<Int>) {
|
||||
self.base = elements
|
||||
self.indexes = indexes
|
||||
self.lengths = lengths
|
||||
}
|
||||
|
||||
@inlinable
|
||||
public mutating func next() -> [Base.Element]? {
|
||||
// In the end case, `lengths` is an empty range.
|
||||
if lengths.isEmpty {
|
||||
return nil
|
||||
}
|
||||
|
||||
// The first iteration must produce the original sorted array, before any
|
||||
// permutations. We skip the permutation the first time so that we can
|
||||
// always mutate the array _before_ returning a slice, which avoids
|
||||
// copying when possible.
|
||||
if initial {
|
||||
initial = false
|
||||
return indexes[..<lengths.lowerBound].map { base[$0] }
|
||||
}
|
||||
|
||||
if !indexes.nextPermutation(upperBound: lengths.lowerBound) {
|
||||
lengths.removeFirst()
|
||||
|
||||
if lengths.isEmpty {
|
||||
return nil
|
||||
}
|
||||
}
|
||||
|
||||
return indexes[..<lengths.lowerBound].map { base[$0] }
|
||||
}
|
||||
}
|
||||
|
||||
@inlinable
|
||||
public func makeIterator() -> Iterator {
|
||||
Iterator(base, indexes: indexes, lengths: kRange)
|
||||
}
|
||||
}
|
||||
|
||||
extension UniquePermutations: LazySequenceProtocol where Base: LazySequenceProtocol {}
|
||||
|
||||
extension Collection where Element: Hashable {
|
||||
/// Returns a sequence of the unique permutations of this sequence of the
|
||||
/// specified length.
|
||||
///
|
||||
/// Use this method to iterate over the unique permutations of a sequence
|
||||
/// with repeating elements. This example prints every unique two-element
|
||||
/// permutation of an array of numbers:
|
||||
///
|
||||
/// let numbers = [1, 1, 2]
|
||||
/// for perm in numbers.uniquePermutations(ofCount: 2) {
|
||||
/// print(perm)
|
||||
/// }
|
||||
/// // [1, 1]
|
||||
/// // [1, 2]
|
||||
/// // [2, 1]
|
||||
///
|
||||
/// By contrast, the `permutations(ofCount:)` method permutes a collection's
|
||||
/// elements by position, and can include permutations with equal elements
|
||||
/// in each permutation:
|
||||
///
|
||||
/// for perm in numbers.permutations(ofCount: 2)
|
||||
/// print(perm)
|
||||
/// }
|
||||
/// // [1, 1]
|
||||
/// // [1, 1]
|
||||
/// // [1, 2]
|
||||
/// // [1, 2]
|
||||
/// // [2, 1]
|
||||
/// // [2, 1]
|
||||
///
|
||||
/// The returned permutations are in lexicographically sorted order.
|
||||
///
|
||||
/// - Parameter k: The number of elements to include in each permutation.
|
||||
/// If `k` is `nil`, the resulting sequence represents permutations of this
|
||||
/// entire collection. If `k` is greater than the number of elements in
|
||||
/// this collection, the resulting sequence is empty.
|
||||
///
|
||||
/// - Complexity: O(*n*), where *n* is the number of elements in this
|
||||
/// collection.
|
||||
public func uniquePermutations(ofCount k: Int? = nil) -> UniquePermutations<Self> {
|
||||
if let k = k {
|
||||
return UniquePermutations(self, k ..< (k + 1))
|
||||
} else {
|
||||
return UniquePermutations(self)
|
||||
}
|
||||
}
|
||||
|
||||
/// Returns a collection of the unique permutations of this sequence with
|
||||
/// lengths in the specified range.
|
||||
///
|
||||
/// Use this method to iterate over the unique permutations of a sequence
|
||||
/// with repeating elements. This example prints every unique permutation
|
||||
/// of an array of numbers with lengths through 2 elements:
|
||||
///
|
||||
/// let numbers = [1, 1, 2]
|
||||
/// for perm in numbers.uniquePermutations(ofCount: ...2) {
|
||||
/// print(perm)
|
||||
/// }
|
||||
/// // []
|
||||
/// // [1]
|
||||
/// // [2]
|
||||
/// // [1, 1]
|
||||
/// // [1, 2]
|
||||
/// // [2, 1]
|
||||
///
|
||||
/// The returned permutations are in ascending order by length, and then
|
||||
/// lexicographically within each group of the same length.
|
||||
///
|
||||
/// - Parameter kRange: A range of the number of elements to include in each
|
||||
/// permutation. `kRange` can be any integer range expression, and is
|
||||
/// clamped to the number of elements in this collection. Passing a range
|
||||
/// covering sizes greater than the number of elements in this collection
|
||||
/// results in an empty sequence.
|
||||
///
|
||||
/// - Complexity: O(*n*), where *n* is the number of elements in this
|
||||
/// collection.
|
||||
public func uniquePermutations<R: RangeExpression>(ofCount kRange: R) -> UniquePermutations<Self>
|
||||
where R.Bound == Int
|
||||
{
|
||||
UniquePermutations(self, kRange)
|
||||
}
|
||||
}
|
||||
@@ -16,7 +16,7 @@ public struct Product2<Base1: Sequence, Base2: Collection> {
|
||||
/// The inner sequence in the product.
|
||||
public let base2: Base2
|
||||
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal init(_ base1: Base1, _ base2: Base2) {
|
||||
self.base1 = base1
|
||||
self.base2 = base2
|
||||
@@ -35,7 +35,7 @@ extension Product2: Sequence {
|
||||
@usableFromInline
|
||||
internal let base2: Base2
|
||||
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal init(_ c: Product2) {
|
||||
self.base2 = c.base2
|
||||
self.i1 = c.base1.makeIterator()
|
||||
@@ -90,7 +90,7 @@ extension Product2: Collection where Base1: Collection {
|
||||
@usableFromInline
|
||||
internal var i2: Base2.Index
|
||||
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal init(i1: Base1.Index, i2: Base2.Index) {
|
||||
self.i1 = i1
|
||||
self.i2 = i2
|
||||
@@ -128,7 +128,7 @@ extension Product2: Collection where Base1: Collection {
|
||||
/// Forms an index from a pair of base indices, normalizing
|
||||
/// `(i, base2.endIndex)` to `(base1.index(after: i), base2.startIndex)` if
|
||||
/// necessary.
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal func normalizeIndex(_ i1: Base1.Index, _ i2: Base2.Index) -> Index {
|
||||
i2 == base2.endIndex
|
||||
? Index(i1: base1.index(after: i1), i2: base2.startIndex)
|
||||
@@ -195,6 +195,7 @@ extension Product2: Collection where Base1: Collection {
|
||||
}
|
||||
}
|
||||
|
||||
@inlinable
|
||||
public func index(_ i: Index, offsetBy distance: Int) -> Index {
|
||||
guard distance != 0 else { return i }
|
||||
|
||||
@@ -203,6 +204,7 @@ extension Product2: Collection where Base1: Collection {
|
||||
: offsetBackward(i, by: -distance)
|
||||
}
|
||||
|
||||
@inlinable
|
||||
public func index(
|
||||
_ i: Index,
|
||||
offsetBy distance: Int,
|
||||
@@ -219,21 +221,21 @@ extension Product2: Collection where Base1: Collection {
|
||||
}
|
||||
}
|
||||
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
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
|
||||
@inlinable
|
||||
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
|
||||
@inlinable
|
||||
internal func offsetForward(
|
||||
_ i: Index, by distance: Int, limitedBy limit: Index
|
||||
) -> Index? {
|
||||
@@ -311,7 +313,7 @@ extension Product2: Collection where Base1: Collection {
|
||||
.map { i2 in Index(i1: i1, i2: i2) }
|
||||
}
|
||||
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal func offsetBackward(
|
||||
_ i: Index, by distance: Int, limitedBy limit: Index
|
||||
) -> Index? {
|
||||
|
||||
@@ -0,0 +1,643 @@
|
||||
//===----------------------------------------------------------------------===//
|
||||
//
|
||||
// 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
|
||||
//
|
||||
//===----------------------------------------------------------------------===//
|
||||
|
||||
// MARK: - Exclusive Reductions
|
||||
|
||||
extension LazySequenceProtocol {
|
||||
|
||||
/// Returns a sequence containing the accumulated results of combining the
|
||||
/// elements of the sequence using the given closure.
|
||||
///
|
||||
/// This can be seen as applying the reduce function to each element and
|
||||
/// providing the initial value followed by these results as a sequence.
|
||||
///
|
||||
/// ```
|
||||
/// let runningTotal = [1, 2, 3, 4].lazy.reductions(0, +)
|
||||
/// print(Array(runningTotal))
|
||||
///
|
||||
/// // prints [0, 1, 3, 6, 10]
|
||||
/// ```
|
||||
///
|
||||
/// - Parameters:
|
||||
/// - initial: The value to use as the initial value.
|
||||
/// - transform: A closure that combines the previously reduced result and
|
||||
/// the next element in the receiving sequence.
|
||||
/// - Returns: A sequence of the initial value followed by the reduced
|
||||
/// elements.
|
||||
///
|
||||
/// - Complexity: O(1)
|
||||
@inlinable
|
||||
public func reductions<Result>(
|
||||
_ initial: Result,
|
||||
_ transform: @escaping (Result, Element) -> Result
|
||||
) -> ExclusiveReductions<Result, Self> {
|
||||
return reductions(into: initial) { result, element in
|
||||
result = transform(result, element)
|
||||
}
|
||||
}
|
||||
|
||||
/// Returns a sequence containing the accumulated results of combining the
|
||||
/// elements of the sequence using the given closure.
|
||||
///
|
||||
/// This can be seen as applying the reduce function to each element and
|
||||
/// providing the initial value followed by these results as a sequence.
|
||||
///
|
||||
/// ```
|
||||
/// let runningTotal = [1, 2, 3, 4].lazy.reductions(into: 0, +)
|
||||
/// print(Array(runningTotal))
|
||||
///
|
||||
/// // prints [0, 1, 3, 6, 10]
|
||||
/// ```
|
||||
///
|
||||
/// - Parameters:
|
||||
/// - initial: The value to use as the initial value.
|
||||
/// - transform: A closure that combines the previously reduced result and
|
||||
/// the next element in the receiving sequence.
|
||||
/// - Returns: A sequence of the initial value followed by the reduced
|
||||
/// elements.
|
||||
///
|
||||
/// - Complexity: O(1)
|
||||
@inlinable
|
||||
public func reductions<Result>(
|
||||
into initial: Result,
|
||||
_ transform: @escaping (inout Result, Element) -> Void
|
||||
) -> ExclusiveReductions<Result, Self> {
|
||||
ExclusiveReductions(base: self, initial: initial, transform: transform)
|
||||
}
|
||||
}
|
||||
|
||||
extension Sequence {
|
||||
|
||||
/// Returns an array containing the accumulated results of combining the
|
||||
/// elements of the sequence using the given closure.
|
||||
///
|
||||
/// This can be seen as applying the reduce function to each element and
|
||||
/// providing the initial value followed by these results as a sequence.
|
||||
///
|
||||
/// ```
|
||||
/// let runningTotal = [1, 2, 3, 4].reductions(0, +)
|
||||
/// print(runningTotal)
|
||||
///
|
||||
/// // prints [0, 1, 3, 6, 10]
|
||||
/// ```
|
||||
///
|
||||
/// When `reductions(_:_:)` is called, the following steps occur:
|
||||
///
|
||||
/// 1. The `initial` result is added to an array of results.
|
||||
/// 2. The `transform` closure is called with the `initial` result and the
|
||||
/// first element of the sequence, appending the result to the array.
|
||||
/// 3. The closure is called again repeatedly with the updated accumulating
|
||||
/// result and each element of the sequence, adding each result to the
|
||||
/// array.
|
||||
/// 4. When the sequence is exhausted, the results array is returned to the
|
||||
/// caller.
|
||||
///
|
||||
/// If the sequence has no elements, `transform` is never executed and
|
||||
/// an array containing only the `initial` result is returned.
|
||||
///
|
||||
/// - Parameters:
|
||||
/// - initial: The value to use as the initial value.
|
||||
/// - transform: A closure that combines the previously reduced result and
|
||||
/// the next element in the receiving sequence.
|
||||
/// - Returns: An array of the initial value followed by the reduced elements.
|
||||
///
|
||||
/// - Complexity: O(_n_), where _n_ is the length of the sequence.
|
||||
@inlinable
|
||||
public func reductions<Result>(
|
||||
_ initial: Result,
|
||||
_ transform: (Result, Element) throws -> Result
|
||||
) rethrows -> [Result] {
|
||||
return try reductions(into: initial) { result, element in
|
||||
result = try transform(result, element)
|
||||
}
|
||||
}
|
||||
|
||||
/// Returns an array containing the accumulated results of combining the
|
||||
/// elements of the sequence using the given closure.
|
||||
///
|
||||
/// This can be seen as applying the reduce function to each element and
|
||||
/// providing the initial value followed by these results as a sequence.
|
||||
///
|
||||
/// ```
|
||||
/// let runningTotal = [1, 2, 3, 4].reductions(into: 0, +)
|
||||
/// print(runningTotal)
|
||||
///
|
||||
/// // prints [0, 1, 3, 6, 10]
|
||||
/// ```
|
||||
///
|
||||
/// When `reductions(into:_:_)` is called, the following steps occur:
|
||||
///
|
||||
/// 1. The `initial` result is added to an array of results.
|
||||
/// 2. The `transform` closure is called with the `initial` result and the
|
||||
/// first element of the sequence, appending the result to the array.
|
||||
/// 3. The closure is called again repeatedly with the updated accumulating
|
||||
/// result and each element of the sequence, adding each result to the
|
||||
/// array.
|
||||
/// 4. When the sequence is exhausted, the results array is returned to the
|
||||
/// caller.
|
||||
///
|
||||
/// If the sequence has no elements, `transform` is never executed and
|
||||
/// an array containing only the `initial` result is returned.
|
||||
///
|
||||
/// - Parameters:
|
||||
/// - initial: The value to use as the initial value.
|
||||
/// - transform: A closure that combines the previously reduced result and
|
||||
/// the next element in the receiving sequence.
|
||||
/// - Returns: An array of the initial value followed by the reduced elements.
|
||||
///
|
||||
/// - Complexity: O(_n_), where _n_ is the length of the sequence.
|
||||
@inlinable
|
||||
public func reductions<Result>(
|
||||
into initial: Result,
|
||||
_ transform: (inout Result, Element) throws -> Void
|
||||
) rethrows -> [Result] {
|
||||
|
||||
var output = [Result]()
|
||||
output.reserveCapacity(underestimatedCount + 1)
|
||||
output.append(initial)
|
||||
|
||||
var initial = initial
|
||||
for element in self {
|
||||
try transform(&initial, element)
|
||||
output.append(initial)
|
||||
}
|
||||
|
||||
return output
|
||||
}
|
||||
}
|
||||
|
||||
/// A sequence of applying a transform to the element of a sequence and the
|
||||
/// previously transformed result.
|
||||
public struct ExclusiveReductions<Result, Base: Sequence> {
|
||||
@usableFromInline
|
||||
internal let base: Base
|
||||
|
||||
@usableFromInline
|
||||
internal let initial: Result
|
||||
|
||||
@usableFromInline
|
||||
internal let transform: (inout Result, Base.Element) -> Void
|
||||
|
||||
@inlinable
|
||||
internal init(
|
||||
base: Base,
|
||||
initial: Result,
|
||||
transform: @escaping (inout Result, Base.Element) -> Void
|
||||
) {
|
||||
self.base = base
|
||||
self.initial = initial
|
||||
self.transform = transform
|
||||
}
|
||||
}
|
||||
|
||||
extension ExclusiveReductions: Sequence {
|
||||
public struct Iterator: IteratorProtocol {
|
||||
@usableFromInline
|
||||
internal var iterator: Base.Iterator
|
||||
|
||||
@usableFromInline
|
||||
internal var current: Result?
|
||||
|
||||
@usableFromInline
|
||||
internal let transform: (inout Result, Base.Element) -> Void
|
||||
|
||||
@inlinable
|
||||
internal init(
|
||||
iterator: Base.Iterator,
|
||||
current: Result? = nil,
|
||||
transform: @escaping (inout Result, Base.Element) -> Void
|
||||
) {
|
||||
self.iterator = iterator
|
||||
self.current = current
|
||||
self.transform = transform
|
||||
}
|
||||
|
||||
@inlinable
|
||||
public mutating func next() -> Result? {
|
||||
guard let result = current else { return nil }
|
||||
current = iterator.next().map { element in
|
||||
var result = result
|
||||
transform(&result, element)
|
||||
return result
|
||||
}
|
||||
return result
|
||||
}
|
||||
}
|
||||
|
||||
@inlinable
|
||||
public func makeIterator() -> Iterator {
|
||||
Iterator(iterator: base.makeIterator(),
|
||||
current: initial,
|
||||
transform: transform)
|
||||
}
|
||||
}
|
||||
|
||||
extension ExclusiveReductions: Collection where Base: Collection {
|
||||
public struct Index: Comparable {
|
||||
@usableFromInline
|
||||
internal let representation: ReductionsIndexRepresentation<Base.Index, Result>
|
||||
|
||||
@inlinable
|
||||
internal init(
|
||||
_ representation: ReductionsIndexRepresentation<Base.Index, Result>
|
||||
) {
|
||||
self.representation = representation
|
||||
}
|
||||
|
||||
@inlinable
|
||||
public static func < (lhs: Self, rhs: Self) -> Bool {
|
||||
lhs.representation < rhs.representation
|
||||
}
|
||||
}
|
||||
|
||||
@inlinable
|
||||
public var startIndex: Index { Index(.start) }
|
||||
|
||||
@inlinable
|
||||
public var endIndex: Index { Index(.end) }
|
||||
|
||||
@inlinable
|
||||
public subscript(position: Index) -> Result {
|
||||
switch position.representation {
|
||||
case .start: return initial
|
||||
case .base(_, let result): return result
|
||||
case .end: fatalError("Cannot get element of end index.")
|
||||
}
|
||||
}
|
||||
|
||||
@inlinable
|
||||
public func index(after i: Index) -> Index {
|
||||
func index(base index: Base.Index, previous: Result) -> Index {
|
||||
guard index != base.endIndex else { return endIndex }
|
||||
var previous = previous
|
||||
transform(&previous, base[index])
|
||||
return Index(.base(index: index, result: previous))
|
||||
}
|
||||
switch i.representation {
|
||||
case .start:
|
||||
return index(base: base.startIndex, previous: initial)
|
||||
case let .base(i, result):
|
||||
return index(base: base.index(after: i), previous: result)
|
||||
case .end:
|
||||
fatalError("Cannot get index after end index.")
|
||||
}
|
||||
}
|
||||
|
||||
@inlinable
|
||||
public func distance(from start: Index, to end: Index) -> Int {
|
||||
switch (start.representation, end.representation) {
|
||||
case (.start, .start):
|
||||
return 0
|
||||
case let (.start, .base(index, _)):
|
||||
return base.distance(from: base.startIndex, to: index) + 1
|
||||
case (.start, .end):
|
||||
return base.distance(from: base.startIndex, to: base.endIndex) + 1
|
||||
case let (.base(index, _), .start):
|
||||
return base.distance(from: index, to: base.startIndex) - 1
|
||||
case let (.base(start, _), .base(end, _)):
|
||||
return base.distance(from: start, to: end)
|
||||
case let (.base(index, _), .end):
|
||||
return base.distance(from: index, to: base.endIndex)
|
||||
case (.end, .start):
|
||||
return base.distance(from: base.endIndex, to: base.startIndex) - 1
|
||||
case let (.end, .base(index, _)):
|
||||
return base.distance(from: base.endIndex, to: index)
|
||||
case (.end, .end):
|
||||
return 0
|
||||
}
|
||||
}
|
||||
}
|
||||
|
||||
extension ExclusiveReductions: LazySequenceProtocol
|
||||
where Base: LazySequenceProtocol {}
|
||||
|
||||
extension ExclusiveReductions: LazyCollectionProtocol
|
||||
where Base: LazyCollectionProtocol {}
|
||||
|
||||
// MARK: - Inclusive Reductions
|
||||
|
||||
extension LazySequenceProtocol {
|
||||
|
||||
/// Returns a sequence containing the accumulated results of combining the
|
||||
/// elements of the sequence using the given closure.
|
||||
///
|
||||
/// This can be seen as applying the reduce function to each element and
|
||||
/// providing the initial value followed by these results as a sequence.
|
||||
///
|
||||
/// ```
|
||||
/// let runningTotal = [1, 2, 3, 4].lazy.reductions(+)
|
||||
/// print(Array(runningTotal))
|
||||
///
|
||||
/// // prints [1, 3, 6, 10]
|
||||
/// ```
|
||||
///
|
||||
/// - Parameters:
|
||||
/// - transform: A closure that combines the previously reduced result and
|
||||
/// the next element in the receiving sequence.
|
||||
/// - Returns: A sequence of the reduced elements.
|
||||
///
|
||||
/// - Complexity: O(1)
|
||||
@inlinable
|
||||
public func reductions(
|
||||
_ transform: @escaping (Element, Element) -> Element
|
||||
) -> InclusiveReductions<Self> {
|
||||
InclusiveReductions(base: self, transform: transform)
|
||||
}
|
||||
}
|
||||
|
||||
extension Sequence {
|
||||
|
||||
/// Returns an array containing the accumulated results of combining the
|
||||
/// elements of the sequence using the given closure.
|
||||
///
|
||||
/// This can be seen as applying the reduce function to each element and
|
||||
/// providing the initial value followed by these results as a sequence.
|
||||
///
|
||||
/// ```
|
||||
/// let runningTotal = [1, 2, 3, 4].reductions(+)
|
||||
/// print(runningTotal)
|
||||
///
|
||||
/// // prints [1, 3, 6, 10]
|
||||
/// ```
|
||||
///
|
||||
/// When `reductions(_:)` is called, the following steps occur:
|
||||
///
|
||||
/// 1. The `transform` closure is called with the first and second elements
|
||||
/// of the sequence, appending the result to an array of results.
|
||||
/// 2. The closure is called again repeatedly with the updated accumulating
|
||||
/// result and the next element of the sequence, adding each result to the
|
||||
/// array.
|
||||
/// 3. When the sequence is exhausted, the results array is returned to the
|
||||
/// caller.
|
||||
///
|
||||
/// If the sequence has no elements, `transform` is never executed and
|
||||
/// an empty array is returned.
|
||||
///
|
||||
/// If the sequence has one element, `transform` is never executed and
|
||||
/// an array containing only that first element is returned.
|
||||
///
|
||||
/// - Parameters:
|
||||
/// - transform: A closure that combines the previously reduced result and
|
||||
/// the next element in the receiving sequence.
|
||||
/// - Returns: An array of the reduced elements.
|
||||
///
|
||||
/// - Complexity: O(_n_), where _n_ is the length of the sequence.
|
||||
@inlinable
|
||||
public func reductions(
|
||||
_ transform: (Element, Element) throws -> Element
|
||||
) rethrows -> [Element] {
|
||||
var iterator = makeIterator()
|
||||
guard let initial = iterator.next() else { return [] }
|
||||
return try IteratorSequence(iterator).reductions(initial, transform)
|
||||
}
|
||||
}
|
||||
|
||||
public struct InclusiveReductions<Base: Sequence> {
|
||||
@usableFromInline
|
||||
internal let base: Base
|
||||
|
||||
@usableFromInline
|
||||
internal let transform: (Base.Element, Base.Element) -> Base.Element
|
||||
|
||||
@inlinable
|
||||
internal init(
|
||||
base: Base,
|
||||
transform: @escaping (Base.Element, Base.Element) -> Base.Element
|
||||
) {
|
||||
self.base = base
|
||||
self.transform = transform
|
||||
}
|
||||
}
|
||||
|
||||
extension InclusiveReductions: Sequence {
|
||||
public struct Iterator: IteratorProtocol {
|
||||
@usableFromInline
|
||||
internal var iterator: Base.Iterator
|
||||
|
||||
@usableFromInline
|
||||
internal var element: Base.Element?
|
||||
|
||||
@usableFromInline
|
||||
internal let transform: (Base.Element, Base.Element) -> Base.Element
|
||||
|
||||
@inlinable
|
||||
internal init(
|
||||
iterator: Base.Iterator,
|
||||
element: Base.Element? = nil,
|
||||
transform: @escaping (Base.Element, Base.Element) -> Base.Element
|
||||
) {
|
||||
self.iterator = iterator
|
||||
self.element = element
|
||||
self.transform = transform
|
||||
}
|
||||
|
||||
@inlinable
|
||||
public mutating func next() -> Base.Element? {
|
||||
guard let previous = element else {
|
||||
element = iterator.next()
|
||||
return element
|
||||
}
|
||||
guard let next = iterator.next() else { return nil }
|
||||
element = transform(previous, next)
|
||||
return element
|
||||
}
|
||||
}
|
||||
|
||||
@inlinable
|
||||
public func makeIterator() -> Iterator {
|
||||
Iterator(iterator: base.makeIterator(),
|
||||
transform: transform)
|
||||
}
|
||||
}
|
||||
|
||||
extension InclusiveReductions: Collection where Base: Collection {
|
||||
public struct Index: Comparable {
|
||||
@usableFromInline
|
||||
internal let representation: ReductionsIndexRepresentation<Base.Index, Base.Element>
|
||||
|
||||
@inlinable
|
||||
internal init(
|
||||
_ representation: ReductionsIndexRepresentation<Base.Index, Base.Element>
|
||||
) {
|
||||
self.representation = representation
|
||||
}
|
||||
|
||||
@inlinable
|
||||
public static func < (lhs: Self, rhs: Self) -> Bool {
|
||||
lhs.representation < rhs.representation
|
||||
}
|
||||
}
|
||||
|
||||
@inlinable
|
||||
public var startIndex: Index {
|
||||
guard base.startIndex != base.endIndex else { return endIndex }
|
||||
return Index(.start)
|
||||
}
|
||||
|
||||
@inlinable
|
||||
public var endIndex: Index { Index(.end) }
|
||||
|
||||
@inlinable
|
||||
public subscript(position: Index) -> Base.Element {
|
||||
switch position.representation {
|
||||
case .start: return base[base.startIndex]
|
||||
case .base(_, let result): return result
|
||||
case .end: fatalError("Cannot get element of end index.")
|
||||
}
|
||||
}
|
||||
|
||||
@inlinable
|
||||
public func index(after i: Index) -> Index {
|
||||
func index(after i: Base.Index, previous: Base.Element) -> Index {
|
||||
let index = base.index(after: i)
|
||||
guard index != base.endIndex else { return endIndex }
|
||||
return Index(.base(index: index, result: transform(previous, base[index])))
|
||||
}
|
||||
switch i.representation {
|
||||
case .start:
|
||||
return index(after: base.startIndex, previous: base[base.startIndex])
|
||||
case let .base(i, element):
|
||||
return index(after: i, previous: element)
|
||||
case .end:
|
||||
fatalError("Cannot get index after end index.")
|
||||
}
|
||||
}
|
||||
|
||||
@inlinable
|
||||
public func distance(from start: Index, to end: Index) -> Int {
|
||||
switch (start.representation, end.representation) {
|
||||
case (.start, .start):
|
||||
return 0
|
||||
case let (.start, .base(index, _)):
|
||||
return base.distance(from: base.startIndex, to: index)
|
||||
case (.start, .end):
|
||||
return base.distance(from: base.startIndex, to: base.endIndex)
|
||||
case let (.base(index, _), .start):
|
||||
return base.distance(from: index, to: base.startIndex)
|
||||
case let (.base(start, _), .base(end, _)):
|
||||
return base.distance(from: start, to: end)
|
||||
case let (.base(index, _), .end):
|
||||
return base.distance(from: index, to: base.endIndex)
|
||||
case (.end, .start):
|
||||
return base.distance(from: base.endIndex, to: base.startIndex)
|
||||
case let (.end, .base(index, _)):
|
||||
return base.distance(from: base.endIndex, to: index)
|
||||
case (.end, .end):
|
||||
return 0
|
||||
}
|
||||
}
|
||||
}
|
||||
|
||||
extension InclusiveReductions: LazySequenceProtocol
|
||||
where Base: LazySequenceProtocol {}
|
||||
|
||||
extension InclusiveReductions: LazyCollectionProtocol
|
||||
where Base: LazyCollectionProtocol {}
|
||||
|
||||
// MARK: - ReductionsIndexRepresentation
|
||||
|
||||
@usableFromInline
|
||||
enum ReductionsIndexRepresentation<BaseIndex: Comparable, Result> {
|
||||
case start
|
||||
case base(index: BaseIndex, result: Result)
|
||||
case end
|
||||
}
|
||||
|
||||
extension ReductionsIndexRepresentation: Equatable {
|
||||
@inlinable
|
||||
static func == (lhs: Self, rhs: Self) -> Bool {
|
||||
switch (lhs, rhs) {
|
||||
case (.start, .start): return true
|
||||
case (.end, .end): return true
|
||||
case let (.base(lhs, _), .base(rhs, _)): return lhs == rhs
|
||||
default: return false
|
||||
}
|
||||
}
|
||||
}
|
||||
|
||||
extension ReductionsIndexRepresentation: Comparable {
|
||||
@inlinable
|
||||
static func < (lhs: Self, rhs: Self) -> Bool {
|
||||
switch (lhs, rhs) {
|
||||
case (_, .start): return false
|
||||
case (.start, _): return true
|
||||
case (.end, _): return false
|
||||
case (_, .end): return true
|
||||
case let (.base(lhs, _), .base(rhs, _)): return lhs < rhs
|
||||
}
|
||||
}
|
||||
}
|
||||
|
||||
// MARK: - Scan
|
||||
|
||||
extension LazySequenceProtocol {
|
||||
|
||||
@available(*, deprecated, message: "Use reductions(_:_:) instead.")
|
||||
@inlinable
|
||||
public func scan<Result>(
|
||||
_ initial: Result,
|
||||
_ transform: @escaping (Result, Element) -> Result
|
||||
) -> ExclusiveReductions<Result, Self> {
|
||||
reductions(initial, transform)
|
||||
}
|
||||
|
||||
@available(*, deprecated, message: "Use reductions(into:_:) instead.")
|
||||
@inlinable
|
||||
public func scan<Result>(
|
||||
into initial: Result,
|
||||
_ transform: @escaping (inout Result, Element) -> Void
|
||||
) -> ExclusiveReductions<Result, Self> {
|
||||
reductions(into: initial, transform)
|
||||
}
|
||||
}
|
||||
|
||||
extension Sequence {
|
||||
|
||||
@available(*, deprecated, message: "Use reductions(_:_:) instead.")
|
||||
@inlinable
|
||||
public func scan<Result>(
|
||||
_ initial: Result,
|
||||
_ transform: (Result, Element) throws -> Result
|
||||
) rethrows -> [Result] {
|
||||
try reductions(initial, transform)
|
||||
}
|
||||
|
||||
@available(*, deprecated, message: "Use reductions(into:_:) instead.")
|
||||
@inlinable
|
||||
public func scan<Result>(
|
||||
into initial: Result,
|
||||
_ transform: (inout Result, Element) throws -> Void
|
||||
) rethrows -> [Result] {
|
||||
try reductions(into: initial, transform)
|
||||
}
|
||||
}
|
||||
|
||||
extension LazySequenceProtocol {
|
||||
|
||||
@available(*, deprecated, message: "Use reductions(_:) instead.")
|
||||
@inlinable
|
||||
public func scan(
|
||||
_ transform: @escaping (Element, Element) -> Element
|
||||
) -> InclusiveReductions<Self> {
|
||||
reductions(transform)
|
||||
}
|
||||
}
|
||||
|
||||
extension Sequence {
|
||||
|
||||
@available(*, deprecated, message: "Use reductions(_:) instead.")
|
||||
@inlinable
|
||||
public func scan(
|
||||
_ transform: (Element, Element) throws -> Element
|
||||
) rethrows -> [Element] {
|
||||
try reductions(transform)
|
||||
}
|
||||
}
|
||||
@@ -29,7 +29,7 @@ extension MutableCollection where Self: BidirectionalCollection {
|
||||
///
|
||||
/// - Postcondition: For returned indices `(lower, upper)`:
|
||||
/// `lower == limit || upper == limit`
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
@discardableResult
|
||||
internal mutating func _reverse(
|
||||
subrange: Range<Index>, until limit: Index
|
||||
@@ -94,7 +94,7 @@ extension MutableCollection {
|
||||
/// - distance(from: lhs.lowerBound, to: p) == distance(from:
|
||||
/// rhs.lowerBound, to: q)
|
||||
/// - p == lhs.upperBound || q == rhs.upperBound
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal mutating func _swapNonemptySubrangePrefixes(
|
||||
_ lhs: Range<Index>, _ rhs: Range<Index>
|
||||
) -> (Index, Index) {
|
||||
|
||||
@@ -61,7 +61,7 @@ public struct StrideSequence<Base: Sequence>: Sequence {
|
||||
@usableFromInline
|
||||
internal let stride: Int
|
||||
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal init(base: Base, stride: Int) {
|
||||
precondition(stride > 0, "striding must be greater than zero")
|
||||
self.base = base
|
||||
@@ -82,7 +82,7 @@ extension StrideSequence {
|
||||
@usableFromInline
|
||||
internal var striding: Bool = false
|
||||
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal init(iterator: Base.Iterator, stride: Int) {
|
||||
self.iterator = iterator
|
||||
self.stride = stride
|
||||
@@ -122,7 +122,7 @@ public struct StrideCollection<Base: Collection> {
|
||||
@usableFromInline
|
||||
internal let stride: Int
|
||||
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal init(base: Base, stride: Int) {
|
||||
precondition(stride > 0, "striding must be greater than zero")
|
||||
self.base = base
|
||||
@@ -190,7 +190,7 @@ extension StrideCollection: Collection {
|
||||
: offsetBackward(i, offsetBy: -n, limitedBy: limit)
|
||||
}
|
||||
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal func offsetForward(
|
||||
_ i: Index,
|
||||
offsetBy n: Int,
|
||||
@@ -220,7 +220,7 @@ extension StrideCollection: Collection {
|
||||
}
|
||||
}
|
||||
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal func offsetBackward(
|
||||
_ i: Index,
|
||||
offsetBy n: Int,
|
||||
|
||||
@@ -45,7 +45,7 @@ extension Collection {
|
||||
/// be called again.
|
||||
///
|
||||
/// - Complexity: O(*n*), where *n* is the length of the collection.
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal func endOfPrefix(
|
||||
while predicate: (Element) throws -> Bool
|
||||
) rethrows -> Index {
|
||||
@@ -71,7 +71,7 @@ extension BidirectionalCollection {
|
||||
/// be called again.
|
||||
///
|
||||
/// - Complexity: O(*n*), where *n* is the length of the collection.
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal func startOfSuffix(
|
||||
while predicate: (Element) throws -> Bool
|
||||
) rethrows -> Index {
|
||||
|
||||
@@ -53,7 +53,7 @@ public struct Windows<Base: Collection> {
|
||||
@usableFromInline
|
||||
internal var firstUpperBound: Base.Index?
|
||||
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal init(base: Base, size: Int) {
|
||||
precondition(size > 0, "Windows size must be greater than zero")
|
||||
self.base = base
|
||||
@@ -72,7 +72,7 @@ extension Windows: Collection {
|
||||
@usableFromInline
|
||||
internal var upperBound: Base.Index
|
||||
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal init(lowerBound: Base.Index, upperBound: Base.Index) {
|
||||
self.lowerBound = lowerBound
|
||||
self.upperBound = upperBound
|
||||
@@ -150,21 +150,21 @@ extension Windows: Collection {
|
||||
}
|
||||
}
|
||||
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
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
|
||||
@inlinable
|
||||
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
|
||||
@inlinable
|
||||
internal func offsetForward(
|
||||
_ i: Index, by distance: Int, limitedBy limit: Index
|
||||
) -> Index? {
|
||||
@@ -235,7 +235,7 @@ extension Windows: Collection {
|
||||
}
|
||||
}
|
||||
|
||||
@usableFromInline
|
||||
@inlinable
|
||||
internal func offsetBackward(
|
||||
_ i: Index, by distance: Int, limitedBy limit: Index
|
||||
) -> Index? {
|
||||
|
||||
@@ -0,0 +1,81 @@
|
||||
//===----------------------------------------------------------------------===//
|
||||
//
|
||||
// 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 ReductionsTests: XCTestCase {
|
||||
|
||||
struct TestError: Error {}
|
||||
|
||||
// MARK: - Exclusive Reductions
|
||||
|
||||
func testExclusiveLazy() {
|
||||
XCTAssertEqualSequences((1...).prefix(4).lazy.reductions(0, +), [0, 1, 3, 6, 10])
|
||||
XCTAssertEqualSequences((1...).prefix(1).lazy.reductions(0, +), [0, 1])
|
||||
XCTAssertEqualSequences((1...).prefix(0).lazy.reductions(0, +), [0])
|
||||
|
||||
XCTAssertEqualCollections([1, 2, 3, 4].lazy.reductions(0, +), [0, 1, 3, 6, 10])
|
||||
XCTAssertEqualCollections([1].lazy.reductions(0, +), [0, 1])
|
||||
XCTAssertEqualCollections(EmptyCollection<Int>().lazy.reductions(0, +), [0])
|
||||
|
||||
XCTAssertEqual([1, 2, 3, 4].lazy.reductions(into: 0, +=), [0, 1, 3, 6, 10])
|
||||
|
||||
XCTAssertEqual([1].lazy.reductions(into: 0, +=), [0, 1])
|
||||
|
||||
XCTAssertEqual(EmptyCollection<Int>().lazy.reductions(into: 0, +=), [0])
|
||||
|
||||
XCTAssertLazySequence((1...).prefix(1).lazy.reductions(0, +))
|
||||
XCTAssertLazySequence([1].lazy.reductions(0, +))
|
||||
XCTAssertLazyCollection([1].lazy.reductions(0, +))
|
||||
}
|
||||
|
||||
func testExclusiveEager() {
|
||||
XCTAssertEqual([1, 2, 3, 4].reductions(0, +), [0, 1, 3, 6, 10])
|
||||
XCTAssertEqual([1].reductions(0, +), [0, 1])
|
||||
XCTAssertEqual(EmptyCollection<Int>().reductions(0, +), [0])
|
||||
|
||||
XCTAssertEqual([1, 2, 3, 4].reductions(into: 0, +=), [0, 1, 3, 6, 10])
|
||||
|
||||
XCTAssertEqual([1].reductions(into: 0, +=), [0, 1])
|
||||
|
||||
XCTAssertEqual(EmptyCollection<Int>().reductions(into: 0, +=), [0])
|
||||
|
||||
XCTAssertNoThrow(try [].reductions(0) { _, _ in throw TestError() })
|
||||
XCTAssertThrowsError(try [1].reductions(0) { _, _ in throw TestError() })
|
||||
}
|
||||
|
||||
// MARK: - Inclusive Reductions
|
||||
|
||||
func testInclusiveLazy() {
|
||||
XCTAssertEqualSequences((1...).prefix(4).lazy.reductions(+), [1, 3, 6, 10])
|
||||
XCTAssertEqualSequences((1...).prefix(1).lazy.reductions(+), [1])
|
||||
XCTAssertEqualSequences((1...).prefix(0).lazy.reductions(+), [])
|
||||
|
||||
XCTAssertEqualCollections([1, 2, 3, 4].lazy.reductions(+), [1, 3, 6, 10])
|
||||
XCTAssertEqualCollections([1].lazy.reductions(+), [1])
|
||||
XCTAssertEqualCollections(EmptyCollection<Int>().lazy.reductions(+), [])
|
||||
|
||||
XCTAssertLazySequence((1...).prefix(1).lazy.reductions(+))
|
||||
XCTAssertLazySequence([1].lazy.reductions(+))
|
||||
XCTAssertLazyCollection([1].lazy.reductions(+))
|
||||
}
|
||||
|
||||
func testInclusiveEager() {
|
||||
XCTAssertEqual([1, 2, 3, 4].reductions(+), [1, 3, 6, 10])
|
||||
XCTAssertEqual([1].reductions(+), [1])
|
||||
XCTAssertEqual(EmptyCollection<Int>().reductions(+), [])
|
||||
|
||||
XCTAssertNoThrow(try [].reductions { _, _ in throw TestError() })
|
||||
XCTAssertNoThrow(try [1].reductions { _, _ in throw TestError() })
|
||||
XCTAssertThrowsError(try [1, 1].reductions { _, _ in throw TestError() })
|
||||
}
|
||||
}
|
||||
@@ -148,6 +148,21 @@ func XCTAssertEqualSequences<S1: Sequence, S2: Sequence>(
|
||||
func XCTAssertLazySequence<S: LazySequenceProtocol>(_: S) {}
|
||||
func XCTAssertLazyCollection<S: LazyCollectionProtocol>(_: S) {}
|
||||
|
||||
/// Asserts two collections are equal by using their indices to access elements.
|
||||
func XCTAssertEqualCollections<C1: Collection, C2: Collection>(
|
||||
_ expression1: @autoclosure () throws -> C1,
|
||||
_ expression2: @autoclosure () throws -> C2,
|
||||
_ message: @autoclosure () -> String = "",
|
||||
file: StaticString = #file, line: UInt = #line
|
||||
) rethrows where C1.Element: Equatable, C1.Element == C2.Element {
|
||||
let c1 = try expression1()
|
||||
let c2 = try expression2()
|
||||
XCTAssertEqual(c1.indices.count, c2.indices.count, message(), file: file, line: line)
|
||||
for index in zip(c1.indices, c2.indices) {
|
||||
XCTAssertEqual(c1[index.0], c2[index.1], message(), file: file, line: line)
|
||||
}
|
||||
}
|
||||
|
||||
/// Tests that all index traversal methods behave as expected.
|
||||
///
|
||||
/// Verifies the correctness of the implementations of `startIndex`, `endIndex`,
|
||||
|
||||
@@ -0,0 +1,122 @@
|
||||
//===----------------------------------------------------------------------===//
|
||||
//
|
||||
// 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 UniquePermutationsTests: XCTestCase {
|
||||
static let numbers = [1, 1, 1, 2, 3]
|
||||
|
||||
static let numbersPermutations: [[[Int]]] = [
|
||||
// k = 0
|
||||
[[]],
|
||||
// 1
|
||||
[[1], [2], [3]],
|
||||
// 2
|
||||
[[1, 1], [1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]],
|
||||
// 3
|
||||
[[1, 1, 1], [1, 1, 2], [1, 1, 3],
|
||||
[1, 2, 1], [1, 2, 3], [1, 3, 1], [1, 3, 2],
|
||||
[2, 1, 1], [2, 1, 3], [2, 3, 1],
|
||||
[3, 1, 1], [3, 1, 2], [3, 2, 1]],
|
||||
// 4
|
||||
[[1, 1, 1, 2], [1, 1, 1, 3],
|
||||
[1, 1, 2, 1], [1, 1, 2, 3],
|
||||
[1, 1, 3, 1], [1, 1, 3, 2],
|
||||
[1, 2, 1, 1], [1, 2, 1, 3], [1, 2, 3, 1],
|
||||
[1, 3, 1, 1], [1, 3, 1, 2], [1, 3, 2, 1],
|
||||
[2, 1, 1, 1], [2, 1, 1, 3], [2, 1, 3, 1], [2, 3, 1, 1],
|
||||
[3, 1, 1, 1], [3, 1, 1, 2], [3, 1, 2, 1], [3, 2, 1, 1]],
|
||||
// 5
|
||||
[[1, 1, 1, 2, 3], [1, 1, 1, 3, 2],
|
||||
[1, 1, 2, 1, 3], [1, 1, 2, 3, 1],
|
||||
[1, 1, 3, 1, 2], [1, 1, 3, 2, 1],
|
||||
[1, 2, 1, 1, 3], [1, 2, 1, 3, 1], [1, 2, 3, 1, 1],
|
||||
[1, 3, 1, 1, 2], [1, 3, 1, 2, 1], [1, 3, 2, 1, 1],
|
||||
[2, 1, 1, 1, 3], [2, 1, 1, 3, 1], [2, 1, 3, 1, 1], [2, 3, 1, 1, 1],
|
||||
[3, 1, 1, 1, 2], [3, 1, 1, 2, 1], [3, 1, 2, 1, 1], [3, 2, 1, 1, 1]]
|
||||
]
|
||||
}
|
||||
|
||||
extension UniquePermutationsTests {
|
||||
func testEmpty() {
|
||||
XCTAssertEqualSequences(([] as [Int]).uniquePermutations(), [[]])
|
||||
XCTAssertEqualSequences(([] as [Int]).uniquePermutations(ofCount: 0), [[]])
|
||||
XCTAssertEqualSequences(([] as [Int]).uniquePermutations(ofCount: 1), [])
|
||||
XCTAssertEqualSequences(
|
||||
([] as [Int]).uniquePermutations(ofCount: 1...3), [])
|
||||
}
|
||||
|
||||
func testSingleCounts() {
|
||||
for (k, expectation) in Self.numbersPermutations.enumerated() {
|
||||
XCTAssertEqualSequences(
|
||||
expectation,
|
||||
Self.numbers.uniquePermutations(ofCount: k))
|
||||
}
|
||||
|
||||
XCTAssertEqualSequences(
|
||||
Self.numbersPermutations[5],
|
||||
Self.numbers.uniquePermutations())
|
||||
}
|
||||
|
||||
func testRanges() {
|
||||
for lower in Self.numbersPermutations.indices {
|
||||
// upper bounded
|
||||
XCTAssertEqualSequences(
|
||||
Self.numbersPermutations[...lower].joined(),
|
||||
Self.numbers.uniquePermutations(ofCount: ...lower))
|
||||
|
||||
// lower bounded
|
||||
XCTAssertEqualSequences(
|
||||
Self.numbersPermutations[lower...].joined(),
|
||||
Self.numbers.uniquePermutations(ofCount: lower...))
|
||||
|
||||
for upper in lower..<Self.numbersPermutations.count {
|
||||
XCTAssertEqualSequences(
|
||||
Self.numbersPermutations[lower..<upper].joined(),
|
||||
Self.numbers.uniquePermutations(ofCount: lower..<upper))
|
||||
}
|
||||
}
|
||||
}
|
||||
}
|
||||
|
||||
extension UniquePermutationsTests {
|
||||
private final class IntBox: Hashable {
|
||||
var value: Int
|
||||
|
||||
init(_ value: Int) {
|
||||
self.value = value
|
||||
}
|
||||
|
||||
static func == (lhs: IntBox, rhs: IntBox) -> Bool {
|
||||
lhs.value == rhs.value
|
||||
}
|
||||
|
||||
func hash(into hasher: inout Hasher) {
|
||||
hasher.combine(value)
|
||||
}
|
||||
}
|
||||
|
||||
func testFirstUnique() {
|
||||
// When duplicate elements are encountered, all permutations use the first
|
||||
// instance of the duplicated elements.
|
||||
let numbers = Self.numbers.map(IntBox.init)
|
||||
for k in 0...numbers.count {
|
||||
for p in numbers.uniquePermutations(ofCount: k) {
|
||||
XCTAssertTrue(p.filter { $0.value == 1 }.allSatisfy { $0 === numbers[0] })
|
||||
}
|
||||
}
|
||||
}
|
||||
|
||||
func testLaziness() {
|
||||
XCTAssertLazySequence("ABCD".lazy.uniquePermutations())
|
||||
}
|
||||
}
|
||||
Reference in new issue
Block a user