Searching for a subsequence within a sequence. Also, rotating elements and a ring-buffer collection.

MultipleSearch.swift

/*
 MultipleSearch.swift -- Sequence and collection multi-element search, all locations

 Copyright (c) 2019 Daryle Walker

 */

// MARK: Searching for every occurance of a string of elements within a sequence

extension Sequence {

    /**
     Returns all subsequences of the sequence that match the given collection, *i.e.* equivalent elements in the same order, using the given predicate as the equivalence test, in a collection of the given type.

     - Precondition: `areEquivalent` must be an equivalence relation over the elements.

     - Parameter pattern: A collection to compare to this sequence.
     - Parameter allowingOverlap: Whether or not to include matching subsequences that start before the previous one ends.
     - Parameter storingAs: A metatype specifier for the collection type to be returned.
     - Parameter areEquivalent: A predicate that returns `true` if its two arguments are equivalent; otherwise, `false`.

     - Returns: A collection of collections of the matching subsequences' elements.

     - Complexity: O(*nm*), where *m* is the length of this sequence and *n* is the length of the pattern.
     */
    public func allMatches<Pattern: Collection, Result: RangeReplaceableCollection>(for pattern: Pattern, allowingOverlap: Bool, storingAs: Result.Type, by areEquivalent: (Element, Pattern.Element) throws -> Bool) rethrows -> Result where Result.Element: RangeReplaceableCollection, Result.Element.Element == Element {
        // If the pattern is empty, return an empty subsequence after each element, plus one before the first
        var result = Result()
        var iterator = makeIterator()
        var innerResult = Result.Element()
        guard !pattern.isEmpty else {
            result.append(innerResult)
            while iterator.next() != nil {
                result.append(innerResult)
            }
            return result
        }

        // Prime the initial buffer
        let patternCount = pattern.count
        innerResult.reserveCapacity(patternCount)
        for _ in 0..<patternCount {
            guard let nextBuffered = iterator.next() else { return result }

            innerResult.append(nextBuffered)
        }

        // Check for a match after every buffer update
        var buffer = RingBuffer(innerResult)!
        updateLoop: while true {
            if try buffer.elementsEqual(pattern, by: areEquivalent) {
                innerResult.replaceSubrange(innerResult.startIndex ..< innerResult.endIndex, with: buffer)
                result.append(innerResult)

                // Skip over the current elements when overlap is banned.
                if !allowingOverlap {
                    // Skip one because it'll be inserted by the next loop
                    for _ in 0..<patternCount - 1 {
                        if let afterOverlap = iterator.next() {
                            buffer.pushThrough(asLastElement: afterOverlap)
                        } else {
                            break updateLoop
                        }
                    }
                }
            }
            guard let nextBuffered = iterator.next() else {
                break
            }

            buffer.pushThrough(asLastElement: nextBuffered)
        }
        return result
    }

    /**
     Returns all subsequences of the sequence that match the given collection, *i.e.* equivalent elements in the same order, using the given predicate as the equivalence test, in an array of the given collection type.

     - Precondition: `areEquivalent` must be an equivalence relation over the elements.

     - Parameter pattern: A collection to compare to this sequence.
     - Parameter allowingOverlap: Whether or not to include matching subsequences that start before the previous one ends.
     - Parameter storingEachAs: A metatype specifier for the collection type to be returned per match.
     - Parameter areEquivalent: A predicate that returns `true` if its two arguments are equivalent; otherwise, `false`.

     - Returns: An array of collections of the matching subsequences' elements.

     - Complexity: O(*nm*), where *m* is the length of this sequence and *n* is the length of the pattern.
     */
    public func allMatches<Pattern: Collection, Result: RangeReplaceableCollection>(for pattern: Pattern, allowingOverlap: Bool, storingEachAs: Result.Type, by areEquivalent: (Element, Pattern.Element) throws -> Bool) rethrows -> [Result] where Result.Element == Element {
        return try allMatches(for: pattern, allowingOverlap: allowingOverlap, storingAs: Array<Result>.self, by: areEquivalent)
    }

    /**
     Returns all subsequences of the sequence that match the given collection, *i.e.* equivalent elements in the same order, using the given predicate as the equivalence test.

     - Precondition: `areEquivalent` must be an equivalence relation over the elements.

     - Parameter pattern: A collection to compare to this sequence.
     - Parameter allowingOverlap: Whether or not to include matching subsequences that start before the previous one ends.
     - Parameter areEquivalent: A predicate that returns `true` if its two arguments are equivalent; otherwise, `false`.

     - Returns: An array of arrays of the matching subsequences' elements.

     - Complexity: O(*nm*), where *m* is the length of this sequence and *n* is the length of the pattern.
     */
    public func allMatches<Pattern: Collection>(for pattern: Pattern, allowingOverlap: Bool, by areEquivalent: (Element, Pattern.Element) throws -> Bool) rethrows -> [[Element]] {
        return try allMatches(for: pattern, allowingOverlap: allowingOverlap, storingEachAs: Array.self, by: areEquivalent)
    }

}

extension Sequence where Element: Equatable {

    /**
     Returns all subsequences of the sequence that equal the given collection, in a collection of the given type.

     - Parameter pattern: A collection to compare to this sequence.
     - Parameter allowingOverlap: Whether or not to include matching subsequences that start before the previous one ends.
     - Parameter storingAs: A metatype specifier for the collection type to be returned.

     - Returns: A collection of collections of the matching subsequences' elements.

     - Complexity: O(*nm*), where *m* is the length of this sequence and *n* is the length of the pattern.
     */
    public func allMatches<Pattern: Collection, Result: RangeReplaceableCollection>(for pattern: Pattern, allowingOverlap: Bool, storingAs: Result.Type) -> Result where Pattern.Element == Element, Result.Element: RangeReplaceableCollection, Result.Element.Element == Element {
        return allMatches(for: pattern, allowingOverlap: allowingOverlap, storingAs: Result.self, by: ==)
    }

    /**
     Returns all subsequences of the sequence that equal the given collection, in an array of the given collection type.

     - Parameter pattern: A collection to compare to this sequence.
     - Parameter allowingOverlap: Whether or not to include matching subsequences that start before the previous one ends.
     - Parameter storingEachAs: A metatype specifier for the collection type to be returned per match.

     - Returns: An array of collections of the matching subsequences' elements.

     - Complexity: O(*nm*), where *m* is the length of this sequence and *n* is the length of the pattern.
     */
    public func allMatches<Pattern: Collection, Result: RangeReplaceableCollection>(for pattern: Pattern, allowingOverlap: Bool, storingEachAs: Result.Type) -> [Result] where Pattern.Element == Element, Result.Element == Element {
        return allMatches(for: pattern, allowingOverlap: allowingOverlap, storingEachAs: Result.self, by: ==)
    }

    /**
     Returns all subsequences of the sequence that equal the given collection.

     - Parameter pattern: A collection to compare to this sequence.
     - Parameter allowingOverlap: Whether or not to include matching subsequences that start before the previous one ends.

     - Returns: An array of arrays of the matching subsequences' elements.

     - Complexity: O(*nm*), where *m* is the length of this sequence and *n* is the length of the pattern.
     */
    public func allMatches<Pattern: Collection>(for pattern: Pattern, allowingOverlap: Bool) -> [[Element]] where Pattern.Element == Element {
        return allMatches(for: pattern, allowingOverlap: allowingOverlap, by: ==)
    }

}

// MARK: Searching for every occurance of a string of elements within a collection

extension Collection {

    /**
     Returns all ranges of this collection where the respective subsequences match the given collection, *i.e.* equivalent elements in the same order, using the given predicate as the equivalence test, in a collection of the given type.

     - Precondition: `areEquivalent` must be an equivalence relation over the elements.

     - Parameter pattern: A collection to compare to this collection.
     - Parameter allowingOverlap: Whether or not to include matching subsequences that start before the previous one ends.
     - Parameter storingAs: A metatype specifier for the collection type to be returned.
     - Parameter areEquivalent: A predicate that returns `true` if its two arguments are equivalent; otherwise, `false`.

     - Returns: A collection of ranges for the matching subsequences' locations.

     - Complexity: O(*nm*), where *m* is the length of this collection and *n* is the length of the pattern.
     */
    public func allRanges<Pattern: Collection, Result: RangeReplaceableCollection>(matching pattern: Pattern, allowingOverlap: Bool, storingAs: Result.Type, by areEquivalent: (Element, Pattern.Element) throws -> Bool) rethrows -> Result where Result.Element == Range<Index> {
        // The call to allMatches won't handle this correctly.
        guard !pattern.isEmpty else {
            var allEmpties = Result()
            let rangeCount = count
            allEmpties.reserveCapacity(rangeCount + 1)
            allEmpties.append(contentsOf: indices.lazy.map { $0 ..< $0 })
            allEmpties.append(endIndex ..< endIndex)
            return allEmpties
        }

        let rawResult = try indices.allMatches(for: pattern, allowingOverlap: allowingOverlap) { try areEquivalent(self[$0], $1) }
        var result = Result()
        result.reserveCapacity(rawResult.count)
        result.append(contentsOf: rawResult.lazy.map { $0.first! ..< self.index(after: $0.last!) })
        return result
    }

    /**
     Returns all ranges of this collection where the respective subsequences match the given collection, *i.e.* equivalent elements in the same order, using the given predicate as the equivalence test.

     - Precondition: `areEquivalent` must be an equivalence relation over the elements.

     - Parameter pattern: A collection to compare to this collection.
     - Parameter allowingOverlap: Whether or not to include matching subsequences that start before the previous one ends.
     - Parameter areEquivalent: A predicate that returns `true` if its two arguments are equivalent; otherwise, `false`.

     - Returns: An array of ranges of the matching subsequences' locations.

     - Complexity: O(*nm*), where *m* is the length of this collection and *n* is the length of the pattern.
     */
    public func allRanges<Pattern: Collection>(matching pattern: Pattern, allowingOverlap: Bool, by areEquivalent: (Element, Pattern.Element) throws -> Bool) rethrows -> [Range<Index>] {
        return try allRanges(matching: pattern, allowingOverlap: allowingOverlap, storingAs: Array.self, by: areEquivalent)
    }

    /**
     Returns all subsequences of this collection that match the given collection, *i.e.* equivalent elements in the same order, using the given predicate as the equivalence test, in a collection of the given type.

     - Precondition: `areEquivalent` must be an equivalence relation over the elements.

     - Parameter pattern: A collection to compare to this collection.
     - Parameter allowingOverlap: Whether or not to include matching subsequences that start before the previous one ends.
     - Parameter storingAs: A metatype specifier for the collection type to be returned.
     - Parameter areEquivalent: A predicate that returns `true` if its two arguments are equivalent; otherwise, `false`.

     - Returns: A collection of the matching subsequences.

     - Complexity: O(*nm*), where *m* is the length of this collection and *n* is the length of the pattern.
     */
    public func allSubsequences<Pattern: Collection, Result: RangeReplaceableCollection>(matching pattern: Pattern, allowingOverlap: Bool, storingAs: Result.Type, by areEquivalent: (Element, Pattern.Element) throws -> Bool) rethrows -> Result where Result.Element == SubSequence {
        let rawResult = try allRanges(matching: pattern, allowingOverlap: allowingOverlap, by: areEquivalent)
        var result = Result()
        result.reserveCapacity(rawResult.count)
        result.append(contentsOf: rawResult.lazy.map { self[$0] })
        return result
    }

    /**
     Returns all subsequences of this collection that match the given collection, *i.e.* equivalent elements in the same order, using the given predicate as the equivalence test.

     - Precondition: `areEquivalent` must be an equivalence relation over the elements.

     - Parameter pattern: A collection to compare to this collection.
     - Parameter allowingOverlap: Whether or not to include matching subsequences that start before the previous one ends.
     - Parameter areEquivalent: A predicate that returns `true` if its two arguments are equivalent; otherwise, `false`.

     - Returns: An array of the matching subsequences.

     - Complexity: O(*nm*), where *m* is the length of this collection and *n* is the length of the pattern.
     */
    public func allSubsequences<Pattern: Collection>(matching pattern: Pattern, allowingOverlap: Bool, by areEquivalent: (Element, Pattern.Element) throws -> Bool) rethrows -> [SubSequence] {
        return try allSubsequences(matching: pattern, allowingOverlap: allowingOverlap, storingAs: Array.self, by: areEquivalent)
    }

}

