Attempts to make a lazy version of the Collection.split function.

LazyEmptyAdmittingSplitCollection.swift

/**
 A lazy wrapper for `Collection.split`, but only when empty subsequences can also be vended.

 Based off the `LazySplitCollection` sample type in the [article "Conditional Conformance in the Standard Library" at the Swift Blog](https://swift.org/blog/conditional-conformance/) by [Ben Cohen](https://twitter.com/airspeedswift/), but extended only to support maximum subsequence counts.
 */
public struct LazyEmptyAdmittingSplitCollection<Base: Collection> {

    /// The wrapped collection, whose subsequences will be vended as elements of `self`.
    let base: Base
    /// The maximum number of splits allowed; the count of subsequences vended is at most one greater than this.
    let maxSplitCount: Int
    /// The function determining whether an element value is a splitting separator.
    let isSeparator: (Base.Element) -> Bool

}

extension LazyEmptyAdmittingSplitCollection: Collection {

    public struct Index: Comparable {
        /// The encounter rank of the corresponding subsequence, from `maxSplitCount` to 0.
        let downCount: Int
        /// The location of the subsequence in `base`.
        let range: Range<Base.Index>

        public static func < (lhs: Index, rhs: Index) -> Bool {
            return lhs.downCount > rhs.downCount
        }
    }

    public var startIndex: Index {
        let firstRangeEnd: Base.Index
        if maxSplitCount > 0, let firstSeparatorIndex = base.firstIndex(where: isSeparator) {
            firstRangeEnd = firstSeparatorIndex
        } else {
            firstRangeEnd = base.endIndex
        }
        return Index(downCount: maxSplitCount, range: base.startIndex..<firstRangeEnd)
    }
    public var endIndex: Index { return Index(downCount: -1, range: base.endIndex..<base.endIndex) }  // Dummy value

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

    public func index(after i: Index) -> Index {
        guard i.downCount > 0, let nextRangeStart = base.index(i.range.upperBound, offsetBy: +1, limitedBy: base.endIndex) else { return endIndex }

        let nextRangeEnd: Base.Index
        if i.downCount > 1, let nextSeparatorIndex = base[nextRangeStart...].firstIndex(where: isSeparator) {
            nextRangeEnd = nextSeparatorIndex
        } else {
            nextRangeEnd = base.endIndex
        }
        return Index(downCount: i.downCount - 1, range: nextRangeStart..<nextRangeEnd)
    }

}

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

extension LazyEmptyAdmittingSplitCollection: LazyCollectionProtocol {}

extension LazyCollectionProtocol {

    /**
     Returns the longest possible subsequences of the collection, in order, that don't contain elements satisfying the given predicate.

     This lazily-generated collection, sections off the wrapped collection at every separator element.  If two separators abut, or a separator starts and/or ends the wrapped collection, an empty subsequence is vended.

     - Parameter maxSplits: The maximum number of times to split the collection, or one less than the number of subsequences to return.  If `maxSplits + 1` subsequences are returned, the last one is a suffix of the original collection containing the remaining elements.  `maxSplits` must be greater than or equal to zero.  The default value is `Int.max`.
     - Parameter matches: A closure that takes an element as an argument and returns a Boolean value indicating whether the collection should be split at that element.
     - Returns: A proxy wrapping collection that lazily sections of subsequences of `elements` based off `matches`.
     */
    public func split_10(maxSplits: Int = Int.max, whereSeparator matches: @escaping (Element) -> Bool) -> LazyEmptyAdmittingSplitCollection<Elements> {
        precondition(maxSplits > 0)

        return LazyEmptyAdmittingSplitCollection(base: elements, maxSplitCount: maxSplits, isSeparator: matches)
    }

}

extension LazyCollectionProtocol where Element: Equatable {

    /**
     Returns the longest possible subsequences of the collection, in order, around elements equal to the given element.

     This lazily-generated collection, sections off the wrapped collection at every separator.  If two separators abut, or a separator starts and/or ends the wrapped collection, an empty subsequence is vended.

     - Parameter separator: The element that should be split upon.
     - Parameter maxSplits: The maximum number of times to split the collection, or one less than the number of subsequences to return.  If `maxSplits + 1` subsequences are returned, the last one is a suffix of the original collection containing the remaining elements.  `maxSplits` must be greater than or equal to zero.  The default value is `Int.max`.
     - Returns: A proxy wrapping collection that lazily sections of subsequences of `elements` between `separator` values.
     */
    public func split_10(separator: Element, maxSplits: Int = Int.max) -> LazyEmptyAdmittingSplitCollection<Elements> {
        return split_10(maxSplits: maxSplits) { $0 == separator }
    }

}

