= Solution
Use one cached optional result. Only a request for availability or the next result fills that cache:
``
class FilterIterator[T](test: T => Boolean, iter: Iterator[T])
extends Iterator[T] {
private var cached: Option[T] = None
private def prepare(): Unit = {
while (cached.isEmpty && iter.hasNext) {
val x = iter.next()
if (test(x)) cached = Some(x)
}
}
def hasNext: Boolean = {
prepare()
cached.nonEmpty
}
def next(): T = {
prepare()
cached match {
case Some(x) =>
cached = None
x
case None => throw new NoSuchElementException("Filtered iterator exhausted")
}
}
}
``
This is a <demand-driven filtering iterator>. When the cache is empty, its abstract remaining <sequence> is the filtered remaining input. When it holds `Some(x)`, the abstract <sequence> is `x` followed by the filtered remaining input. The <loop invariant> for `prepare` says that all input elements consumed during the present search have failed `test`, except for the one cached passing value if one has been found. The first passing value stops the loop, so it cannot read past a result that the client has not yet consumed.
\b[Construction performs no underlying reads, and repeated `hasNext` calls reuse a cached result.] `next` also works without a preceding `hasNext`, clears only the result it returns, and does not prefetch its successor. `Some(x)`, rather than `Option(x)`, allows a passing null value to remain a genuine cached value. For finite remaining input, its length is a <loop variant>; for infinite input, availability can legitimately run forever if no further passing element exists. Deterministic terminating tests and exclusive ownership of the consuming input are assumed. One cache slot is $O(1)$ extra storage.
Back to article page
