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`
490 lines
15 KiB
Swift
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)
|
|
}
|
|
}
|