A sorted sequence with elements of another sorted sequence filtered out. Based on <https://forums.swift.org/t/how-to-effectively-filter-array-by-another-array-in-functional-paradigm/20442>.

BasicSetSubtraction.swift

// BasicSetSubtraction.swift by Daryle Walker

/// An iterator that vends elements from a sorted wrapped iterator, subtracting the elements from in another wrapped sorted filter iterator.
public struct SetSubtractionIterator<Base: IteratorProtocol, Filter: IteratorProtocol> where Base.Element == Filter.Element, Base.Element: Comparable {

    /// The iterator where the vended elements come from.
    var base: Base
    /// The iterator where matches to be filtered come from.
    var filters: Filter

    /// The last element from `base`, to help confirm its underlying sequence is sorted.
    var lastBase: Base.Element?
    /// The last element from `filters`, to help confirm its underlying sequence is sorted.
    var lastFilter: Filter.Element?

    /// Creates an iterator vending elements of a given base iterator minus the elements that are also in another iterator.
    init(_ base: Base, filter: Filter) {
        self.base = base
        filters = filter
        lastBase = nil
        lastFilter = nil
    }

}

extension SetSubtractionIterator: IteratorProtocol {

    public mutating func next() -> Base.Element? {
        // Can't return wrapped element if there's no more.
        lastBase = lastBase ?? base.next()
        guard let latestBase = lastBase else { return nil }

        /*
         Compare latest from base and filtered:

         - filtered is NIL: return base and increment it
         - base < filtered: return base and increment it
         - base == filtered: increment both then recursive call
         - base > filtered: increment filter then recursive call
         */
        do {
            let incrementBase: Bool
            defer {
                if incrementBase {
                    lastBase = base.next()
                    if let nextBase = lastBase, nextBase < latestBase {
                        preconditionFailure("To-be-filtered sequence isn't actually sorted")
                    }
                }
            }

            lastFilter = lastFilter ?? filters.next()
            guard let latestFilter = lastFilter, latestBase >= latestFilter else {
                incrementBase = true
                return latestBase
            }
            defer {
                lastFilter = filters.next()
                if let nextFiltered = lastFilter, nextFiltered < latestFilter {
                    preconditionFailure("Filtering sequence isn't actually sorted")
                }
            }

            incrementBase = latestBase == latestFilter
        }
        return next()
    }

}

/// A sequence that vends elements from a sorted wrapped sequence, subtracting the elements from in another wrapped sorted filter sequence.
public struct SetSubtractionSequence<Base: Sequence, Filter: Sequence> where Base.Element == Filter.Element, Base.Element: Comparable {

    /// The sequence where the vended elements come from.
    var base: Base
    /// The sequence where matches to be filtered come from.
    var filters: Filter

    /// Creates a sequence vending elements of a given base sequence minus the elements that are also in another sequence.
    init(_ base: Base, filter: Filter) {
        self.base = base
        filters = filter
    }

}

extension SetSubtractionSequence: Sequence {

    public func makeIterator() -> SetSubtractionIterator<Base.Iterator, Filter.Iterator> {
        return SetSubtractionIterator(base.makeIterator(), filter: filters.makeIterator())
    }

    public var underestimatedCount: Int {
        return Swift.max(0, base.underestimatedCount - filters.underestimatedCount)
    }

}

extension Sequence where Element: Comparable {

    /**
     Returns a sequence consisting of copy of this sequence without any elements from the given sequence, respecting encounter multiplicity.

     - Precondition: Both this sequence and `sortedFilterElements` are sorted with respect to `<`.

     - Parameter sortedFilterElements: A sequence of elements to exclude from the returned copy of this sequence.  If there are more copies of a given element value in `self` than in `sortedFilterElements`, then a count of the difference will remain in the return value.

     - Returns: A sequence consisting of the elements of this sequence, with each element value's count reduced (possibly to zero) by the occurance count in `sortedFilterElements`.
     */
    public func subtract<T: Sequence>(sortedFilterElements: T) -> SetSubtractionSequence<Self, T> where T.Element == Element {
        return SetSubtractionSequence(self, filter: sortedFilterElements)
    }

}

SetSubtraction.swift

// SetSubtraction.swift by Daryle Walker

