mirror of
https://github.com/apple/swift-algorithms
synced 2026-11-22 04:10:39 +00:00
646 lines
19 KiB
Swift
646 lines
19 KiB
Swift
//===----------------------------------------------------------------------===//
|
|
//
|
|
// 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)
|
|
}
|
|
}
|