Merging, Combining, and Testing of Sorted Sequences in Swift, inspired by the C++ Standard Library. See <https://forums.swift.org/t/sorted-sequence-operations-merge-sort-set-operations-inclusion-testing/31145> for more information.

MergedSortedSequence.swift

// MARK: Per-Element Sharing in Merged Sorted Sequences

/// Primary source categories when merging two sets together.
public enum MergedSetElementSource<Element> {

    /// The given element is only in the first set.
    case exclusivelyFirst(Element)
    /// The element is in both sets.  Both versions are given.
    case shared(Element, Element)
    /// The given element is only in the second set.
    case exclusivelySecond(Element)

}

// MARK: - Eager Merger of Sorted Sequences

extension Sequence {

    /// Assuming this sequence is sorted according to the given predicate
    /// comparing elements, and the given sequence is sorted the same way,
    /// process the virtual set-merger of the two sequences with the other given
    /// closure.
    ///
    /// `areInIncreasingOrder` must be a strict weak ordering over the elements.
    ///
    /// Relative to elements from the same source sequence, the resulting
    /// virtual sequence sorts stably.
    ///
    /// - Precondition: Both this sequence and `other` are finite, and they are
    ///   both sorted according to `areInIncreaasingOrder`.
    ///
    /// - Parameter other: A sequence to blend with this one.
    /// - Parameter body: A closure processing each element of both sequences.
    ///   Each call indicates if an element value is in only one sequence or in
    ///   both.  If a value is duplicated in a sequence, a call will be made for
    ///   each copy.
    /// - Parameter areInIncreasingOrder: A predicate that returns `true` if its
    ///   first argument should be ordered before its second argument;
    ///   otherwise, `false`.
    ///
    /// - Complexity: O(*n* + *m*), where *n* and *m* are the lengths of this
    ///   sequence and `other`.
    public func whileMergingSorted<S: Sequence>(with other: S, do body: (MergedSetElementSource<Element>) throws -> Void, by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows where S.Element == Element {
        var iterator = makeIterator(), otherIterator = other.makeIterator()
        var cache = iterator.next(), otherCache = otherIterator.next()
        while let current = cache, let otherCurrent = otherCache {
            if try areInIncreasingOrder(current, otherCurrent) {
                try body(.exclusivelyFirst(current))
                cache = iterator.next()
            } else if try areInIncreasingOrder(otherCurrent, current) {
                try body(.exclusivelySecond(otherCurrent))
                otherCache = otherIterator.next()
            } else {
                try body(.shared(current, otherCurrent))
                cache = iterator.next()
                otherCache = otherIterator.next()
            }
        }
        if let firstSuffix = cache {
            assert(otherCache == nil)

            try body(.exclusivelyFirst(firstSuffix))
            while let suffix = iterator.next() {
                try body(.exclusivelyFirst(suffix))
            }
        } else if let firstOtherSuffix = otherCache {
            try body(.exclusivelySecond(firstOtherSuffix))
            while let suffix = otherIterator.next() {
                try body(.exclusivelySecond(suffix))
            }
        }
    }

}

// MARK: - Merger of Sorted Sequences, Iterator

/// An iterator blending two iterators' sorted sequences together.
public struct MergingSortedIterator<Base1: IteratorProtocol, Base2: IteratorProtocol> where Base1.Element == Base2.Element {

    /// The first source iterator.
    var iterator1: Base1
    /// The second source iterator.
    var iterator2: Base2

    /// The ordering predicate.
    let areInIncreasingOrder: (Base1.Element, Base2.Element) -> Bool

    /// The last element read from `iterator1`.
    var cache1: Base1.Element?
    /// The last element read from `iterator2`.
    var cache2: Base2.Element?

    /// Creates a blend of the sorted source iterators into an also-sorted
    /// iterator.
    @usableFromInline
    init(merging first: Base1, and second: Base2, by areInIncreasingOrder: @escaping (Base1.Element, Base2.Element) -> Bool) {
        iterator1 = first
        iterator2 = second
        self.areInIncreasingOrder = areInIncreasingOrder
    }

}

extension MergingSortedIterator: IteratorProtocol {

    public mutating func next() -> MergedSetElementSource<Base1.Element>? {
        if cache1 == nil {
            cache1 = iterator1.next()
        }
        if cache2 == nil {
            cache2 = iterator2.next()
        }
        switch (cache1, cache2) {
        case (nil, nil):
            return nil
        case (let first?, nil):
            defer { cache1 = nil }

            return .exclusivelyFirst(first)
        case (nil, let second?):
            defer { cache2 = nil }

            return .exclusivelySecond(second)
        case let (first?, second?):
            if areInIncreasingOrder(first, second) {
                defer { cache1 = nil }

                return .exclusivelyFirst(first)
            } else if areInIncreasingOrder(second, first) {
                defer { cache2 = nil }

                return .exclusivelySecond(second)
            } else {
                defer {
                    cache1 = nil
                    cache2 = nil
                }

                return .shared(first, second)
            }
        }
    }

}

// MARK: - Lazy Merger of Sorted Sequences

/// A sequence blending two sorted sequences together.
///
/// An instance is finite only when both source sequences are.  It is multi-pass
/// only when both source sequences are.  It is also a collection only when both
/// sources are also collections.  (An instance can be at most a forward-only,
/// non-mutable collection, even when the sources' common refinement is past
/// `Collection`.)
public struct MergedSortedSequence<Base1: Sequence, Base2: Sequence> where Base1.Element == Base2.Element {