LazyEmptyAdmittingUnlimitedSplitCollection.swift

/**
 A lazy wrapper for `Collection.split`, but only when the number of splits is unlimited and empty subsequences can be vended.

 Based off the `LazySplitCollection` sample type in the [article "Conditional Conformance in the Standard Library" at the Swift Blog](https://swift.org/blog/conditional-conformance/) by [Ben Cohen](https://twitter.com/airspeedswift/).
 */
public struct LazyEmptyAdmittingUnlimitedSplitCollection<Base: Collection> {

    /// The wrapped collection, whose subsections will be vended as elements of `self`.
    let base: Base
    /// The function determing whether an element value is a splitting separator.
    let isSeparator: (Base.Element) -> Bool

}

extension LazyEmptyAdmittingUnlimitedSplitCollection: Collection {

    public var startIndex: Base.Index { return base.startIndex }
    public var endIndex: Base.Index { return base.endIndex }

    public subscript(i: Base.Index) -> Base.SubSequence {
        return base[i..<(firstSeparator(after: i) ?? endIndex)]
    }

    public func index(after i: Base.Index) -> Base.Index {
        return firstSeparator(after: i).map(base.index(after:)) ?? endIndex
    }

    /// Returns the index of the next separator element after the given index, if any.
    func firstSeparator(after i: Base.Index) -> Base.Index? {
        return base[i...].firstIndex(where: isSeparator)
    }

}

extension LazyEmptyAdmittingUnlimitedSplitCollection: BidirectionalCollection where Base: BidirectionalCollection {

    public func index(before i: Base.Index) -> Base.Index {
        return base[..<base.index(before: i)].lastIndex(where: isSeparator).map(index(after:)) ?? startIndex
    }

}

extension LazyEmptyAdmittingUnlimitedSplitCollection: LazyCollectionProtocol {}

extension LazyCollectionProtocol {

    /**
     Returns the longest possible subsequences of the collection, in order, that don't contain elements satisfying the given predicate.

     This lazily-generated collection, sections off the wrapped collection at every separator element.  If two separators abut, or a separator starts and/or ends the wrapped collection, an empty subsequence is vended.

     - Parameter matches: A closure that takes an element as an argument and returns a Boolean value indicating whether the collection should be split at that element.
     - Returns: A proxy wrapping collection that lazily sections of subsequences of `elements` based off `matches`.
     */
    public func split_00(whereSeparator matches: @escaping (Element) -> Bool) -> LazyEmptyAdmittingUnlimitedSplitCollection<Elements> {
        return LazyEmptyAdmittingUnlimitedSplitCollection(base: elements, isSeparator: matches)
    }

}

extension LazyCollectionProtocol where Element: Equatable {

    /**
     Returns the longest possible subsequences of the collection, in order, around elements equal to the given element.

     This lazily-generated collection, sections off the wrapped collection at every separator.  If two separators abut, or a separator starts and/or ends the wrapped collection, an empty subsequence is vended.

     - Parameter separator: The element that should be split upon.
     - Returns: A proxy wrapping collection that lazily sections of subsequences of `elements` between `separator` values.
     */
    public func split_00(separator: Element) -> LazyEmptyAdmittingUnlimitedSplitCollection<Elements> {
        return LazyEmptyAdmittingUnlimitedSplitCollection(base: elements) { $0 == separator }
    }

}

LazySplitCollection.swift

/**
 A lazy wrapper for `Collection.split`.

 Based off the `LazySplitCollection` sample type in the [article "Conditional Conformance in the Standard Library" at the Swift Blog](https://swift.org/blog/conditional-conformance/) by [Ben Cohen](https://twitter.com/airspeedswift/), but extended to support maximum subsequence counts and skipping of empty subsequences.
 */
public struct LazySplitCollection<Base: Collection> {

    /// The wrapped collection, whose subsections will be vended as elements of `self`.
    let base: Base
    /// The maximum number of splits allowed; the count of subsequences vended is at most one greater than this.
    let maxSplitCount: Int
    /// Whether to exclude empty subsequences from being vended.  Such subsequences are defined by two consecutive elements of `base` that are separators, or where a separator is the first or last element.
    let omitEmptySubsequences: Bool
    /// The function determing whether an element value is a splitting separator.
    let isSeparator: (Base.Element) -> Bool

