Bidirectional iterator 2026-10-31
An iterator with forward and backward cursor movement. With the cursor between elements, next crosses and returns the element to the right, and prev crosses and returns the element to the left. Memoizing a forward-only source's consumed prefix supports arbitrary backward travel over that prefix without replaying source effects. The required history storage grows with the farthest explored position, even if the current cursor later moves backward.
A function together with the bindings of variables from its defining environment. A mutable captured variable makes successive calls stateful. Sharing such a closure between copied iterators can violate the promised independent enumeration even when their current values are copied separately.
Cursor 2026-10-24
A sequential-access object with a non-consuming current-value operation and a separate advance operation. Repeated reads of the current value leave its abstract sequence unchanged. Converting a consuming iterator into a cursor therefore needs a cache or an equivalent saved-current representation.
Demand-driven filtering iterator Created 2026-10-24 Updated 2026-10-31
An iterator adapter that consumes underlying values only far enough to find the next value passing a predicate. Store at most one passing value in an optional value. With no cached value, its abstract remainder is the filtered underlying remainder; with cached , it is followed by that filtered remainder.
Construction performs no read. On hasNext or next, consume rejected values until one passes or the input is exhausted. Cache the passing value immediately and stop. Repeated availability tests reuse it. Returning it clears the cache without prefetching another value. This gives a precise demand boundary even when producing source values is expensive. Availability need not terminate on an infinite input with no further passing value.
Iterator concatenation 2026-10-24
Consume the first iterator until it is exhausted, then consume the second. Short-circuit availability testing avoids polling the second producer while the first still has entries. Construction need not request any entry. If both wrappers share an underlying cursor, however, draining the first may also consume entries the second would otherwise have returned.
Iterator pattern 2026-10-25
Expose sequential consumption through availability and next-element operations while hiding storage and traversal details. The abstraction supports common clients for arrays, linked structures or generated sequences. A separate iterator can own separate cursor state; an alias of the same iterator does not create an independent traversal.
Represent a cursor by an underlying consuming iterator plus an optional cached head. Without a cache, its abstract sequence is the iterator's sequence; with cached , it is concatenated with the remaining iterator sequence. current fetches and caches exactly one value when needed, repeated reads reuse it, and advance discards it. Availability testing need not fetch a value, and construction need not query the input. This avoids forcing a future stream element that the client may never request.
Lookahead iterator 2026-10-31
An iterator that physically consumes and caches source elements to determine whether another logical result exists. A prepared optional result makes repeated availability queries idempotent. This is useful when a result requires a complete group of source elements and the underlying iterator exposes neither its remaining length nor a rewind operation. Source consumption is owned by the wrapper; clients must not independently advance the underlying iterator.
Represent each generated sequence position by an immutable head and a lazily memoized successor, and give each iterator its own pointer into the shared chain. Computing a successor invokes the privately owned generator once; lagging copies reuse that same successor. Consequently a mutable programming closure generating Fibonacci numbers can support interleaved independent cursor positions. Sharing only the generator and a copied current value would instead consume the generator's mutable state twice. This construction can retain all cells between the fastest and slowest live cursors; it does not guarantee constant memory usage.
The iterator pattern separates traversal state from the aggregate being traversed. A client asks whether another entry exists, then requests that entry, without knowing whether storage is an array, a linked list or another data structure. Distinct iterators have independent positions in a traversal.
In Java, declare DataList implements Iterable<Point> and provide public Iterator<Point> iterator(). The returned iterator implements hasNext() and next(); exhausted next() throws NoSuchElementException. This also permits an enhanced for (Point p : data) loop.[ref]
Returning points.iterator() directly would permit removal through that iterator and expose mutable stored Point instances. Part (e) instead returns an unmodifiable iterator snapshot containing fresh Point copies. That choice gives stable traversals and prevents representation exposure, with the tradeoff that a traversal does not see subsequent insertions. Thus
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.
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
  }
}
Assume the source iterator is owned by the wrapper, its 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. Therefore
When 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.
These operations consume the receiver, as expected for this destructive iterator interface. exists stops immediately after the first successful test.
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 acc = x
    while (hasNext) acc = f(acc, next())
    acc
  }
}
For foreach, after iterations the supplied function has been applied in order to exactly the first entries. For exists, every consumed entry has failed the predicate unless the method is returning true. For the left fold, the loop invariant after consuming entries is
Each iteration extends the expression by the next entry on the right. For a finite remaining sequence, its unconsumed length is a common loop variant. Thus
An empty iterator invokes no callback, gives false for exists, and returns from the left fold. On an infinite iterator, exists can terminate when it finds a match; the other two operations ordinarily do not terminate. With constant-cost callbacks, finite input of length takes time complexity and constant auxiliary space.
A simple current-value implementation works when is a pure function, but sharing a mutable closure between copies would violate the independence requirement used in part (d). Use a memoized successor chain for stateful iterator copies: the generated sequence has shared cells, and each iterator has its own current-cell pointer.
object FunIter {
  final class Cell[T](val head: T, f: T => T) {
    lazy val tail: Cell[T] = new Cell[T](f(head), f)
  }
}

