Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Imperative programming / 7 / b / Solution 2026-10-31
View more
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.
(1)
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.
Read the full article
Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Imperative programming / 7 / c / Solution 2026-10-31
View more
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
(1)
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.
Read the full article