mirror of
https://github.com/apple/swift-algorithms
synced 2026-11-22 04:10:39 +00:00
* Rename types to include a Sequence or Collection suffix, and clean up some guides * Various refactors * Replace `validateIndexTraversals` test method with `IndexValidator` type * Add LazySequenceProtocol to StridingSequence, StridingCollection * Update the Numerics dependency to 1.0 * Set `IndexedCollection.Indices` to `Base.Indices` * Remove deprecations * Update the changelog/README for the 1.0.0 release * Fix compiler error on Linux * Rename `WindowsCollection` to `WindowsOfCountCollection`
670 lines
21 KiB
Swift
670 lines
21 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
|
||
//
|
||
//===----------------------------------------------------------------------===//
|
||
|
||
//===----------------------------------------------------------------------===//
|
||
// Intersperse
|
||
//===----------------------------------------------------------------------===//
|
||
|
||
/// A sequence that presents the elements of a base sequence of elements with a
|
||
/// separator between each of those elements.
|
||
public struct InterspersedSequence<Base: Sequence> {
|
||
@usableFromInline
|
||
internal let base: Base
|
||
|
||
@usableFromInline
|
||
internal let separator: Base.Element
|
||
|
||
@inlinable
|
||
internal init(base: Base, separator: Base.Element) {
|
||
self.base = base
|
||
self.separator = separator
|
||
}
|
||
}
|
||
|
||
extension InterspersedSequence: Sequence {
|
||
/// The iterator for an `InterspersedSequence` sequence.
|
||
public struct Iterator: IteratorProtocol {
|
||
@usableFromInline
|
||
internal enum State {
|
||
case start
|
||
case element(Base.Element)
|
||
case separator
|
||
}
|
||
|
||
@usableFromInline
|
||
internal var iterator: Base.Iterator
|
||
|
||
@usableFromInline
|
||
internal let separator: Base.Element
|
||
|
||
@usableFromInline
|
||
internal var state = State.start
|
||
|
||
@inlinable
|
||
internal init(iterator: Base.Iterator, separator: Base.Element) {
|
||
self.iterator = iterator
|
||
self.separator = separator
|
||
}
|
||
|
||
@inlinable
|
||
public mutating func next() -> Base.Element? {
|
||
// After the start, the state flips between element and separator. Before
|
||
// returning a separator, a check is made for the next element as a
|
||
// separator is only returned between two elements. The next element is
|
||
// stored to allow it to be returned in the next iteration.
|
||
switch state {
|
||
case .start:
|
||
state = .separator
|
||
return iterator.next()
|
||
case .separator:
|
||
guard let next = iterator.next() else { return nil }
|
||
state = .element(next)
|
||
return separator
|
||
case .element(let element):
|
||
state = .separator
|
||
return element
|
||
}
|
||
}
|
||
}
|
||
|
||
@inlinable
|
||
public func makeIterator() -> InterspersedSequence<Base>.Iterator {
|
||
Iterator(iterator: base.makeIterator(), separator: separator)
|
||
}
|
||
}
|
||
|
||
extension InterspersedSequence: Collection where Base: Collection {
|
||
/// A position in an `InterspersedSequence` instance.
|
||
public struct Index: Comparable {
|
||
@usableFromInline
|
||
internal enum Representation: Equatable {
|
||
case element(Base.Index)
|
||
case separator(next: Base.Index)
|
||
}
|
||
|
||
@usableFromInline
|
||
internal let representation: Representation
|
||
|
||
@inlinable
|
||
internal init(representation: Representation) {
|
||
self.representation = representation
|
||
}
|
||
|
||
@inlinable
|
||
public static func < (lhs: Index, rhs: Index) -> Bool {
|
||
switch (lhs.representation, rhs.representation) {
|
||
case let (.element(li), .element(ri)),
|
||
let (.separator(next: li), .separator(next: ri)),
|
||
let (.element(li), .separator(next: ri)):
|
||
return li < ri
|
||
case let (.separator(next: li), .element(ri)):
|
||
return li <= ri
|
||
}
|
||
}
|
||
|
||
@inlinable
|
||
internal static func element(_ index: Base.Index) -> Self {
|
||
Self(representation: .element(index))
|
||
}
|
||
|
||
@inlinable
|
||
internal static func separator(next: Base.Index) -> Self {
|
||
Self(representation: .separator(next: next))
|
||
}
|
||
}
|
||
|
||
@inlinable
|
||
public var startIndex: Index {
|
||
base.startIndex == base.endIndex ? endIndex : .element(base.startIndex)
|
||
}
|
||
|
||
@inlinable
|
||
public var endIndex: Index {
|
||
.separator(next: base.endIndex)
|
||
}
|
||
|
||
@inlinable
|
||
public func index(after i: Index) -> Index {
|
||
precondition(i != endIndex, "Can't advance past endIndex")
|
||
switch i.representation {
|
||
case let .element(index):
|
||
return .separator(next: base.index(after: index))
|
||
case let .separator(next):
|
||
return .element(next)
|
||
}
|
||
}
|
||
|
||
@inlinable
|
||
public subscript(position: Index) -> Element {
|
||
switch position.representation {
|
||
case .element(let index): return base[index]
|
||
case .separator: return separator
|
||
}
|
||
}
|
||
|
||
@inlinable
|
||
public func distance(from start: Index, to end: Index) -> Int {
|
||
switch (start.representation, end.representation) {
|
||
case let (.element(element), .separator(next: separator)):
|
||
return 2 * base.distance(from: element, to: separator) - 1
|
||
case let (.separator(next: separator), .element(element)):
|
||
return 2 * base.distance(from: separator, to: element) + 1
|
||
case let (.element(start), .element(end)),
|
||
let (.separator(start), .separator(end)):
|
||
return 2 * base.distance(from: start, to: end)
|
||
}
|
||
}
|
||
|
||
@inlinable
|
||
public func index(_ index: Index, offsetBy distance: Int) -> Index {
|
||
distance >= 0
|
||
? offsetForward(index, by: distance)
|
||
: offsetBackward(index, by: -distance)
|
||
}
|
||
|
||
@inlinable
|
||
public func index(
|
||
_ index: Index,
|
||
offsetBy distance: Int,
|
||
limitedBy limit: Index
|
||
) -> Index? {
|
||
if distance >= 0 {
|
||
return limit >= index
|
||
? offsetForward(index, by: distance, limitedBy: limit)
|
||
: offsetForward(index, by: distance)
|
||
} else {
|
||
return limit <= index
|
||
? offsetBackward(index, by: -distance, limitedBy: limit)
|
||
: offsetBackward(index, by: -distance)
|
||
}
|
||
}
|
||
|
||
@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
|
||
}
|
||
|
||
@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
|
||
}
|
||
|
||
@inlinable
|
||
internal func offsetForward(
|
||
_ index: Index, by distance: Int, limitedBy limit: Index
|
||
) -> Index? {
|
||
assert(distance >= 0)
|
||
assert(limit >= index)
|
||
|
||
switch (index.representation, limit.representation, distance.isMultiple(of: 2)) {
|
||
case let (.element(index), .element(limit), true),
|
||
let (.separator(next: index), .element(limit), false):
|
||
return base.index(index, offsetBy: distance / 2, limitedBy: limit)
|
||
.map { .element($0) }
|
||
|
||
case let (.element(index), .element(limit), false),
|
||
let (.element(index), .separator(next: limit), false),
|
||
let (.separator(next: index), .element(limit), true),
|
||
let (.separator(next: index), .separator(next: limit), true):
|
||
return base.index(index, offsetBy: (distance + 1) / 2, limitedBy: limit)
|
||
.map { .separator(next: $0) }
|
||
|
||
case let (.element(index), .separator(next: limit), true),
|
||
let (.separator(next: index), .separator(next: limit), false):
|
||
return base.index(index, offsetBy: distance / 2, limitedBy: limit)
|
||
.flatMap { $0 == limit ? nil : .element($0) }
|
||
}
|
||
}
|
||
|
||
@inlinable
|
||
internal func offsetBackward(
|
||
_ index: Index, by distance: Int, limitedBy limit: Index
|
||
) -> Index? {
|
||
assert(distance >= 0)
|
||
assert(limit <= index)
|
||
|
||
switch (index.representation, limit.representation, distance.isMultiple(of: 2)) {
|
||
case let (.element(index), .element(limit), true),
|
||
let (.element(index), .separator(next: limit), true),
|
||
let (.separator(next: index), .element(limit), false),
|
||
let (.separator(next: index), .separator(next: limit), false):
|
||
return base.index(index, offsetBy: -((distance + 1) / 2), limitedBy: limit)
|
||
.map { .element($0) }
|
||
|
||
case let (.element(index), .separator(next: limit), false),
|
||
let (.separator(next: index), .separator(next: limit), true):
|
||
return base.index(index, offsetBy: -(distance / 2), limitedBy: limit)
|
||
.map { .separator(next: $0) }
|
||
|
||
case let (.element(index), .element(limit), false),
|
||
let (.separator(next: index), .element(limit), true):
|
||
return base.index(index, offsetBy: -(distance / 2), limitedBy: limit)
|
||
.flatMap { $0 == limit ? nil : .separator(next: $0) }
|
||
}
|
||
}
|
||
}
|
||
|
||
extension InterspersedSequence: BidirectionalCollection
|
||
where Base: BidirectionalCollection
|
||
{
|
||
@inlinable
|
||
public func index(before i: Index) -> Index {
|
||
precondition(i != startIndex, "Can't move before startIndex")
|
||
switch i.representation {
|
||
case let .element(index):
|
||
return .separator(next: index)
|
||
case let .separator(next):
|
||
return .element(base.index(before: next))
|
||
}
|
||
}
|
||
}
|
||
|
||
extension InterspersedSequence: RandomAccessCollection
|
||
where Base: RandomAccessCollection {}
|
||
|
||
extension InterspersedSequence: LazySequenceProtocol
|
||
where Base: LazySequenceProtocol {}
|
||
|
||
extension InterspersedSequence: LazyCollectionProtocol
|
||
where Base: LazySequenceProtocol & Collection {}
|
||
|
||
//===----------------------------------------------------------------------===//
|
||
// InterspersedMap
|
||
//===----------------------------------------------------------------------===//
|
||
|
||
|
||
/// A sequence over the results of applying a closure to the sequence's
|
||
/// elements, with a separator that separates each pair of adjacent transformed
|
||
/// values.
|
||
@usableFromInline
|
||
internal struct InterspersedMapSequence<Base: Sequence, Result> {
|
||
@usableFromInline
|
||
internal let base: Base
|
||
|
||
@usableFromInline
|
||
internal let transform: (Base.Element) -> Result
|
||
|
||
@usableFromInline
|
||
internal let separator: (Base.Element, Base.Element) -> Result
|
||
}
|
||
|
||
extension InterspersedMapSequence: Sequence {
|
||
@usableFromInline
|
||
internal struct Iterator: IteratorProtocol {
|
||
@usableFromInline
|
||
internal enum State {
|
||
case start
|
||
case element(Base.Element)
|
||
case separator(previous: Base.Element)
|
||
}
|
||
|
||
@usableFromInline
|
||
internal var base: Base.Iterator
|
||
|
||
@usableFromInline
|
||
internal let transform: (Base.Element) -> Result
|
||
|
||
@usableFromInline
|
||
internal let separator: (Base.Element, Base.Element) -> Result
|
||
|
||
@usableFromInline
|
||
internal var state = State.start
|
||
|
||
@inlinable
|
||
internal init(
|
||
base: Base.Iterator,
|
||
transform: @escaping (Base.Element) -> Result,
|
||
separator: @escaping (Base.Element, Base.Element) -> Result
|
||
) {
|
||
self.base = base
|
||
self.transform = transform
|
||
self.separator = separator
|
||
}
|
||
|
||
@inlinable
|
||
internal mutating func next() -> Result? {
|
||
switch state {
|
||
case .start:
|
||
guard let first = base.next() else { return nil }
|
||
state = .separator(previous: first)
|
||
return transform(first)
|
||
case .separator(let previous):
|
||
guard let next = base.next() else { return nil }
|
||
state = .element(next)
|
||
return separator(previous, next)
|
||
case .element(let element):
|
||
state = .separator(previous: element)
|
||
return transform(element)
|
||
}
|
||
}
|
||
}
|
||
|
||
@inlinable
|
||
internal func makeIterator() -> Iterator {
|
||
Iterator(
|
||
base: base.makeIterator(),
|
||
transform: transform,
|
||
separator: separator)
|
||
}
|
||
}
|
||
|
||
extension InterspersedMapSequence: Collection where Base: Collection {
|
||
@usableFromInline
|
||
internal struct Index: Comparable {
|
||
@usableFromInline
|
||
internal enum Representation {
|
||
case element(Base.Index)
|
||
case separator(previous: Base.Index, next: Base.Index)
|
||
}
|
||
|
||
@usableFromInline
|
||
internal let representation: Representation
|
||
|
||
@inlinable
|
||
internal init(representation: Representation) {
|
||
self.representation = representation
|
||
}
|
||
|
||
@inlinable
|
||
internal static func element(_ index: Base.Index) -> Self {
|
||
Self(representation: .element(index))
|
||
}
|
||
|
||
@inlinable
|
||
internal static func separator(previous: Base.Index, next: Base.Index) -> Self {
|
||
Self(representation: .separator(previous: previous, next: next))
|
||
}
|
||
|
||
@inlinable
|
||
internal static func == (lhs: Self, rhs: Self) -> Bool {
|
||
switch (lhs.representation, rhs.representation) {
|
||
case let (.element(lhs), .element(rhs)),
|
||
let (.separator(_, next: lhs), .separator(_, next: rhs)):
|
||
return lhs == rhs
|
||
case (.element, .separator), (.separator, .element):
|
||
return false
|
||
}
|
||
}
|
||
|
||
@inlinable
|
||
internal static func < (lhs: Self, rhs: Self) -> Bool {
|
||
switch (lhs.representation, rhs.representation) {
|
||
case let (.element(lhs), .element(rhs)),
|
||
let (.separator(_, next: lhs), .separator(_, next: rhs)),
|
||
let (.element(lhs), .separator(_, next: rhs)),
|
||
let (.separator(previous: lhs, _), .element(rhs)):
|
||
return lhs < rhs
|
||
}
|
||
}
|
||
}
|
||
|
||
@inlinable
|
||
internal var startIndex: Index {
|
||
base.isEmpty ? endIndex : .element(base.startIndex)
|
||
}
|
||
|
||
@inlinable
|
||
internal var endIndex: Index {
|
||
.separator(previous: base.endIndex, next: base.endIndex)
|
||
}
|
||
|
||
@inlinable
|
||
internal func index(after index: Index) -> Index {
|
||
switch index.representation {
|
||
case .element(let index):
|
||
let next = base.index(after: index)
|
||
return .separator(previous: index, next: next)
|
||
case .separator(_, let next):
|
||
return .element(next)
|
||
}
|
||
}
|
||
|
||
@inlinable
|
||
internal subscript(position: Index) -> Result {
|
||
switch position.representation {
|
||
case .element(let index):
|
||
return transform(base[index])
|
||
case let .separator(previous, next):
|
||
return separator(base[previous], base[next])
|
||
}
|
||
}
|
||
|
||
@inlinable
|
||
internal func distance(from start: Index, to end: Index) -> Int {
|
||
switch (start.representation, end.representation) {
|
||
case let (.element(lhs), .element(rhs)),
|
||
let (.separator(_, next: lhs), .separator(_, next: rhs)):
|
||
return 2 * base.distance(from: lhs, to: rhs)
|
||
case let (.element(lhs), .separator(_, next: rhs)):
|
||
return 2 * base.distance(from: lhs, to: rhs) - 1
|
||
case let (.separator(_, next: lhs), .element(rhs)):
|
||
return 2 * base.distance(from: lhs, to: rhs) + 1
|
||
}
|
||
}
|
||
|
||
@inlinable
|
||
internal func index(_ index: Index, offsetBy distance: Int) -> Index {
|
||
guard distance != 0 else { return index }
|
||
|
||
return distance > 0
|
||
? offsetForward(index, by: distance)
|
||
: offsetBackward(index, by: -distance)
|
||
}
|
||
|
||
@inlinable
|
||
internal func index(
|
||
_ index: Index,
|
||
offsetBy distance: Int,
|
||
limitedBy limit: Index
|
||
) -> Index? {
|
||
guard distance != 0 else { return index }
|
||
|
||
if distance > 0 {
|
||
return limit >= index
|
||
? offsetForward(index, by: distance, limitedBy: limit)
|
||
: offsetForward(index, by: distance)
|
||
} else {
|
||
return limit <= index
|
||
? offsetBackward(index, by: -distance, limitedBy: limit)
|
||
: offsetBackward(index, by: -distance)
|
||
}
|
||
}
|
||
|
||
@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
|
||
}
|
||
|
||
@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
|
||
}
|
||
|
||
@inlinable
|
||
internal func offsetForward(
|
||
_ index: Index, by distance: Int, limitedBy limit: Index
|
||
) -> Index? {
|
||
assert(distance > 0)
|
||
assert(limit >= index)
|
||
|
||
switch (index.representation, limit.representation, distance.isMultiple(of: 2)) {
|
||
case let (.element(index), .element(limit), true),
|
||
let (.separator(_, next: index), .element(limit), false):
|
||
return base.index(index, offsetBy: distance / 2, limitedBy: limit)
|
||
.map { .element($0) }
|
||
|
||
case let (.element(index), .element(limit), false),
|
||
let (.element(index), .separator(_, next: limit), false),
|
||
let (.separator(_, next: index), .element(limit), true),
|
||
let (.separator(_, next: index), .separator(_, next: limit), true):
|
||
return base.index(index, offsetBy: (distance - 1) / 2, limitedBy: limit)
|
||
.flatMap {
|
||
guard $0 != limit else { return nil }
|
||
let next = base.index(after: $0)
|
||
return next == base.endIndex
|
||
? endIndex
|
||
: .separator(previous: $0, next: next)
|
||
}
|
||
|
||
case let (.element(index), .separator(_, next: limit), true),
|
||
let (.separator(_, next: index), .separator(_, next: limit), false):
|
||
return base.index(index, offsetBy: distance / 2, limitedBy: limit)
|
||
.flatMap { $0 == limit ? nil : .element($0) }
|
||
}
|
||
}
|
||
|
||
@inlinable
|
||
internal func offsetBackward(
|
||
_ index: Index, by distance: Int, limitedBy limit: Index
|
||
) -> Index? {
|
||
assert(distance > 0)
|
||
assert(limit <= index)
|
||
|
||
switch (index.representation, limit.representation, distance.isMultiple(of: 2)) {
|
||
case let (.element(index), .element(limit), true),
|
||
let (.element(index), .separator(_, next: limit), true),
|
||
let (.separator(_, next: index), .element(limit), false),
|
||
let (.separator(_, next: index), .separator(_, next: limit), false):
|
||
return base.index(index, offsetBy: -((distance + 1) / 2), limitedBy: limit)
|
||
.map { .element($0) }
|
||
|
||
case let (.element(index), .separator(_, next: limit), false),
|
||
let (.separator(_, next: index), .separator(_, next: limit), true):
|
||
return base.index(index, offsetBy: -(distance / 2), limitedBy: limit)
|
||
.map { .separator(previous: base.index($0, offsetBy: -1), next: $0) }
|
||
|
||
case let (.element(index), .element(limit), false),
|
||
let (.separator(_, next: index), .element(limit), true):
|
||
return base.index(index, offsetBy: -(distance / 2), limitedBy: limit)
|
||
.flatMap {
|
||
$0 == limit
|
||
? nil
|
||
: .separator(previous: base.index($0, offsetBy: -1), next: $0)
|
||
}
|
||
}
|
||
}
|
||
}
|
||
|
||
extension InterspersedMapSequence: BidirectionalCollection
|
||
where Base: BidirectionalCollection
|
||
{
|
||
@inlinable
|
||
internal func index(before index: Index) -> Index {
|
||
switch index.representation {
|
||
case .element(let index):
|
||
let previous = base.index(before: index)
|
||
return .separator(previous: previous, next: index)
|
||
case let .separator(previous, next):
|
||
let index = next == base.endIndex ? base.index(before: next) : previous
|
||
return .element(index)
|
||
}
|
||
}
|
||
}
|
||
|
||
extension InterspersedMapSequence.Index: Hashable
|
||
where Base.Index: Hashable
|
||
{
|
||
@inlinable
|
||
internal func hash(into hasher: inout Hasher) {
|
||
switch representation {
|
||
case .element(let base):
|
||
hasher.combine(false)
|
||
hasher.combine(base)
|
||
case .separator(_, let next):
|
||
hasher.combine(true)
|
||
hasher.combine(next)
|
||
}
|
||
}
|
||
}
|
||
|
||
extension InterspersedMapSequence: LazySequenceProtocol {}
|
||
extension InterspersedMapSequence: LazyCollectionProtocol
|
||
where Base: Collection {}
|
||
|
||
//===----------------------------------------------------------------------===//
|
||
// interspersed(with:)
|
||
//===----------------------------------------------------------------------===//
|
||
|
||
extension Sequence {
|
||
/// Returns a sequence containing elements of this sequence with the given
|
||
/// separator inserted in between each element.
|
||
///
|
||
/// Any value of the sequence's element type can be used as the separator.
|
||
///
|
||
/// ```
|
||
/// for value in [1,2,3].interspersed(with: 0) {
|
||
/// print(value)
|
||
/// }
|
||
/// // 1
|
||
/// // 0
|
||
/// // 2
|
||
/// // 0
|
||
/// // 3
|
||
/// ```
|
||
///
|
||
/// The following shows a String being interspersed with a Character:
|
||
/// ```
|
||
/// let result = "ABCDE".interspersed(with: "-")
|
||
/// print(String(result))
|
||
/// // "A-B-C-D-E"
|
||
/// ```
|
||
///
|
||
/// - Parameter separator: Value to insert in between each of this sequence’s
|
||
/// elements.
|
||
/// - Returns: The interspersed sequence of elements.
|
||
///
|
||
/// - Complexity: O(1)
|
||
@inlinable
|
||
public func interspersed(
|
||
with separator: Element
|
||
) -> InterspersedSequence<Self> {
|
||
InterspersedSequence(base: self, separator: separator)
|
||
}
|
||
}
|
||
|
||
//===----------------------------------------------------------------------===//
|
||
// lazy.interspersedMap(_:with:)
|
||
//===----------------------------------------------------------------------===//
|
||
|
||
extension LazySequenceProtocol {
|
||
/// Returns a sequence over the results of applying a closure to the
|
||
/// sequence's elements, with a separator that separates each pair of adjacent
|
||
/// transformed values.
|
||
///
|
||
/// The transformation closure lets you intersperse a sequence using a
|
||
/// separator of a different type than the original's sequence's elements.
|
||
/// Each separator is produced by a closure that is given access to the
|
||
/// two elements in the original sequence right before and after it.
|
||
///
|
||
/// let strings = [1, 2, 2].interspersedMap(String.init,
|
||
/// with: { $0 == $1 ? " == " : " != " })
|
||
/// print(strings.joined()) // "1 != 2 == 2"
|
||
///
|
||
@usableFromInline
|
||
internal func interspersedMap<Result>(
|
||
_ transform: @escaping (Element) -> Result,
|
||
with separator: @escaping (Element, Element) -> Result
|
||
) -> InterspersedMapSequence<Elements, Result> {
|
||
InterspersedMapSequence(
|
||
base: elements,
|
||
transform: transform,
|
||
separator: separator)
|
||
}
|
||
}
|