A prefix-dropping iterator must preserve the first satisfying element. Reading it to test the predicate physically consumes it from the source, so keep it in a one-element buffer. Once a match is found, return the entire suffix without testing subsequent elements again.Assume the source iterator is owned by the wrapper, its
trait Iter[T] {
def hasNext: Boolean
def next(): T
def copy(): Iter[T]
}
class DropUntil[T](p: T => Boolean, iter: Iter[T]) extends Iter[T] {
private var seeking = true
private var saved: Option[T] = None
private def prepare(): Unit = {
if (seeking) {
while (saved.isEmpty && iter.hasNext) {
val x = iter.next()
if (p(x)) saved = Some(x)
}
seeking = false
}
}
def hasNext: Boolean = {
prepare()
saved.nonEmpty || iter.hasNext
}
def next(): T = {
prepare()
saved match {
case Some(x) => saved = None; x
case None =>
if (!iter.hasNext) throw new NoSuchElementException("next")
iter.next()
}
}
def copy(): Iter[T] = {
val result = new DropUntil[T](p, iter.copy())
result.seeking = seeking
result.saved = saved
result
}
}copy meets the stated independent-cursor contract, and is a pure function. Before preparation, the logical remainder is the source remainder with its maximal initial failing prefix removed. After preparation, it is the buffered match followed by the source remainder, or simply the source remainder when the buffer is empty. This describes the abstraction function and proves that repeated hasNext calls neither lose the match nor skip more values.Copying preserves the phase flag and optional buffered value and independently copies the source iterator. It does not rerun the predicate on an already accepted match. A shallow copy of the wrapper alone would give shared iterator consumption, violating the specification. ThereforeWhen no element satisfies , a finite source yields an empty iterator. Seeking can diverge on an infinite source with no match; this is inherent in determining whether its required suffix begins anywhere. An element object is not deep-copied by this cursor operation.
Articles by others on the same topic
There are currently no matching articles.