    /// An always-mutable cache for vended elements.
    final class RangeCache {
        /// The location for the first vended range in `base`, if any.  Initialized when first needed.
        var firstRange: Range<Base.Index>?? = nil
    }

    /// The location for first vended element.  Cached so `startIndex` doesn't have to repeatedly search.
    let rangeCache = RangeCache()

}

extension LazySplitCollection: Collection {

    public struct Index: Comparable {
        /// The encounter rank of the corresponding subsequence, from `maxSplitCount` to 0.
        let downCount: Int
        /// The location of the subsequence in `base`, or `nil` for *really* past-the-end.
        let range: Range<Base.Index>?

        public static func < (lhs: Index, rhs: Index) -> Bool {
            return lhs.downCount > rhs.downCount
        }
    }

    /**
     The position of the first element in a non-empty collection.

     In an empty collection, `startIndex == endIndex`.

     - Complexity: *Amortized* O(1), since the first attempt runs in O(*n*), where *n* is the count of elements in the wrapped collection, and then is cached.
     */
    public var startIndex: Index {
        switch rangeCache.firstRange {
        case .none:
            let start, end: Base.Index
            if omitEmptySubsequences, maxSplitCount > 0 {
                start = base.firstIndex(where: { !isSeparator($0) }) ?? base.endIndex
            } else {
                start = base.startIndex
            }
            if maxSplitCount > 0 {
                end = base[start...].firstIndex(where: isSeparator) ?? base.endIndex
            } else {
                end = base.endIndex
            }

            let firstRange = start..<end
            if omitEmptySubsequences, firstRange.isEmpty {
                rangeCache.firstRange = .some(nil)
            } else {
                rangeCache.firstRange = .some(firstRange)
            }
            return self.startIndex
        case .some(.none):
            return endIndex
        case .some(let firstRange?):
            return Index(downCount: maxSplitCount, range: firstRange)
        }
    }
    public var endIndex: Index {
        return Index(downCount: -1, range: nil)
    }

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

    public func index(after i: Index) -> Index {
        var previousRange = i.range!
        guard i.downCount != 1 else {
            guard previousRange.upperBound < base.endIndex else { return endIndex }

            return Index(downCount: 0, range: base.index(after: previousRange.upperBound)..<base.endIndex)
        }

        repeat {
            // When i.downCount is 0, this should always trigger too.
            guard previousRange.upperBound < base.endIndex else { return endIndex }

            let start = base.index(after: previousRange.upperBound)
            let end = base[start...].firstIndex(where: isSeparator) ?? base.endIndex
            previousRange = start..<end
        } while omitEmptySubsequences && previousRange.isEmpty
        return Index(downCount: i.downCount - 1, range: previousRange)
    }

}

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

extension LazySplitCollection: LazyCollectionProtocol {}

extension LazyCollectionProtocol {

    /**
     Returns the longest possible subsequences of the collection, in order, that don't contain elements satisfying the given predicate.

     This lazily-generated collection, sections off the wrapped collection at every separator element.  If two separators abut, or a separator starts and/or ends the wrapped collection, an empty subsequence is vended.

     - Note: Unlike the default `Collection` requirements, the returned collection's `startIndex` (and therefore `isEmpty` too) have *amortized* O(1) complexity.

     - Precondition: If the copy of `elements` that returned collection makes has its elements shared by reference to other objects, none of those objects can mutate the shared collection state while the collection is active.

     - Parameter maxSplits: The maximum number of times to split the collection, or one less than the number of subsequences to return.  If `maxSplits + 1` subsequences are returned, the last one is a suffix of the original collection containing the remaining elements.  `maxSplits` must be greater than or equal to zero.  The default value is `Int.max`.
     - Parameter omittingEmptySubsequences: If `false`, an empty subsequence is vended for each pair of consecutive elements satisfying the `isSeparator` predicate and for each element at the start or end of the collection satisfying the `isSeparator` predicate.  The default value is `true`.
     - Parameter matches: A closure that takes an element as an argument and returns a Boolean value indicating whether the collection should be split at that element.
     - Returns: A proxy wrapping collection that lazily sections of subsequences of `elements` based off `matches`.
     */
    public func split(maxSplits: Int = Int.max, omittingEmptySubsequences: Bool = true, whereSeparator matches: @escaping (Element) -> Bool) -> LazySplitCollection<Elements> {
        precondition(maxSplits >= 0)

        return LazySplitCollection(base: elements, maxSplitCount: maxSplits, omitEmptySubsequences: omittingEmptySubsequences, isSeparator: matches)
    }

}

