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:For example,
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
}
}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.The Command pattern separates a request into a common command interface, concrete commands carrying arguments and execution behavior, a receiver doing the application work, an invoker requesting execution or retaining history, and a client assembling these software objects. A menu item, toolbar button or keyboard shortcut can invoke the same command without duplicating the playlist manipulation.
SongSuite is the receiver. The application/controller invokes its operations, and the returned Change software objects hold the concrete inverse/forward behavior. A command wrapper can expose an initial execute that calls the appropriate SongSuite operation and then delegates later undo/redo to its returned record. History is the history-managing part of the invoker. Separating these roles avoids making a graphical control know how the playlist representation is edited; requests can be retained and reversed through a common object interface.If sequence versions are immutable, replace The unused inverse argument can subsequently be removed from
perform by the following method; the insert, delete and move entry points can stay as written:private def perform(forward: () => Unit,
backward: () => Unit): Change = {
val before = songs
forward()
val after = songs
new Change {
def undo(): Unit = { songs = before }
def redo(): Unit = { songs = after }
}
}perform and its callers. Each history record now captures two complete versions. Undo and redo restore the respective roots without replaying an operation, an instance of the Memento pattern. The same chronological history discipline still applies.The supplied method signatures alone do not establish immutability or persistence. If
insert or delete changes a shared mutable software object, merely storing its reference fails to freeze the earlier state. Then independent copies of the relevant state are needed, including any mutable song state intended to be undoable, or the implementation must provide immutable persistent data structure versions. This is a representation requirement, not a reason to invent a particular unavailable copying API.Version snapshots simplify correctness: a complicated command restores the complete prior state, so a bespoke inverse cannot accidentally omit an auxiliary field. Redo restores the recorded result without re-executing behavior that might depend on time, randomness or external input. Restoring an immutable root takes constant time, though refreshing the display can cost more.
The storage comparison depends on the representation. A change-specific record for these elementary edits retains only a few indices and song references. Copying a length- array for each of edits can require storage and copying per edit. A persistent data structure with structural sharing can preserve many versions much more cheaply; balanced path copying can make small edits allocate new entries. Retaining versions also keeps their reachable data alive. Snapshot references are only constant-sized roots, not a guarantee of constant total retained memory. Neither scheme automatically reverses external effects such as playing audio or writing files. The desired undo boundary must be specified.
Articles by others on the same topic
There are currently no matching articles.