The first matching entry must be retained, and copying an already-started prefix-dropping iterator must not restart the search. Use a private initial buffer together with the underlying iterator snapshot:Before preparation, the iterator still represents the original remaining sequence. During the search, the loop invariant says that every discarded entry fails the predicate, and
class DropUntil[T] private (
p: T => Boolean, iter: Iter[T],
saved: Option[T], alreadyStarted: Boolean) extends Iter[T] {
def this(p: T => Boolean, iter: Iter[T]) =
this(p, iter, None, false)
private var pending: Option[T] = saved
private var started: Boolean = alreadyStarted
private def prepare(): Unit = {
if (!started) {
var found = false
while (!found && iter.hasNext) {
val x = iter.next()
if (p(x)) {
pending = Some(x)
found = true
}
}
started = true
}
}
def hasNext: Boolean = {
prepare()
pending.nonEmpty || iter.hasNext
}
def next(): T = {
prepare()
pending match {
case Some(x) => pending = None; x
case None =>
if (!iter.hasNext) throw new NoSuchElementException("DropUntil.next")
iter.next()
}
}
def copy(): Iter[T] =
new DropUntil[T](p, iter.copy(), pending, started)
}pending is either empty or contains the first satisfying entry just consumed. For a finite input, the number of unread entries is a loop variant. After preparation, the abstract remaining sequence is pending.toList followed by the underlying iterator's remaining sequence. Repeated hasNext calls do not discard or test more entries after the first match.The iterator snapshot copies both the cached entry and the started flag. In particular, copying after the matching entry has been returned continues with the remaining suffix, including later entries that fail
p. Restarting new DropUntil(p, iter.copy()) at that point would wrongly drop another prefix.As usual, assume a deterministic predicate without shared mutable effects. On an infinite input having no match, the first demand cannot terminate: no finite inspection establishes absence. Independence here concerns cursor state; arbitrary mutation of shared element objects is outside the iterator contract. Articles by others on the same topic
There are currently no matching articles.