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.