extension LazyCollectionProtocol where Element: Equatable {

    /**
     Returns the longest possible subsequences of the collection, in order, around elements equal to the given element.

     This lazily-generated collection, sections off the wrapped collection at every separator.  If two separators abut, or a separator starts and/or ends the wrapped collection, an empty subsequence is vended.

     - Note: Unlike the default `Collection` requirements, the returned collection's `startIndex` (and therefore `isEmpty` too) have *amortized* O(1) complexity.

     - Precondition: If the copy of `elements` that returned collection makes has its elements shared by reference to other objects, none of those objects can mutate the shared collection state while the collection is active.

     - Parameter separator: The element that should be split upon.
     - Parameter maxSplits: The maximum number of times to split the collection, or one less than the number of subsequences to return.  If `maxSplits + 1` subsequences are returned, the last one is a suffix of the original collection containing the remaining elements.  `maxSplits` must be greater than or equal to zero.  The default value is `Int.max`.
     - Parameter omittingEmptySubsequences: If `false`, an empty subsequence is vended for each consecutive pair of `separator` elements in the collection and for each instance of `separator` at the start or end of the collection.  If `true`, only nonempty subsequences are vended.  The default value is `true`.
     - Returns: A proxy wrapping collection that lazily sections of subsequences of `elements` between `separator` values.
     */
    public func split(separator: Element, maxSplits: Int = Int.max, omittingEmptySubsequences: Bool = true) -> LazySplitCollection<Elements> {
        return split(maxSplits: maxSplits, omittingEmptySubsequences: omittingEmptySubsequences, whereSeparator: { $0 == separator })
    }

}

LazyUnlimitedSplitCollection.swift

/**
 A lazy wrapper for `Collection.split`, but only when the number of splits is unlimited.

 Based off the `LazySplitCollection` sample type in the [article "Conditional Conformance in the Standard Library" at the Swift Blog](https://swift.org/blog/conditional-conformance/) by [Ben Cohen](https://twitter.com/airspeedswift/), but extended only to support omission of empty subsequences.
 */
public struct LazyUnlimitedSplitCollection<Base: Collection> {

    /// The wrapped collection, whose subsequences will be vended as elements of `self`.
    let base: Base
    /// Whether to exclude empty subsequences from being vended.  Such subsequences are defined by two consecutive elements of `base` that are separators, or where a separator is the first or last element.
    let omitEmptySubsequences: Bool
    /// The function determining whether an element value is a splitting separator.
    let isSeparator: (Base.Element) -> Bool

    /// An always-mutable cache for vended elements.
    final class RangeCache {
        /// The location for the first vended range in `base`, if any.  Initialized when first needed.
        var firstRange: Range<Base.Index>?? = nil
        /// The location for the last vended range in `base`, if any.  Initialized when first needed for bidirectional collections.
        var lastRange: Range<Base.Index>?? = nil
    }

    /// The locations for first and last vended elements.  Cached so `startIndex` and `endIndex` don't have to repeatedly search.
    let endcapRanges = RangeCache()

}

extension LazyUnlimitedSplitCollection: Collection {

    public struct Index: Comparable {
        /// The location of the subsequence in `base`, or `nil` for *really* past-the-end.
        let range: Range<Base.Index>?

        public static func < (lhs: Index, rhs: Index) -> Bool {
            switch (lhs.range, rhs.range) {
            case (let lrange?, let rrange?):
                precondition(lrange == rrange || !lrange.overlaps(rrange))

                return lrange.lowerBound < rrange.lowerBound
            case (.some, .none):
                return true
            default:
                return false
            }
        }
    }

    public var startIndex: Index {
        switch endcapRanges.firstRange {
        case .none:
            let start: Base.Index
            if omitEmptySubsequences {
                start = base.firstIndex(where: { !isSeparator($0) }) ?? base.endIndex
            } else {
                start = base.startIndex
            }
            guard start < base.endIndex || (!omitEmptySubsequences && base.isEmpty) else {
                endcapRanges.firstRange = .some(.none)
                fallthrough
            }

            let end = base[start...].firstIndex(where: isSeparator) ?? base.endIndex
            endcapRanges.firstRange = .some(.some(start..<end))
            return Index(range: endcapRanges.firstRange!!)
        case .some(.none):
            return endIndex
        case .some(.some(let firstSubsequenceRange)):
            return Index(range: firstSubsequenceRange)
        }
    }
    public var endIndex: Index {
        return Index(range: nil)
    }

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