    /// The first source sequence.
    @usableFromInline
    let sequence1: Base1
    /// The second source sequence.
    @usableFromInline
    let sequence2: Base2

    /// The ordering predicate.
    @usableFromInline
    let areInIncreasingOrder: (Base1.Element, Base2.Element) -> Bool

    /// Creates a sorted sequence that is a blend of the two given sequences
    /// that are both sorted according to the given predicate.
    ///
    /// `areInIncreasingOrder` must be a strict weak ordering over the elements.
    ///
    /// Relative to elements from the same source sequence, this sequence sorts
    /// stably.
    ///
    /// - Precondition: Both `first` and `second` are sorted along
    ///   `areInIncreasingOrder`.
    ///
    /// - Parameter first: The first source sequence.
    /// - Parameter second: The second source sequence.
    /// - Parameter areInIncreasingOrder: A predicate that returns `true` if its
    ///   first argument should be ordered before its second argument;
    ///   otherwise, `false`.
    ///
    /// - Postcondition: Each turn, this sequence will vend the lowest-ordered
    ///   available element between the two source sequences.  A tag will
    ///   accompany the element value indicating which source sequence it came
    ///   from.  When the two currently available elements are equivalent, then
    ///   both are extracted and returned with a tag indicating a tie.
    @inlinable
    public init(merging first: Base1, and second: Base2, by areInIncreasingOrder: @escaping (Base1.Element, Base2.Element) -> Bool) {
        sequence1 = first
        sequence2 = second
        self.areInIncreasingOrder = areInIncreasingOrder
    }

}

extension MergedSortedSequence where Base1.Element: Comparable {

    /// Creates a sorted sequence that is a blend of the two given sorted
    /// sequences.
    ///
    /// Relative to elements from the same source sequence, this sequence sorts
    /// stably.
    ///
    /// - Precondition: Both `first` and `second` are sorted.
    ///
    /// - Parameter first: The first source sequence.
    /// - Parameter second: The second source sequence.
    ///
    /// - Postcondition: Each turn, this sequence will vend the minimum
    ///   available element between the two source sequences.  A tag will
    ///   accompany the element value indicating which source sequence it came
    ///   from.  When the two currently available elements are equal, then both
    ///   both are extracted and returned with a tag indicating a tie.
    @inlinable
    public init(merging first: Base1, and second: Base2) {
        self.init(merging: first, and: second, by: <)
    }

}

extension MergedSortedSequence: Sequence {

    public typealias Iterator = MergingSortedIterator<Base1.Iterator, Base2.Iterator>
    public typealias Element = Iterator.Element

    @inlinable
    public func makeIterator() -> Iterator {
        return MergingSortedIterator(merging: sequence1.makeIterator(), and: sequence2.makeIterator(), by: areInIncreasingOrder)
    }

    @inlinable
    public var underestimatedCount: Int
    { Swift.max(sequence1.underestimatedCount, sequence2.underestimatedCount) }

}

extension MergedSortedSequence: LazySequenceProtocol {}

// MARK: - Support for Merged Collections

/// An index type for `MergedSortedCollection`.
public struct MergedSortedIndex<Base1: Comparable, Base2: Comparable> {

    /// The index into the first collection.
    let first: Base1
    /// The index into the second collection.
    let second: Base2
    /// Whether to dereference `first`.
    let dereferenceFirst: Bool
    /// Whether to dereference `second`.
    let dereferenceSecond: Bool

    /// Creates an index from the two given indices and whether
    /// to use either or both for dereferencing.
    @usableFromInline
    init(first: Base1, second: Base2, dereferenceFirst: Bool, dereferenceSecond: Bool) {
        self.first = first
        self.second = second
        self.dereferenceFirst = dereferenceFirst
        self.dereferenceSecond = dereferenceSecond
    }

}

extension MergedSortedIndex: Equatable {}

extension MergedSortedIndex: Hashable where Base1: Hashable, Base2: Hashable {}

extension MergedSortedIndex: Comparable {

    public static func < (lhs: Self, rhs: Self) -> Bool {
        let less1 = lhs.first < rhs.first || lhs.first == rhs.first && !lhs.dereferenceFirst && rhs.dereferenceFirst
        let equal1 = lhs.first == rhs.first && lhs.dereferenceFirst == rhs.dereferenceFirst
        let less2 = lhs.second < rhs.second || lhs.second == rhs.second && !lhs.dereferenceSecond && rhs.dereferenceSecond
        let equal2 = lhs.second == rhs.second && lhs.dereferenceSecond == rhs.dereferenceSecond
        return less1 && less2 || equal1 && less2 || less1 && equal2
    }

}

// MARK: Merged Collection of Sorted Collections

/// A collection blending two sorted collections together.
public typealias MergedSortedCollection<T: Collection, U: Collection> = MergedSortedSequence<T, U> where T.Element == U.Element

extension MergedSortedCollection: Collection {

