= Solution
A <demand-driven filtering iterator> needs one cached accepted value. Otherwise `hasNext` would either lose an element or consume another accepted value every time it is queried.
``
def filterIter[T](p: T => Boolean, it: Iter[T]): Iter[T] =
new Iter[T] {
private var buffered: Option[T] = None
private var finished = false
private def fill(): Unit = {
while (buffered.isEmpty && !finished) {
if (!it.hasNext) finished = true
else {
val x = it.next()
if (p(x)) buffered = Some(x)
}
}
}
def hasNext: Boolean = {
fill()
buffered.nonEmpty
}
def next(): T = {
fill()
require(buffered.nonEmpty)
val answer = buffered.get
buffered = None
answer
}
}
``
The <representation invariant> says that `buffered` holds at most one accepted value. The represented <sequence> is the buffered value, if present, followed by the subsequence of the underlying remainder satisfying the <predicate>. Filling moves the next accepted value into the cache and discards only rejected values, so this abstract <sequence> is unchanged by `hasNext`. Clearing the cache in `next` removes its head. Thus
$$
\boxed{\alpha(\mathrm{filterIter}(p,it))=\mathrm{filter}(p,\alpha(it)).}
$$
`next` works even when the client has not first called `hasNext`; exhaustion violates its stated precondition. As with ordinary <iterator> adapters, clients should give this wrapper exclusive consumption of `it`, and the <predicate> should give a stable answer for each element. One call may scan several rejected elements, but across a complete traversal each source element is consumed once. Cache storage is constant.
Back to article page
