Files
swift-algorithms/Sources/Algorithms/Intersperse.swift
Tim Vermeulen c5ea9e3e36 Prepare for Swift Algorithms 1.0 (#167)
* 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`
2021-09-09 01:01:36 +02:00

670 lines
21 KiB
Swift
Raw Permalink Blame History

This file contains ambiguous Unicode characters
This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
//===----------------------------------------------------------------------===//
//
// 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)
}
}