extension Collection where Element: Equatable {

    /**
     Returns all ranges of this collection where the respective subsequences equal the given collection, in a collection of the given type.

     - Parameter pattern: A collection to compare to this collection.
     - Parameter allowingOverlap: Whether or not to include matching subsequences that start before the previous one ends.
     - Parameter storingAs: A metatype specifier for the collection type to be returned.

     - Returns: A collection of ranges of the matching subsequences' locations.

     - Complexity: O(*nm*), where *m* is the length of this collection and *n* is the length of the pattern.
     */
    public func allRanges<Pattern: Collection, Result: RangeReplaceableCollection>(matching pattern: Pattern, allowingOverlap: Bool, storingAs: Result.Type) -> Result where Pattern.Element == Element, Result.Element == Range<Index> {
        return allRanges(matching: pattern, allowingOverlap: allowingOverlap, storingAs: Result.self, by: ==)
    }

    /**
     Returns all ranges of this collection where the respective subsequences equal the given collection.

     - Parameter pattern: A collection to compare to this collection.
     - Parameter allowingOverlap: Whether or not to include matching subsequences that start before the previous one ends.

     - Returns: An array of ranges of the matching subsequences' locations.

     - Complexity: O(*nm*), where *m* is the length of this collection and *n* is the length of the pattern.
     */
    public func allRanges<Pattern: Collection>(matching pattern: Pattern, allowingOverlap: Bool) -> [Range<Index>] where Pattern.Element == Element {
        return allRanges(matching: pattern, allowingOverlap: allowingOverlap, by: ==)
    }

    /**
     Returns all subsequences of this collection that equal the given collection, in a collection of the given type.

     - Parameter pattern: A collection to compare to this collection.
     - Parameter allowingOverlap: Whether or not to include matching subsequences that start before the previous one ends.
     - Parameter storingAs: A metatype specifier for the collection type to be returned.

     - Returns: A collection of the matching subsequences.

     - Complexity: O(*nm*), where *m* is the length of this collection and *n* is the length of the pattern.
     */
    public func allSubsequences<Pattern: Collection, Result: RangeReplaceableCollection>(matching pattern: Pattern, allowingOverlap: Bool, storingAs: Result.Type) -> Result where Pattern.Element == Element, Result.Element == SubSequence {
        return allSubsequences(matching: pattern, allowingOverlap: allowingOverlap, storingAs: Result.self, by: ==)
    }

    /**
     Returns all subsequences of this collection that equal the given collection.

     - Parameter pattern: A collection to compare to this collection.
     - Parameter allowingOverlap: Whether or not to include matching subsequences that start before the previous one ends.

     - Returns: An array of the matching subsequences.

     - Complexity: O(*nm*), where *m* is the length of this collection and *n* is the length of the pattern.
     */
    public func allSubsequences<Pattern: Collection>(matching pattern: Pattern, allowingOverlap: Bool) -> [SubSequence] where Pattern.Element == Element {
        return allSubsequences(matching: pattern, allowingOverlap: allowingOverlap, by: ==)
    }

}


// MARK: - Lazily Search for all Occurances of a String of Elements

// MARK: Iterator

/// States for iterating through a sequence, searching for multi-element matches.
enum LazyMatchProgress {

    /// Ready to vend out the first subsequence when the pattern is empty.
    case emptyStart
    /// Ready to vend out subsequent subsequences when the pattern is empty.
    case emptyContinuing
    /// Ready to read the first set of elements for the buffer, and check said buffer.
    case bufferedStart
    /// Ready to read in the next element, update the buffer, then check it.
    case bufferedContinuing
    /// Flagging that the initialization of the buffer failed.
    case bufferedBroken

}

/// An iterator that vends from a wrapped iterator multi-element matches to a pattern.
public struct LazyMatchIterator<Base: IteratorProtocol, Element: RangeReplaceableCollection, Pattern: Collection> where Base.Element == Element.Element {

    /// The wrapped iterator, whose elements will be grouped for tests and vending.
    var base: Base
    /// The collection to match every subsequence against.
    let pattern: Pattern

    /// The number of base elements to skip after a match is found before searching for another, not counting a single minimum read.
    let skipCount: Int
    /// The closure for element-level equivalence testing.
    let areEquivalent: (Base.Element, Pattern.Element) -> Bool

    /// The cache for the pattern length, in case `Pattern` doesn't conform to `RandomAccessCollection`.
    let patternCount: Int
    /// The current state in looking for matches.
    var progress: LazyMatchProgress
    /// The latest subsequence, to match against the pattern.
    lazy var buffer: RingBuffer<Base.Element>? = {
        var trialBuffer = [Base.Element]()
        trialBuffer.reserveCapacity(patternCount)
        for _ in 0..<patternCount {
            guard let nextBuffered = base.next() else { return nil }

            trialBuffer.append(nextBuffered)
        }
        return RingBuffer(trialBuffer)
    }()

    /// Creates an iterator wrapping the given one, along with the given parameters as search bounds.
    init(_ base: Base, pattern: Pattern, allowOverlap: Bool, by areEquivalent: @escaping (Base.Element, Pattern.Element) -> Bool) {
        self.base = base
        self.pattern = pattern

        self.areEquivalent = areEquivalent

        patternCount = self.pattern.count
        skipCount = patternCount <= 0 || allowOverlap ? 0 : patternCount - 1
        progress = patternCount <= 0 ? .emptyStart : .bufferedStart
    }

}

extension LazyMatchIterator: IteratorProtocol {

    mutating public func next() -> Element? {
        /// Return the buffer if it's a match.
        func checkAndReadPast() -> Element? {
            if buffer!.elementsEqual(pattern, by: areEquivalent) {
                var theMatch = Element()
                theMatch.reserveCapacity(patternCount)
                theMatch.append(contentsOf: buffer!)

                defer {
                    for _ in 0..<skipCount {
                        guard let overlap = base.next() else { break }

                        buffer?.pushThrough(asLastElement: overlap)
                    }
                }
                return theMatch
            } else {
                return nil
            }
        }

        switch progress {
        case .emptyStart:
            progress = .emptyContinuing
            return Element()
        case .emptyContinuing:
            guard base.next() != nil else { return nil }

            return Element()
        case .bufferedStart:
            guard buffer != nil else {
                progress = .bufferedBroken
                return nil
            }
            progress = .bufferedContinuing

            if let match = checkAndReadPast() {
                return match
            } else {
                fallthrough
            }
        case .bufferedContinuing:
            while let nextBuffered = base.next() {
                buffer!.pushThrough(asLastElement: nextBuffered)
                guard let match = checkAndReadPast() else { continue }

                return match
            }
            fallthrough
        case .bufferedBroken:
            return nil
        }
    }

}

// MARK: Sequence

/// A sequence that vends from a wrapped sequence multi-element matches to a pattern.
public struct LazyMatchSequence<Base: Sequence, Element: RangeReplaceableCollection, Pattern: Collection> where Base.Element == Element.Element {

    /// The wrapped sequence, whose elements will be grouped for tests and vending.
    let base: Base
    /// The collection to match every subsequence against.
    let pattern: Pattern

    /// Whether or not to include matches that start before a previous one ends.
    let allowOverlap: Bool
    /// The closure for element-level equivalence testing.
    let areEquivalent: (Base.Element, Pattern.Element) -> Bool

    // The automatically-defined member-wise initializer should be declared internal.

}

extension LazyMatchSequence: Sequence {

    public func makeIterator() -> LazyMatchIterator<Base.Iterator, Element, Pattern> {
        return LazyMatchIterator(base.makeIterator(), pattern: pattern, allowOverlap: allowOverlap, by: areEquivalent)
    }

}

extension LazyMatchSequence: LazySequenceProtocol {}

// MARK: Collection

/// A collection that vends the subsequences of the wrapped collection that match a pattern.
public struct LazyMatchCollection<Base: Collection, Pattern: Collection> {

    /// A wrapper for the collection's properties, nested one level to allow lazy initialization.
    final class Core {

        /// The wrapped collection, whose elements will be grouped for tests and vending.
        let base: Base
        /// The collection to match every subsequence against.
        let pattern: Pattern

        /// The closure for element-level equivalence testing.
        let areEquivalent: (Base.Element, Pattern.Element) -> Bool

        /// The cached range of the first matching subsequence.
        lazy var firstRange = {
            return base.firstRange(matching: pattern, by: areEquivalent)
        }()

        /// Creates the core data for a collection whose elements are the subsequences of the given collection with the given bounds.
        init(_ base: Base, pattern: Pattern, by areEquivalent: @escaping (Base.Element, Pattern.Element) -> Bool) {
            self.base = base
            self.pattern = pattern
            self.areEquivalent = areEquivalent
        }

    }

    /// The key data of this type, moved to a class to provide first-run mutability.
    let core: Core
    /// Whether or not to include matches that start before a previous one ends.
    let allowOverlap: Bool
    /// The cache for the pattern length, in case `Pattern` doesn't conform to `RandomAccessCollection`.
    let patternCount: Int

    /**
     Creates a collection whose elements are the subsequences of a copy of the given collection that conform to the other given arguments.

     - Precondition: `areEquivalent` must be an equivalence relation over the elements.

     - Parameter pattern: A collection to compare to this sequence.
     - Parameter allowingOverlap: Whether or not to include matching subsequences that start before the previous one ends.
     - Parameter areEquivalent: A predicate that returns `true` if its two arguments are equivalent; otherwise, `false`.

     - Postcondition: `self` is a collection of the subsequences of `base` that are equivalent to `pattern`, using `areEquivalent` as the comparison test, optionally modulo overlapping subsequences (determined by `allowingOverlap`).
     */
    init(_ base: Base, pattern: Pattern, allowingOverlap: Bool, by areEquivalent: @escaping (Base.Element, Pattern.Element) -> Bool) {
        core = Core(base, pattern: pattern, by: areEquivalent)
        allowOverlap = allowingOverlap
        patternCount = core.pattern.count
    }

}

/// An index that uses a subrange of its target collection.
public struct LazyMatchCollectionIndex<Base: Collection> {

    /// The location of the target subsequence, or `nil` for past-the-end.
    public let base: Range<Base.Index>?

}

extension LazyMatchCollectionIndex: Comparable {

    public static func < (lhs: LazyMatchCollectionIndex, rhs: LazyMatchCollectionIndex) -> Bool {
        switch (lhs.base, rhs.base) {
        case (nil, _):
            return false
        case (_, nil):
            return true
        case let (lb?, rb?):
            // The upper bounds are not checked because there shouldn't be operands with differing range spans.
            return lb.lowerBound < rb.lowerBound
        }
    }

}

extension LazyMatchCollectionIndex: Hashable where Base.Index: Hashable {}

extension LazyMatchCollection: Collection {

    public typealias Index = LazyMatchCollectionIndex<Base>

    public var startIndex: Index { return Index(base: core.firstRange) }
    public var endIndex: Index { return Index(base: nil) }

    public subscript(position: Index) -> Base.SubSequence { return core.base[position.base!] }

    public func index(after i: Index) -> Index {
        let indexRange = i.base!
        guard indexRange.upperBound < core.base.endIndex else { return endIndex }

        let tailIndex: Base.Index
        if allowOverlap || indexRange.isEmpty {
            tailIndex = core.base.index(after: indexRange.lowerBound)
        } else {
            tailIndex = indexRange.upperBound
        }
        return Index(base: core.base[tailIndex...].firstRange(matching: core.pattern, by: core.areEquivalent))
    }

}

extension LazyMatchCollection: BidirectionalCollection where Base: BidirectionalCollection {

