The return types suggest an immutable sequence implementation: insertion and deletion return a new
Sequence[A], while the receiver can remain unchanged. A mutable implementation would more naturally return Unit for in-place edits, though it could return itself. Thus the signatures are evidence of an intended immutable object implementation, not a logical guarantee. For the snapshot solution below, require that returned and retained Sequence values really are immutable. The owning SlideSuite can still have a mutable variable referring to its current immutable sequence.Represent an applied edit by a command pattern object with
undo and redo. Use zero-based positions. For move(from,to), define to as the slide's index in the resulting sequence; it is in for a presentation of length . Removing the slide first and then inserting at that index implements this convention in either direction.trait Change {
// Pre: this is the most recent applied change not yet undone.
def undo(): Unit
// Pre: this is the next change on the redo history.
def redo(): Unit
}
class SlideSuite(initial: Sequence[Slide]) {
private var slides = initial
private def insertRaw(i: Int, x: Slide): Unit = {
slides = slides.insert(i, x)
}
private def deleteRaw(i: Int): Unit = {
slides = slides.delete(i)
}
private def moveRaw(from: Int, to: Int): Unit = {
val x = slides.elementAt(from)
slides = slides.delete(from).insert(to, x)
}
def insert(i: Int, x: Slide): Change = {
insertRaw(i, x)
new Change {
def undo(): Unit = deleteRaw(i)
def redo(): Unit = insertRaw(i, x)
}
}
def delete(i: Int): Change = {
val x = slides.elementAt(i)
deleteRaw(i)
new Change {
def undo(): Unit = insertRaw(i, x)
def redo(): Unit = deleteRaw(i)
}
}
def move(from: Int, to: Int): Change = {
moveRaw(from, to)
new Change {
def undo(): Unit = moveRaw(to, from)
def redo(): Unit = moveRaw(from, to)
}
}
}Sequence and Slide are the supplied external types. Valid insertion positions are , deletion positions are , and both move positions are valid indices of the original length. These are the permitted unchecked argument preconditions. The private raw operations perform exactly their named state transformation and do not create history entries. A move to the same index is a legitimate no-op.The deleted slide must be saved because its index alone cannot reconstruct it. By contrast, insertion already receives the slide to retain. For a move, the inverse of moving the slide from
from to its final index to is to remove it at to and reinsert it at from; all other slides retain their relative order. Thus each returned object satisfies undo restores the state immediately before the edit, and redo restores the state immediately after it, under the stated history protocol.A controller can enforce the protocol with two stacks. This code records changes that have already been executed:For example,
class History {
private var done = List.empty[Change]
private var undone = List.empty[Change]
// Pre: c is a fresh, already-applied change of this history's suite.
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)) executes and records one move. The representation invariant says that done contains applied changes in reverse application order, while undone contains undone changes in the next-redo order, all belonging to the same suite. A fresh edit clears the redo branch. Undo and redo transfer one command between the two heads, so they neither skip intervening edits nor generate new history records. Unrecorded external edits and out-of-order use of old command objects are excluded by this protocol.Replace edit-specific inverse information by before/after snapshots implementing the Memento pattern. The same By-value evaluation computes
Change and History interfaces still work. A complete alternative suite is:class SnapshotSlideSuite(initial: Sequence[Slide]) {
private var slides = initial
private def changeTo(after: Sequence[Slide]): Change = {
val before = slides
slides = after
new Change {
def undo(): Unit = { slides = before }
def redo(): Unit = { slides = after }
}
}
def insert(i: Int, x: Slide): Change =
changeTo(slides.insert(i, x))
def delete(i: Int): Change =
changeTo(slides.delete(i))
def move(from: Int, to: Int): Change = {
val x = slides.elementAt(from)
changeTo(slides.delete(from).insert(to, x))
}
}after without changing slides, then changeTo captures the still-current before and installs the new value. The val bindings inside each call are stable snapshots, rather than later reads of a mutable variable. Under the same chronological history preconditions, undo and redo are constant-time reference assignments. This is the Memento pattern applied to an immutable sequence. Retaining a reference to an in-place-mutated sequence would not save its old state. The snapshot covers slide order and membership; it does not promise to undo unrelated mutations inside a Slide object.Not necessarily: structural sharing can make snapshots cheap, but the trait alone gives no storage guarantee. With a persistent data structure, unchanged portions of old and new sequences can be shared safely. Saving two root references costs additional space per edit, and adjacent history entries commonly refer to the same intermediate version. With an appropriate balanced persistent tree, each positional edit may add only new vertices, giving approximately storage for retained edits of comparable presentation size, plus references to slides.
There are important qualifications. A fully copied immutable array may allocate per edit and use across its history. A persistent linked list shares suffixes but may copy a long prefix for a late positional edit. Moreover, snapshot history keeps old versions alive that an edit-specific inverse representation might otherwise release. Consequently a significant increase is possible with some implementations or workloads; it is not forced by saving
Sequence references, and it cannot be ruled out from the interface alone. Articles by others on the same topic
There are currently no matching articles.