= Solution
Use an inverse edit record with a common undo/redo interface. Positions are zero-based. For `move(i,j)`, \b[`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 $m$, require $0\leq i,j<m$; insertion permits $0\leq i\leq m$ and deletion requires $0\leq i<m$. 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 $i$ is reversed by deleting at $i$; deleting at $i$ is reversed by reinserting the saved song there. After moving from $i$ to $j$, removing the moved song at $j$ recovers the original <sequence> with that one entry missing, and reinserting it at $i$ restores the original. This also covers $i=j$. 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.
Back to article page