    public func index(before i: Index) -> Index {
        // The "!" at the end of the lastRange(matching:) calls simulate calling this function on startIndex.
        let firstTrialRange: Range<Base.Index>
        if let indexRange = i.base {
            firstTrialRange = core.base[..<core.base.index(before: indexRange.upperBound)].lastRange(matching: core.pattern, by: core.areEquivalent)!
        } else {
            firstTrialRange = core.base.lastRange(matching: core.pattern, by: core.areEquivalent)!
        }
        guard !allowOverlap, !firstTrialRange.isEmpty else { return Index(base: firstTrialRange) }

        // 1. Make list with just firstTrialRange in it
        var trailingRanges = [firstTrialRange]

        // 2. Add to list the possible ranges that can overlap ranges already in the list
        // 3. Repeat [2] until no more earlier ranges can overlap with those in the list
        while case let trEnd = core.base.index(before: trailingRanges.last!.upperBound), case let trStart = core.base.index(trEnd, offsetBy: -2 * patternCount, limitedBy: core.base.startIndex) ?? core.base.startIndex, let previousRange = core.base[trStart..<trEnd].lastRange(matching: core.pattern, by: core.areEquivalent) {
            if trailingRanges.last!.overlaps(previousRange) {
                trailingRanges.append(previousRange)
            } else {
                break
            }
        }

        // 4. If there's only one range in the list, return it
        // 5. Take the earliest range out of the list, since we know it must be valid
        // 6. Remove all ranges in the list that can overlap with the range in [5]
        // 7. If the list is now empty, return the range from [5], otherwise go back to [4]
        while trailingRanges.count > 1 {
            let earliestRange = trailingRanges.popLast()!
            while let laterRange = trailingRanges.last {
                if earliestRange.overlaps(laterRange) {
                    trailingRanges.removeLast()
                } else {
                    break
                }
            }
            if trailingRanges.isEmpty {
                return Index(base: earliestRange)
            }
        }
        return Index(base: trailingRanges.first!)
    }

}

extension LazyMatchCollection: LazyCollectionProtocol {}

// MARK: Adaptor Generators

extension LazySequenceProtocol {

    /**
     Returns all subsequences of the sequence that match the given collection, *i.e.* equivalent elements in the same order, using the given predicate as the equivalence test, lazily vended through collections of the given type.

     - Precondition: `areEquivalent` must be an equivalence relation over the elements.

     - Parameter pattern: A collection to compare to this sequence.
     - Parameter allowingOverlap: Whether or not to include matching subsequences that start before the previous one ends.
     - Parameter storingEachAs: A metatype specifier for the collection type to be returned per match.
     - Parameter areEquivalent: A predicate that returns `true` if its two arguments are equivalent; otherwise, `false`.

     - Returns: A lazy sequence of collections of the matching subsequences' elements.
     */
    public func allMatches<Pattern: Collection, Result: RangeReplaceableCollection>(for pattern: Pattern, allowingOverlap: Bool, storingEachAs: Result.Type, by areEquivalent: @escaping (Element, Pattern.Element) -> Bool) -> LazyMatchSequence<Elements, Result, Pattern> where Result.Element == Element {
        return LazyMatchSequence(base: elements, pattern: pattern, allowOverlap: allowingOverlap, areEquivalent: areEquivalent)
    }

    /**
     Returns all subsequences of the sequence that match the given collection, *i.e.* equivalent elements in the same order, using the given predicate as the equivalence test, lazily vended through arrays of the given type.

     - Precondition: `areEquivalent` must be an equivalence relation over the elements.

     - Parameter pattern: A collection to compare to this sequence.
     - Parameter allowingOverlap: Whether or not to include matching subsequences that start before the previous one ends.
     - Parameter areEquivalent: A predicate that returns `true` if its two arguments are equivalent; otherwise, `false`.

     - Returns: A lazy sequence of arrays of the matching subsequences' elements.
     */
    public func allMatches<Pattern: Collection>(for pattern: Pattern, allowingOverlap: Bool, by areEquivalent: @escaping (Element, Pattern.Element) -> Bool) -> LazyMatchSequence<Elements, [Element], Pattern> {
        return allMatches(for: pattern, allowingOverlap: allowingOverlap, storingEachAs: Array<Element>.self, by: areEquivalent)
    }

}

extension LazySequenceProtocol where Element: Equatable {

    /**
     Returns all subsequences of the sequence that equal the given collection, lazily vended through collections of the given type.

     - Parameter pattern: A collection to compare to this sequence.
     - Parameter allowingOverlap: Whether or not to include matching subsequences that start before the previous one ends.
     - Parameter storingEachAs: A metatype specifier for the collection type to be returned per match.

     - Returns: A lazy sequence of collections of the matching subsequences' elements.
     */
    public func allMatches<Pattern: Collection, Result: RangeReplaceableCollection>(for pattern: Pattern, allowingOverlap: Bool, storingEachAs: Result.Type) -> LazyMatchSequence<Elements, Result, Pattern> where Result.Element == Element, Pattern.Element == Element {
        return allMatches(for: pattern, allowingOverlap: allowingOverlap, storingEachAs: Result.self, by: ==)
    }

    /**
     Returns all subsequences of the sequence that equal the given collection, lazily vended through arrays of the given type.

     - Parameter pattern: A collection to compare to this sequence.
     - Parameter allowingOverlap: Whether or not to include matching subsequences that start before the previous one ends.

     - Returns: A lazy sequence of arrays of the matching subsequences' elements.
     */
    public func allMatches<Pattern: Collection>(for pattern: Pattern, allowingOverlap: Bool) -> LazyMatchSequence<Elements, [Element], Pattern> where Pattern.Element == Element {
        return allMatches(for: pattern, allowingOverlap: allowingOverlap, by: ==)
    }

}

extension LazyCollectionProtocol {

    /**
     Returns all subsequences of this collection that match the given collection, *i.e.* equivalent elements in the same order, using the given predicate as the equivalence test, lazily vended.

     - Precondition: `areEquivalent` must be an equivalence relation over the elements.

     - Parameter pattern: A collection to compare to this collection.
     - Parameter allowingOverlap: Whether or not to include matching subsequences that start before the previous one ends.
     - Parameter areEquivalent: A predicate that returns `true` if its two arguments are equivalent; otherwise, `false`.

     - Returns: A lazy collection of the matching subsequences.
     */
    public func allMatches<Pattern: Collection>(for pattern: Pattern, allowingOverlap: Bool, by areEquivalent: @escaping (Element, Pattern.Element) -> Bool) -> LazyMatchCollection<Elements, Pattern> {
        return LazyMatchCollection(elements, pattern: pattern, allowingOverlap: allowingOverlap, by: areEquivalent)
    }

}

extension LazyCollectionProtocol where Element: Equatable {

    /**
     Returns all subsequences of this collection that equal the given collection, lazily vended.

     - Parameter pattern: A collection to compare to this collection.
     - Parameter allowingOverlap: Whether or not to include matching subsequences that start before the previous one ends.

     - Returns: A lazy collection of the matching subsequences.
     */
    public func allMatches<Pattern: Collection>(for pattern: Pattern, allowingOverlap: Bool) -> LazyMatchCollection<Elements, Pattern> where Pattern.Element == Element {
        return allMatches(for: pattern, allowingOverlap: allowingOverlap, by: ==)
    }

}

RingBuffer.swift

/*
 RingBuffer.swift -- Ring-buffer collection type

 Copyright (c) 2019 Daryle Walker

 */

// MARK: Primary Definition

/// A collection that only inserts at each end, and removes the element at the opposite end when doing so.
public struct RingBuffer<Element> {

    /// The raw storage for the elements.
    public var elements: [Element]
    /// The proxy for the elements in their logical iteration order.
    public var rotatedIndices: RotatedCollection<[Array<Element>.Index]>

    /**
     Creates a ring buffer sized to the given sequence.

     - Parameter initialElements: The source of the initial elements of the buffer.

     - Postcondition: The underlying sequences of `self` and `initialElements` are equal, but only if the latter was not empty, else this initializer fails.
     */
    public init?<S: Sequence>(_ initialElements: S) where S.Element == Element {
        let rawElements = Array(initialElements)
        guard !rawElements.isEmpty else { return nil }

        elements = []
        elements.reserveCapacity(rawElements.count)
        elements.append(contentsOf: rawElements)

        var rawElementIndices = [Array<Element>.Index]()
        rawElementIndices.reserveCapacity(rawElements.count)
        rawElementIndices.append(contentsOf: elements.indices)
        rotatedIndices = rawElementIndices.rotated(toFirst: elements.startIndex)
    }

}

// MARK: Custom Operations, Rotating Elements

extension RingBuffer {

    /**
     Rotates the elements such that the element at the given index is now at the start of the buffer.

     - Parameter f: The index for the element that will be the new `startIndex`.

     - Postcondition:
         - `startIndex` now points to the same element that `f` did.
         - If `f` wasn't already `startIndex`, all outstanding `Index` values are invalidated.
     */
    public mutating func realign(asFirst f: Index) {
        rotatedIndices.reseat(asFirst: f)
    }

    /**
     Rotates the elements such that the element at the given index is now at the end of the buffer.

     - Parameter l: The index for the element that will be the new last element.

     - Postcondition:
         - `index(before: endIndex)` now points to the same element that `l` did.
         - If `l` wasn't already pointing to the last element, all outstanding `Index` values are invalidated.
     */
    public mutating func realign(asLast l: Index) {
        rotatedIndices.reseat(asLast: l)
    }

}

// MARK: Custom Operations, Inserting Elements

extension RingBuffer {

    /**
     Appends a new element to the buffer, ejecting the first element.

     - Parameter l: The new last element for the buffer.

     - Returns: The element that was first before this method was called.

     - Postcondition:
         - `self == oldSelf[index(after: startIndex)...] + [l]`.
         - All outstanding `Index` values are invalidated.
     */
    @discardableResult
    public mutating func pushThrough(asLastElement l: Element) -> Element {
        defer {
            elements[rotatedIndices.first!] = l
            realign(asLast: startIndex)
        }
        return first!
    }

    /**
     Prepends a new element to the buffer, ejecting the last element.

     - Parameter f: The new first element for the buffer.

     - Returns: The element that was last before this method was called.

     - Postcondition:
         - `self == [f] + oldSelf[..<index(before: endIndex)]`.
         - All outstanding `Index` values are invalidated.
     */
    @discardableResult
    public mutating func pushThrough(asFirstElement f: Element) -> Element {
        defer {
            elements[rotatedIndices.last!] = f
            realign(asFirst: index(before: endIndex))
        }
        return last!
    }

}

// MARK: Collection Support

extension RingBuffer: MutableCollection, RandomAccessCollection {

    public typealias Index = RotatedCollection<[Array<Element>.Index]>.Index

    public var startIndex: Index { return rotatedIndices.startIndex }
    public var endIndex: Index { return rotatedIndices.endIndex }

    public subscript(position: Index) -> Element {
        get { return elements[rotatedIndices[position]] }
        set { elements[rotatedIndices[position]] = newValue }
    }

    public func index(after i: Index) -> Index {
        return rotatedIndices.index(after: i)
    }

    public func index(before i: Index) -> Index {
        return rotatedIndices.index(before: i)
    }

    public func index(_ i: Index, offsetBy distance: Int) -> Index {
        return rotatedIndices.index(i, offsetBy: distance)
    }
    public func distance(from start: Index, to end: Index) -> Int {
        return rotatedIndices.distance(from: start, to: end)
    }

}

// MARK: Comparisons

extension RingBuffer: Equatable where Element: Equatable {

    public static func == (lhs: RingBuffer<Element>, rhs: RingBuffer<Element>) -> Bool {
        return lhs.elementsEqual(rhs)
    }

}

extension RingBuffer: Hashable where Element: Hashable {

    public func hash(into hasher: inout Hasher) {
        // Same algorithm as Array (at the time of typing this).
        hasher.combine(count)
        for element in self {
            hasher.combine(element)
        }
    }

}

// MARK: Initialization

extension RingBuffer: ExpressibleByArrayLiteral {

    // YIKES: This initializer will crash if its array literal is empty!
    public init(arrayLiteral elements: Element...) {
        self.init(elements)!
    }

}

extension RingBuffer: Decodable where Element: Decodable {

    public init(from decoder: Decoder) throws {
        let values = try decoder.singleValueContainer()
        guard let self0 = RingBuffer(try values.decode(type(of: elements))) else {
            throw DecodingError.dataCorruptedError(in: values, debugDescription: "Elements array was unexpectedly empty")
        }
        self = self0
    }

}

// MARK: Externalization

extension RingBuffer: CustomStringConvertible {