class FunIter[T](v: T, f: T => T) extends Iter[T] {
  private var cursor = new FunIter.Cell[T](v, f)

  def hasNext: Boolean = true

  def next(): T = {
    val x = cursor.head
    cursor = cursor.tail
    x
  }

  def copy(): Iter[T] = {
    val result = new FunIter[T](cursor.head, f)
    result.cursor = cursor
    result
  }
}
The representation invariant is that cursor points to the next cell to be returned, and each cell's lazy tail is computed at most once. The abstraction function is the infinite sequence of heads starting at that cell. Advancing changes only this iterator's pointer. A copy starts at the same cell, so both observe the same remaining heads even when their calls are interleaved:
For a stateful , the generator state must be privately owned by this shared chain; unrelated external calls to must not change it. As usual, the values and transition must allow successive results to be observed without externally mutating old results. No interface can independently clone the hidden state of an arbitrary externally mutated closure from its function type alone. The chain avoids needing such cloning: a lagging copy reuses the already generated future instead of invoking again.
Each new cell needs one transition and constant bookkeeping, but retained slower copies can keep a long generated prefix alive. This is an intentional space tradeoff that permits the stateful generator in part (d). No output is possible if computing a demanded transition itself fails or diverges.
Keep the neighboring Fibonacci number in a private closure. Before calling the transition with , let its captured following equal .
def fibonacci(): Iter[BigInt] = {
  var following = BigInt(1)
  val step: BigInt => BigInt = (x: BigInt) => {
    val result = following
    following = x + following
    result
  }
  new FunIter[BigInt](BigInt(0), step)
}
The transition returns and stores , preserving the paired Fibonacci recurrence. Initialization gives and , so
Using BigInt allows all Fibonacci numbers rather than a finite prefix before integer overflow. Replacing BigInt by Int gives the source's suggested machine-integer interface with that limitation. With the FunIter implementation from part (c), each transition runs once per generated cell, and copied iterators can advance independently while sharing the privately owned generator. A simpler alternative uses a pure function on pairs, , and projects the first component; the closure above follows the source's suggested single-value approach directly.
A demand-driven filtering iterator needs one cached accepted value. Otherwise 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
    }
  }
The representation invariant says that 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. Thus
next 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.
Use the iterator adapter from part (b) with a primality test by trial division. A composite positive integer has a divisor no greater than its square root.
def primeIter(upperBound: Int): Iter[Int] = {
  def isPrime(n: Int): Boolean = {
    if (n < 2) false
    else {
      var d = 2
      while (d <= n / d && n % d != 0) d += 1
      d > n / d
    }
  }
  filterIter[Int](isPrime _, new RangeIter(2, upperBound, 1))
}
Before each trial division iteration, no integer in divides n. If division succeeds, the condition becomes false with , and isPrime returns false. Otherwise the loop ends with , so every possible small divisor has been excluded. The quotient comparison is equivalent to for positive values and avoids integer overflow in d*d.
Bounds at most two give an empty iterator. This method tests candidates lazily and uses trial divisions for candidate ; no efficiency requirement in the question forces a sieve of Eratosthenes implementation.
The source comment saying that 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")
      }
    }
  }
}
The iterator owns consumption of 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 is
The 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, 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)
  }
}
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 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.
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))
  }
}
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 update is never called after shouldStop becomes true. For the printed Add example, the first three observed states are
Because 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.
Each physical update is executed at most once. Previously observed values can be revisited without rerunning the machine, and repeated hasNext calls do not perform duplicate updates once the next result is prepared.
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:
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)
}
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 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.