    public typealias Index = MergedSortedIndex<Base1.Index, Base2.Index>

    public var startIndex: Index {
        if let first1 = sequence1.first, let first2 = sequence2.first {
            let willDereference1 = !areInIncreasingOrder(first2, first1)
            let willDereference2 = !areInIncreasingOrder(first1, first2)
            return Index(first: sequence1.startIndex, second: sequence2.startIndex, dereferenceFirst: willDereference1, dereferenceSecond: willDereference2)
        } else {
            return Index(first: sequence1.startIndex, second: sequence2.startIndex, dereferenceFirst: !sequence1.isEmpty, dereferenceSecond: !sequence2.isEmpty)
        }
    }
    @inlinable
    public var endIndex: Index {
        Index(first: sequence1.endIndex, second: sequence2.endIndex, dereferenceFirst: false, dereferenceSecond: false)
    }

    public subscript(position: Index) -> Element {
        switch (position.dereferenceFirst, position.dereferenceSecond) {
        case (false, false):
            assert(position.first == sequence1.endIndex)
            assert(position.second == sequence2.endIndex)
            preconditionFailure("Attempt to dereference endIndex")
        case (false, true):
            return .exclusivelySecond(sequence2[position.second])
        case (true, false):
            return .exclusivelyFirst(sequence1[position.first])
        case (true, true):
            return .shared(sequence1[position.first], sequence2[position.second])
        }
    }
    public func index(after i: Index) -> Index {
        let end1 = sequence1.endIndex, end2 = sequence2.endIndex
        switch (i.first < end1, i.second < end2) {
        case (false, false):
            assert(!i.dereferenceFirst)
            assert(!i.dereferenceSecond)
            preconditionFailure("Attempt to increment past endIndex")
        case (false, true):
            assert(!i.dereferenceFirst)
            assert(i.dereferenceSecond)

            let afterSecond = sequence2.index(after: i.second)
            return Index(first: i.first, second: afterSecond, dereferenceFirst: false, dereferenceSecond: afterSecond < end2)
        case (true, false):
            assert(i.dereferenceFirst)
            assert(!i.dereferenceSecond)

            let afterFirst = sequence1.index(after: i.first)
            return Index(first: afterFirst, second: i.second, dereferenceFirst: afterFirst < end1, dereferenceSecond: false)
        case (true, true):
            assert(i.dereferenceFirst || i.dereferenceSecond)

            let nextFirst = sequence1.index(i.first, offsetBy: i.dereferenceFirst ? +1 : 0)
            let nextSecond = sequence2.index(i.second, offsetBy: i.dereferenceSecond ? +1 : 0)
            let couldDereference1 = nextFirst < end1
            let couldDereference2 = nextSecond < end2
            if couldDereference1, couldDereference2 {
                let next1 = sequence1[nextFirst], next2 = sequence2[nextSecond]
                let willDereference1 = !areInIncreasingOrder(next2, next1)
                let willDereference2 = !areInIncreasingOrder(next1, next2)
                return Index(first: nextFirst, second: nextSecond, dereferenceFirst: willDereference1, dereferenceSecond: willDereference2)
            } else {
                return Index(first: nextFirst, second: nextSecond, dereferenceFirst: couldDereference1, dereferenceSecond: couldDereference2)
            }
        }
    }

}

extension MergedSortedCollection: LazyCollectionProtocol {}

// MARK: - Overlap Detection in Merged Sorted Sequences

/// Degree of overlap when merging two sets together.
public enum TwoSetOverlap: UInt, CaseIterable {

    /// Neither set has any elements.
    case bothEmpty
    /// Only the second set has any elements.
    case onlyFirstEmpty
    /// Both sets have elements, all shared.
    case total
    /// The first set has elements; the second has those and at least one more.
    case secondExtendsFirst
    /// Only the first set has any elements.
    case onlySecondEmpty
    /// Both sets have elements, but none in common.
    case disjoint
    /// The second set has elements; the first has those and at least one more.
    case firstExtendsSecond
    /// Both sets have elements, but only some in common.
    case partial

    /// Whether there is at least one element exclusive to the second set.
    @inlinable
    public var hasExclusivesToSecond: Bool { rawValue & 0x01 != 0 }
    /// Whether there is at least one element that is in both sets.
    @inlinable
    public var hasSomeOverlap: Bool { rawValue & 0x02 != 0 }
    /// Whether there is at least one element exclusive to the first set.
    @inlinable
    public var hasExclusivesToFirst: Bool { rawValue & 0x04 != 0 }

    /// Creates an overlap pack representing the given combination of flags.
    @inlinable
    public init(hasExclusivesToFirst firstOnly: Bool, hasSomeOverlap overlap: Bool, hasExclusivesToSecond secondOnly: Bool) {
        self.init(rawValue: (firstOnly ? 0x04 : 0) | (overlap ? 0x02 : 0) | (secondOnly ? 0x01 : 0))!
    }

    /// Whether the sets equal, *i.e.* no exclusives.
    @inlinable
    public var areEqual: Bool { rawValue & 0x05 == 0 }
    /// Whether the first set has at least one element.
    @inlinable
    public var isFirstEmpty: Bool { rawValue & 0x06 == 0 }
    /// Whether the second set has at least one element.
    @inlinable
    public var isSecondEmpty: Bool { rawValue & 0x03 == 0 }