    public var description: String {
        // Using "describing" instead of "reflecting" differs from the Standard Library's text-serialization for Collection.
        return "[\(lazy.map(String.init(describing:)).joined(separator: ", "))]"
    }

}

extension RingBuffer: CustomDebugStringConvertible {

    public var debugDescription: String {
        var result = "\(RingBuffer.self)(["
        let pivotIntroducer = "baseStart: "
        if rotatedIndices.first! == elements.startIndex {
            result += pivotIntroducer
        }

        func printItem(_ i: RotatedCollection<[Array<Element>.Index]>.Index) {
            let elementIndex = rotatedIndices[i]
            let afterI = rotatedIndices.index(after: i)
            if afterI < rotatedIndices.endIndex {
                let introducer = rotatedIndices[afterI] == elements.startIndex ? pivotIntroducer : ""
                debugPrint(elements[elementIndex], terminator: ", " + introducer, to: &result)
            } else {
                debugPrint(elements[elementIndex], terminator: "", to: &result)
            }
        }

        rotatedIndices.indices.forEach(printItem)
        result += "])"
        return result
    }

}

extension RingBuffer: CustomReflectable {

    public var customMirror: Mirror {
        // Turns out that debug-description simulation is broken (for now) if some children have labels and others don't, unless the display style is "tuple."
        // ("collection" expects everything to be unlabeled, while "dictionary" and "struct" need everything labeled.)
        return Mirror(self, children: rotatedIndices.map { (label: $0 == elements.startIndex ? "baseStart" : nil, value: elements[$0]) }, displayStyle: .collection)
    }

}

extension RingBuffer: Encodable where Element: Encodable {

    public func encode(to encoder: Encoder) throws {
        var container = encoder.singleValueContainer()
        try container.encode(elements)
    }

}

Rotate.swift

/*
 Rotate.swift -- Sequence and collection element rotation

 Copyright (c) 2019 Daryle Walker

 */

// MARK: In-place Rotation

extension MutableCollection {

    /**
     Rotates the elements such that the value at the given index is now at `startIndex`.

     Passing `startIndex` as `i` has no effect.

     The method applies a left-rotation, bringing the target element's value to `startIndex`.

         var letters = ["A", "B", "C", "D", "E", "F"]
         letters.rotate(toFirst: letters.index(after: letters.startIndex))
         print(String(letters))
         // Prints "BCDEFA"

     - Precondition: `i` must be a valid index of this collection and not equal to `endIndex`.

     - Parameter i: The index of the element whose value will move to `startIndex`.

     - Returns: The index of the element where the value originally at `startIndex` went.

     - Postcondition: The new value is a left-rotation of the old; `newValue == oldValue[i...] + oldValue[..<i]`.

     - Complexity: O(*n*), where *n* is the collection's length.
     */
    @discardableResult
    mutating public func rotate(toFirst i: Index) -> Index {
        precondition(i != endIndex)
        guard i != startIndex else { return startIndex }

        // Adapted from <http://www.cplusplus.com/reference/algorithm/rotate/>.
        var pivot = i, next = pivot, start = startIndex
        let startOffset = distance(from: pivot, to: endIndex)
        while start != next {
            swapAt(start, next)
            formIndex(after: &start)
            formIndex(after: &next)
            if next == endIndex {
                next = pivot
            } else if start == pivot {
                pivot = next
            }
        }
        return index(startIndex, offsetBy: startOffset)
    }

    /**
     Rotates the elements such that the value at the given index is now at the last valid index before `endIndex`.

     Passing the index value before `endIndex` as `i` has no effect.

     The method applies a right-rotation, bringing the target element's value towards `endIndex`.

         var letters = ["A", "B", "C", "D", "E", "F"]
         letters.rotate(toLast: letters.index(after: letters.startIndex))
         print(String(letters))
         // Prints "CDEFAB"

     - Precondition: `i` must be a valid index of this collection and not equal to `endIndex`.

     - Parameter i: The index of the element whose value will move to the last valid element.

     - Returns: The index of where the value originally at `startIndex` went.

     - Postcondition: The new value is a right-rotation of the old; `newValue == oldValue[i>..] + oldValue[...i]`.

     - Complexity: O(*n*), where *n* is the collection's length.
     */
    @discardableResult
    mutating public func rotate(toLast i: Index) -> Index {
        let shiftedPivot = index(i, offsetBy: +1, limitedBy: endIndex)!
        guard shiftedPivot != endIndex else { return startIndex }

        return rotate(toFirst: shiftedPivot)
    }

}


// MARK: - Rotation Lazy-Adapater for Collections

/// A collection that presents the elements of its base collection in a shifted (*i.e.* rotated) order.
public struct RotatedCollection<Base: Collection> {

    /// The wrapped collection.
    public let base: Base
    /// The position of the external `startIndex` relative to `base`.
    var origin: Base.Index

    /// Creates a copy of the given collection such that its elements are rotated to start at the given index's position instead.
    init(_ base: Base, toFirst i: Base.Index) {
        precondition(i != base.endIndex)

        self.base = base
        origin = i
    }

}

// MARK: Index Preliminaries

extension RotatedCollection {

    public struct Index {
        /// The start index relative to the wrapped base.
        let origin: Base.Index
        /// The position of the target element, or `nil` as a past-the-end marker.
        public let base: Base.Index?
    }

}

extension RotatedCollection.Index: Equatable {

    public static func == (lhs: RotatedCollection<Base>.Index, rhs: RotatedCollection<Base>.Index) -> Bool {
        precondition(lhs.origin == rhs.origin)

        return lhs.base == rhs.base
    }

}

extension RotatedCollection.Index: Comparable {

    public static func < (lhs: RotatedCollection<Base>.Index, rhs: RotatedCollection<Base>.Index) -> Bool {
        // In rotated logic, origin..<endIndex elements are earlier than the startIndex..<origin ones.

        precondition(lhs.origin == rhs.origin)
        guard let leftBase = lhs.base else { return false }
        guard let rightBase = rhs.base else { return true }

        switch (lhs.origin <= leftBase, rhs.origin <= rightBase) {
        case (true, true), (false, false):
            return leftBase < rightBase
        case (false, true):
            return false
        case (true, false):
            return true
        }
    }

}

extension RotatedCollection.Index: Hashable where Base.Index: Hashable {}

// MARK: Index conversion

extension RotatedCollection {

    /// Returns the translation of the given index in `base` to the corresponding rotated element's index in `self`.
    public func translate(baseIndex: Base.Index) -> Index {
        guard baseIndex != base.endIndex else { return Index(origin: origin, base: nil) }

        return Index(origin: origin, base: baseIndex)
    }

}

// MARK: Collection Support

extension RotatedCollection: Collection {

    public var startIndex: Index { return Index(origin: origin, base: origin) }
    public var endIndex: Index { return Index(origin: origin, base: nil) }

    public subscript(position: Index) -> Base.Element {
        precondition(origin == position.origin)

        return base[position.base!]
    }

    public func index(after i: Index) -> Index {
        precondition(origin == i.origin)

        let baseAfter = base.index(after: i.base!)
        if baseAfter == origin || baseAfter == base.endIndex && origin == base.startIndex {
            // Past-the-end
            return Index(origin: origin, base: nil)
        } else if baseAfter == base.endIndex {
            // Wrap-around
            return Index(origin: origin, base: base.startIndex)
        } else {
            // Normal
            return Index(origin: origin, base: baseAfter)
        }
    }

}

extension RotatedCollection: BidirectionalCollection where Base: BidirectionalCollection {

    public func index(before i: Index) -> Index {
        precondition(origin == i.origin)
        precondition(origin != i.base)  // No external-level wraparound

        let baseCurrent = i.base ?? origin
        if baseCurrent == base.startIndex {
            // Base-level wrap-around
            return Index(origin: origin, base: base.index(before: base.endIndex))
        } else {
            // Normal
            return Index(origin: origin, base: base.index(before: baseCurrent))
        }
    }

}

extension RotatedCollection: RandomAccessCollection where Base: RandomAccessCollection {

    public func index(_ i: Index, offsetBy distance: Int) -> Index {
        precondition(origin == i.origin)
        guard origin == i.base else {
            return index(startIndex, offsetBy: self.distance(from: startIndex, to: i) + distance)
        }

        let earlyBarrageCount = base.distance(from: origin, to: base.endIndex)
        switch distance {
        case 0..<earlyBarrageCount:
            return Index(origin: origin, base: base.index(origin, offsetBy: distance))
        case earlyBarrageCount..<base.count:
            return Index(origin: origin, base: base.index(base.startIndex, offsetBy: distance - earlyBarrageCount))
        case base.count:
            return endIndex
        default:
            preconditionFailure("Out of bounds distance value")
        }
    }

    public func distance(from start: Index, to end: Index) -> Int {
        /// Returns the distance from the origin to the given index.  Easier to encapsulate all the combinations.
        func distanceFromOrigin(_ x: Index) -> Int {
            precondition(origin == x.origin)

            if let xBase = x.base {
                if origin <= xBase {
                    return base.distance(from: origin, to: xBase)
                } else {
                    return base.distance(from: origin, to: base.endIndex) + base.distance(from: base.startIndex, to: xBase)
                }
            } else {
                return base.count
            }
        }

        return distanceFromOrigin(end) - distanceFromOrigin(start)
    }

}

// MARK: Laziness Support

extension RotatedCollection: LazySequenceProtocol where Base: LazySequenceProtocol {}

// TODO: Should LazyCollectionProtocol support be added?

// MARK: Adaptor Generators

extension RotatedCollection {

    /// Returns the elements of this collection rotated left, with an optimized type.
    public func rotated(toFirst i: Index) -> RotatedCollection {
        return base.rotated(toFirst: i.base!)
    }

    /// Returns the elements of this collection rotated right, with an optimized type.
    public func rotated(toLast i: Index) -> RotatedCollection {
        return base.rotated(toLast: i.base!)
    }

}

extension Collection {

    /// Returns the elements of this collection rotated left.
    public func rotated(toFirst i: Index) -> RotatedCollection<Self> {
        return RotatedCollection(self, toFirst: i)
    }

    /// Returns the elements of this collection rotated right.
    public func rotated(toLast i: Index) -> RotatedCollection<Self> {
        let next = index(after: i)
        return rotated(toFirst: next == endIndex ? startIndex : next)
    }

}

// MARK: Custom In-place Rotation

extension RotatedCollection {

    /// Rerotates this collection to start at the given index.  If `i != startIndex`, invalidates all outstanding `Index` values.
    mutating public func reseat(asFirst i: Index) {
        precondition(i.origin == origin)

        origin = i.base!
    }

    /// Rerotates this collection to end at the given index.  If `index(after: i) != endIndex`, invalidates all outstanding `Index` values.
    mutating public func reseat(asLast i: Index) {
        let next = index(after: i)
        if next != endIndex {
            reseat(asFirst: next)
        }
    }

}


// MARK: - (Left-)Rotation Lazy-Adapater for Sequences

// MARK: Iterator

/// An iterator that vends the prefix of its wrapped underlying sequence after vending that sequence's suffix.
public struct RotateLeftIterator<Base: IteratorProtocol> {

    /// The wrapped iterator, whose elements' vending order will be shifted.
    var base: Base
    /// The amount of elements to cache in order to shift their vending.
    let offset: Int

    /// The element cache.
    lazy var cache = makeCache()
    /// The iterator for the cache.
    var cacheIterator: Array<Base.Element>.Iterator?

    /// Creates an iterator that wraps the given iterator and vends the suffix of the wrapped iterator's underlying sequence, followed by the displaced prefix (of the given length).
    init(_ base: Base, shifting limit: Int) {
        precondition(limit >= 0)

        self.base = base
        offset = limit
    }

    /// Caches the first `offset` elements from `base`, to be vended later.
    mutating private func makeCache() -> [Base.Element] {
        var scratch = [Base.Element]()
        scratch.reserveCapacity(offset)
        for _ in 0..<offset {
            guard let nextCached = base.next() else { break }

            scratch.append(nextCached)
        }
        guard !scratch.isEmpty else { return [] }

        return Array(scratch.rotated(toFirst: scratch.index(scratch.startIndex, offsetBy: offset % scratch.count)))
    }

}

extension RotateLeftIterator: IteratorProtocol {

