Step 4 of 4

A new command cuts the branch

You start from the build so far — your own work where you have written it, the reference build where you have not. Either way this step stands on its own.

One case is still wrong, and every first implementation gets it wrong.

Undo something, then type something new. What should redo do?

insert("a")   ->  "a"
insert("b")   ->  "ab"
undo()        ->  "a"
insert("c")   ->  "ac"
redo()        ->  ???

Your version will happily replay Insert("b") and produce "acb" — a document that never existed, assembled from two branches of history at once. The undone command was recorded against a document that has since been replaced, so it is no longer meaningful.

Editors resolve this by cutting the branch: running a new command discards everything that was undone. Redo goes dead until the next undo.

depth() reports [undoable, redoable] and is already written. Use it to see the redo stack disappear.

Your build

Running is free — Submit is what records the step. Or press ⌘↩

Tests

4 cases, 1 hidden

call	type	expected	result
runOps([["insert","a"],["insert","b"],["undo"],["insert","c"],["redo"],["text"]])	a new command discards the redo stack	["a","ab","a","ac","ac","ac"]	—
runOps([["insert","a"],["undo"],["insert","b"],["depth"]])	depth reports an empty redo stack after a new command	["a","","b",[1,0]]	—
runOps([["insert","a"],["insert","b"],["undo"],["depth"]])	depth still reports what can be redone	["a","ab","a",[1,1]]	—
withheld	hidden	withheld	—

Hidden cases run too — their inputs aren't listed here, so aim for a general solution rather than one fitted to the cases above.

Complexity

target time: O(1) per command
target space: O(commands) — but proportional to the size of each change, not the document

This is the whole argument for the pattern over snapshotting. Snapshots cost the size of the document per change; commands cost the size of the change. For a large document edited one keystroke at a time, that is the difference between a few bytes per undo and a few megabytes.

Hints

Stuck? Hints open one at a time, each giving a little more away.

3 hints left