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.Implement the three consumers directly with while loops. These methods consume the receiver; For
exists stops immediately after the first witness:trait RichIter[T] extends Iter[T] {
def foreach(f: T => Unit): Unit = {
while (hasNext) f(next())
}
def exists(p: T => Boolean): Boolean = {
while (hasNext) {
if (p(next())) return true
}
false
}
def foldLeft[U](x: U)(f: (U, T) => U): U = {
var result = x
while (hasNext) result = f(result, next())
result
}
}foreach, the loop invariant is that f has been called once, in order, on exactly the consumed prefix. For exists, provided it has not returned, every consumed entry fails the predicate; a returned true has a witness, while exhaustion proves there is none. For foldLeft, after consumed entries the loop invariant iswith result = x at . Thus initialization, one further application, and exhaustion prove the required left fold. On finite inputs, the remaining length is a loop variant for each loop. Callbacks are assumed not to mutate this iterator independently.With constant-cost callbacks and iterator operations, full consumption costs ; exists may return earlier. Empty inputs respectively do nothing, return false, and return x. Infinite inputs need not terminate, except that exists terminates upon reaching a witness.If The first cell stores ; its lazily memoized successor stores ; the next stores , and so on. A cell's successor is evaluated at most once. The representation invariant is that each cursor points to the cell holding its next result.
f is a pure function on immutable values, a simple implementation stores the next value and copies it into a fresh FunIter. Part (d)'s suggested mutable programming closure, however, would be shared by such copies and violate independence. A memoized iterator snapshot avoids that contradiction: all cursors share already determined sequence values, but each has its own position.class FunIter[T](v: T, f: T => T) extends Iter[T] {
private class Cell(val head: T) {
lazy val tail: Cell = new Cell(f(head))
}
private class Cursor(private var cell: Cell) extends Iter[T] {
def hasNext: Boolean = true
def next(): T = {
val answer = cell.head
cell = cell.tail
answer
}
def copy(): Iter[T] = new Cursor(cell)
}
private val cursor = new Cursor(new Cell(v))
def hasNext: Boolean = true
def next(): T = cursor.next()
def copy(): Iter[T] = cursor.copy()
}next returns that result and advances only this cursor. copy shares the cell, whose future is memoized, rather than the mutable cursor. Advancing either copy therefore cannot skip entries in the other.Assume each demanded application of f terminates and generated values are immutable for purposes of observation. A stateful generator should be privately owned by this family of cursors; arbitrary external changes to it cannot be made independent by the supplied interface. Unlike the pure-function implementation, memoization can retain a long prefix while one copy lags far behind another. The question imposes no constant-storage requirement.Use a programming closure whose private variable holds the next Fibonacci number. Use arbitrary-precision integers to enumerate all terms exactly:At the cell containing , the private state immediately before computing its successor is
def fibonacci(): Iter[BigInt] = {
var following = BigInt(1)
val step: BigInt => BigInt = (current: BigInt) => {
val result = following
following = current + following
result
}
new FunIter[BigInt](BigInt(0), step)
}following = F_(i+1). The successor returns that value and sets following to , preserving the recursion invariant. The resulting sequence startsEach successor is computed once by the memoized implementation in part (c); interleaved copies see the same already generated successor instead of independently advancing shared programming closure state. Replacing BigInt by Int and the two initial values by 0,1 gives exactly the hinted Int => Int implementation, but eventually incurs integer overflow, so it does not enumerate all mathematical Fibonacci numbers.An alternative avoiding mutable programming closure state represents the current and next Fibonacci numbers by a pair and uses the pure function with initial state ; a projecting iterator returns the first component. The closure construction above meets the suggested one-number interface directly.
Articles by others on the same topic
There are currently no matching articles.