Thanks, I haven't studied that list, but I made a
proof of concept implementation
extension Sequence where Element: Equatable {
/// Returns a Boolean value that indicates whether the sequence contains
/// the given sequence.
///
/// - Parameter other: The sequence to find within
/// this sequence. `other` must be finite.
/// - Returns: `true` if the sequence contains `other`;
/// otherwise, `false`.
public func isSupersequence<S>(of other: S) -> Bool
where S : Sequence, S.Element == Element
{
var selfIter = self.makeIterator()
var otherIter = RewindableIterator(other.makeIterator())
guard let otherFirst = otherIter.next() else { return false }
while let selfNext = selfIter.next() {
if selfNext == otherFirst {
while true {
let selfNext = selfIter.next()
let otherNext = otherIter.next()
if selfNext != otherNext {
if selfNext == nil { return false }
if otherNext == nil { return true }
break
} else {
if selfNext == nil { return true }
}
}
otherIter.rewind()
let _ = otherIter.next()
}
}
return false
}
}
// Helper type for the above implementation of `isSupersequence(of:)`.
struct RewindableIterator<Base: IteratorProtocol> : IteratorProtocol {
var base: Base
var cachedPrefix: [Base.Element] = []
var position = 0
init(_ base: Base) {
self.base = base
}
mutating func rewind() {
position = 0
}
mutating func next() -> Base.Element? {
if position < cachedPrefix.count {
defer { position += 1 }
return cachedPrefix[position]
} else if let next = base.next() {
defer { position += 1 }
cachedPrefix.append(next)
return next
} else {
return nil
}
}
}
// An example sequence type that is destructively consumed by iteration.
final class CountOnce: Sequence, IteratorProtocol {
var current: Int
let afterLast: Int
let step: Int
init(from: Int, to: Int) {
self.step = from <= to ? 1 : -1
self.current = from
self.afterLast = to + step
}
func makeIterator() -> CountOnce {
return self
}
func next() -> Int? {
if current != afterLast {
defer { current += step }
return current
} else {
return nil
}
}
}
let a = CountOnce(from: 1, to: 7)
let b = CountOnce(from: 4, to: 6)
let c = a.isSupersequence(of: b)
print(c) // true
let d = a.isSupersequence(of: b)
print(d) // false since they have been destructively consumed.
that demonstrates that it is possible to write one that will "only" need memory to store the longest subsequence-prefix that occurs within the sequence.