#if swift(>=5)
// MARK: Set-Subtraction Implementation Iterator

/// An iterator that vends elements from a sorted wrapped iterator or errors, subtracting the elements from in another wrapped sorted filter iterator.
struct FullSetSubtractionImplementationIterator<Base: IteratorProtocol, Filter: IteratorProtocol> where Base.Element == Filter.Element {

    /// The iterator where the vended elements come from.
    var base: Base
    /// The iterator where matches to be filtered come from.
    var filters: Filter
    /// The closure for determining the relative order of elements.
    let areInIncreasingOrder: (Base.Element, Base.Element) throws -> Bool

    /// The error that ended iteration, if that happened.  `nil` if no throw has occurred / did occur.
    private(set) var endingError: Error?
    /// The last element from `base`, to help confirm its underlying sequence is sorted.
    var lastBase: Base.Element?
    /// The last element from `filters`, to help confirm its underlying sequence is sorted.
    var lastFilter: Filter.Element?

    /// Creates an iterator vending elements of a given base iterator minus the elements that are also in another iterator.
    init(_ base: Base, filter: Filter, by areInIncreasingOrder: @escaping (Base.Element, Base.Element) throws -> Bool) {
        self.base = base
        filters = filter
        self.areInIncreasingOrder = areInIncreasingOrder
        endingError = nil
        lastBase = nil
        lastFilter = nil
    }

}

extension FullSetSubtractionImplementationIterator: IteratorProtocol {

    mutating func next() -> Result<Base.Element, Error>? {
        guard endingError == nil else { return nil }

        // Can't return wrapped element if there's no more.
        lastBase = lastBase ?? base.next()
        guard let latestBase = lastBase else { return nil }

        /*
         Compare latest from base and filtered:

         - filtered is NIL: return base and increment it
         - base < filtered: return base and increment it
         - base == filtered: increment both then recursive call
         - base > filtered: increment filter then recursive call
         */
        let returnBase: Bool
        do {
            let incrementBase: Bool
            lastFilter = lastFilter ?? filters.next()
            if let latestFilter = lastFilter, try !areInIncreasingOrder(latestBase, latestFilter) {
                returnBase = false
                incrementBase = try !areInIncreasingOrder(latestFilter, latestBase)

                // Increment filter
                lastFilter = filters.next()
                if let nextFilter = lastFilter, try areInIncreasingOrder(nextFilter, latestFilter) {
                    preconditionFailure("Filtering sequence isn't actually sorted")
                }
            } else {
                returnBase = true
                incrementBase = true
            }
            if incrementBase {
                lastBase = base.next()
                if let nextBase = lastBase, try areInIncreasingOrder(nextBase, latestBase) {
                    preconditionFailure("To-be-filtered sequence isn't actually sorted")
                }
            }
        } catch {
            endingError = error
            return .failure(error)
        }
        return returnBase ? .success(latestBase) : next()
    }

}


// MARK: - Set-Subtraction, Eager Versions

extension Sequence {

    /**
     Returns a copy of this sequence without any elements from the given sequence, respecting encounter order and multiplicity, using the given throwing predicate to compare elements, as a collection of the given type.

     The predicate must be a *strict weak ordering* over the elements.  That is, for any elements `a`, `b`, and `c`, the following conditions must hold:

     - `areInIncreasingOrder(a, a)` is always `false`. (Irreflexivity)
     - If `areInIncreasingOrder(a, b)` and `areInIncreasingOrder(b, c)` are both `true`, then `areInIncreasingOrder(a, c)` is also `true`.  (Transitive comparability)
     - Two elements are *incomparable* if neither is ordered before the other according to the predicate.  If `a` and `b` are incomparable, and `b` and `c` are incomparable, then `a` and `c` are also incomparable.  (Transitive incomparability)

     - Precondition: Both `self` and `sortedFilterElements` are sorted with respect to `areInIncreasingOrder`.

     - Parameter sortedFilterElements: A sequence of elements to exclude from the returned copy of this sequence.  If there are more copies of a given element value in `self` than in `sortedFilterElements`, then a count of the difference will remain in the return value.
     - Parameter storingAs: A metatype specifier for the type of the collection to be returned.
     - Parameter areInIncreasingOrder: A predicate that returns `true` if its first argument should be ordered before its second argument; otherwise, `false`.

     - Returns: A (sorted) collection consisting of the elements of this sequence, with each element value's count reduced (possibly to zero) by its occurance count in `sortedFilterElements`.

     - Complexity: O(_n_ + _k_), where *n* is the element count of this sequence and *k* is the element count of `sortedFilterElements`.
     */
    public func presortedSubtract<T: Sequence, U: RangeReplaceableCollection>(sortedFilterElements: T, storingAs: U.Type, by areInIncreasingOrder: (Element, Element) throws -> Bool) throws -> U where T.Element == Element, U.Element == Element {
        return try withoutActuallyEscaping(areInIncreasingOrder) { predicate in
            return try U(IteratorSequence(FullSetSubtractionImplementationIterator(makeIterator(), filter: sortedFilterElements.makeIterator(), by: predicate)).lazy.map { try $0.get() })
        }
    }

