Undo and Redo with Commands
An undo button that remembers only the last change can't take back two mistakes, and can't redo anything; when each command knows how to reverse itself, a stack of done commands and a stack of undone ones give the dispatcher as many undos and redos as she needs.
Journeyman · OOP · Updated
After this lesson you can
- Give each command a way to reverse itself, and undo and redo with two stacks
- Predict what the undo and redo stacks hold after a series of actions
Key takeaways
- The smell: undo that remembers one change in a few variables, so a second undo does nothing and there's no redo.
- The fix: each command saves what it needs to reverse itself, and has an undo method beside execute.
- A stack is a pile you only touch at the top: push adds to the top, pop takes the top off, so the last one in is the first one out.
- Undo pops the undo stack and pushes onto the redo stack; redo does the opposite; a new action empties the redo stack.
Before this: Command: An Action You Can Hold. This lesson also uses a stack, explained below.
In the last lesson, each of the dispatcher's actions became an object you can hold. This lesson uses that. The dispatcher gives package 43 to Leo, and then package 42, which Dana had. Then Leo calls: his van is in the shop. Both changes have to come off, in the opposite order to how they went on. An hour later the van is fixed, with room for one package, so one of them goes back on. That's two undos and a redo, and the dispatch board has a single "undo last change" button.
The symptom: undo remembers one change
The board's undo was added in a hurry: the dispatcher remembers the last change it made, in two variables, and puts it back.
Dispatcher dispatcher = new Dispatcher(new DispatchBoard());
dispatcher.Assign(42, "Dana");
dispatcher.Assign(43, "Leo");
dispatcher.Assign(42, "Leo");
dispatcher.Undo();
dispatcher.Undo();
dispatcher.ShowBoard();
class Dispatcher
{
private readonly DispatchBoard board;
// Undo remembers the last change only.
private int? lastPackage;
private string? driverBefore;
public Dispatcher(DispatchBoard board) { this.board = board; }
public void Assign(int package, string driver)
{
lastPackage = package;
driverBefore = board.DriverFor(package);
board.Assign(package, driver);
Console.WriteLine( quot;Assign package {package} to {driver}");
}
public void Undo()
{
if (lastPackage is not int package) { Console.WriteLine("Nothing to undo"); return; }
if (driverBefore == null) { board.Unassign(package); }
else { board.Assign(package, driverBefore); }
Console.WriteLine( quot;Undo: package {package} back to {driverBefore ?? "nobody"}");
lastPackage = null;
}
public void ShowBoard() => Console.WriteLine(board.Describe());
}
class DispatchBoard
{
private readonly SortedDictionary<int, string> drivers = new SortedDictionary<int, string>();
public string? DriverFor(int package) => drivers.TryGetValue(package, out string? driver) ? driver : null;
public void Assign(int package, string driver) => drivers[package] = driver;
public void Unassign(int package) => drivers.Remove(package);
public string Describe() => "Board: " + string.Join(", ", drivers.Select(pair => quot;package {pair.Key} with {pair.Value}"));
}
Assign package 42 to Dana
Assign package 43 to Leo
Assign package 42 to Leo
Undo: package 42 back to Dana
Nothing to undo
Board: package 42 with Dana, package 43 with Leo
class DispatchBoard {
private final TreeMap<Integer, String> drivers = new TreeMap<>();
String driverFor(int pkg) { return drivers.get(pkg); }
void assign(int pkg, String driver) { drivers.put(pkg, driver); }
void unassign(int pkg) { drivers.remove(pkg); }
String describe() {
List<String> lines = new ArrayList<>();
drivers.forEach((pkg, driver) -> lines.add("package " + pkg + " with " + driver));
return "Board: " + String.join(", ", lines);
}
}
class Dispatcher {
private final DispatchBoard board;
// Undo remembers the last change only.
private Integer lastPackage = null;
private String driverBefore = null;
Dispatcher(DispatchBoard board) { this.board = board; }
void assign(int pkg, String driver) {
lastPackage = pkg;
driverBefore = board.driverFor(pkg);
board.assign(pkg, driver);
IO.println("Assign package " + pkg + " to " + driver);
}
void undo() {
if (lastPackage == null) { IO.println("Nothing to undo"); return; }
if (driverBefore == null) { board.unassign(lastPackage); }
else { board.assign(lastPackage, driverBefore); }
IO.println("Undo: package " + lastPackage + " back to " + (driverBefore == null ? "nobody" : driverBefore));
lastPackage = null;
}
void showBoard() { IO.println(board.describe()); }
}
void main() {
Dispatcher dispatcher = new Dispatcher(new DispatchBoard());
dispatcher.assign(42, "Dana");
dispatcher.assign(43, "Leo");
dispatcher.assign(42, "Leo");
dispatcher.undo();
dispatcher.undo();
dispatcher.showBoard();
}
Assign package 42 to Dana
Assign package 43 to Leo
Assign package 42 to Leo
Undo: package 42 back to Dana
Nothing to undo
Board: package 42 with Dana, package 43 with Leo
class DispatchBoard:
def __init__(self):
self.drivers = {}
def driver_for(self, package):
return self.drivers.get(package)
def assign(self, package, driver):
self.drivers[package] = driver
def unassign(self, package):
del self.drivers[package]
def describe(self):
return "Board: " + ", ".join(f"package {p} with {self.drivers[p]}" for p in sorted(self.drivers))
class Dispatcher:
def __init__(self, board):
self.board = board
# Undo remembers the last change only.
self.last_package = None
self.driver_before = None
def assign(self, package, driver):
self.last_package = package
self.driver_before = self.board.driver_for(package)
self.board.assign(package, driver)
print(f"Assign package {package} to {driver}")
def undo(self):
if self.last_package is None:
print("Nothing to undo")
return
if self.driver_before is None:
self.board.unassign(self.last_package)
else:
self.board.assign(self.last_package, self.driver_before)
print(f"Undo: package {self.last_package} back to {self.driver_before or 'nobody'}")
self.last_package = None
def show_board(self):
print(self.board.describe())
dispatcher = Dispatcher(DispatchBoard())
dispatcher.assign(42, "Dana")
dispatcher.assign(43, "Leo")
dispatcher.assign(42, "Leo")
dispatcher.undo()
dispatcher.undo()
dispatcher.show_board()
Assign package 42 to Dana
Assign package 43 to Leo
Assign package 42 to Leo
Undo: package 42 back to Dana
Nothing to undo
Board: package 42 with Dana, package 43 with Leo
class DispatchBoard {
#drivers = new Map();
driverFor(pkg) { return this.#drivers.get(pkg) ?? null; }
assign(pkg, driver) { this.#drivers.set(pkg, driver); }
unassign(pkg) { this.#drivers.delete(pkg); }
describe() {
const pkgs = [...this.#drivers.keys()].sort((a, b) => a - b);
return "Board: " + pkgs.map((pkg) => `package ${pkg} with ${this.#drivers.get(pkg)}`).join(", ");
}
}
class Dispatcher {
// Undo remembers the last change only.
#lastPackage = null;
#driverBefore = null;
constructor(board) { this.board = board; }
assign(pkg, driver) {
this.#lastPackage = pkg;
this.#driverBefore = this.board.driverFor(pkg);
this.board.assign(pkg, driver);
console.log(`Assign package ${pkg} to ${driver}`);
}
undo() {
if (this.#lastPackage === null) { console.log("Nothing to undo"); return; }
if (this.#driverBefore === null) { this.board.unassign(this.#lastPackage); }
else { this.board.assign(this.#lastPackage, this.#driverBefore); }
console.log(`Undo: package ${this.#lastPackage} back to ${this.#driverBefore ?? "nobody"}`);
this.#lastPackage = null;
}
showBoard() { console.log(this.board.describe()); }
}
const dispatcher = new Dispatcher(new DispatchBoard());
dispatcher.assign(42, "Dana");
dispatcher.assign(43, "Leo");
dispatcher.assign(42, "Leo");
dispatcher.undo();
dispatcher.undo();
dispatcher.showBoard();
Assign package 42 to Dana
Assign package 43 to Leo
Assign package 42 to Leo
Undo: package 42 back to Dana
Nothing to undo
Board: package 42 with Dana, package 43 with Leo
class DispatchBoard {
#drivers = new Map<number, string>();
driverFor(pkg: number): string | null { return this.#drivers.get(pkg) ?? null; }
assign(pkg: number, driver: string): void { this.#drivers.set(pkg, driver); }
unassign(pkg: number): void { this.#drivers.delete(pkg); }
describe(): string {
const pkgs = [...this.#drivers.keys()].sort((a, b) => a - b);
return "Board: " + pkgs.map((pkg) => `package ${pkg} with ${this.#drivers.get(pkg)}`).join(", ");
}
}
class Dispatcher {
board: DispatchBoard;
// Undo remembers the last change only.
#lastPackage: number | null = null;
#driverBefore: string | null = null;
constructor(board: DispatchBoard) { this.board = board; }
assign(pkg: number, driver: string): void {
this.#lastPackage = pkg;
this.#driverBefore = this.board.driverFor(pkg);
this.board.assign(pkg, driver);
console.log(`Assign package ${pkg} to ${driver}`);
}
undo(): void {
if (this.#lastPackage === null) { console.log("Nothing to undo"); return; }
if (this.#driverBefore === null) { this.board.unassign(this.#lastPackage); }
else { this.board.assign(this.#lastPackage, this.#driverBefore); }
console.log(`Undo: package ${this.#lastPackage} back to ${this.#driverBefore ?? "nobody"}`);
this.#lastPackage = null;
}
showBoard(): void { console.log(this.board.describe()); }
}
const dispatcher = new Dispatcher(new DispatchBoard());
dispatcher.assign(42, "Dana");
dispatcher.assign(43, "Leo");
dispatcher.assign(42, "Leo");
dispatcher.undo();
dispatcher.undo();
dispatcher.showBoard();
Assign package 42 to Dana
Assign package 43 to Leo
Assign package 42 to Leo
Undo: package 42 back to Dana
Nothing to undo
Board: package 42 with Dana, package 43 with Leo
The first undo worked: 42 went back to Dana. The second found nothing, so package 43 is still with Leo, whose van is in the shop. And there's no redo at all, so when the van is fixed, the dispatcher has to remember what she did and do it again by hand.
- The symptom: undo that remembers one change in a few variables, so a second undo does nothing, and there's no redo.
- The cause: the dispatcher's actions are gone once they've run. The two variables are a stand-in for one action, so there's room for only one.
What would you try?
Remember the last two changes instead of one, in four variables. The dispatcher will want three.
Save a copy of the whole board before every change, and put a copy back to undo. It works, and for a small board it's even simple. But it copies everything to take back one line, and it can't say what each undo did. (Saving whole snapshots has its own pattern, which Pass 3 meets.)
Ask the dispatcher to fix mistakes by hand. To fix one, she has to know what was there before, which is exactly what the app forgot.
What we want is a list of the actions themselves, newest last, where each one knows how to take itself back.
A stack, in a paragraph
Think of a stack of plates in a cupboard. You put a clean plate on top, and you take a plate from the top; you never pull one from the middle. In code, a stack is a list used only that way: push adds an item to the top, and pop takes the top item off and hands it to you. So the last item pushed is always the first one popped, which is called last in, first out. That's exactly the order undo needs: the last thing done is the first thing taken back.

Every language has one: C#'s Stack<T> and Java's ArrayDeque have Push and Pop (push and pop in Java), and in Python, JavaScript and TypeScript a plain list or array does it with append/push and pop.
The fix: commands that take themselves back, and two stacks
Each command gets a second method, Undo. To take itself back, AssignPackage needs to know who had the package before, so Execute saves it first. An UndoHistory keeps two stacks. Running a command executes it and pushes it on the undo stack. Undo pops the undo stack, undoes that command and pushes it on the redo stack. Redo pops the redo stack, executes the command again and pushes it back on the undo stack. And a brand-new action empties the redo stack, because "redo" no longer makes sense once something new has happened.

DispatchBoard board = new DispatchBoard();
UndoHistory undoHistory = new UndoHistory();
undoHistory.Run(new AssignPackage(board, 42, "Dana"));
undoHistory.Run(new AssignPackage(board, 43, "Leo"));
undoHistory.Run(new AssignPackage(board, 42, "Leo"));
undoHistory.Undo();
undoHistory.Undo();
Console.WriteLine(board.Describe());
undoHistory.Redo();
Console.WriteLine(board.Describe());
interface IDispatchCommand
{
void Execute();
void Undo();
string Describe();
}
class AssignPackage : IDispatchCommand
{
private readonly DispatchBoard board;
private readonly int package;
private readonly string driver;
private string? driverBefore;
public AssignPackage(DispatchBoard board, int package, string driver)
{
this.board = board; this.package = package; this.driver = driver;
}
public void Execute()
{
driverBefore = board.DriverFor(package); // what it needs to take itself back
board.Assign(package, driver);
}
public void Undo()
{
if (driverBefore == null) { board.Unassign(package); }
else { board.Assign(package, driverBefore); }
}
public string Describe() => quot;Assign package {package} to {driver}";
}
// Two stacks: what can be undone, and what can be redone.
class UndoHistory
{
private readonly Stack<IDispatchCommand> undoStack = new Stack<IDispatchCommand>();
private readonly Stack<IDispatchCommand> redoStack = new Stack<IDispatchCommand>();
public void Run(IDispatchCommand command)
{
command.Execute();
undoStack.Push(command);
redoStack.Clear(); // something new happened, so the old redos no longer fit
Console.WriteLine(command.Describe());
}
public void Undo()
{
if (undoStack.Count == 0) { Console.WriteLine("Nothing to undo"); return; }
IDispatchCommand command = undoStack.Pop();
command.Undo();
redoStack.Push(command);
Console.WriteLine("Undo: " + command.Describe());
}
public void Redo()
{
if (redoStack.Count == 0) { Console.WriteLine("Nothing to redo"); return; }
IDispatchCommand command = redoStack.Pop();
command.Execute();
undoStack.Push(command);
Console.WriteLine("Redo: " + command.Describe());
}
}
class DispatchBoard
{
private readonly SortedDictionary<int, string> drivers = new SortedDictionary<int, string>();
public string? DriverFor(int package) => drivers.TryGetValue(package, out string? driver) ? driver : null;
public void Assign(int package, string driver) => drivers[package] = driver;
public void Unassign(int package) => drivers.Remove(package);
public string Describe() => "Board: " + string.Join(", ", drivers.Select(pair => quot;package {pair.Key} with {pair.Value}"));
}
Assign package 42 to Dana
Assign package 43 to Leo
Assign package 42 to Leo
Undo: Assign package 42 to Leo
Undo: Assign package 43 to Leo
Board: package 42 with Dana
Redo: Assign package 43 to Leo
Board: package 42 with Dana, package 43 with Leo
interface DispatchCommand {
void execute();
void undo();
String describe();
}
class DispatchBoard {
private final TreeMap<Integer, String> drivers = new TreeMap<>();
String driverFor(int pkg) { return drivers.get(pkg); }
void assign(int pkg, String driver) { drivers.put(pkg, driver); }
void unassign(int pkg) { drivers.remove(pkg); }
String describe() {
List<String> lines = new ArrayList<>();
drivers.forEach((pkg, driver) -> lines.add("package " + pkg + " with " + driver));
return "Board: " + String.join(", ", lines);
}
}
class AssignPackage implements DispatchCommand {
private final DispatchBoard board;
private final int pkg;
private final String driver;
private String driverBefore = null;
AssignPackage(DispatchBoard board, int pkg, String driver) {
this.board = board; this.pkg = pkg; this.driver = driver;
}
public void execute() {
driverBefore = board.driverFor(pkg); // what it needs to take itself back
board.assign(pkg, driver);
}
public void undo() {
if (driverBefore == null) { board.unassign(pkg); }
else { board.assign(pkg, driverBefore); }
}
public String describe() { return "Assign package " + pkg + " to " + driver; }
}
// Two stacks: what can be undone, and what can be redone.
class UndoHistory {
private final ArrayDeque<DispatchCommand> undoStack = new ArrayDeque<>();
private final ArrayDeque<DispatchCommand> redoStack = new ArrayDeque<>();
void run(DispatchCommand command) {
command.execute();
undoStack.push(command);
redoStack.clear(); // something new happened, so the old redos no longer fit
IO.println(command.describe());
}
void undo() {
if (undoStack.isEmpty()) { IO.println("Nothing to undo"); return; }
DispatchCommand command = undoStack.pop();
command.undo();
redoStack.push(command);
IO.println("Undo: " + command.describe());
}
void redo() {
if (redoStack.isEmpty()) { IO.println("Nothing to redo"); return; }
DispatchCommand command = redoStack.pop();
command.execute();
undoStack.push(command);
IO.println("Redo: " + command.describe());
}
}
void main() {
DispatchBoard board = new DispatchBoard();
UndoHistory undoHistory = new UndoHistory();
undoHistory.run(new AssignPackage(board, 42, "Dana"));
undoHistory.run(new AssignPackage(board, 43, "Leo"));
undoHistory.run(new AssignPackage(board, 42, "Leo"));
undoHistory.undo();
undoHistory.undo();
IO.println(board.describe());
undoHistory.redo();
IO.println(board.describe());
}
Assign package 42 to Dana
Assign package 43 to Leo
Assign package 42 to Leo
Undo: Assign package 42 to Leo
Undo: Assign package 43 to Leo
Board: package 42 with Dana
Redo: Assign package 43 to Leo
Board: package 42 with Dana, package 43 with Leo
class DispatchBoard:
def __init__(self):
self.drivers = {}
def driver_for(self, package):
return self.drivers.get(package)
def assign(self, package, driver):
self.drivers[package] = driver
def unassign(self, package):
del self.drivers[package]
def describe(self):
return "Board: " + ", ".join(f"package {p} with {self.drivers[p]}" for p in sorted(self.drivers))
# Every command keeps the same promise: execute(), undo() and describe().
class AssignPackage:
def __init__(self, board, package, driver):
self.board = board
self.package = package
self.driver = driver
self.driver_before = None
def execute(self):
self.driver_before = self.board.driver_for(self.package) # what it needs to take itself back
self.board.assign(self.package, self.driver)
def undo(self):
if self.driver_before is None:
self.board.unassign(self.package)
else:
self.board.assign(self.package, self.driver_before)
def describe(self):
return f"Assign package {self.package} to {self.driver}"
# Two stacks: what can be undone, and what can be redone.
class UndoHistory:
def __init__(self):
self.undo_stack = []
self.redo_stack = []
def run(self, command):
command.execute()
self.undo_stack.append(command)
self.redo_stack.clear() # something new happened, so the old redos no longer fit
print(command.describe())
def undo(self):
if not self.undo_stack:
print("Nothing to undo")
return
command = self.undo_stack.pop()
command.undo()
self.redo_stack.append(command)
print("Undo: " + command.describe())
def redo(self):
if not self.redo_stack:
print("Nothing to redo")
return
command = self.redo_stack.pop()
command.execute()
self.undo_stack.append(command)
print("Redo: " + command.describe())
board = DispatchBoard()
undo_history = UndoHistory()
undo_history.run(AssignPackage(board, 42, "Dana"))
undo_history.run(AssignPackage(board, 43, "Leo"))
undo_history.run(AssignPackage(board, 42, "Leo"))
undo_history.undo()
undo_history.undo()
print(board.describe())
undo_history.redo()
print(board.describe())
Assign package 42 to Dana
Assign package 43 to Leo
Assign package 42 to Leo
Undo: Assign package 42 to Leo
Undo: Assign package 43 to Leo
Board: package 42 with Dana
Redo: Assign package 43 to Leo
Board: package 42 with Dana, package 43 with Leo
class DispatchBoard {
#drivers = new Map();
driverFor(pkg) { return this.#drivers.get(pkg) ?? null; }
assign(pkg, driver) { this.#drivers.set(pkg, driver); }
unassign(pkg) { this.#drivers.delete(pkg); }
describe() {
const pkgs = [...this.#drivers.keys()].sort((a, b) => a - b);
return "Board: " + pkgs.map((pkg) => `package ${pkg} with ${this.#drivers.get(pkg)}`).join(", ");
}
}
// Every command keeps the same promise: execute(), undo() and describe().
class AssignPackage {
#driverBefore = null;
constructor(board, pkg, driver) { this.board = board; this.pkg = pkg; this.driver = driver; }
execute() {
this.#driverBefore = this.board.driverFor(this.pkg); // what it needs to take itself back
this.board.assign(this.pkg, this.driver);
}
undo() {
if (this.#driverBefore === null) { this.board.unassign(this.pkg); }
else { this.board.assign(this.pkg, this.#driverBefore); }
}
describe() { return `Assign package ${this.pkg} to ${this.driver}`; }
}
// Two stacks: what can be undone, and what can be redone.
class UndoHistory {
#undoStack = [];
#redoStack = [];
run(command) {
command.execute();
this.#undoStack.push(command);
this.#redoStack = []; // something new happened, so the old redos no longer fit
console.log(command.describe());
}
undo() {
if (this.#undoStack.length === 0) { console.log("Nothing to undo"); return; }
const command = this.#undoStack.pop();
command.undo();
this.#redoStack.push(command);
console.log("Undo: " + command.describe());
}
redo() {
if (this.#redoStack.length === 0) { console.log("Nothing to redo"); return; }
const command = this.#redoStack.pop();
command.execute();
this.#undoStack.push(command);
console.log("Redo: " + command.describe());
}
}
const board = new DispatchBoard();
const undoHistory = new UndoHistory();
undoHistory.run(new AssignPackage(board, 42, "Dana"));
undoHistory.run(new AssignPackage(board, 43, "Leo"));
undoHistory.run(new AssignPackage(board, 42, "Leo"));
undoHistory.undo();
undoHistory.undo();
console.log(board.describe());
undoHistory.redo();
console.log(board.describe());
Assign package 42 to Dana
Assign package 43 to Leo
Assign package 42 to Leo
Undo: Assign package 42 to Leo
Undo: Assign package 43 to Leo
Board: package 42 with Dana
Redo: Assign package 43 to Leo
Board: package 42 with Dana, package 43 with Leo
class DispatchBoard {
#drivers = new Map<number, string>();
driverFor(pkg: number): string | null { return this.#drivers.get(pkg) ?? null; }
assign(pkg: number, driver: string): void { this.#drivers.set(pkg, driver); }
unassign(pkg: number): void { this.#drivers.delete(pkg); }
describe(): string {
const pkgs = [...this.#drivers.keys()].sort((a, b) => a - b);
return "Board: " + pkgs.map((pkg) => `package ${pkg} with ${this.#drivers.get(pkg)}`).join(", ");
}
}
interface DispatchCommand {
execute(): void;
undo(): void;
describe(): string;
}
class AssignPackage implements DispatchCommand {
board: DispatchBoard;
pkg: number;
driver: string;
#driverBefore: string | null = null;
constructor(board: DispatchBoard, pkg: number, driver: string) { this.board = board; this.pkg = pkg; this.driver = driver; }
execute(): void {
this.#driverBefore = this.board.driverFor(this.pkg); // what it needs to take itself back
this.board.assign(this.pkg, this.driver);
}
undo(): void {
if (this.#driverBefore === null) { this.board.unassign(this.pkg); }
else { this.board.assign(this.pkg, this.#driverBefore); }
}
describe(): string { return `Assign package ${this.pkg} to ${this.driver}`; }
}
// Two stacks: what can be undone, and what can be redone.
class UndoHistory {
#undoStack: DispatchCommand[] = [];
#redoStack: DispatchCommand[] = [];
run(command: DispatchCommand): void {
command.execute();
this.#undoStack.push(command);
this.#redoStack = []; // something new happened, so the old redos no longer fit
console.log(command.describe());
}
undo(): void {
const command = this.#undoStack.pop();
if (command === undefined) { console.log("Nothing to undo"); return; }
command.undo();
this.#redoStack.push(command);
console.log("Undo: " + command.describe());
}
redo(): void {
const command = this.#redoStack.pop();
if (command === undefined) { console.log("Nothing to redo"); return; }
command.execute();
this.#undoStack.push(command);
console.log("Redo: " + command.describe());
}
}
const board = new DispatchBoard();
const undoHistory = new UndoHistory();
undoHistory.run(new AssignPackage(board, 42, "Dana"));
undoHistory.run(new AssignPackage(board, 43, "Leo"));
undoHistory.run(new AssignPackage(board, 42, "Leo"));
undoHistory.undo();
undoHistory.undo();
console.log(board.describe());
undoHistory.redo();
console.log(board.describe());
Assign package 42 to Dana
Assign package 43 to Leo
Assign package 42 to Leo
Undo: Assign package 42 to Leo
Undo: Assign package 43 to Leo
Board: package 42 with Dana
Redo: Assign package 43 to Leo
Board: package 42 with Dana, package 43 with Leo
Two undos took both of Leo's packages back, newest first: 42 went back to Dana, and 43 went back to nobody. One redo gave 43 to Leo again. Ten undos would work the same way, and UndoHistory doesn't know what an assignment is: an "unassign" or a "swap" command with its own Undo goes on the same stacks.
The modern version: two functions and a label
A command with Execute and Undo is really two functions, plus a label for the log. So UndoHistory can hold those, and each action is written where it's used:
DispatchBoard board = new DispatchBoard();
UndoHistory undoHistory = new UndoHistory();
Assign(42, "Dana");
Assign(43, "Leo");
Assign(42, "Leo");
undoHistory.Undo();
undoHistory.Undo();
Console.WriteLine(board.Describe());
undoHistory.Redo();
Console.WriteLine(board.Describe());
// One action: a label, a way to do it and a way to take it back.
void Assign(int package, string driver)
{
string? driverBefore = board.DriverFor(package);
undoHistory.Run(new Command(
quot;Assign package {package} to {driver}",
() => board.Assign(package, driver),
() => { if (driverBefore == null) { board.Unassign(package); } else { board.Assign(package, driverBefore); } }));
}
record Command(string Description, Action Execute, Action Undo);
class UndoHistory
{
private readonly Stack<Command> undoStack = new Stack<Command>();
private readonly Stack<Command> redoStack = new Stack<Command>();
public void Run(Command command)
{
command.Execute();
undoStack.Push(command);
redoStack.Clear();
Console.WriteLine(command.Description);
}
public void Undo()
{
if (undoStack.Count == 0) { Console.WriteLine("Nothing to undo"); return; }
Command command = undoStack.Pop();
command.Undo();
redoStack.Push(command);
Console.WriteLine("Undo: " + command.Description);
}
public void Redo()
{
if (redoStack.Count == 0) { Console.WriteLine("Nothing to redo"); return; }
Command command = redoStack.Pop();
command.Execute();
undoStack.Push(command);
Console.WriteLine("Redo: " + command.Description);
}
}
class DispatchBoard
{
private readonly SortedDictionary<int, string> drivers = new SortedDictionary<int, string>();
public string? DriverFor(int package) => drivers.TryGetValue(package, out string? driver) ? driver : null;
public void Assign(int package, string driver) => drivers[package] = driver;
public void Unassign(int package) => drivers.Remove(package);
public string Describe() => "Board: " + string.Join(", ", drivers.Select(pair => quot;package {pair.Key} with {pair.Value}"));
}
Assign package 42 to Dana
Assign package 43 to Leo
Assign package 42 to Leo
Undo: Assign package 42 to Leo
Undo: Assign package 43 to Leo
Board: package 42 with Dana
Redo: Assign package 43 to Leo
Board: package 42 with Dana, package 43 with Leo
// One action: a label, a way to do it and a way to take it back.
record Command(String description, Runnable execute, Runnable undo) { }
class DispatchBoard {
private final TreeMap<Integer, String> drivers = new TreeMap<>();
String driverFor(int pkg) { return drivers.get(pkg); }
void assign(int pkg, String driver) { drivers.put(pkg, driver); }
void unassign(int pkg) { drivers.remove(pkg); }
String describe() {
List<String> lines = new ArrayList<>();
drivers.forEach((pkg, driver) -> lines.add("package " + pkg + " with " + driver));
return "Board: " + String.join(", ", lines);
}
}
class UndoHistory {
private final ArrayDeque<Command> undoStack = new ArrayDeque<>();
private final ArrayDeque<Command> redoStack = new ArrayDeque<>();
void run(Command command) {
command.execute().run();
undoStack.push(command);
redoStack.clear();
IO.println(command.description());
}
void undo() {
if (undoStack.isEmpty()) { IO.println("Nothing to undo"); return; }
Command command = undoStack.pop();
command.undo().run();
redoStack.push(command);
IO.println("Undo: " + command.description());
}
void redo() {
if (redoStack.isEmpty()) { IO.println("Nothing to redo"); return; }
Command command = redoStack.pop();
command.execute().run();
undoStack.push(command);
IO.println("Redo: " + command.description());
}
}
DispatchBoard board = new DispatchBoard();
UndoHistory undoHistory = new UndoHistory();
void assign(int pkg, String driver) {
String driverBefore = board.driverFor(pkg);
undoHistory.run(new Command(
"Assign package " + pkg + " to " + driver,
() -> board.assign(pkg, driver),
() -> { if (driverBefore == null) { board.unassign(pkg); } else { board.assign(pkg, driverBefore); } }));
}
void main() {
assign(42, "Dana");
assign(43, "Leo");
assign(42, "Leo");
undoHistory.undo();
undoHistory.undo();
IO.println(board.describe());
undoHistory.redo();
IO.println(board.describe());
}
Assign package 42 to Dana
Assign package 43 to Leo
Assign package 42 to Leo
Undo: Assign package 42 to Leo
Undo: Assign package 43 to Leo
Board: package 42 with Dana
Redo: Assign package 43 to Leo
Board: package 42 with Dana, package 43 with Leo
class DispatchBoard:
def __init__(self):
self.drivers = {}
def driver_for(self, package):
return self.drivers.get(package)
def assign(self, package, driver):
self.drivers[package] = driver
def unassign(self, package):
del self.drivers[package]
def describe(self):
return "Board: " + ", ".join(f"package {p} with {self.drivers[p]}" for p in sorted(self.drivers))
class UndoHistory:
def __init__(self):
self.undo_stack = []
self.redo_stack = []
# A command is a label, a way to do it and a way to take it back.
def run(self, description, execute, undo):
execute()
self.undo_stack.append((description, execute, undo))
self.redo_stack.clear()
print(description)
def undo(self):
if not self.undo_stack:
print("Nothing to undo")
return
command = self.undo_stack.pop()
description, execute, undo = command
undo()
self.redo_stack.append(command)
print("Undo: " + description)
def redo(self):
if not self.redo_stack:
print("Nothing to redo")
return
command = self.redo_stack.pop()
description, execute, undo = command
execute()
self.undo_stack.append(command)
print("Redo: " + description)
board = DispatchBoard()
undo_history = UndoHistory()
def assign(package, driver):
driver_before = board.driver_for(package)
def take_back():
if driver_before is None:
board.unassign(package)
else:
board.assign(package, driver_before)
undo_history.run(f"Assign package {package} to {driver}", lambda: board.assign(package, driver), take_back)
assign(42, "Dana")
assign(43, "Leo")
assign(42, "Leo")
undo_history.undo()
undo_history.undo()
print(board.describe())
undo_history.redo()
print(board.describe())
Assign package 42 to Dana
Assign package 43 to Leo
Assign package 42 to Leo
Undo: Assign package 42 to Leo
Undo: Assign package 43 to Leo
Board: package 42 with Dana
Redo: Assign package 43 to Leo
Board: package 42 with Dana, package 43 with Leo
class DispatchBoard {
#drivers = new Map();
driverFor(pkg) { return this.#drivers.get(pkg) ?? null; }
assign(pkg, driver) { this.#drivers.set(pkg, driver); }
unassign(pkg) { this.#drivers.delete(pkg); }
describe() {
const pkgs = [...this.#drivers.keys()].sort((a, b) => a - b);
return "Board: " + pkgs.map((pkg) => `package ${pkg} with ${this.#drivers.get(pkg)}`).join(", ");
}
}
class UndoHistory {
#undoStack = [];
#redoStack = [];
// A command is a label, a way to do it and a way to take it back.
run(command) {
command.execute();
this.#undoStack.push(command);
this.#redoStack = [];
console.log(command.description);
}
undo() {
if (this.#undoStack.length === 0) { console.log("Nothing to undo"); return; }
const command = this.#undoStack.pop();
command.undo();
this.#redoStack.push(command);
console.log("Undo: " + command.description);
}
redo() {
if (this.#redoStack.length === 0) { console.log("Nothing to redo"); return; }
const command = this.#redoStack.pop();
command.execute();
this.#undoStack.push(command);
console.log("Redo: " + command.description);
}
}
const board = new DispatchBoard();
const undoHistory = new UndoHistory();
function assign(pkg, driver) {
const driverBefore = board.driverFor(pkg);
undoHistory.run({
description: `Assign package ${pkg} to ${driver}`,
execute: () => board.assign(pkg, driver),
undo: () => (driverBefore === null ? board.unassign(pkg) : board.assign(pkg, driverBefore)),
});
}
assign(42, "Dana");
assign(43, "Leo");
assign(42, "Leo");
undoHistory.undo();
undoHistory.undo();
console.log(board.describe());
undoHistory.redo();
console.log(board.describe());
Assign package 42 to Dana
Assign package 43 to Leo
Assign package 42 to Leo
Undo: Assign package 42 to Leo
Undo: Assign package 43 to Leo
Board: package 42 with Dana
Redo: Assign package 43 to Leo
Board: package 42 with Dana, package 43 with Leo
class DispatchBoard {
#drivers = new Map<number, string>();
driverFor(pkg: number): string | null { return this.#drivers.get(pkg) ?? null; }
assign(pkg: number, driver: string): void { this.#drivers.set(pkg, driver); }
unassign(pkg: number): void { this.#drivers.delete(pkg); }
describe(): string {
const pkgs = [...this.#drivers.keys()].sort((a, b) => a - b);
return "Board: " + pkgs.map((pkg) => `package ${pkg} with ${this.#drivers.get(pkg)}`).join(", ");
}
}
// A command is a label, a way to do it and a way to take it back.
type Command = { description: string; execute: () => void; undo: () => void };
class UndoHistory {
#undoStack: Command[] = [];
#redoStack: Command[] = [];
run(command: Command): void {
command.execute();
this.#undoStack.push(command);
this.#redoStack = [];
console.log(command.description);
}
undo(): void {
const command = this.#undoStack.pop();
if (command === undefined) { console.log("Nothing to undo"); return; }
command.undo();
this.#redoStack.push(command);
console.log("Undo: " + command.description);
}
redo(): void {
const command = this.#redoStack.pop();
if (command === undefined) { console.log("Nothing to redo"); return; }
command.execute();
this.#undoStack.push(command);
console.log("Redo: " + command.description);
}
}
const board = new DispatchBoard();
const undoHistory = new UndoHistory();
function assign(pkg: number, driver: string): void {
const driverBefore = board.driverFor(pkg);
undoHistory.run({
description: `Assign package ${pkg} to ${driver}`,
execute: () => board.assign(pkg, driver),
undo: () => (driverBefore === null ? board.unassign(pkg) : board.assign(pkg, driverBefore)),
});
}
assign(42, "Dana");
assign(43, "Leo");
assign(42, "Leo");
undoHistory.undo();
undoHistory.undo();
console.log(board.describe());
undoHistory.redo();
console.log(board.describe());
Assign package 42 to Dana
Assign package 43 to Leo
Assign package 42 to Leo
Undo: Assign package 42 to Leo
Undo: Assign package 43 to Leo
Board: package 42 with Dana
Redo: Assign package 43 to Leo
Board: package 42 with Dana, package 43 with Leo
All three versions print the same lines. In the modern one, the "who had it before" is captured by the functions when the action is made, instead of being saved by Execute. That's fine here, because each action runs the moment it's made. For a plan that runs later, the class version is safer: it looks up "who had it before" when it actually runs.
Where the languages differ. C# has a ready-made Stack<T>; Java's ArrayDeque is its usual stack (the older Stack class still works, but ArrayDeque is recommended). Python, JavaScript and TypeScript use a plain list or array, adding with append or push and removing with pop, which always takes the last item. TypeScript's pop() returns undefined on an empty array, so its UndoHistory checks that instead of the length.
How it got its name
There's no new pattern here: this is the Command pattern doing one of the jobs it's best known for. The original 1994 book lists undo among the reasons the pattern exists. UndoHistory is this course's name for it; you may also see it called a command history or an undo manager.
Where you've already used it
- Ctrl+Z and Ctrl+Y (Cmd+Z and Cmd+Shift+Z on a Mac) in any editor, drawing app or spreadsheet.
- A browser's Back and Forward buttons: two stacks of pages.
- Database migrations that have both an "up" (apply this change) and a "down" (take it back).
When not to use it
- When an action can't be taken back. A text message that's been sent, or a payment that's gone through, can't be undone by the app; offer a new action ("send a correction", "refund") instead of an undo that pretends.
- When the whole state is small and cheap to copy. Saving a copy of a three-field form before each change may be simpler than an undo for every action.
The cost: every command needs a correct Undo, and an undo that's slightly wrong (one that forgets a package had a driver before) is a bug that only shows up after a mistake.
How often you'll meet it: now and then in the apps you write, and every day in the apps you use (our estimate).
Check yourself
2 questions to try on the lesson page.
So what
Undo isn't one variable that remembers the last change. It's a history of actions that each know how to take themselves back, kept on two stacks: the last thing done is the first thing undone, and redo puts it back.