= Solution
Prefer the first <sequence> whenever it is nonempty, otherwise delegate to the second:
``
def cat[T](t: Iter[T], u: Iter[T]): Iter[T] = new Iter[T] {
def hasNext: Boolean = t.hasNext || u.hasNext
def next(): T = {
if (t.hasNext) t.next()
else {
require(u.hasNext, "empty iterator")
u.next()
}
}
}
def cat[T](t: Cursor[T], u: Cursor[T]): Cursor[T] = new Cursor[T] {
def hasCurrent: Boolean = t.hasCurrent || u.hasCurrent
def current: T = {
if (t.hasCurrent) t.current
else {
require(u.hasCurrent, "empty cursor")
u.current
}
}
def next(): Unit = {
if (t.hasCurrent) t.next()
else {
require(u.hasCurrent, "empty cursor")
u.next()
}
}
}
``
Assume the two destructive inputs have noninterfering states; in particular, passing the same <iterator> twice does not create a replayable copy of its original <sequence>. Fresh independent <iterators> provide that behavior. Under this ownership condition, the <abstraction function> is always the concatenation `t.seq ++ u.seq`. Consumption from `t` removes the concatenation's head; once `t` is empty, consumption from `u` does so. Availability tests short-circuit, so an infinite first <sequence> never unnecessarily touches the second.
For finite lengths $p,q$, under a client loop with one availability test and one advance per element, the <iterator> version directly invokes `t.hasNext` \b[$2(p+q)+1$ times], including the final false test. For a <cursor> client with one availability test, one `current` read and one advance per element, the corresponding count is \b[$3(p+q)+1$]. These count calls made by the shown adapters, not extra checks hidden inside arbitrary underlying methods. A client can repeat availability/current queries arbitrarily often, so no bound depending only on $p,q$ applies without such a client protocol.
Cache a permanent “first input exhausted” flag after the first negative test to avoid repeated queries to `t` while traversing `u`; this reduces the dependence to $O(p+1)$ first-input queries under the same protocols. Availability caching can reduce additional repeated checks. The flag is sound because an <iterator>'s consumed <sequence> does not spontaneously grow again.
Back to article page