    /**
     Returns a copy of this sequence without any elements from the given sequence, respecting encounter order and multiplicity, using the given throwing predicate to compare elements, as an array of the given type.

     The predicate must be a *strict weak ordering* over the elements.  That is, for any elements `a`, `b`, and `c`, the following conditions must hold:

     - `areInIncreasingOrder(a, a)` is always `false`. (Irreflexivity)
     - If `areInIncreasingOrder(a, b)` and `areInIncreasingOrder(b, c)` are both `true`, then `areInIncreasingOrder(a, c)` is also `true`.  (Transitive comparability)
     - Two elements are *incomparable* if neither is ordered before the other according to the predicate.  If `a` and `b` are incomparable, and `b` and `c` are incomparable, then `a` and `c` are also incomparable.  (Transitive incomparability)

     - Precondition: Both `self` and `sortedFilterElements` are sorted with respect to `areInIncreasingOrder`.

     - Parameter sortedFilterElements: A sequence of elements to exclude from the returned copy of this sequence.  If there are more copies of a given element value in `self` than in `sortedFilterElements`, then a count of the difference will remain in the return value.
     - Parameter areInIncreasingOrder: A predicate that returns `true` if its first argument should be ordered before its second argument; otherwise, `false`.

     - Returns: A (sorted) array consisting of the elements of this sequence, with each element value's count reduced (possibly to zero) by its occurance count in `sortedFilterElements`.

     - Complexity: O(_n_ + _k_), where *n* is the element count of this sequence and *k* is the element count of `sortedFilterElements`.
     */
    public func presortedSubtract<T: Sequence>(sortedFilterElements: T, by areInIncreasingOrder: (Element, Element) throws -> Bool) throws -> [Element] where T.Element == Element {
        return try presortedSubtract(sortedFilterElements: sortedFilterElements, storingAs: Array.self, by: areInIncreasingOrder)
    }

    /**
     Returns a copy of this sequence without any elements from the given sequence, respecting encounter order and multiplicity, using the given non-throwing predicate to compare elements, as a collection of the given type.

     The predicate must be a *strict weak ordering* over the elements.  That is, for any elements `a`, `b`, and `c`, the following conditions must hold:

     - `areInIncreasingOrder(a, a)` is always `false`. (Irreflexivity)
     - If `areInIncreasingOrder(a, b)` and `areInIncreasingOrder(b, c)` are both `true`, then `areInIncreasingOrder(a, c)` is also `true`.  (Transitive comparability)
     - Two elements are *incomparable* if neither is ordered before the other according to the predicate.  If `a` and `b` are incomparable, and `b` and `c` are incomparable, then `a` and `c` are also incomparable.  (Transitive incomparability)

     - Precondition: Both `self` and `sortedFilterElements` are sorted with respect to `areInIncreasingOrder`.

     - Parameter sortedFilterElements: A sequence of elements to exclude from the returned copy of this sequence.  If there are more copies of a given element value in `self` than in `sortedFilterElements`, then a count of the difference will remain in the return value.
     - Parameter storingAs: A metatype specifier for the type of the collection to be returned.
     - Parameter areInIncreasingOrder: A predicate that returns `true` if its first argument should be ordered before its second argument; otherwise, `false`.

     - Returns: A (sorted) collection consisting of the elements of this sequence, with each element value's count reduced (possibly to zero) by its occurance count in `sortedFilterElements`.

     - Complexity: O(_n_ + _k_), where *n* is the element count of this sequence and *k* is the element count of `sortedFilterElements`.
     */
    public func presortedSubtract<T: Sequence, U: RangeReplaceableCollection>(sortedFilterElements: T, storingAs: U.Type, by areInIncreasingOrder: (Element, Element) -> Bool) -> U where T.Element == Element, U.Element == Element {
        return withoutActuallyEscaping(areInIncreasingOrder) { predicate in
            return U(IteratorSequence(FullSetSubtractionImplementationIterator(makeIterator(), filter: sortedFilterElements.makeIterator(), by: predicate)).lazy.map { try! $0.get() })
        }
    }

