Since you are extracting elements from the source and filter each one at a time and always in order, it seemed that the iterator interface would be perfect. Instead of putting it here, I put my version in a gist. But I'll copy the business method here:
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()
}
}
I had to put the bulk of the code in a do-block, otherwise I'll get infinite recursion. Could someone check if it generates the sought-after tail-recursion?
Since I qualified the array requirements as small as possible, this code will even work with single-pass Sequences. It helps here that you require <; using a general predicate would change how the comparisons are done, need to check for exceptions, and probably need eager/lazy versions. Maybe I'll try that later; it'd need Swift 5's Result to generalize it to one copy of the algorithm.