    mutating public func next() -> Base.Element? {
        // "cacheIterator" can't be lazily initialized because "cache" needs to read from "base" before "base" is used directly for elements.
        if cacheIterator == nil {
            cacheIterator = cache.makeIterator()
        }

        // Read from "base," then from "cacheIterator" once the former is empty.
        return base.next() ?? cacheIterator?.next()
    }

}

// MARK: Sequence

/// A sequence that vends the prefix of its wrapped sequence after vending that sequence's suffix.
public struct RotateLeftSequence<Base: Sequence> {

    /// The wrapped sequence, whose elements' vending order will be shifted.
    var base: Base
    /// The amount of elements to cache in order to shift their vending.
    let offset: Int

    /// Creates a sequence that wraps the given sequence and vends the suffix of the wrapped sequence, followed by the displaced prefix (of the given length).
    init(_ base: Base, shifting limit: Int) {
        precondition(limit >= 0)

        self.base = base
        offset = limit
    }

}

extension RotateLeftSequence: Sequence {

    public func makeIterator() -> RotateLeftIterator<Base.Iterator> {
        return RotateLeftIterator(base.makeIterator(), shifting: offset)
    }

    public var underestimatedCount: Int { return base.underestimatedCount }

}

// MARK: Adaptor Generator

extension Sequence {

    /**
     Returns a sequence that skips over a given number of elements of this sequence, vends its suffix, then vends the initially-skipped prefix.
     
     If the skipped amount exceeds the number of elements in the sequence, then that amount is reduced modulo the sequence length.  (This is the same effect as a series of single-step rotations.)

        let numbers = [1, 2, 3, 4, 5]
        print(Array(numbers.leftRotate(3)))
        // Prints "[4, 5, 1, 2, 3]"
        print(Array(numbers.leftRotate(7)))
        // Prints "[3, 4, 5, 1, 2]"
        print(Array(numbers.leftRotate(10)))
        // Prints "[1, 2, 3, 4, 5]"

     - Precondition: `initialSkipCount >= 0`.

     - Parameter initialSkipCount: The number of elements to initially skip over.

     - Returns: A sequence of the suffix of this sequence followed by this sequence's prefix.

     - Complexity: O(1), except for O(*k*) at the first iteration call, where *k* is the displaced prefix length.

     - Note: The returned sequence can only perform a left rotation relative to this sequence.  For right rotations, copy this sequence to a collection and call `Collection`'s rotation methods.
     */
    public func leftRotate(_ initialSkipCount: Int) -> RotateLeftSequence<Self> {
        return RotateLeftSequence(self, shifting: initialSkipCount)
    }

}

Search.swift

/*
 Search.swift -- Sequence and collection multi-element search, single location

 Copyright (c) 2019 Daryle Walker

 */

// MARK: Searching for a string of elements within a sequence

extension Sequence {

    /**
     Returns the first subsequence of the sequence that matches the given collection, *i.e.* equivalent elements in the same order, using the given predicate as the equivalence test, in a collection of the given type.

     - Precondition: `areEquivalent` must be an equivalence relation over the elements.

     - Parameter pattern: A collection to compare to this sequence.
     - Parameter storingAs: A metatype specifier for the collection type to be returned
     - Parameter areEquivalent: A predicate that returns `true` if its two arguments are equivalent; otherwise, `false`.

     - Returns: A collection of the matching subsequence's elements, or `nil` if no match can be found.

     - Complexity: O(*nm*), where *m* is the length of this sequence and *n* is the length of the pattern.
     */
    public func firstMatch<Pattern: Collection, Result: RangeReplaceableCollection>(for pattern: Pattern, storingAs: Result.Type, by areEquivalent: (Element, Pattern.Element) throws -> Bool) rethrows -> Result? where Result.Element == Element {
        // An empty pattern always matches.
        var result = Result()
        guard !pattern.isEmpty else { return result }

        // Check if the sequence is too short to match.
        var iterator = makeIterator()
        let patternCount = pattern.count
        result.reserveCapacity(patternCount)
        for _ in 0..<patternCount {
            guard let nextBuffered = iterator.next() else { return nil }

            result.append(nextBuffered)
        }

        // Check for a match, and return it.
        var buffer = RingBuffer(result)!
        while try !buffer.elementsEqual(pattern, by: areEquivalent) {
            guard let nextBuffered = iterator.next() else { return nil }

            buffer.pushThrough(asLastElement: nextBuffered)
        }
        result.replaceSubrange(result.startIndex..<result.endIndex, with: buffer)
        return result
    }

    /**
     Returns the first subsequence of the sequence that matches the given collection, *i.e.* equivalent elements in the same order, using the given predicate as the equivalence test.

     - Precondition: `areEquivalent` must be an equivalence relation over the elements.

     - Parameter pattern: A collection to compare to this sequence.
     - Parameter areEquivalent: A predicate that returns `true` if its two arguments are equivalent; otherwise, `false`.

     - Returns: An array of the matching subsequence's elements, or `nil` if no match can be found.

     - Complexity: O(*nm*), where *m* is the length of this sequence and *n* is the length of the pattern.
     */
    public func firstMatch<Pattern: Collection>(for pattern: Pattern, by areEquivalent: (Element, Pattern.Element) throws -> Bool) rethrows -> [Element]? {
        return try firstMatch(for: pattern, storingAs: Array.self, by: areEquivalent)
    }

    /**
     Returns a Boolean value indicating whether the given collection can be found as a subsequence within this sequence, *i.e.* equivalent elements in the same order, using the given predicate as the equivalence test.

     - Precondition: `areEquivalent` must be an equivalence relation over the elements.

     - Parameter pattern: A collection to compare to this sequence.
     - Parameter areEquivalent: A predicate that returns `true` if its two arguments are equivalent; otherwise, `false`.

     - Returns: `true` if there is some subsequence of this sequence that is equivalent to `pattern`, using `areEquivalent` as the element-wise equivalence test; otherwise, `false`.

     - Complexity: O(*nm*), where *m* is the length of this sequence and *n* is the length of the pattern.
     */
    public func contains<Pattern: Collection>(_ pattern: Pattern, by areEquivalent: (Element, Pattern.Element) throws -> Bool) rethrows -> Bool {
        return try firstMatch(for: pattern, by: areEquivalent) != nil
    }

}

extension Sequence where Element: Equatable {

    /**
     Returns the first subsequence of the sequence that equals the given collection, in a collection of the given type.

     - Parameter pattern: A collection to compare to this sequence.
     - Parameter storingAs: A metatype specifier for the collection type to be returned

     - Returns: A collection of the matching subsequence's elements, or `nil` if no match can be found.

     - Complexity: O(*nm*), where *m* is the length of this sequence and *n* is the length of the pattern.
     */
    public func firstMatch<Pattern: Collection, Result: RangeReplaceableCollection>(for pattern: Pattern, storingAs: Result.Type) -> Result? where Pattern.Element == Element, Result.Element == Element {
        return firstMatch(for: pattern, storingAs: Result.self, by: ==)
    }

    /**
     Returns the first subsequence of the sequence that equals the given collection.

     - Parameter pattern: A collection to compare to this sequence.

     - Returns: An array of the matching subsequence's elements, or `nil` if no match can be found.

     - Complexity: O(*nm*), where *m* is the length of this sequence and *n* is the length of the pattern.
     */
    public func firstMatch<Pattern: Collection>(for pattern: Pattern) -> [Element]? where Pattern.Element == Element {
        return firstMatch(for: pattern, by: ==)
    }

    /**
     Returns a Boolean value indicating whether some subsequence of the sequence equals the given collection.

     - Parameter pattern: A collection to compare to this sequence.

     - Returns: `true` if there is some subsequence of this sequence that is identical to `pattern`; otherwise, `false`.

     - Complexity: O(*nm*), where *m* is the length of this sequence and *n* is the length of the pattern.
     */
    public func contains<Pattern: Collection>(_ pattern: Pattern) -> Bool where Pattern.Element == Element {
        return contains(pattern, by: ==)
    }

}

// MARK: Searching how far in a string of elements is within a sequence

extension Sequence {

    /// Returns how many elements had to be skipped in this sequence until a subsequence matching the given collection was found, using the given predicate as the element-wise equivalence test.
    public func offset<Pattern: Collection>(forMatch pattern: Pattern, by areEquivalent: (Element, Pattern.Element) throws -> Bool) rethrows -> Int? {
        guard let offsets = try enumerated().firstMatch(for: pattern, by: { try areEquivalent($0.1, $1) }) else { return nil }

        return offsets.first?.offset ?? 0
    }

}

extension Sequence where Element: Equatable {

    /// Returns how many elements had to be skipped in this sequence until a subsequence identical to the given collection was found.
    public func offset<Pattern: Collection>(forMatch pattern: Pattern) -> Int? where Pattern.Element == Element {
        return offset(forMatch: pattern, by: ==)
    }

}

// MARK: Searching within a collection

extension Collection {

    /// Returns the range of the first subsequence of this collection that matches the given collection, using the given predicate as the element-wise equivalence test.
    public func firstRange<Pattern: Collection>(matching pattern: Pattern, by areEquivalent: (Element, Pattern.Element) throws -> Bool) rethrows -> Range<Index>? {
        guard let matches = try indices.firstMatch(for: pattern, by: { try areEquivalent(self[$0], $1) }) else { return nil }
        guard let firstMatch = matches.first, let lastMatch = matches.last else { return startIndex..<startIndex }

        return firstMatch ..< index(after: lastMatch)
    }

}

extension Collection where Element: Equatable {

    /// Returns the range of the first subsequence of this collection that equals the given collection.
    public func firstRange<Pattern: Collection>(equaling pattern: Pattern) -> Range<Index>? where Pattern.Element == Element {
        return firstRange(matching: pattern, by: ==)
    }

}

// MARK: Searching backwards within a collection

extension BidirectionalCollection {

    /// Returns the range of the last subsequence of this collection that matches the given collection, using the given predicate as the element-wise equivalence test.
    public func lastRange<Pattern: Collection>(matching pattern: Pattern, by areEquivalent: (Element, Pattern.Element) throws -> Bool) rethrows -> Range<Index>? {
        guard let rawResult = try reversed().firstRange(matching: pattern.reversed(), by: areEquivalent) else { return nil }

        return rawResult.upperBound.base ..< rawResult.lowerBound.base
    }

}

extension BidirectionalCollection where Element: Equatable {

    /// Returns the range of the last subsequence of this collection that equals the given collection.
    public func lastRange<Pattern: Collection>(equaling pattern: Pattern) -> Range<Index>? where Pattern.Element == Element {
        return lastRange(matching: pattern, by: ==)
    }

}

SearchN.swift

/*
 SearchN.swift -- Sequence and collection multi-same-element search

 Copyright (c) 2019 Daryle Walker

 */

// MARK: Searching for a repeated string of elements of a set length within a sequence

extension Sequence {

    /**
     Returns, as the given collection type, the first subsequence of this sequence that is the given count in length and has all its elements match the given predicate.

     - Precondition: `count >= 0`.

     - Parameter count: The amount of consecutively conforming elements to find.
     - Parameter storingAs: A metatype specifier for the collection type to be returned.
     - Parameter predicate: A closure that takes an element of the sequence as its argument and returns a Boolean value indicating whether the element is a match.

     - Returns: A collection of the matching span of elements, or `nil` if no match can be found.

     - Complexity: O(*n*), where *n* is the length of the sequence.
     */
    public func firstSpan<Result: RangeReplaceableCollection>(withCount count: Int, storingAs: Result.Type, allSatisfying predicate: (Element) throws -> Bool) rethrows -> Result? where Result.Element == Element {
        precondition(count >= 0)

        var iterator = makeIterator()
        var remaining = count
        var result = Result()
        result.reserveCapacity(count)
        while remaining > 0 {
            guard let element = iterator.next() else { return nil }

            if try predicate(element) {
                result.append(element)
                remaining -= 1
            } else {
                result.removeAll(keepingCapacity: true)
                remaining = count
            }
        }
        return result
    }

