Card 08/ 09
Practice: Undo and Redo in a Text Editor
Two stacks hold what can be undone and what can be redone.
Undo and redo in a text editor practise both halves of working with these structures: choosing one from the order a problem needs, and tracing what it holds. This card covers them as an exercise, with an answer to check yours against.
An editor records each word typed as one edit. Undo takes back the most recent edit still in the text. Redo puts back the edit that undo took back most recently. Typing a new word after an undo means the edits undone can no longer be redone.
- Say which structure should hold the edits that can be undone, and which should hold the edits that can be redone.
- Starting from an empty document, trace both through: type red, type green, type blue, undo, undo, redo, type pink. Give the text and both structures after each command.
- State what each command costs.
An answer: two stacks, traced through all seven commands, and their cost
Both are stacks, because both commands want the most recent edit: undo the last one made, and redo the last one undone. Typing pushes the word onto the undo stack and empties the redo stack. Undo pops from the undo stack and pushes the same word onto the redo stack, and redo does the reverse. A run printed the text and both stacks after each command:
| Command | Text | Undo stack, top first | Redo stack, top first |
|---|---|---|---|
| Type red | red | red | (empty) |
| Type green | red green | green red | (empty) |
| Type blue | red green blue | blue green red | (empty) |
| Undo | red green | green red | blue |
| Undo | red | red | green blue |
| Redo | red green | green red | blue |
| Type pink | red green pink | pink green red | (empty) |
Without the emptying, a redo after pink would bring back blue, an edit made to a text that no longer exists, and the document would read red green pink blue. A queue would be wrong for either stack: the first undo would take back red, the oldest edit, instead of blue.
Typing, undo and redo each push or pop once, so each is O(1). Emptying the redo stack is the exception, and costs one step for each edit it discards, which is at most the number of undos made since the last word typed.
← → move through sections and cards