    /// Whether the first set has all the elements of the second.
    @inlinable
    public var firstIsSupersetOfSecond: Bool { !hasExclusivesToSecond }
    /// Whether the second set has all the elements of the first.
    @inlinable
    public var firstIsSubsetOfSecond: Bool { !hasExclusivesToFirst }

    /// Whether the first set has all the elements of the second, and then some.
    @inlinable
    public var firstIsStrictSupersetOfSecond: Bool { rawValue & 0x05 == 0x04 }
    /// Whether the second set has all the elements of the first, and then some.
    @inlinable
    public var firstIsStrictSubsetOfSecond: Bool { rawValue & 0x05 == 0x01 }

}

/// An error for the internals of `Sequence.whileMergingSortedConfirmFor(selfOnly: shared: otherOnly: mergingWith: by:)`.
fileprivate enum ConfirmationFail: Error {
    /// An element was found that was not supposed to be there.
    case failed
}

extension Sequence {

    /// Assuming this sequence is sorted according to the given predicate
    /// comparing elements, and the given sequence is sorted the same way,
    /// count how many elements are shared or not shared between sequences.
    ///
    /// `areInIncreasingOrder` must be a strict weak ordering over the elements.
    ///
    /// - Precondition: Both this sequence and `other` are finite, and they are
    ///   both sorted according to `areInIncreaasingOrder`.
    ///
    /// - Parameter other: A sequence to blend with this one.
    /// - Parameter areInIncreasingOrder: A predicate that returns `true` if its
    ///   first argument should be ordered before its second argument;
    ///   otherwise, `false`.
    /// - Returns: A tuple containing how many elements are exclusive to this
    ///   sequence, how many are shared, and how many are exclusive to `other`.
    ///
    /// - Complexity: O(*n* + *m*), where *n* and *m* are the lengths of this
    ///   sequence and `other`.
    public func sourceCountWhileMergingSorted<S: Sequence>(with other: S, by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> (selfOnly: Int, shared: Int, otherOnly: Int) where S.Element == Element {
        var (selfCount, sharedCount, otherCount) = (0, 0, 0)
        try whileMergingSorted(with: other, do: {
            switch $0 {
            case .exclusivelyFirst:
                selfCount += 1
            case .shared:
                sharedCount += 1
            case .exclusivelySecond:
                otherCount += 1
            }
        }, by: areInIncreasingOrder)
        return (selfOnly: selfCount, shared: sharedCount, otherOnly: otherCount)
    }

    /// Assuming this sequence is sorted according to the given predicate
    /// comparing elements, and the given sequence is sorted the same way,
    /// confirm if the distribution of the sources of elements matches the given
    /// desired outcome.
    ///
    /// `areInIncreasingOrder` must be a strict weak ordering over the elements.
    ///
    /// - Precondition: Both this sequence and `other` are finite, and they are
    ///   both sorted according to `areInIncreaasingOrder`.
    ///
    /// - Parameter selfOnly: Whether elements exclusive to this sequence were
    ///   present.  Use `true` to confirm at least one element was present, use
    ///   `false` to confirm their absence instead, or `nil` if you don't care.
    /// - Parameter shared: Whether elements shared between the sequences were
    ///   present.  Use `true` to confirm at least one element was present, use
    ///   `false` to confirm their absence, or `nil` if you don't care.
    /// - Parameter otherOnly: Whether elements exclusive to `other` were
    ///   present.  Use `true` to confirm at least one element was present, use
    ///   `false` to confirm their absence instead, or `nil` if you don't care.
    /// - Parameter other: A sequence to blend with this one.
    /// - Parameter areInIncreasingOrder: A predicate that returns `true` if its
    ///   first argument should be ordered before its second argument;
    ///   otherwise, `false`.
    /// - Returns: `true` if the desired outcome matches; otherwise, `false`.
    ///
    /// - Complexity: O(*n* + *m*) if at least one desired outcome was `true`,
    ///   O(1) if all outcomes were `nil`, and something in between otherwise;
    ///   where *n* and *m* are the lengths of this sequence and `other`.
    public func whileMergingSortedConfirmFor<S: Sequence>(selfOnly: Bool?, shared: Bool?, otherOnly: Bool?, mergingWith other: S, by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> Bool where S.Element == Element {
        guard selfOnly != nil || shared != nil || otherOnly != nil else {
            return true
        }

        var foundSelfOnly = false, foundShared = false, foundOtherOnly = false
        do {
            try whileMergingSorted(with: other, do: {
                switch ($0, selfOnly, shared, otherOnly) {
                case (.exclusivelyFirst, true, _, _):
                    foundSelfOnly = true
                case (.shared, _, true, _):
                    foundShared = true
                case (.exclusivelySecond, _, _, true):
                    foundOtherOnly = true
                case (.exclusivelyFirst, false, _, _), (.shared, _, false, _),
                     (.exclusivelySecond, _, _, false):
                    throw ConfirmationFail.failed
                default:
                    break
                }
            }, by: areInIncreasingOrder)
        } catch is ConfirmationFail {
            return false
        }

        if selfOnly == true && !foundSelfOnly
            || shared == true && !foundShared
            || otherOnly == true && !foundOtherOnly {
            return false
        }
        return true
    }

    /// Assuming this sequence is sorted according to the given predicate
    /// comparing elements, and the given sequence is sorted the same way,
    /// determine how the sequences would overlap.
    ///
    /// `areInIncreasingOrder` must be a strict weak ordering over the elements.
    ///
    /// - Precondition: Both this sequence and `other` are finite, and they are
    ///   both sorted according to `areInIncreaasingOrder`.
    ///
    /// - Parameter other: A sequence to blend with this one.
    /// - Parameter areInIncreasingOrder: A predicate that returns `true` if its
    ///   first argument should be ordered before its second argument;
    ///   otherwise, `false`.
    /// - Returns: A set of flags indicating the degree of overlap between the
    ///   sequences.  The first sequence referenced in the flags is this
    ///   sequence, and the second sequence referenced to is `other`.
    ///
    /// - Complexity: O(*n* + *m*), where *n* and *m* are the lengths of this
    ///   sequence and `other`.
    public func overlapIfMergedSorted<S: Sequence>(with other: S, by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> TwoSetOverlap where S.Element == Element {
        var haveExclusivesToFirst = false, haveExclusivesToSecond = false
        var haveSharedElements = false
        try whileMergingSorted(with: other, do: {
            switch $0 {
            case .exclusivelyFirst:
                haveExclusivesToFirst = true
            case .shared:
                haveSharedElements = true
            case .exclusivelySecond:
                haveExclusivesToSecond = true
            }
        }, by: areInIncreasingOrder)
        return TwoSetOverlap(hasExclusivesToFirst: haveExclusivesToFirst, hasSomeOverlap: haveSharedElements, hasExclusivesToSecond: haveExclusivesToSecond)
    }

}

extension Sequence where Element: Comparable {

    /// Assuming this sequence and the given sequence are both sorted, count how
    /// many elements are shared or not shared between sequences.
    ///
    /// - Precondition: Both this sequence and `other` are finite and sorted.
    ///
    /// - Parameter other: A sequence to blend with this one.
    /// - Returns: A tuple containing how many elements are exclusive to this
    ///   sequence, how many are shared, and how many are exclusive to `other`.
    ///
    /// - Complexity: O(*n* + *m*), where *n* and *m* are the lengths of this
    ///   sequence and `other`.
    @inlinable
    public func sourceCountWhileMergingSorted<S: Sequence>(with other: S) -> (selfOnly: Int, shared: Int, otherOnly: Int) where S.Element == Element {
        return sourceCountWhileMergingSorted(with: other, by: <)
    }

    /// Assuming this sequence and the given sequence are both sorted, confirm
    /// if the distribution of the sources of elements matches the given desired
    /// outcome.
    ///
    /// - Precondition: Both this sequence and `other` are finite and sorted.
    ///
    /// - Parameter selfOnly: Whether elements exclusive to this sequence were
    ///   present.  Use `true` to confirm at least one element was present, use
    ///   `false` to confirm their absence instead, or `nil` if you don't care.
    /// - Parameter shared: Whether elements shared between the sequences were
    ///   present.  Use `true` to confirm at least one element was present, use
    ///   `false` to confirm their absence, or `nil` if you don't care.
    /// - Parameter otherOnly: Whether elements exclusive to `other` were
    ///   present.  Use `true` to confirm at least one element was present, use
    ///   `false` to confirm their absence instead, or `nil` if you don't care.
    /// - Parameter other: A sequence to blend with this one.
    /// - Returns: `true` if the desired outcome matches; otherwise, `false`.
    ///
    /// - Complexity: O(*n* + *m*) if at least one desired outcome was `true`,
    ///   O(1) if all outcomes were `nil`, and something in between otherwise;
    ///   where *n* and *m* are the lengths of this sequence and `other`.
    @inlinable
    public func whileMergingSortedConfirmFor<S: Sequence>(selfOnly: Bool?, shared: Bool?, otherOnly: Bool?, mergingWith other: S) -> Bool where S.Element == Element {
        return whileMergingSortedConfirmFor(selfOnly: selfOnly, shared: shared, otherOnly: otherOnly, mergingWith: other, by: <)
    }

    /// Assuming this sequence and the given one are both sorted, determine how
    /// the sequences would overlap.
    ///
    /// - Precondition: Both this sequence and `other` are finite and sorted.
    ///
    /// - Parameter other: A sequence to blend with this one.
    /// - Returns: A set of flags indicating the degree of overlap between the
    ///   sequences.  The first sequence referenced in the flags is this
    ///   sequence, and the second sequence referenced to is `other`.
    ///
    /// - Complexity: O(*n* + *m*), where *n* and *m* are the lengths of this
    ///   sequence and `other`.
    @inlinable
    public func overlapIfMergedSorted<S: Sequence>(with other: S) -> TwoSetOverlap where S.Element == Element {
        return overlapIfMergedSorted(with: other, by: <)
    }

}

SetOperations.swift

// MARK: Ways to Combine 2 Sets

/// Operations to combine two sets.
public enum SetOperation: UInt, CaseIterable {

    /// Exclude all elements.
    case none
    /// Include elements that are only in the second set.
    case exclusivesFromSecond
    /// Include elements that are present in both sets.
    case intersection
    /// Include all elements from the second set.
    case anyFromSecond
    /// Include elements that are only in the first set.
    case exclusivesFromFirst
    /// Include all elements that are only in exactly one set.
    case symmetricDifference
    /// Include all elements from the first set.
    case anyFromFirst
    /// Include all elements.
    case union

    /// Whether elements that are only in the second set are included.
    @inlinable
    public var hasExclusivesFromSecond: Bool { rawValue & 0x01 != 0 }
    /// Whether elements shared in both sets are included.
    @inlinable
    public var hasNonExclusives: Bool { rawValue & 0x02 != 0 }
    /// Whether elements that are only in the first set are included.
    @inlinable
    public var hasExclusivesFromFirst: Bool { rawValue & 0x04 != 0 }

}

// MARK: - Eager Set Operations on Sorted Sequences

extension Sequence {

    /// Assuming this sequence is sorted according to the given predicate
    /// comparing elements, and the given sequence is sorted the same way,
    /// return a sorted collection consisting of the two sequences blended
    /// together as sets, keeping only the elements indicated by the given
    /// operation.
    ///
    /// `areInIncreasingOrder` must be a strict weak ordering over the elements.
    ///
    /// The sort is stable.
    ///
    /// - Precondition: Both this sequence and `other` are finite, and are both
    ///   sorted according to `areInIncreasingOrder`.
    ///
    /// - Parameter other: A sequence to blend with this one.
    /// - Parameter filter: The set operation (union, intersection, *etc.*) to
    ///   apply to the merger.
    /// - Parameter type: A meta-type specifier for the collection to return.
    /// - Parameter areInIncreasingOrder: A predicate that returns `true` if its
    ///   first argument should be ordered before its second argument;
    ///   otherwise, `false`.
    /// - Returns: A collection of the given type containing the elements of
    ///   this sequence and `other` in a way that maintains the sort determined
    ///   by `areInIncreasingOrder`.  For each value that exists in both sets,
    ///   only one copy is kept.  (Usually the one from this sequence is kept,
    ///   unless `filter == anyFromSecond`.)
    ///
    /// - Complexity: O(*n* + *m*), where *n* and *m* are the lengths of this
    ///   sequence and `other`.
    public func mergeSortedAsSets<S: Sequence, T: RangeReplaceableCollection>(with other: S, keeping filter: SetOperation, into type: T.Type, by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> T where S.Element == Element, T.Element == Element {
        var result = T()
        let breakTiesWithFirst = filter != .anyFromSecond
        result.reserveCapacity(Swift.max(underestimatedCount, other.underestimatedCount))
        try whileMergingSorted(with: other, do: {
            switch $0 {
            case .exclusivelyFirst(let first) where filter.hasExclusivesFromFirst:
                result.append(first)
            case let .shared(first, second) where filter.hasNonExclusives:
                result.append(breakTiesWithFirst ? first : second)
            case .exclusivelySecond(let second) where filter.hasExclusivesFromSecond:
                result.append(second)
            default:
                break
            }
        }, by: areInIncreasingOrder)
        return result
    }

    /// Assuming this sequence is sorted according to the given predicate
    /// comparing elements, and the given sequence is sorted the same way,
    /// return a sorted array consisting of the two sequences blended together
    /// as sets, keeping only the elements indicated by the given operation.
    ///
    /// `areInIncreasingOrder` must be a strict weak ordering over the elements.
    ///
    /// The sort is stable.
    ///
    /// - Precondition: Both this sequence and `other` are finite, and are both
    ///   sorted according to `areInIncreasingOrder`.
    ///
    /// - Parameter other: A sequence to blend with this one.
    /// - Parameter filter: The set operation (union, intersection, *etc.*) to
    ///   apply to the merger.
    /// - Parameter areInIncreasingOrder: A predicate that returns `true` if its
    ///   first argument should be ordered before its second argument;
    ///   otherwise, `false`.
    /// - Returns: An array containing the elements of this sequence and `other`
    ///   in a way that maintains the sort determined by `areInIncreasingOrder`.
    ///   For each value that exists in both sets, only one copy is kept.
    ///   (Usually the one from this sequence is kept, unless
    ///   `filter == anyFromSecond`.)
    ///
    /// - Complexity: O(*n* + *m*), where *n* and *m* are the lengths of this
    ///   sequence and `other`.
    @inlinable
    public func mergeSortedAsSets<S: Sequence>(with other: S, keeping filter: SetOperation, by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> [Element] where S.Element == Element {
        return try mergeSortedAsSets(with: other, keeping: filter, into: Array.self, by: areInIncreasingOrder)
    }

}

extension Sequence where Element: Comparable {

    /// Assuming this sequence and the given sequence are sorted, return a
    /// sorted array consisting of the two sequences blended together as sets,
    /// keeping only the elements indicated by the given operation.
    ///
    /// The sort is stable.
    ///
    /// - Precondition: Both this sequence and `other` are finite and sorted.
    ///
    /// - Parameter other: A sequence to blend with this one.
    /// - Parameter filter: The set operation (union, intersection, *etc.*) to
    ///   apply to the merger.
    /// - Returns: An array containing the elements of this sequence and `other`
    ///   in a monotonically increasing sequence.  For each value that exists in
    ///   both sets, only one copy is kept.  (Usually the one from this sequence
    ///   is kept, unless `filter == anyFromSecond`.)
    ///
    /// - Complexity: O(*n* + *m*), where *n* and *m* are the lengths of this
    ///   sequence and `other`.
    @inlinable
    public func mergeSortedAsSets<S: Sequence>(with other: S, keeping filter: SetOperation) -> [Element] where S.Element == Element {
        return mergeSortedAsSets(with: other, keeping: filter, by: <)
    }

}

// MARK: - Lazy Set Operations on Sorted Sequences

// MARK: Iterator

/// An iterator merging two sets, represented by iterators that vend sorted
/// virtual sequences, in a set operation.
public struct SetOperationIterator<Base1: IteratorProtocol, Base2: IteratorProtocol> where Base1.Element == Base2.Element {

    /// The sorting iterator.
    var iterator: MergingSortedIterator<Base1, Base2>
    /// Whether to vend elements exclusive to the first inner iterator.
    let useExclusivesToFirst: Bool
    /// Which member to take from a returned `.shared(Element, Element)`.
    let useFirstFromShared: Bool?
    /// Whether to vend elements exclusive to the second inner iterator.
    let useExclusivesToSecond: Bool

    /// Creates an iterator that vends the filtered/mapped results from the
    /// given iterator.
    @usableFromInline
    init(base: MergingSortedIterator<Base1, Base2>, keeping filter: SetOperation) {
        iterator = base
        useExclusivesToFirst = filter.hasExclusivesFromFirst
        if filter.hasNonExclusives {
            useFirstFromShared = filter != .anyFromSecond
        } else {
            useFirstFromShared = nil
        }
        useExclusivesToSecond = filter.hasExclusivesFromSecond
    }

}

extension SetOperationIterator: IteratorProtocol {

    public mutating func next() -> Base1.Element? {
        while let baseNext = iterator.next() {
            switch baseNext {
            case .exclusivelyFirst(let e) where useExclusivesToFirst,
                 .exclusivelySecond(let e) where useExclusivesToSecond,
                 .shared(let e, _) where useFirstFromShared == true,
                 .shared(_, let e) where useFirstFromShared == false:
                return e
            default:
                continue
            }
        }
        return nil
    }

}

// MARK: Sequence

/// A sequence merging two sets, represented by two sorted sequences, in a set operation.
public struct SetOperationSequence<Base1: Sequence, Base2: Sequence> where Base1.Element == Base2.Element {

    /// The sorting sequence.
    @usableFromInline
    let sequence: MergedSortedSequence<Base1, Base2>
    /// The set operation to apply.
    @usableFromInline
    let operation: SetOperation

    /// Creates a sorted sequence that applies the given set operation to the
    /// merger of the two given sequences, where both sequences are sorted
    /// according to the given predicate.
    @usableFromInline
    init(merging first: Base1, and second: Base2, applying filter: SetOperation, by areInIncreasingOrder: @escaping (Base1.Element, Base2.Element) -> Bool) {
        sequence = MergedSortedSequence(merging: first, and: second, by: areInIncreasingOrder)
        operation = filter
    }

}

extension SetOperationSequence: Sequence {

    public typealias Iterator = SetOperationIterator<Base1.Iterator, Base2.Iterator>
    public typealias Element = Iterator.Element

    @inlinable
    public func makeIterator() -> Iterator {
        return Iterator(base: sequence.makeIterator(), keeping: operation)
    }

    @inlinable
    public var underestimatedCount: Int { 0 }

}

extension SetOperationSequence: LazySequenceProtocol {}

// MARK: Collection

/// A collection merging two sets, represented by two sorted collections, in a
/// set operation.
///
/// - Warning: `startIndex` needs to filter, so it's O(*n*) instead of O(1).
public typealias SetOperationCollection<T: Collection, U: Collection> = SetOperationSequence<T, U> where T.Element == U.Element

extension SetOperationCollection: Collection {

    public typealias Index = MergedSortedIndex<Base1.Index, Base2.Index>

    public var startIndex: Index {
        for i in sequence.indices {
            switch sequence[i] {
            case .exclusivelyFirst where operation.hasExclusivesFromFirst,
                 .shared where operation.hasNonExclusives,
                 .exclusivelySecond where operation.hasExclusivesFromSecond:
                return i
            default:
                continue
            }
        }
        return endIndex
    }
    @inlinable
    public var endIndex: Index { sequence.endIndex }

    @inlinable
    public subscript(position: Index) -> Element {
        switch sequence[position] {
        case .exclusivelyFirst(let e), .exclusivelySecond(let e):
            return e
        case let .shared(first, second):
            return operation != .anyFromSecond ? first : second
        }
    }
    public func index(after i: Index) -> Index {
        precondition(i < endIndex)

        for j in sequence.indices[i...].dropFirst() {
            switch sequence[j] {
            case .exclusivelyFirst where operation.hasExclusivesFromFirst,
                 .shared where operation.hasNonExclusives,
                 .exclusivelySecond where operation.hasExclusivesFromSecond:
                return j
            default:
                continue
            }
        }
        return endIndex
    }

}

extension SetOperationCollection: LazyCollectionProtocol {}

// MARK: Generators

extension LazySequenceProtocol {

    /// Assuming this lazy sequence is sorted according to the given predicate
    /// comparing elements, and the given lazy sequence is sorted the same way,
    /// return a lazy sequence vending sorted elements consisting of the two
    /// sequences blended together as sets, keeping only the elements indicated
    /// by the given operation.
    ///
    /// `areInIncreasingOrder` must be a strict weak ordering over the elements.
    ///
    /// The sort is stable.
    ///
    /// The implementation pulls elements until one from the desired subset is
    /// found.  If at least one sequence isn't finite, then the thread will
    /// soft-lock if a sequence has no more matches for the targeted subset.
    ///
    /// - Precondition: Both this sequence and `other` are sorted according to
    ///   `areInIncreasingOrder`.
    ///
    /// - Parameter other: A lazy sequence to blend with this one.
    /// - Parameter filter: The set operation (union, intersection, *etc.*) to
    ///   apply to the merger.
    /// - Parameter areInIncreasingOrder: A predicate that returns `true` if its
    ///   first argument should be ordered before its second argument;
    ///   otherwise, `false`.
    /// - Returns: A lazy sequence containing the elements of this sequence and
    ///   `other` in a way that maintains the sort determined by
    ///   `areInIncreasingOrder`.  For each value that exists in both sets, only
    ///   one copy is kept.  (Usually the one from this sequence is kept, unless
    ///   `filter == anyFromSecond`.)
    @inlinable
    public func mergeSortedAsSets<L: LazySequenceProtocol>(with other: L, keeping filter: SetOperation, by areInIncreasingOrder: @escaping (Element, Element) -> Bool) -> SetOperationSequence<Elements, L.Elements> where L.Element == Element {
        return SetOperationSequence(merging: elements, and: other.elements, applying: filter, by: areInIncreasingOrder)
    }

    /// Assuming this lazy sequence is sorted according to the given predicate
    /// comparing elements, and the given sequence is sorted the same way,
    /// return a lazy sequence vending sorted elements consisting of the two
    /// sequences blended together as sets, keeping only the elements indicated
    /// by the given operation.
    ///
    /// `areInIncreasingOrder` must be a strict weak ordering over the elements.
    ///
    /// The sort is stable.
    ///
    /// The implementation pulls elements until one from the desired subset is
    /// found.  If at least one sequence isn't finite, then the thread will
    /// soft-lock if a sequence has no more matches for the targeted subset.
    ///
    /// - Precondition: Both this sequence and `other` are sorted according to
    ///   `areInIncreasingOrder`.
    ///
    /// - Parameter other: A sequence to blend with this one.
    /// - Parameter filter: The set operation (union, intersection, *etc.*) to
    ///   apply to the merger.
    /// - Parameter areInIncreasingOrder: A predicate that returns `true` if its
    ///   first argument should be ordered before its second argument;
    ///   otherwise, `false`.
    /// - Returns: A lazy sequence containing the elements of this sequence and
    ///   `other` in a way that maintains the sort determined by
    ///   `areInIncreasingOrder`.  For each value that exists in both sets, only
    ///   one copy is kept.  (Usually the one from this sequence is kept, unless
    ///   `filter == anyFromSecond`.)
    @inlinable
    public func mergeSortedAsSets<S: Sequence>(with other: S, keeping filter: SetOperation, by areInIncreasingOrder: @escaping (Element, Element) -> Bool) -> SetOperationSequence<Elements, LazySequence<S>.Elements> where S.Element == Element {
        return mergeSortedAsSets(with: other.lazy, keeping: filter, by: areInIncreasingOrder)
    }

}

extension LazySequenceProtocol where Element: Comparable {

    /// Assuming this lazy sequence and the given sequence are sorted, return a
    /// lazy sequence vending sorted elements consisting of the two sequences
    /// blended together as sets, keeping only the elements indicated by the
    /// given operation.
    ///
    /// The sort is stable.
    ///
    /// The implementation pulls elements until one from the desired subset is
    /// found.  If at least one sequence isn't finite, then the thread will
    /// soft-lock if a sequence has no more matches for the targeted subset.
    ///
    /// - Precondition: Both this sequence and `other` are sorted.
    ///
    /// - Parameter other: A sequence to blend with this one.
    /// - Parameter filter: The set operation (union, intersection, *etc.*) to
    ///   apply to the merger.
    /// - Returns: A lazily-generated sequence vending the elements of this
    ///   sequence and `other` in a monotonically increasing sequence.  For each
    ///   value that exists in both sets, only one copy is kept.  (Usually the
    ///   one from this sequence is kept, unless `filter == anyFromSecond`.)
    @inlinable
    public func mergeSortedAsSets<S: Sequence>(with other: S, keeping filter: SetOperation) -> SetOperationSequence<Elements, LazySequence<S>.Elements> where S.Element == Element {
        return mergeSortedAsSets(with: other, keeping: filter, by: <)
    }

}