    /**
     Returns the first subsequence of this sequence that is the given count in length and has all its elements match the given predicate.

     - Precondition: `count >= 0`.

     - Parameter count: The amount of consecutively conforming elements to find.
     - Parameter predicate: A closure that takes an element of the sequence as its argument and returns a Boolean value indicating whether the element is a match.

     - Returns: An array of the matching span of elements, or `nil` if no match can be found.

     - Complexity: O(*n*), where *n* is the length of the sequence.
     */
    public func firstSpan(withCount count: Int, allSatisfying predicate: (Element) throws -> Bool) rethrows -> [Element]? {
        return try firstSpan(withCount: count, storingAs: Array<Element>.self, allSatisfying: predicate)
    }

}

extension Sequence where Element: Equatable {

    /**
     Returns, as the given collection type, the first subsequence of this sequence that is the given count in length and has all its elements equal the given value.

     - Precondition: `count >= 0`.

     - Parameter count: The amount of consecutively conforming elements to find.
     - Parameter storingAs: A metatype specifier for the collection type to be returned.
     - Parameter value: The value to match all elements against.

     - Returns: A collection of the matching span of elements, or `nil` if no match can be found.

     - Complexity: O(*n*), where *n* is the length of the sequence.
     */
    public func firstSpan<Result: RangeReplaceableCollection>(withCount count: Int, storingAs: Result.Type, allEqualing value: Element) -> Result? where Result.Element == Element {
        return firstSpan(withCount: count, storingAs: Result.self, allSatisfying: { $0 == value })
    }

    /**
     Returns the first subsequence of this sequence that is the given count in length and has all its elements equal the given value.

     - Precondition: `count >= 0`.

     - Parameter count: The amount of consecutively conforming elements to find.
     - Parameter value: The value to match all elements against.

     - Returns: An array of the matching span of elements, or `nil` if no match can be found.

     - Complexity: O(*n*), where *n* is the length of the sequence.
     */
    public func firstSpan(withCount count: Int, allEqualing value: Element) -> [Element]? {
        return firstSpan(withCount: count, allSatisfying: { $0 == value })
    }

}

// MARK: Searching all strings of a repeated element with a set minimum length within a sequence

extension Sequence {

    /**
     Returns all subsequences of the sequence that are at least the given count in length and have all their elements match the given predicate, in a collection of the given type.

     - Precondition: `count >= 1`.

     - Parameter count: The minimum amount of consecutively conforming elements to find per match.
     - Parameter storingAs: A metatype specifier for the collection type to be returned.
     - Parameter predicate: A closure that takes an element of the sequence as its argument and returns a Boolean value indicating whether the element is a match.

     - Returns: A collection of collections of the matching spanning subsequences' elements.

     - Complexity: O(*n*), where *n* is the length of the sequence.
     */
    public func allSpans<Result: RangeReplaceableCollection>(ofMinimumCount count: Int, storingAs: Result.Type, withAllSatisfying predicate: (Element) throws -> Bool) rethrows -> Result where Result.Element: RangeReplaceableCollection, Result.Element.Element == Element {
        precondition(count > 0)

        var iterator = makeIterator(), runningCount = 0
        var result = Result(), cache = Result.Element()
        cache.reserveCapacity(count)
        while let element = iterator.next() {
            guard try predicate(element) else {
                if runningCount >= count {
                    assert(cache.count == runningCount)
                    result.append(cache)
                }
                cache.removeAll(keepingCapacity: true)
                runningCount = 0
                continue
            }

            cache.append(element)
            runningCount += 1
        }
        if runningCount >= count {
            assert(cache.count == runningCount)
            result.append(cache)
        }
        return result
    }

    /**
     Returns all subsequences of the sequence that are at least the given count in length and have all their elements match the given predicate, in an array of the given collection type.

     - Precondition: `count >= 1`.

     - Parameter count: The minimum amount of consecutively conforming elements to find per match.
     - Parameter storingEachAs: A metatype specifier for the collection type to be returned per match.
     - Parameter predicate: A closure that takes an element of the sequence as its argument and returns a Boolean value indicating whether the element is a match.

     - Returns: An array of collections of the matching spanning subsequences' elements.

     - Complexity: O(*n*), where *n* is the length of the sequence.
     */
    public func allSpans<Result: RangeReplaceableCollection>(ofMinimumCount count: Int, storingEachAs: Result.Type, withAllSatisfying predicate: (Element) throws -> Bool) rethrows -> [Result] where Result.Element == Element {
        return try allSpans(ofMinimumCount: count, storingAs: Array<Result>.self, withAllSatisfying: predicate)
    }

    /**
     Returns all subsequences of the sequence that are at least the given count in length and have all their elements match the given predicate.

     - Precondition: `count >= 1`.

     - Parameter count: The minimum amount of consecutively conforming elements to find per match.
     - Parameter predicate: A closure that takes an element of the sequence as its argument and returns a Boolean value indicating whether the element is a match.

     - Returns: An array of arrays of the matching spanning subsequences' elements.

     - Complexity: O(*n*), where *n* is the length of the sequence.
     */
    public func allSpans(ofMinimumCount count: Int, withAllSatisfying predicate: (Element) throws -> Bool) rethrows -> [[Element]] {
        return try allSpans(ofMinimumCount: count, storingEachAs: Array<Element>.self, withAllSatisfying: predicate)
    }

}

extension Sequence where Element: Equatable {

    /**
     Returns all subsequences of the sequence that are at least the given count in length and have all their elements equal the given value, in a collection of the given type.

     - Precondition: `count >= 1`.

     - Parameter count: The minimum amount of consecutively conforming elements to find per match.
     - Parameter storingAs: A metatype specifier for the collection type to be returned.
     - Parameter value: The value to match all elements against.

     - Returns: A collection of collections of the matching spanning subsequences' elements.

     - Complexity: O(*n*), where *n* is the length of the sequence.
     */
    public func allSpans<Result: RangeReplaceableCollection>(ofMinimumCount count: Int, storingAs: Result.Type, withAllEqualing value: Element) -> Result where Result.Element: RangeReplaceableCollection, Result.Element.Element == Element {
        return allSpans(ofMinimumCount: count, storingAs: Result.self, withAllSatisfying: { $0 == value })
    }

    /**
     Returns all subsequences of the sequence that are at least the given count in length and have all their elements equal the given value, in an array of the given collection type.

     - Precondition: `count >= 1`.

     - Parameter count: The minimum amount of consecutively conforming elements to find per match.
     - Parameter storingEachAs: A metatype specifier for the collection type to be returned per match.
     - Parameter value: The value to match all elements against.

     - Returns: An array of collections of the matching spanning subsequences' elements.

     - Complexity: O(*n*), where *n* is the length of the sequence.
     */
    public func allSpans<Result: RangeReplaceableCollection>(ofMinimumCount count: Int, storingEachAs: Result.Type, withAllEqualing value: Element) -> [Result] where Result.Element == Element {
        return allSpans(ofMinimumCount: count, storingEachAs: Result.self, withAllSatisfying: { $0 == value })
    }

    /**
     Returns all subsequences of the sequence that are at least the given count in length and have all their elements equal the given value.

     - Precondition: `count >= 1`.

     - Parameter count: The minimum amount of consecutively conforming elements to find per match.
     - Parameter value: The value to match all elements against.

     - Returns: An array of arrays of the matching spanning subsequences' elements.

     - Complexity: O(*n*), where *n* is the length of the sequence.
     */
    public func allSpans(ofMinimumCount count: Int, withAllEqualing value: Element) -> [[Element]] {
        return allSpans(ofMinimumCount: count, withAllSatisfying: { $0 == value })
    }

}

// MARK: Searching for a repeated string of elements of a set length within a collection

extension Collection {

    /**
     Returns the range of the first subsequence with the given length in the collection where every element matches the given predicate.

     - Precondition: `count >= 0`.

     - Parameter count: The amount of consecutively conforming elements to find.
     - Parameter predicate: A closure that takes an element as its argument and returns a Boolean value that indicates whether the passed element represents a match.

     - Returns: A range for the matching span of elements, or `nil` if no match can be found.

     - Complexity: O(*n*), where *n* is the length of the collection.
     */
    public func firstRange(ofCount count: Int, whereAllSatisfy predicate: (Element) throws -> Bool) rethrows -> Range<Index>? {
        precondition(count >= 0)
        guard count > 0 else { return startIndex..<startIndex }

        var i = startIndex
        while true {
            // Find the next trial search bounds.
            guard let nextStart = try self[i...].firstIndex(where: predicate), let nextHopefulEnd = index(nextStart, offsetBy: count, limitedBy: endIndex) else { return nil }

            let bounds = nextStart..<nextHopefulEnd

            // If this fails, then every element in the bounds was conforming!
            guard let nextEnd = try self[bounds].firstIndex(where: { try !predicate($0) }) else { return bounds }

            // The run of conforming elements ended before the bounds' limit.  Try again.
            i = nextEnd
        }
    }

    /**
     Returns the range of the first subsequence with at least the given length in the collection where every element matches the given predicate.

     - Precondition: `count >= 0`.

     - Parameter count: The minimum amount of consecutively conforming elements to find.
     - Parameter predicate: A closure that takes an element as its argument and returns a Boolean value that indicates whether the passed element represents a match.

     - Returns: A range for the matching span of elements, or `nil` if no match can be found.

     - Complexity: O(*n*), where *n* is the length of the collection.
     */
    public func firstRange(ofMinimumCount count: Int, whereAllSatisfy predicate: (Element) throws -> Bool) rethrows -> Range<Index>? {
        // Re-special-case zero.
        guard count != 0 else { return try firstRange(ofMinimumCount: 1, whereAllSatisfy: predicate) ?? startIndex..<startIndex }

        return try firstRange(ofCount: count, whereAllSatisfy: predicate).map {
            $0.lowerBound ..< (try self[$0.upperBound...].firstIndex(where: { e in try !predicate(e) }) ?? endIndex)
        }
    }

}

extension Collection where Element: Equatable {

    /**
     Returns the range of the first subsequence with the given length in the collection where every element equals the given value.

     - Precondition: `count >= 0`.

     - Parameter count: The amount of consecutively conforming elements to find.
     - Parameter value: The value to match all elements against.

     - Returns: A range for the matching span of elements, or `nil` if no match can be found.

     - Complexity: O(*n*), where *n* is the length of the collection.
     */
    public func firstRange(ofCount count: Int, whereAllEqual value: Element) -> Range<Index>? {
        return firstRange(ofCount: count, whereAllSatisfy: { $0 == value })
    }

    /**
     Returns the range of the first subsequence with at least the given length in the collection where every element equals the given value.

     - Precondition: `count >= 0`.

     - Parameter count: The minimum amount of consecutively conforming elements to find.
     - Parameter value: The value to match all elements against.

     - Returns: A range for the matching span of elements, or `nil` if no match can be found.

     - Complexity: O(*n*), where *n* is the length of the collection.
     */
    public func firstRange(ofMinimumCount count: Int, whereAllEqual value: Element) -> Range<Index>? {
        return firstRange(ofMinimumCount: count, whereAllSatisfy: { $0 == value })
    }

}

extension BidirectionalCollection {

    /**
     Returns the range of the last subsequence with the given length in the collection where every element matches the given predicate.

     - Precondition: `count >= 0`.

     - Parameter count: The amount of consecutively conforming elements to find.
     - Parameter predicate: A closure that takes an element as its argument and returns a Boolean value that indicates whether the passed element represents a match.

     - Returns: A range for the matching span of elements, or `nil` if no match can be found.

     - Complexity: O(*n*), where *n* is the length of the collection.
     */
    public func lastRange(ofCount count: Int, whereAllSatisfy predicate: (Element) throws -> Bool) rethrows -> Range<Index>? {
        return try reversed().firstRange(ofCount: count, whereAllSatisfy: predicate).map { $0.upperBound.base ..< $0.lowerBound.base }
    }

    /**
     Returns the range of the last subsequence with at least the given length in the collection where every element matches the given predicate.

     - Precondition: `count >= 0`.

     - Parameter count: The minimum amount of consecutively conforming elements to find.
     - Parameter predicate: A closure that takes an element as its argument and returns a Boolean value that indicates whether the passed element represents a match.

     - Returns: A range for the matching span of elements, or `nil` if no match can be found.

     - Complexity: O(*n*), where *n* is the length of the collection.
     */
    public func lastRange(ofMinimumCount count: Int, whereAllSatisfy predicate: (Element) throws -> Bool) rethrows -> Range<Index>? {
        return try reversed().firstRange(ofMinimumCount: count, whereAllSatisfy: predicate).map { $0.upperBound.base ..< $0.lowerBound.base }
    }

}

