= Solution
Use a history <dynamic array> and a cursor between elements. If the cursor is behind the history's end, `next` replays history; otherwise it pulls a new element from the source. `prev` moves the cursor left and returns the element crossed, so `prev` followed by `next` returns the same element twice and restores the cursor.
``
def genBiIter[T](it: Iter[T]): BiIter[T] = new BiIter[T] {
private val history = scala.collection.mutable.ArrayBuffer.empty[T]
private var pos = 0
def hasPrev: Boolean = pos > 0
def hasNext: Boolean = pos < history.length || it.hasNext
def next(): T = {
if (pos < history.length) {
val v = history(pos); pos += 1; v
} else if (it.hasNext) {
val v = it.next()
history += v; pos += 1; v
} else {
throw new NoSuchElementException("BiIter.next")
}
}
def prev(): T = {
if (!hasPrev) throw new NoSuchElementException("BiIter.prev")
pos -= 1
history(pos)
}
}
``
The <representation invariant> is $0\leq\mathrm{pos}\leq|\mathrm{history}|$, with history exactly the prefix already consumed from the original source. The logical unread <sequence> is the history suffix starting at `pos`, followed by the source's remaining <sequence>. The logical backward history is the prefix before `pos`. Every operation preserves this model, including alternating backward and forward moves after source exhaustion.
$$
\boxed{\text{Memoize the consumed prefix; move a cursor through it before fetching new elements.}}
$$
This <bidirectional iterator> uses $O(k)$ storage after consuming $k$ distinct source elements. Replay and backward moves take constant time; appending has <amortized time complexity> $O(1)$ under the usual <dynamic array> model. The input <iterator> must not be advanced separately.
Back to article page
