A demand-driven filtering iterator needs one cached accepted value. Otherwise The representation invariant says that
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
}
}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. Thusnext 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. Articles by others on the same topic
There are currently no matching articles.