    /**
     Returns a copy of this sequence without any elements from the given sequence, respecting encounter order and multiplicity, using the given non-throwing predicate to compare elements, as an array of the given type.

     The predicate must be a *strict weak ordering* over the elements.  That is, for any elements `a`, `b`, and `c`, the following conditions must hold:

     - `areInIncreasingOrder(a, a)` is always `false`. (Irreflexivity)
     - If `areInIncreasingOrder(a, b)` and `areInIncreasingOrder(b, c)` are both `true`, then `areInIncreasingOrder(a, c)` is also `true`.  (Transitive comparability)
     - Two elements are *incomparable* if neither is ordered before the other according to the predicate.  If `a` and `b` are incomparable, and `b` and `c` are incomparable, then `a` and `c` are also incomparable.  (Transitive incomparability)

     - Precondition: Both `self` and `sortedFilterElements` are sorted with respect to `areInIncreasingOrder`.

     - Parameter sortedFilterElements: A sequence of elements to exclude from the returned copy of this sequence.  If there are more copies of a given element value in `self` than in `sortedFilterElements`, then a count of the difference will remain in the return value.
     - Parameter areInIncreasingOrder: A predicate that returns `true` if its first argument should be ordered before its second argument; otherwise, `false`.

     - Returns: A (sorted) array consisting of the elements of this sequence, with each element value's count reduced (possibly to zero) by its occurance count in `sortedFilterElements`.

     - Complexity: O(_n_ + _k_), where *n* is the element count of this sequence and *k* is the element count of `sortedFilterElements`.
     */
    public func presortedSubtract<T: Sequence>(sortedFilterElements: T, by areInIncreasingOrder: (Element, Element) -> Bool) -> [Element] where T.Element == Element {
        return presortedSubtract(sortedFilterElements: sortedFilterElements, storingAs: Array.self, by: areInIncreasingOrder)
    }

}

extension Sequence where Element: Comparable {

    /**
     Returns a copy of this sequence without any elements from the given sequence, respecting encounter order and multiplicity, as a collection of the given type.

     - Precondition: Both `self` and `sortedFilterElements` are sorted with respect to `<`.

     - Parameter sortedFilterElements: A sequence of elements to exclude from the returned copy of this sequence.  If there are more copies of a given element value in `self` than in `sortedFilterElements`, then a count of the difference will remain in the return value.
     - Parameter storingAs: A metatype specifier for the type of the collection to be returned.

     - Returns: A (sorted) collection consisting of the elements of this sequence, with each element value's count reduced (possibly to zero) by its occurance count in `sortedFilterElements`.

     - Complexity: O(_n_ + _k_), where *n* is the element count of this sequence and *k* is the element count of `sortedFilterElements`.
     */
    public func presortedSubtract<T: Sequence, U: RangeReplaceableCollection>(sortedFilterElements: T, storingAs: U.Type) -> U where T.Element == Element, U.Element == Element {
        return presortedSubtract(sortedFilterElements: sortedFilterElements, storingAs: U.self, by: <)
    }

    /**
     Returns a copy of this sequence without any elements from the given sequence, respecting encounter order and multiplicity, as an array of the given type.

     - Precondition: Both `self` and `sortedFilterElements` are sorted with respect to `<`.

     - Parameter sortedFilterElements: A sequence of elements to exclude from the returned copy of this sequence.  If there are more copies of a given element value in `self` than in `sortedFilterElements`, then a count of the difference will remain in the return value.

     - Returns: A (sorted) array consisting of the elements of this sequence, with each element value's count reduced (possibly to zero) by its occurance count in `sortedFilterElements`.

     - Complexity: O(_n_ + _k_), where *n* is the element count of this sequence and *k* is the element count of `sortedFilterElements`.
     */
    public func presortedSubtract<T: Sequence>(sortedFilterElements: T) -> [Element] where T.Element == Element {
        return presortedSubtract(sortedFilterElements: sortedFilterElements, by: <)
    }

}