extension BidirectionalCollection where Element: Equatable {

    /**
     Returns the range of the last subsequence with the given length in the collection where every element equals the given value.

     - Precondition: `count >= 0`.

     - Parameter count: The amount of consecutively conforming elements to find.
     - Parameter value: The value to match all elements against.

     - Returns: A range for the matching span of elements, or `nil` if no match can be found.

     - Complexity: O(*n*), where *n* is the length of the collection.
     */
    public func lastRange(ofCount count: Int, whereAllEqual value: Element) -> Range<Index>? {
        return lastRange(ofCount: count, whereAllSatisfy: { $0 == value })
    }

    /**
     Returns the range of the last subsequence with at least the given length in the collection where every element equals the given value.

     - Precondition: `count >= 0`.

     - Parameter count: The minimum amount of consecutively conforming elements to find.
     - Parameter value: The value to match all elements against.

     - Returns: A range for the matching span of elements, or `nil` if no match can be found.

     - Complexity: O(*n*), where *n* is the length of the collection.
     */
    public func lastRange(ofMinimumCount count: Int, whereAllEqual value: Element) -> Range<Index>? {
        return lastRange(ofMinimumCount: count, whereAllSatisfy: { $0 == value })
    }

}


// MARK: - Lazily Search for all Occurances of a Repeated String of Elements

// MARK: Iterators

/// An iterator that vends from a wrapped iterator fixed-sized multi-element blocks of the same classification.
public struct LazyConsecutiveMatchIterator<Base: IteratorProtocol, Element: RangeReplaceableCollection> where Base.Element == Element.Element {

    /// The wrapped iterator, whose elements will be grouped for tests and vending.
    var base: Base

    /// The count of elements per vended group.
    let spanCount: Int
    /// Whether to start searching for another span before the previous match's end.
    let allowOverlap: Bool
    /// The test for each element to check whether it can be part of a match.
    let predicate: (Element.Element) -> Bool

    /// The latest subsequence, for matching.
    lazy var buffer: RingBuffer<Base.Element>? = {
        var trialBuffer = [Base.Element]()
        trialBuffer.reserveCapacity(spanCount)
        for _ in 0..<spanCount {
            guard let nextBuffered = base.next() else { return nil }

            trialBuffer.append(nextBuffered)
        }
        return RingBuffer(trialBuffer)
    }()

    /// Creates an iterator wrapping the given one, along with the given parameters as search bounds.
    init(_ base: Base, withSpanOf count: Int, allowingOverlap: Bool, allSatisfying: @escaping (Element.Element) -> Bool) {
        precondition(count > 0)

        self.base = base
        spanCount = count
        allowOverlap = allowingOverlap
        predicate = allSatisfying
    }

}

extension LazyConsecutiveMatchIterator: IteratorProtocol {

    public mutating func next() -> Element? {
        while buffer != nil {
            if buffer!.allSatisfy(predicate) {
                defer {
                    for _ in 0..<(allowOverlap ? 1 : spanCount) {
                        if let nextElement = base.next() {
                            buffer!.pushThrough(asLastElement: nextElement)
                        } else {
                            buffer = nil
                            break
                        }
                    }
                }

                var result = Element()
                result.reserveCapacity(spanCount)
                result.append(contentsOf: buffer!)
                return result
            }
            guard let nextElement = base.next() else {
                buffer = nil
                break
            }

            buffer!.pushThrough(asLastElement: nextElement)
        }
        return nil
    }

}

/// An iterator that vends from a wrapped iterator fixed-minimum-sized multi-element blocks of the same classification.
public struct LazyConsecutiveMinimumMatchIterator<Base: IteratorProtocol, Element: RangeReplaceableCollection> where Base.Element == Element.Element {

    /// The wrapped iterator, whose elements will be grouped for tests and vending.
    var base: Base

    /// The minimum count of elements per vended group.
    let spanCount: Int
    /// The test for each element to check whether it can be part of a match.
    let predicate: (Element.Element) -> Bool

    /// Creates an iterator wrapping the given one, along with the given parameters as search bounds.
    init(_ base: Base, withMinimumSpanOf count: Int, allSatisfying: @escaping (Element.Element) -> Bool) {
        precondition(count > 0)

        self.base = base
        spanCount = count
        predicate = allSatisfying
    }

}

extension LazyConsecutiveMinimumMatchIterator: IteratorProtocol {

    public mutating func next() -> Element? {
        var result = Element(), runningCount = 0
        result.reserveCapacity(spanCount)
        while let nextElement = base.next() {
            if predicate(nextElement) {
                result.append(nextElement)
                runningCount += 1
            } else {
                guard runningCount < spanCount else { break }

                runningCount = 0
                result.removeAll(keepingCapacity: true)
            }
        }
        if runningCount >= spanCount {
            assert(result.count == runningCount)
            return result
        } else {
            return nil
        }
    }

}

// MARK: Sequences

/// A sequence that vends from a wrapped sequence fixed-sized multi-element blocks of the same classification.
public struct LazyConsecutiveMatchSequence<Base: Sequence, Element: RangeReplaceableCollection> where Base.Element == Element.Element {

    /// The wrapped sequence, whose elements will be grouped for tests and vending.
    var base: Base

    /// The count of elements per vended group.
    let spanCount: Int
    /// Whether to start searching for another span before the previous match's end.
    let allowOverlap: Bool
    /// The test for each element to check whether it can be part of a match.
    let predicate: (Element.Element) -> Bool

    /// Creates an iterator wrapping the given one, along with the given parameters as search bounds.
    init(_ base: Base, withSpanOf count: Int, allowingOverlap: Bool, allSatisfying: @escaping (Element.Element) -> Bool) {
        precondition(count > 0)

        self.base = base
        spanCount = count
        allowOverlap = allowingOverlap
        predicate = allSatisfying
    }

}

extension LazyConsecutiveMatchSequence: Sequence {

    public func makeIterator() -> LazyConsecutiveMatchIterator<Base.Iterator, Element> {
        return LazyConsecutiveMatchIterator(base.makeIterator(), withSpanOf: spanCount, allowingOverlap: allowOverlap, allSatisfying: predicate)
    }

}

extension LazyConsecutiveMatchSequence: LazySequenceProtocol {}

/// A sequence that vends from a wrapped sequence fixed-minimum-sized multi-element blocks of the same classification.
public struct LazyConsecutiveMinimumMatchSequence<Base: Sequence, Element: RangeReplaceableCollection> where Base.Element == Element.Element {

    /// The wrapped sequence, whose elements will be grouped for tests and vending.
    var base: Base

    /// The minimum count of elements per vended group.
    let spanCount: Int
    /// The test for each element to check whether it can be part of a match.
    let predicate: (Element.Element) -> Bool

    /// Creates an iterator wrapping the given one, along with the given parameters as search bounds.
    init(_ base: Base, withMinimumSpanOf count: Int, allSatisfying: @escaping (Element.Element) -> Bool) {
        precondition(count > 0)

        self.base = base
        spanCount = count
        predicate = allSatisfying
    }

}

extension LazyConsecutiveMinimumMatchSequence: Sequence {

    public func makeIterator() -> LazyConsecutiveMinimumMatchIterator<Base.Iterator, Element> {
        return LazyConsecutiveMinimumMatchIterator(base.makeIterator(), withMinimumSpanOf: spanCount, allSatisfying: predicate)
    }

}

extension LazyConsecutiveMinimumMatchSequence: LazySequenceProtocol {}

// MARK: Collections

/// A collection that vends the subsequences of the wrapped collection of an exact length and have all elements match the same classification.
public struct LazyConsecutiveMatchCollection<Base: Collection> {

    /// Wrapper for the collection's properties, nested one level to allow lazy initialization.
    final class Core {
        /// The wrapped collection, whose elements will be grouped for tests and vending.
        var base: Base

        /// The count of elements per vended group.
        let spanCount: Int
        /// The test for each element to check whether it can be part of a match.
        let predicate: (Base.Element) -> Bool

        /// The cached range of the first matching subsequence.
        lazy var firstRange = {
            return base.firstRange(ofCount: spanCount, whereAllSatisfy: predicate)
        }()

        /// Creates a core wrapping the given collection, along with the given parameters as search bounds.
        init(_ base: Base, withSpanOf count: Int, allSatisfying: @escaping (Base.Element) -> Bool) {
            precondition(count > 0)

            self.base = base
            spanCount = count
            predicate = allSatisfying
        }
    }

    /// The key data of this type, moved to a class to provide first-run mutability.
    let core: Core
    /// Whether or not to include matches that start before a previous one ends.
    let allowOverlap: Bool

    /// Creates a collection wrapping the given one, along with the given parameters as search bounds.
    init(_ base: Base, withSpanOf count: Int, allowingOverlap: Bool, allSatisfying: @escaping (Base.Element) -> Bool) {
        core = Core(base, withSpanOf: count, allSatisfying: allSatisfying)
        allowOverlap = allowingOverlap
    }

}

extension LazyConsecutiveMatchCollection: Collection {

    public typealias Index = LazyMatchCollectionIndex<Base>

    public var startIndex: Index { return Index(base: core.firstRange) }
    public var endIndex: Index { return Index(base: nil) }

    public subscript(position: Index) -> Base.SubSequence { return core.base[position.base!] }

    public func index(after i: Index) -> Index {
        let indexRange = i.base!
        if allowOverlap {
            guard indexRange.upperBound < core.base.endIndex else { return endIndex }

            if core.predicate(core.base[indexRange.upperBound]) {
                return Index(base: core.base.index(after: indexRange.lowerBound) ..< core.base.index(after: indexRange.upperBound))
            }
        }

        // Else, or if the allowing-overlap branch failed, search for the next separated block.
        // (If firstRange(ofCount: whereAllSatisfy:) fails, we get endIndex, as we should.)
        return Index(base: core.base[indexRange.upperBound...].firstRange(ofCount: core.spanCount, whereAllSatisfy: core.predicate))
    }

}

extension LazyConsecutiveMatchCollection: BidirectionalCollection where Base: BidirectionalCollection {

    public func index(before i: Index) -> Index {
        let searchEnd: Base.Index
        if let indexRange = i.base {
            // Got a valid element range.  Use what's before it, if possible.
            // (The index(_: offsetBy:) call can crash as needed for going before startIndex.)
            let start = core.base.index(indexRange.lowerBound, offsetBy: allowOverlap ? -1 : -core.spanCount)
            if core.base[start..<indexRange.lowerBound].allSatisfy(core.predicate) {
                return Index(base: start..<(allowOverlap ? core.base.index(before: indexRange.upperBound) : indexRange.lowerBound))
            }
            searchEnd = indexRange.lowerBound
        } else {
            searchEnd = core.base.endIndex
        }

        // Find the last (disconnected) element block.  (The trailing-"!" represents crashing when trying to go before startIndex.)
        let lastRange = core.base[..<searchEnd].lastRange(ofMinimumCount: core.spanCount, whereAllSatisfy: core.predicate)!

        // Get the last segment, ignoring the stragglers, which wouldn't be counted during forward iteration when there's no overlap.
        let lastRangeCount = core.base.distance(from: lastRange.lowerBound, to: lastRange.upperBound)
        let lastEnd = core.base.index(lastRange.upperBound, offsetBy: allowOverlap ? 0 : -(lastRangeCount % core.spanCount))
        let lastStart = core.base.index(lastEnd, offsetBy: -core.spanCount)
        return Index(base: lastStart..<lastEnd)
    }

}

extension LazyConsecutiveMatchCollection: LazyCollectionProtocol {}

/// A collection that vends the subsequences of the wrapped collection of a fixed minimum length and have all elements match the same classification.
public struct LazyConsecutiveMinimumMatchCollection<Base: Collection> {

    /// Wrapper for the collection's properties, nested one level to allow lazy initialization.
    final class Core {
        /// The wrapped collection, whose elements will be grouped for tests and vending.
        var base: Base

