Merge two strictly increasing sequences, without duplicates

This work is motivated by Sum of natural numbers below threshold, where several Swift solutions to Project Euler #1 (with arbitrary upper bound) are provided.

One way to think of it is to

• start with two sequences (the multiples of 3 and the multiples of 5),
• merge these two sequences into a new sequence, in increasing order, without duplicates,
• finally add all elements of the merge sequence.

This question is about reviewing a generic solution for the second part:

Given two sequences (whose elements are strictly increasing), create a new “merged” sequence containing the elements of both, in increasing order, without duplicates.

With that increasingMerge() function, the solution to the above problem could be computed as

let upperBound = 10_000
print(increasingMerge(of: stride(from: 3, to: upperBound, by: 3),
                      and: stride(from: 5, to: upperBound, by: 5))
    .reduce(0, +))

This is surely not the most efficient way to solve Project Euler #1 (which in fact can be solved in O(1) time and O(1) space), but that is not the goal. The goal is to provide universally applicable function to merge two increasing sequences.

There seems to be no such function in Swift Algorithms. The overall approach with a global function, which returns an instance of IncreasingMergeSequence (conforming to the Sequence protocol), is inspired by Chain.swift. The code uses O(1) additional space.

Any and all feedback is welcome (coding style, naming, efficiency, access control, ...)

public struct IncreasingMergeSequence<Base1: Sequence, Base2: Sequence>: Sequence
    where Base1.Element == Base2.Element, Base1.Element: Comparable
{
    public typealias Element = Base1.Element // The common element type
    
    private let base1: Base1
    private let base2: Base2

    fileprivate init(base1: Base1, base2: Base2) {
        self.base1 = base1
        self.base2 = base2
    }
    
    public struct IncreasingMergeIterator: IteratorProtocol {
        private var iterator1: Base1.Iterator
        private var iterator2: Base2.Iterator

        private var elem1: Element? = nil
        private var elem2: Element? = nil
        
        fileprivate init(iterator1: Base1.Iterator, iterator2: Base2.Iterator) {
            self.iterator1 = iterator1
            self.iterator2 = iterator2
            elem1 = self.iterator1.next()
            elem2 = self.iterator2.next()
        }
        
        public mutating func next() -> Element? {
            switch (elem1, elem2) {
            case (let x?, let y?):
                if x < y {
                    elem1 = iterator1.next()
                    return x
                } else if y < x {
                    elem2 = iterator2.next()
                    return y
                } else {
                    elem1 = iterator1.next()
                    elem2 = iterator2.next()
                    return x
                }
            case (let x?, nil):
                elem1 = iterator1.next()
                return x
            case (nil, let y?):
                elem2 = iterator2.next()
                return y
            case (nil, nil):
                return nil
            }
        }
    }

    public func makeIterator() -> IncreasingMergeIterator {
        IncreasingMergeIterator(iterator1: base1.makeIterator(), iterator2: base2.makeIterator())
     }
}

/// Returns a new sequence containing the elements of two sequences, in increasing order,
/// without duplicates.
/// - Attention: It is assumed that the elements of both sequences are in strictly increasing order.
/// - Parameters:
///   - s1: The first sequence.
///   - s2: The second sequence.
/// - Returns: A sequence of the elements of `s1` and `s2`, in increasing order, without duplicates.

public func increasingMerge<S1, S2>(of s1: S1, and s2: S2) -> IncreasingMergeSequence<S1, S2> {
    return IncreasingMergeSequence(base1: s1, base2: s2)
}