// MARK: Set-Subtraction, Specialization for Range-Replaceable Collections

extension RangeReplaceableCollection {

    /**
     Returns a copy of this collection without any elements from the given sequence, respecting encounter order and multiplicity, using the given throwing predicate to compare elements.

     The predicate must be a *strict weak ordering* over the elements.  That is, for any elements `a`, `b`, and `c`, the following conditions must hold:

     - `areInIncreasingOrder(a, a)` is always `false`. (Irreflexivity)
     - If `areInIncreasingOrder(a, b)` and `areInIncreasingOrder(b, c)` are both `true`, then `areInIncreasingOrder(a, c)` is also `true`.  (Transitive comparability)
     - Two elements are *incomparable* if neither is ordered before the other according to the predicate.  If `a` and `b` are incomparable, and `b` and `c` are incomparable, then `a` and `c` are also incomparable.  (Transitive incomparability)

     - Precondition: Both `self` and `sortedFilterElements` are sorted with respect to `areInIncreasingOrder`.

     - Parameter sortedFilterElements: A sequence of elements to exclude from the returned copy of this sequence.  If there are more copies of a given element value in `self` than in `sortedFilterElements`, then a count of the difference will remain in the return value.
     - Parameter areInIncreasingOrder: A predicate that returns `true` if its first argument should be ordered before its second argument; otherwise, `false`.

     - Returns: A (still-sorted) copy of the elements of this collection, with each element value's count reduced (possibly to zero) by its occurance count in `sortedFilterElements`.

     - Complexity: O(_n_ + _k_), where *n* is the element count of this collection and *k* is the element count of `sortedFilterElements`.
     */
    public func presortedSubtract<T: Sequence>(sortedFilterElements: T, by areInIncreasingOrder: (Element, Element) throws -> Bool) throws -> Self where T.Element == Element {
        return try presortedSubtract(sortedFilterElements: sortedFilterElements, storingAs: Self.self, by: areInIncreasingOrder)
    }

    /**
     Returns a copy of this collection without any elements from the given sequence, respecting encounter order and multiplicity, using the given non-throwing predicate to compare elements.

     The predicate must be a *strict weak ordering* over the elements.  That is, for any elements `a`, `b`, and `c`, the following conditions must hold:

     - `areInIncreasingOrder(a, a)` is always `false`. (Irreflexivity)
     - If `areInIncreasingOrder(a, b)` and `areInIncreasingOrder(b, c)` are both `true`, then `areInIncreasingOrder(a, c)` is also `true`.  (Transitive comparability)
     - Two elements are *incomparable* if neither is ordered before the other according to the predicate.  If `a` and `b` are incomparable, and `b` and `c` are incomparable, then `a` and `c` are also incomparable.  (Transitive incomparability)

     - Precondition: Both `self` and `sortedFilterElements` are sorted with respect to `areInIncreasingOrder`.

     - Parameter sortedFilterElements: A sequence of elements to exclude from the returned copy of this sequence.  If there are more copies of a given element value in `self` than in `sortedFilterElements`, then a count of the difference will remain in the return value.
     - Parameter areInIncreasingOrder: A predicate that returns `true` if its first argument should be ordered before its second argument; otherwise, `false`.

     - Returns: A (still-sorted) copy of the elements of this collection, with each element value's count reduced (possibly to zero) by its occurance count in `sortedFilterElements`.

     - Complexity: O(_n_ + _k_), where *n* is the element count of this collection and *k* is the element count of `sortedFilterElements`.
     */
    public func presortedSubtract<T: Sequence>(sortedFilterElements: T, by areInIncreasingOrder: (Element, Element) -> Bool) -> Self where T.Element == Element {
        return presortedSubtract(sortedFilterElements: sortedFilterElements, storingAs: Self.self, by: areInIncreasingOrder)
    }

}

extension RangeReplaceableCollection where Element: Comparable {