        /// The minimum count of elements per vended group.
        let spanCount: Int
        /// The test for each element to check whether it can be part of a match.
        let predicate: (Base.Element) -> Bool

        /// The cached range of the first matching subsequence.
        lazy var firstRange = {
            return base.firstRange(ofMinimumCount: spanCount, whereAllSatisfy: predicate)
        }()

        /// Creates a core wrapping the given collection, along with the given parameters as search bounds.
        init(_ base: Base, withMinimumSpanOf count: Int, allSatisfying: @escaping (Base.Element) -> Bool) {
            precondition(count > 0)

            self.base = base
            spanCount = count
            predicate = allSatisfying
        }
    }

    /// The key data of this type, moved to a class to provide first-run mutability.
    let core: Core

    /// Creates a collection wrapping the given one, along with the given parameters as search bounds.
    init(_ base: Base, withMinimumSpanOf count: Int, allSatisfying: @escaping (Base.Element) -> Bool) {
        core = Core(base, withMinimumSpanOf: count, allSatisfying: allSatisfying)
    }

}

extension LazyConsecutiveMinimumMatchCollection: Collection {

    public typealias Index = LazyMatchCollectionIndex<Base>

    public var startIndex: Index { return Index(base: core.firstRange) }
    public var endIndex: Index { return Index(base: nil) }

    public subscript(position: Index) -> Base.SubSequence { return core.base[position.base!] }

    public func index(after i: Index) -> Index {
        // The trailing-"!" works to crash if i is inappropriately endIndex.
        return Index(base: core.base[i.base!.upperBound...].firstRange(ofMinimumCount: core.spanCount, whereAllSatisfy: core.predicate))
    }

}

extension LazyConsecutiveMinimumMatchCollection: BidirectionalCollection where Base: BidirectionalCollection {

    public func index(before i: Index) -> Index {
        // The trailing-"!" works to crash if i is inappropriately startIndex.
        return Index(base: core.base[..<(i.base?.lowerBound ?? core.base.endIndex)].lastRange(ofMinimumCount: core.spanCount, whereAllSatisfy: core.predicate)!)
    }

}

extension LazyConsecutiveMinimumMatchCollection: LazyCollectionProtocol {}

// MARK: Adaptor Generators

extension LazySequenceProtocol {

    /**
     Returns all subsequences of the sequence that are the given count in length and have all their elements match the given predicate, lazily vended through collections of the given type.

     - Precondition: `count >= 1`.

     - Parameter count: The amount of consecutively conforming elements to find per match.
     - Parameter allowingOverlap: Whether or not to include matching subsequences that start before the previous one ends.
     - Parameter storingEachAs: A metatype specifier for the collection type to be returned per match.
     - Parameter predicate: A closure that takes an element of the sequence as its argument and returns a Boolean value indicating whether the element is a match.

     - Returns: A lazily-vended sequence of collections of the matching spanning subsequences' elements.
     */
    public func allSpans<Result: RangeReplaceableCollection>(ofCount count: Int, allowingOverlap: Bool, storingEachAs: Result.Type, withAllSatisfying predicate: @escaping (Element) -> Bool) -> LazyConsecutiveMatchSequence<Elements, Result> where Result.Element == Element {
        return LazyConsecutiveMatchSequence(elements, withSpanOf: count, allowingOverlap: allowingOverlap, allSatisfying: predicate)
    }

    /**
     Returns all subsequences of the sequence that are the given count in length and have all their elements match the given predicate, lazily vended through arrays of elements.

     - Precondition: `count >= 1`.

     - Parameter count: The amount of consecutively conforming elements to find per match.
     - Parameter allowingOverlap: Whether or not to include matching subsequences that start before the previous one ends.
     - Parameter predicate: A closure that takes an element of the sequence as its argument and returns a Boolean value indicating whether the element is a match.

     - Returns: A lazily-vended sequence of arrays of the matching spanning subsequences' elements.
     */
    public func allSpans(ofCount count: Int, allowingOverlap: Bool, withAllSatisfying predicate: @escaping (Element) -> Bool) -> LazyConsecutiveMatchSequence<Elements, [Element]> {
        return allSpans(ofCount: count, allowingOverlap: allowingOverlap, storingEachAs: Array<Element>.self, withAllSatisfying: predicate)
    }

    /**
     Returns all subsequences of the sequence that are at least the given count in length and have all their elements match the given predicate, lazily vended through collections of the given type.

     - Precondition: `count >= 1`.

     - Parameter count: The minimum amount of consecutively conforming elements to find per match.
     - Parameter storingEachAs: A metatype specifier for the collection type to be returned per match.
     - Parameter predicate: A closure that takes an element of the sequence as its argument and returns a Boolean value indicating whether the element is a match.

     - Returns: A lazily-vended sequence of collections of the matching spanning subsequences' elements.
     */
    public func allSpans<Result: RangeReplaceableCollection>(ofMinimumCount count: Int, storingEachAs: Result.Type, withAllSatisfying predicate: @escaping (Element) -> Bool) -> LazyConsecutiveMinimumMatchSequence<Elements, Result> where Result.Element == Element {
        return LazyConsecutiveMinimumMatchSequence(elements, withMinimumSpanOf: count, allSatisfying: predicate)
    }

    /**
     Returns all subsequences of the sequence that are at least the given count in length and have all their elements match the given predicate, lazily vended through arrays of elements.

     - Precondition: `count >= 1`.

     - Parameter count: The minimum amount of consecutively conforming elements to find per match.
     - Parameter predicate: A closure that takes an element of the sequence as its argument and returns a Boolean value indicating whether the element is a match.

     - Returns: A lazily-vended sequence of arrays of the matching spanning subsequences' elements.
     */
    public func allSpans(ofMinimumCount count: Int, withAllSatisfying predicate: @escaping (Element) -> Bool) -> LazyConsecutiveMinimumMatchSequence<Elements, [Element]> {
        return allSpans(ofMinimumCount: count, storingEachAs: Array<Element>.self, withAllSatisfying: predicate)
    }

}

extension LazySequenceProtocol where Element: Equatable {

    /**
     Returns all subsequences of the sequence that are the given count in length and have all their elements equal the given value, lazily vended through collections of the given type.

     - Precondition: `count >= 1`.

     - Parameter count: The amount of consecutively conforming elements to find per match.
     - Parameter allowingOverlap: Whether or not to include matching subsequences that start before the previous one ends.
     - Parameter storingEachAs: A metatype specifier for the collection type to be returned per match.
     - Parameter value: The value to match all elements against.

     - Returns: A lazily-vended sequence of collections of the matching spanning subsequences' elements.
     */
    public func allSpans<Result: RangeReplaceableCollection>(ofCount count: Int, allowingOverlap: Bool, storingEachAs: Result.Type, withAllEqualing value: Element) -> LazyConsecutiveMatchSequence<Elements, Result> where Result.Element == Element {
        return allSpans(ofCount: count, allowingOverlap: allowingOverlap, storingEachAs: Result.self, withAllSatisfying: { $0 == value })
    }

    /**
     Returns all subsequences of the sequence that are the given count in length and have all their elements equal the given value, lazily vended through arrays of elements.

     - Precondition: `count >= 1`.

     - Parameter count: The amount of consecutively conforming elements to find per match.
     - Parameter allowingOverlap: Whether or not to include matching subsequences that start before the previous one ends.
     - Parameter value: The value to match all elements against.

     - Returns: A lazily-vended sequence of arrays of the matching spanning subsequences' elements.
     */
    public func allSpans(ofCount count: Int, allowingOverlap: Bool, withAllEqualing value: Element) -> LazyConsecutiveMatchSequence<Elements, [Element]> {
        return allSpans(ofCount: count, allowingOverlap: allowingOverlap, withAllSatisfying: { $0 == value })
    }

    /**
     Returns all subsequences of the sequence that are at least the given count in length and have all their elements equal the given value, lazily vended through collections of the given type.

     - Precondition: `count >= 1`.

     - Parameter count: The minimum amount of consecutively conforming elements to find per match.
     - Parameter storingEachAs: A metatype specifier for the collection type to be returned per match.
     - Parameter value: The value to match all elements against.

     - Returns: A lazily-vended sequence of collections of the matching spanning subsequences' elements.
     */
    public func allSpans<Result: RangeReplaceableCollection>(ofMinimumCount count: Int, storingEachAs: Result.Type, withAllEqualing value: Element) -> LazyConsecutiveMinimumMatchSequence<Elements, Result> where Result.Element == Element {
        return allSpans(ofMinimumCount: count, storingEachAs: Result.self, withAllSatisfying: { $0 == value })
    }

    /**
     Returns all subsequences of the sequence that are at least the given count in length and have all their elements equal the given value, lazily vended through arrays of elements.

     - Precondition: `count >= 1`.

     - Parameter count: The minimum amount of consecutively conforming elements to find per match.
     - Parameter value: The value to match all elements against.

     - Returns: A lazily-vended sequence of arrays of the matching spanning subsequences' elements.
     */
    public func allSpans(ofMinimumCount count: Int, withAllEqualing value: Element) -> LazyConsecutiveMinimumMatchSequence<Elements, [Element]> {
        return allSpans(ofMinimumCount: count, withAllSatisfying: { $0 == value })
    }

}

extension LazyCollectionProtocol {

    /**
     Returns all subsequences of the collection that are the given count in length and have all their elements match the given predicate, lazily vended.

     - Precondition: `count >= 1`.

     - Parameter count: The amount of consecutively conforming elements to find per match.
     - Parameter allowingOverlap: Whether or not to include matching subsequences that start before the previous one ends.
     - Parameter predicate: A closure that takes an element of the collection as its argument and returns a Boolean value indicating whether the element is a match.

     - Returns: A lazy collection of the matching spanning subsequences.
     */
    public func allSpans(ofCount count: Int, allowingOverlap: Bool, withAllSatisfying predicate: @escaping (Element) -> Bool) -> LazyConsecutiveMatchCollection<Elements> {
        return LazyConsecutiveMatchCollection(elements, withSpanOf: count, allowingOverlap: allowingOverlap, allSatisfying: predicate)
    }

    /**
     Returns all subsequences of the collection that are at least the given count in length and have all their elements match the given predicate, lazily vended.

     - Precondition: `count >= 1`.

     - Parameter count: The minimum amount of consecutively conforming elements to find per match.
     - Parameter predicate: A closure that takes an element of the collection as its argument and returns a Boolean value indicating whether the element is a match.

     - Returns: A lazy collection of the matching spanning subsequences.
     */
    public func allSpans(ofMinimumCount count: Int, withAllSatisfying predicate: @escaping (Element) -> Bool) -> LazyConsecutiveMinimumMatchCollection<Elements> {
        return LazyConsecutiveMinimumMatchCollection(elements, withMinimumSpanOf: count, allSatisfying: predicate)
    }

}

extension LazyCollectionProtocol where Element: Equatable {

    /**
     Returns all subsequences of the collection that are the given count in length and have all their elements equal the given value, lazily vended.

     - Precondition: `count >= 1`.

     - Parameter count: The amount of consecutively conforming elements to find per match.
     - Parameter allowingOverlap: Whether or not to include matching subsequences that start before the previous one ends.
     - Parameter value: The value to match all elements against.

     - Returns: A lazy collection of the matching spanning subsequences.
     */
    public func allSpans(ofCount count: Int, allowingOverlap: Bool, withAllEqualing value: Element) -> LazyConsecutiveMatchCollection<Elements> {
        return allSpans(ofCount: count, allowingOverlap: allowingOverlap, withAllSatisfying: { $0 == value })
    }

    /**
     Returns all subsequences of the collection that are at least the given count in length and have all their elements equal the given value, lazily vended.

     - Precondition: `count >= 1`.

     - Parameter count: The minimum amount of consecutively conforming elements to find per match.
     - Parameter value: The value to match all elements against.

     - Returns: A lazy collection of the matching spanning subsequences.
     */
    public func allSpans(ofMinimumCount count: Int, withAllEqualing value: Element) -> LazyConsecutiveMinimumMatchCollection<Elements> {
        return allSpans(ofMinimumCount: count, withAllSatisfying: { $0 == value })
    }

}

Maybe rename the Equatable variant to allSpans(of: Element, count: Int, ...), as allEqualing does not seem, well, Swifty.