The source comment saying that The iterator owns consumption of
hasNext checks whether the sequence is empty is read in the standard sense “whether another element exists”; the method must return true for a nonempty logical sequence. The example fixes the meaning: skip source elements and return the next one, repeatedly. Require . A lookahead iterator must determine whether a complete group of elements exists, since a short final group contributes no result.def skipIter[T](it: Iter[T], n: Int): Iter[T] = {
require(n >= 0)
new Iter[T] {
private var prepared = false
private var cached: Option[T] = None
private def prepare(): Unit = {
if (!prepared) {
var skipped = 0
while (skipped < n && it.hasNext) {
it.next(); skipped += 1
}
cached =
if (skipped == n && it.hasNext) Some(it.next())
else None
prepared = true
}
}
def hasNext: Boolean = { prepare(); cached.nonEmpty }
def next(): T = {
prepare()
cached match {
case Some(v) =>
cached = None; prepared = false; v
case None => throw new NoSuchElementException("skipIter.next")
}
}
}
}it; clients must not independently advance the wrapped source. A prepared Some(v) is exactly the next selected source element, and None means no complete group remains. Repeated hasNext calls use the cached decision, and next also works without a preceding hasNext. Using Option[T] avoids an invalid generic sentinel value, including when a valid element is null.For source elements , the result isThe extra storage is and each source element is consumed at most once.
hasNext may physically consume and cache source elements: an arbitrary iterator has no non-consuming length query.Use a history dynamic array and a cursor between elements. If the cursor is behind the history's end, The representation invariant is , with history exactly the prefix already consumed from the original source. The logical unread sequence is the history suffix starting at
next replays history; otherwise it pulls a new element from the source. prev moves the cursor left and returns the element crossed, so prev followed by next returns the same element twice and restores the cursor.def genBiIter[T](it: Iter[T]): BiIter[T] = new BiIter[T] {
private val history = scala.collection.mutable.ArrayBuffer.empty[T]
private var pos = 0
def hasPrev: Boolean = pos > 0
def hasNext: Boolean = pos < history.length || it.hasNext
def next(): T = {
if (pos < history.length) {
val v = history(pos); pos += 1; v
} else if (it.hasNext) {
val v = it.next()
history += v; pos += 1; v
} else {
throw new NoSuchElementException("BiIter.next")
}
}
def prev(): T = {
if (!hasPrev) throw new NoSuchElementException("BiIter.prev")
pos -= 1
history(pos)
}
}pos, followed by the source's remaining sequence. The logical backward history is the prefix before pos. Every operation preserves this model, including alternating backward and forward moves after source exhaustion.This bidirectional iterator uses storage after consuming distinct source elements. Replay and backward moves take constant time; appending has amortized time complexity under the usual dynamic array model. The input iterator must not be advanced separately.Adapt one machine update into one forward iterator element, then apply the skipping iterator of part (a) with and the bidirectional iterator of part (b). Require a positive step and reset once on construction.After forward results at the unexplored frontier, the returned value is the machine's value after exactly updates. A partial final block contributes no element, and
trait StateMachineIter[T] extends StateMachine[T] {
def getBiIter(step: Int): BiIter[T] = {
require(step > 0)
val machine = this
machine.reset()
val everyUpdate = new Iter[T] {
def hasNext: Boolean = !machine.shouldStop
def next(): T = {
if (!hasNext)
throw new NoSuchElementException("StateMachine.next")
machine.update()
machine.getValue
}
}
genBiIter(skipIter(everyUpdate, step-1))
}
}update is never called after shouldStop becomes true. For the printed Add example, the first three observed states areBecause the state machine interface exposes no copy or rollback operation, determining whether enough updates remain generally requires executing them. Thus hasNext may advance the physical machine and cache the next observation. Backward traversal replays stored observations; it does not undo machine effects. This is a trace iterator, with the ordinary cursor semantics of part (b). Assume exclusive use of the machine while this iterator is active, and that returned values remain valid observations rather than mutable views overwritten by later updates. Articles by others on the same topic
There are currently no matching articles.