    /**
     Returns a copy of this collection without any elements from the given sequence, respecting encounter order and multiplicity.

     - Precondition: Both `self` and `sortedFilterElements` are sorted with respect to `<`.

     - Parameter sortedFilterElements: A sequence of elements to exclude from the returned copy of this sequence.  If there are more copies of a given element value in `self` than in `sortedFilterElements`, then a count of the difference will remain in the return value.

     - Returns: A (still-sorted) copy of the elements of this collection, with each element value's count reduced (possibly to zero) by its occurance count in `sortedFilterElements`.

     - Complexity: O(_n_ + _k_), where *n* is the element count of this collection and *k* is the element count of `sortedFilterElements`.
     */
    public func presortedSubtract<T: Sequence>(sortedFilterElements: T) -> Self where T.Element == Element {
        return presortedSubtract(sortedFilterElements: sortedFilterElements, by: <)
    }

}


// MARK: - Set-Subtraction, Lazy Version

/// A sequence that lazily vends elements from a sorted wrapped sequence, subtracting the elements from in another wrapped sorted filter sequence.
public struct LazyPresortedSubtractionSequence<Base: Sequence, Filter: Sequence> where Base.Element == Filter.Element {

    /// The sequence where the vended elements come from.
    var base: Base
    /// The sequence where matches to be filtered come from.
    var filters: Filter
    /// The closure for determining the relative order of elements.
    let areInIncreasingOrder: (Base.Element, Base.Element) -> Bool

    /// Creates a sequence vending elements of a given base sequence minus the elements that are also in another sequence.
    init(_ base: Base, filter: Filter, by areInIncreasingOrder: @escaping (Base.Element, Base.Element) -> Bool) {
        self.base = base
        filters = filter
        self.areInIncreasingOrder = areInIncreasingOrder
    }

}

extension LazyPresortedSubtractionSequence {

    public struct Iterator {
        /// The actual wrapping iterator doing the work.
        var iterator: FullSetSubtractionImplementationIterator<Base.Iterator, Filter.Iterator>

        /// Creates an iterator vending elements of a given base iterator minus the elements that are also in another iterator.
        init(_ base: Base.Iterator, filter: Filter.Iterator, by areInIncreasingOrder: @escaping (Base.Element, Base.Element) -> Bool) {
            iterator = FullSetSubtractionImplementationIterator(base, filter: filter, by: areInIncreasingOrder)
        }
    }

}

extension LazyPresortedSubtractionSequence.Iterator: IteratorProtocol {

    mutating public func next() -> Base.Element? {
        return try! iterator.next()?.get()
    }

}

extension LazyPresortedSubtractionSequence: Sequence {

    public __consuming func makeIterator() -> Iterator {
        return Iterator(base.makeIterator(), filter: filters.makeIterator(), by: areInIncreasingOrder)
    }

    public var underestimatedCount: Int {
        return Swift.max(0, base.underestimatedCount - filters.underestimatedCount)
    }

}

extension LazyPresortedSubtractionSequence: LazySequenceProtocol {}

extension LazyPresortedSubtractionSequence: Collection where Base: Collection, Filter: Collection {

    public struct Index: Comparable {
        /// The targeted element in the base collection.
        public let index: Base.Index
        /// The next unused filter element when the target element is chosen.  Meant to be a cache to calculate the next index, not significant for direct use.
        let filterIndex: Filter.Index

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

    /// Find the first element of `base`'s suffix to not be filtered out by elements in `filter`'s suffix, without using loops.
    private func nextIndex(baseStart: Base.Index, filterStart: Filter.Index) -> Index {
        guard baseStart < base.endIndex, filterStart < filters.endIndex, !areInIncreasingOrder(base[baseStart], filters[filterStart]) else {
            return Index(index: baseStart, filterIndex: filterStart)
        }

        let incrementBase = !areInIncreasingOrder(filters[filterStart], base[baseStart])
        let nextBaseIndex = base.index(baseStart, offsetBy: incrementBase ? +1 : 0)
        return nextIndex(baseStart: nextBaseIndex, filterStart: filters.index(after: filterStart))
    }

