Files
swift-algorithms/Sources/Algorithms/Joined.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

490 lines
15 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
//
//===----------------------------------------------------------------------===//
//===----------------------------------------------------------------------===//
// JoinedBySequence
//===----------------------------------------------------------------------===//
/// A sequence that presents the elements of a base sequence of sequences
/// concatenated using a given separator.
public struct JoinedBySequence<Base: Sequence, Separator: Sequence>
where Base.Element: Sequence, Base.Element.Element == Separator.Element
{
@usableFromInline
internal typealias Inner = FlattenSequence<InterspersedSequence<
LazyMapSequence<Base, EitherSequence<Base.Element, Separator>>>>
@usableFromInline
internal let inner: Inner
@inlinable
internal init(base: Base, separator: Separator) {
self.inner = base.lazy
.map(EitherSequence.left)
.interspersed(with: .right(separator))
.joined()
}
}
extension JoinedBySequence: Sequence {
public struct Iterator: IteratorProtocol {
@usableFromInline
internal var inner: Inner.Iterator
@inlinable
internal init(inner: Inner.Iterator) {
self.inner = inner
}
@inlinable
public mutating func next() -> Base.Element.Element? {
inner.next()
}
}
@inlinable
public func makeIterator() -> Iterator {
Iterator(inner: inner.makeIterator())
}
}
extension JoinedBySequence: LazySequenceProtocol
where Base: LazySequenceProtocol {}
//===----------------------------------------------------------------------===//
// JoinedByClosureSequence
//===----------------------------------------------------------------------===//
/// A sequence that presents the elements of a base sequence of sequences
/// concatenated using a given separator that depends on the sequences right
/// before and after it.
public struct JoinedByClosureSequence<Base: Sequence, Separator: Sequence>
where Base.Element: Sequence, Base.Element.Element == Separator.Element
{
@usableFromInline
internal typealias Inner = FlattenSequence<InterspersedMapSequence<
Base, EitherSequence<Base.Element, Separator>>>
@usableFromInline
internal let inner: Inner
@inlinable
internal init(
base: Base,
separator: @escaping (Base.Element, Base.Element) -> Separator
) {
self.inner = base.lazy
.interspersedMap(
EitherSequence.left,
with: { EitherSequence.right(separator($0, $1)) })
.joined()
}
}
extension JoinedByClosureSequence: Sequence {
public struct Iterator: IteratorProtocol {
@usableFromInline
internal var inner: Inner.Iterator
@inlinable
internal init(inner: Inner.Iterator) {
self.inner = inner
}
@inlinable
public mutating func next() -> Base.Element.Element? {
inner.next()
}
}
@inlinable
public func makeIterator() -> Iterator {
Iterator(inner: inner.makeIterator())
}
}
extension JoinedByClosureSequence: LazySequenceProtocol {}
//===----------------------------------------------------------------------===//
// JoinedByCollection
//===----------------------------------------------------------------------===//
/// A collection that presents the elements of a base collection of collections
/// concatenated using a given separator.
public struct JoinedByCollection<Base: Collection, Separator: Collection>
where Base.Element: Collection, Base.Element.Element == Separator.Element
{
@usableFromInline
internal typealias Inner = FlattenCollection<InterspersedSequence<
LazyMapSequence<Base, EitherSequence<Base.Element, Separator>>>>
@usableFromInline
internal let inner: Inner
@inlinable
internal init(base: Base, separator: Separator) {
self.inner = base.lazy
.map(EitherSequence.left)
.interspersed(with: .right(separator))
.joined()
}
}
extension JoinedByCollection: Collection {
public struct Index: Comparable {
@usableFromInline
internal let inner: Inner.Index
@inlinable
internal init(_ inner: Inner.Index) {
self.inner = inner
}
@inlinable
public static func == (lhs: Self, rhs: Self) -> Bool {
lhs.inner == rhs.inner
}
@inlinable
public static func < (lhs: Self, rhs: Self) -> Bool {
lhs.inner < rhs.inner
}
}
@inlinable
public var startIndex: Index {
Index(inner.startIndex)
}
@inlinable
public var endIndex: Index {
Index(inner.endIndex)
}
@inlinable
public func index(after index: Index) -> Index {
Index(inner.index(after: index.inner))
}
@inlinable
public subscript(position: Index) -> Base.Element.Element {
inner[position.inner]
}
@inlinable
public func index(_ index: Index, offsetBy distance: Int) -> Index {
Index(inner.index(index.inner, offsetBy: distance))
}
@inlinable
public func index(
_ index: Index,
offsetBy distance: Int,
limitedBy limit: Index
) -> Index? {
inner.index(index.inner, offsetBy: distance, limitedBy: limit.inner)
.map(Index.init)
}
@inlinable
public func distance(from start: Index, to end: Index) -> Int {
inner.distance(from: start.inner, to: end.inner)
}
}
extension JoinedByCollection: BidirectionalCollection
where Base: BidirectionalCollection,
Base.Element: BidirectionalCollection,
Separator: BidirectionalCollection
{
@inlinable
public func index(before index: Index) -> Index {
Index(inner.index(before: index.inner))
}
}
extension JoinedByCollection: LazySequenceProtocol, LazyCollectionProtocol
where Base: LazySequenceProtocol {}
//===----------------------------------------------------------------------===//
// JoinedByClosureCollection
//===----------------------------------------------------------------------===//
/// A collection that presents the elements of a base collection of collections
/// concatenated using a given separator that depends on the collections right
/// before and after it.
public struct JoinedByClosureCollection<Base: Collection, Separator: Collection>
where Base.Element: Collection, Base.Element.Element == Separator.Element
{
@usableFromInline
internal typealias Inner = FlattenCollection<InterspersedMapSequence<
Base, EitherSequence<Base.Element, Separator>>>
@usableFromInline
internal let inner: Inner
@inlinable
internal init(
base: Base,
separator: @escaping (Base.Element, Base.Element) -> Separator
) {
self.inner = base.lazy
.interspersedMap(
EitherSequence.left,
with: { EitherSequence.right(separator($0, $1)) })
.joined()
}
}
extension JoinedByClosureCollection: Collection {
public struct Index: Comparable {
@usableFromInline
internal let inner: Inner.Index
@inlinable
internal init(_ inner: Inner.Index) {
self.inner = inner
}
@inlinable
public static func == (lhs: Self, rhs: Self) -> Bool {
lhs.inner == rhs.inner
}
@inlinable
public static func < (lhs: Self, rhs: Self) -> Bool {
lhs.inner < rhs.inner
}
}
@inlinable
public var startIndex: Index {
Index(inner.startIndex)
}
@inlinable
public var endIndex: Index {
Index(inner.endIndex)
}
@inlinable
public func index(after index: Index) -> Index {
Index(inner.index(after: index.inner))
}
@inlinable
public subscript(position: Index) -> Base.Element.Element {
inner[position.inner]
}
@inlinable
public func index(_ index: Index, offsetBy distance: Int) -> Index {
Index(inner.index(index.inner, offsetBy: distance))
}
@inlinable
public func index(
_ index: Index,
offsetBy distance: Int,
limitedBy limit: Index
) -> Index? {
inner.index(index.inner, offsetBy: distance, limitedBy: limit.inner)
.map(Index.init)
}
@inlinable
public func distance(from start: Index, to end: Index) -> Int {
inner.distance(from: start.inner, to: end.inner)
}
}
extension JoinedByClosureCollection: BidirectionalCollection
where Base: BidirectionalCollection,
Base.Element: BidirectionalCollection,
Separator: BidirectionalCollection
{
@inlinable
public func index(before index: Index) -> Index {
Index(inner.index(before: index.inner))
}
}
extension JoinedByClosureCollection: LazyCollectionProtocol {}
//===----------------------------------------------------------------------===//
// Sequence.joined(by:)
//===----------------------------------------------------------------------===//
extension Sequence where Element: Sequence {
/// Returns the concatenation of the elements in this sequence of sequences,
/// inserting the given separator between each sequence.
///
/// for x in [[1, 2], [3, 4], [5, 6]].joined(by: 100) {
/// print(x)
/// }
/// // 1, 2, 100, 3, 4, 100, 5, 6
@inlinable
public func joined(by separator: Element.Element)
-> JoinedBySequence<Self, CollectionOfOne<Element.Element>>
{
joined(by: CollectionOfOne(separator))
}
/// Returns the concatenation of the elements in this sequence of sequences,
/// inserting the given separator between each sequence.
///
/// for x in [[1, 2], [3, 4], [5, 6]].joined(by: [100, 200]) {
/// print(x)
/// }
/// // 1, 2, 100, 200, 3, 4, 100, 200, 5, 6
@inlinable
public func joined<Separator>(
by separator: Separator
) -> JoinedBySequence<Self, Separator>
where Separator: Collection, Separator.Element == Element.Element
{
JoinedBySequence(base: self, separator: separator)
}
@inlinable
internal func _joined(
by update: (inout [Element.Element], Element, Element) throws -> Void
) rethrows -> [Element.Element] {
var iterator = makeIterator()
guard let first = iterator.next() else { return [] }
var result = Array(first)
var previous = first
while let next = iterator.next() {
try update(&result, previous, next)
result.append(contentsOf: next)
previous = next
}
return result
}
/// Returns the concatenation of the elements in this sequence of sequences,
/// inserting the separator produced by the closure between each sequence.
///
/// for x in [[1, 2], [3, 4], [5, 6]].joined(by: { $0.last! * $1.first! }) {
/// print(x)
/// }
/// // 1, 2, 6, 3, 4, 20, 5, 6
@inlinable
public func joined(
by separator: (Element, Element) throws -> Element.Element
) rethrows -> [Element.Element] {
try _joined(by: { $0.append(try separator($1, $2)) })
}
/// Returns the concatenation of the elements in this sequence of sequences,
/// inserting the separator produced by the closure between each sequence.
///
/// for x in [[1, 2], [3, 4], [5, 6]].joined(by: { [100 * $0.last!, 100 * $1.first!] }) {
/// print(x)
/// }
/// // 1, 2, 200, 300, 3, 4, 400, 500, 5, 6
@inlinable
public func joined<Separator>(
by separator: (Element, Element) throws -> Separator
) rethrows -> [Element.Element]
where Separator: Sequence, Separator.Element == Element.Element
{
try _joined(by: { $0.append(contentsOf: try separator($1, $2)) })
}
}
//===----------------------------------------------------------------------===//
// LazySequenceProtocol.joined(by:)
//===----------------------------------------------------------------------===//
extension LazySequenceProtocol where Element: Sequence {
/// Returns the concatenation of the elements in this sequence of sequences,
/// inserting the separator produced by the closure between each sequence.
@inlinable
public func joined(
by separator: @escaping (Element, Element) -> Element.Element
) -> JoinedByClosureSequence<Elements, CollectionOfOne<Element.Element>> {
joined(by: { CollectionOfOne(separator($0, $1)) })
}
/// Returns the concatenation of the elements in this sequence of sequences,
/// inserting the separator produced by the closure between each sequence.
@inlinable
public func joined<Separator>(
by separator: @escaping (Element, Element) -> Separator
) -> JoinedByClosureSequence<Elements, Separator> {
JoinedByClosureSequence(base: elements, separator: separator)
}
}
//===----------------------------------------------------------------------===//
// Collection.joined(by:)
//===----------------------------------------------------------------------===//
extension Collection where Element: Collection {
/// Returns the concatenation of the elements in this collection of
/// collections, inserting the given separator between each collection.
///
/// for x in [[1, 2], [3, 4], [5, 6]].joined(by: 100) {
/// print(x)
/// }
/// // 1, 2, 100, 3, 4, 100, 5, 6
@inlinable
public func joined(by separator: Element.Element)
-> JoinedByCollection<Self, CollectionOfOne<Element.Element>>
{
joined(by: CollectionOfOne(separator))
}
/// Returns the concatenation of the elements in this collection of
/// collections, inserting the given separator between each collection.
///
/// for x in [[1, 2], [3, 4], [5, 6]].joined(by: [100, 200]) {
/// print(x)
/// }
/// // 1, 2, 100, 200, 3, 4, 100, 200, 5, 6
@inlinable
public func joined<Separator>(by separator: Separator)
-> JoinedByCollection<Self, Separator>
{
JoinedByCollection(base: self, separator: separator)
}
}
//===----------------------------------------------------------------------===//
// LazySequenceProtocol.joined(by:) where Self: Collection
//===----------------------------------------------------------------------===//
extension LazySequenceProtocol where Elements: Collection, Element: Collection {
/// Returns the concatenation of the elements in this collection of
/// collections, inserting the separator produced by the closure between each
/// sequence.
@inlinable
public func joined(
by separator: @escaping (Element, Element) -> Element.Element
) -> JoinedByClosureCollection<Elements, CollectionOfOne<Element.Element>> {
joined(by: { CollectionOfOne(separator($0, $1)) })
}
/// Returns the concatenation of the elements in this collection of
/// collections, inserting the separator produced by the closure between each
/// sequence.
@inlinable
public func joined<Separator>(
by separator: @escaping (Element, Element) -> Separator
) -> JoinedByClosureCollection<Elements, Separator> {
JoinedByClosureCollection(base: elements, separator: separator)
}
}