    public func index(after i: Index) -> Index {
        var previousRange = i.range!
        repeat {
            guard previousRange.upperBound < base.endIndex else { return endIndex }

            let start = base.index(after: previousRange.upperBound)
            let end = base[start...].firstIndex(where: isSeparator) ?? base.endIndex
            previousRange = start..<end
        } while omitEmptySubsequences && previousRange.isEmpty
        return Index(range: previousRange)
    }

}

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

extension LazyUnlimitedSplitCollection: BidirectionalCollection where Base: BidirectionalCollection {

    public func index(before i: Index) -> Index {
        guard i < endIndex else {
            switch endcapRanges.lastRange {
            case .none:
                guard let lastIndex = base.index(base.endIndex, offsetBy: -1, limitedBy: base.startIndex) else {
                    if omitEmptySubsequences {
                        endcapRanges.lastRange = .some(nil)
                        preconditionFailure("Attempt to go before startIndex")
                    } else {
                        endcapRanges.lastRange = .some(base.endIndex..<base.endIndex)
                        return Index(range: endcapRanges.lastRange!)
                    }
                }

                if !omitEmptySubsequences, isSeparator(base[lastIndex]) {
                    endcapRanges.lastRange = .some(base.endIndex..<base.endIndex)
                } else {
                    let lastNonSeparatorIndex = base[...lastIndex].lastIndex(where: { !isSeparator($0) }) ?? base.startIndex
                    let startOfLastRange = base[...lastNonSeparatorIndex].lastIndex(where: isSeparator).map(base.index(after:)) ?? base.startIndex
                    endcapRanges.lastRange = .some(startOfLastRange..<base.index(after: lastNonSeparatorIndex))
                }
                return Index(range: endcapRanges.lastRange!)
            case .some(let possibleLastRange):
                return Index(range: possibleLastRange!)
            }
        }

        var previousRange = i.range!
        repeat {
            let end = base.index(before: previousRange.lowerBound)
            let start = base[..<end].lastIndex(where: isSeparator).map(base.index(after:)) ?? base.startIndex
            previousRange = start..<end
        } while omitEmptySubsequences && previousRange.isEmpty
        return Index(range: previousRange)
    }

}

extension LazyUnlimitedSplitCollection: LazyCollectionProtocol {}

extension LazyCollectionProtocol {

    /**
     Returns the longest possible subsequences of the collection, in order, that don't contain elements satisfying the given predicate.

     This lazily-generated collection, sections off the wrapped collection at every separator element.  Whether subsequences that end up empty are vended or not depends on the `omittingEmptySubsequences` parameter.

     - Parameter omittingEmptySubsequences: If `false`, an empty subsequence is vended for each pair of consecutive elements satisfying the `isSeparator` predicate and for each element at the start or end of the collection satisfying the `isSeparator` predicate.  The default value is `true`.
     - Parameter matches: A closure that takes an element as an argument and returns a Boolean value indicating whether the collection should be split at that element.
     - Returns: A proxy wrapping collection that lazily sections of subsequences of `elements` based off `matches`.
     */
    public func split_01(omittingEmptySubsequences: Bool = true, whereSeparator matches: @escaping (Element) -> Bool) -> LazyUnlimitedSplitCollection<Elements> {
        return LazyUnlimitedSplitCollection(base: elements, omitEmptySubsequences: omittingEmptySubsequences, isSeparator: matches)
    }

}

extension LazyCollectionProtocol where Element: Equatable {

    /**
     Returns the longest possible subsequences of the collection, in order, around elements equal to the given element.

     This lazily-generated collection, sections off the wrapped collection at every separator.  Whether subsequences that end up empty are vended or not depends on the `omittingEmptySubsequences` parameter.

     - Parameter separator: The element that should be split upon.
     - Parameter omittingEmptySubsequences: If `false`, an empty subsequence is vended for each consecutive pair of `separator` elements in the collection and for each instance of `separator` at the start or end of the collection.  If `true`, only nonempty subsequences are vended.  The default value is `true`.
     - Returns: A proxy wrapping collection that lazily sections of subsequences of `elements` between `separator` values.
     */
    public func split_01(separator: Element, omittingEmptySubsequences: Bool = true) -> LazyUnlimitedSplitCollection<Elements> {
        return split_01(omittingEmptySubsequences: omittingEmptySubsequences) { $0 == separator }
    }

}