    /**
     The position of the first element in a nonempty collection.

     If the collection is empty, `startIndex` is equal to `endIndex`.

     - Warning: Since the collection filters elements and can't cache the result (since the properties involved are conditional), the computation is linear instead of constant.

     - Complexity: O(_n_ + _k_), where *n* is the element count of the wrapped collection and *k* is the element count of the filter collection.
     */
    public var startIndex: Index {
        return nextIndex(baseStart: base.startIndex, filterStart: filters.startIndex)
    }
    public var endIndex: Index {
        // The value for `filterIndex` may be wrong for some collections, but it's not used in comparisons.
        return Index(index: base.endIndex, filterIndex: filters.endIndex)
    }

    public subscript(position: Index) -> Base.Element {
        return base[position.index]
    }
    public func index(after i: Index) -> Index {
        return nextIndex(baseStart: base.index(after: i.index), filterStart: i.filterIndex)
    }

}

extension LazyPresortedSubtractionSequence.Index: Hashable where Base: Collection, Filter: Collection, Base.Index: Hashable {

    public func hash(into hasher: inout Hasher) {
        hasher.combine(index)
    }

}

/// A collection that vends elements from a sorted wrapped collection, filtering out the elements from another wrapped sorted collection.
public typealias LazyPresortedSubtractionCollection<Base: Collection, Filter: Collection> = LazyPresortedSubtractionSequence<Base, Filter> where Base.Element == Filter.Element

extension LazyPresortedSubtractionCollection: LazyCollectionProtocol {}

// Theoretically, if synchronizing the main and filtered collections can be done backwards, then BidirectionalCollection support is possible.
// (You'd probably need to write a custom endIndex for that specialization.)


extension LazySequenceProtocol {

    /**
     Lazily returns a copy of this sequence without any elements from the given sequence, respecting encounter order and multiplicity, using the given predicate to compare elements.

     The predicate must be a *strict weak ordering* over the elements.  That is, for any elements `a`, `b`, and `c`, the following conditions must hold:

     - `areInIncreasingOrder(a, a)` is always `false`. (Irreflexivity)
     - If `areInIncreasingOrder(a, b)` and `areInIncreasingOrder(b, c)` are both `true`, then `areInIncreasingOrder(a, c)` is also `true`.  (Transitive comparability)
     - Two elements are *incomparable* if neither is ordered before the other according to the predicate.  If `a` and `b` are incomparable, and `b` and `c` are incomparable, then `a` and `c` are also incomparable.  (Transitive incomparability)

     - Precondition: Both `self` and `sortedFilterElements` are sorted with respect to `areInIncreasingOrder`.

     - Parameter sortedFilterElements: A sequence of elements to exclude from the returned copy of this sequence.  If there are more copies of a given element value in `self` than in `sortedFilterElements`, then a count of the difference will remain in the return value.
     - Parameter areInIncreasingOrder: A predicate that returns `true` if its first argument should be ordered before its second argument; otherwise, `false`.

     - Returns: A (still-sorted) copy of the elements of this sequence, with each element value's count reduced (possibly to zero) by its occurance count in `sortedFilterElements`, lazily generated.
     */
    public func presortedSubtract<T: Sequence>(sortedFilterElements: T, by areInIncreasingOrder: @escaping (Element, Element) -> Bool) -> LazyPresortedSubtractionSequence<Elements, T> where T.Element == Element {
        return LazyPresortedSubtractionSequence(elements, filter: sortedFilterElements, by: areInIncreasingOrder)
    }

}

extension LazySequenceProtocol where Element: Comparable {

    /**
     Lazily returns a copy of this sequence without any elements from the given sequence, respecting encounter order and multiplicity.

     - Precondition: Both `self` and `sortedFilterElements` are sorted with respect to `<`.

     - Parameter sortedFilterElements: A sequence of elements to exclude from the returned copy of this sequence.  If there are more copies of a given element value in `self` than in `sortedFilterElements`, then a count of the difference will remain in the return value.

     - Returns: A (still-sorted) copy of the elements of this sequence, with each element value's count reduced (possibly to zero) by its occurance count in `sortedFilterElements`, lazily generated.
     */
    public func presortedSubtract<T: Sequence>(sortedFilterElements: T) -> LazyPresortedSubtractionSequence<Elements, T> where T.Element == Element {
        return presortedSubtract(sortedFilterElements: sortedFilterElements, by: <)
    }

}
#endif