Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Imperative programming / 6 / a / Solution 2026-10-31
View more
Use an inverse edit record with a common undo/redo interface. Positions are zero-based. For move(i,j), j is the song's final index after the move, so it is also the insertion index in the shortened sequence. For an original length , require ; insertion permits and deletion requires . As allowed, the caller guarantees validity.
trait Change {
  def undo(): Unit
  def redo(): Unit
}

class SongSuite(initial: Sequence[Song]) {
  private var songs = initial
  def length: Int = songs.length
  def elementAt(i: Int): Song = songs.elementAt(i)

  private def rawInsert(i: Int, x: Song): Unit = {
    songs = songs.insert(i, x)
  }
  private def rawDelete(i: Int): Unit = {
    songs = songs.delete(i)
  }
  private def rawMove(i: Int, j: Int): Unit = {
    val x = songs.elementAt(i)
    songs = songs.delete(i)
    songs = songs.insert(j, x)
  }
  private def perform(forward: () => Unit,
                      backward: () => Unit): Change = {
    forward()
    new Change {
      def undo(): Unit = backward()
      def redo(): Unit = forward()
    }
  }
  def insert(i: Int, x: Song): Change =
    perform(() => rawInsert(i, x), () => rawDelete(i))

  def delete(i: Int): Change = {
    val x = songs.elementAt(i)
    perform(() => rawDelete(i), () => rawInsert(i, x))
  }
  def move(i: Int, j: Int): Change =
    perform(() => rawMove(i, j), () => rawMove(j, i))
}
Song denotes the application's song type, whose internal fields are irrelevant to these operations. Sequence denotes the supplied interface; each returned sequence is assigned back, so the code does not discard the result of a functional implementation. SongSuite owns its current sequence; independent mutations through outside aliases are excluded. Atomic successful edits and an ordinary sequential history are assumed.
For inverse command correctness, inserting at is reversed by deleting at ; deleting at is reversed by reinserting the saved song there. After moving from to , removing the moved song at recovers the original sequence with that one entry missing, and reinserting it at restores the original. This also covers . Store the actual deleted song reference, rather than identifying it by title, since duplicate songs may occur.
The edits have already executed when returned. A history manager can enforce the chronological protocol with two stacks:
class History {
  private var done: List[Change] = Nil
  private var undone: List[Change] = Nil
  def record(c: Change): Unit = {
    done = c :: done
    undone = Nil
  }
  def undo(): Unit = {
    require(done.nonEmpty)
    val c = done.head
    c.undo()
    done = done.tail
    undone = c :: undone
  }
  def redo(): Unit = {
    require(undone.nonEmpty)
    val c = undone.head
    c.redo()
    undone = undone.tail
    done = c :: done
  }
}
For example, history.record(suite.move(i,j)) records an applied move. The history invariant says that the current playlist results from the applied prefix, the top of done is its last edit, and the top of undone is the first next edit available for redo. Each transfer preserves this invariant. A fresh edit clears the redo branch. Calling an arbitrary old inverse after unrelated edits is outside this protocol and need not be correct.
Read the full article