Memento

Part of the free Low-Level Design course on LogicWiz, in the chapter: Behavioural patterns III. The class-diagram exercises run in the app.

The Undo button that undid nothing

"I removed the milk by mistake and tapped Undo. The milk did not come back. Is Undo connected to anything?"

Priya, reading a customer message

Undo that restores nothing

SwiftKart's cart screen shows a bar after each change: "Milk removed. UNDO". Product wants the same for tips and coupons. A Cart holds a list of lines, a coupon code and a tip in rupees. A line holds a product code, a quantity and a price in paise (one rupee is 100 paise).

Arjun wrote the undo inside the screen class. Before each change, the screen saves the lines. Undo puts them back. First, the Cart:

public class Cart {
    private List<CartLine> lines = new ArrayList<>();

    public void add(CartLine line) { lines.add(line); }
    public void remove(String sku) { lines.removeIf(l -> l.sku().equals(sku)); }
    public List<CartLine> getLines() { return lines; }
    public void setLines(List<CartLine> lines) { this.lines = lines; }
}

Now the screen, and a run that removes the milk and then undoes it:

public class CartScreen {
    private final Cart cart;
    private List<CartLine> backup;

    public CartScreen(Cart cart) { this.cart = cart; }

    public void remove(String sku) {
        backup = cart.getLines();   // "save" the lines
        cart.remove(sku);
    }

    public void undo() {
        cart.setLines(backup);      // "restore" them
    }
}

        CartScreen screen = new CartScreen(cart);

        screen.remove("MILK");
        System.out.println("after remove: " + cart.getLines().size() + " lines");
        screen.undo();
        System.out.println("after undo:   " + cart.getLines().size() + " lines");

after remove: 1 lines
after undo:   1 lines

Undo did nothing. The cause is the line backup = cart.getLines(). In Java, a variable that holds an object holds a reference, which is an address, not a copy. Two variables with one address point to one list, like two keys to one locker. getLines() hands out the cart's own list, so backup and lines are the same list. When the milk is removed, it disappears from both.

So Arjun made a real copy with new ArrayList<>(cart.getLines()), and saved the coupon too. For this, Cart needs a getter and a setter for every field. Then a teammate added a field, tipRupees, to Cart. Nobody changed the screen:

public class CartScreen {
    private final Cart cart;
    private List<CartLine> backupLines;
    private String backupCoupon;

    public CartScreen(Cart cart) { this.cart = cart; }

    public void checkpoint() {
        backupLines = new ArrayList<>(cart.getLines());
        backupCoupon = cart.getCoupon();
    }

    public void undo() {
        cart.setLines(backupLines);
        cart.setCoupon(backupCoupon);
    }
}

        screen.checkpoint();
        cart.setTipRupees(50);
        screen.undo();
        System.out.println("tip after undo: " + cart.getTipRupees());

tip after undo: 50

The customer set a tip of 50 and tapped Undo. The tip stayed, because the screen copies two fields and does not know about the third. Two problems sit here:

• The screen must know the cart's insides. This breaks encapsulation, the rule that an object hides its fields behind methods (see the encapsulation lesson).
• Every new field needs a change in two places. Forget one and Undo fails with no error.

Only the cart knows all its fields. So the cart should make the copy.

The idea in plain words

Think of a clerk who handles forms. Before you change an important form, the clerk photocopies it and seals the copy in an envelope. She hands the envelope to a filing assistant, who stacks the envelopes in order. He cannot read them, and he does not need to.

When you say "undo", the assistant gives the top envelope back to the clerk. She opens it and puts the form back as it was. Only the clerk opens envelopes, because only she knows what is inside.

Where the picture stops working: a paper envelope can be opened by anyone. In Java, the compiler keeps the seal, but only if we make the contents private. Also, a photocopy costs paper. Every snapshot costs memory.

This is the Memento pattern: an object saves a snapshot of its own state so that it can be restored later, without anyone else seeing inside the snapshot. It has three roles:

• Originator: the object whose state is saved, here Cart. It creates snapshots of itself and restores itself from them.
• Memento: the sealed snapshot. The word means a keepsake. Only the originator can read it, and it never changes after creation.
• Caretaker: the object that keeps the mementos and decides when to save and restore, here UndoHistory. It never opens one.

classDiagram
  class Cart {
    -lines: List~CartLine~
    -coupon: String
    -tipRupees: int
    +save() Memento
    +restore(m: Memento)
  }
  class Memento {
    <<interface>>
  }
  class UndoHistory {
    -undoStack: Deque~Memento~
    -redoStack: Deque~Memento~
    +checkpoint(cart: Cart)
    +undo(cart: Cart) boolean
    +redo(cart: Cart) boolean
  }
  Cart ..> Memento : creates
  UndoHistory o-- Memento : keeps
  UndoHistory ..> Cart : asks to save and restore

The caretaker holds mementos of a type with no methods. It cannot read one even if it tries.

Build it step by step

Step 1: the cart saves and restores itself. The memento is a private record inside Cart. A record is a short class that holds data, with fields that cannot change after creation. The outside world sees only an empty interface called Memento.

public final class Cart {
    /** What the outside world may hold. It has no methods: nobody can read it. */
    public interface Memento { }

    private record Saved(List<CartLine> lines, String coupon, int tipRupees) implements Memento { }

    private final List<CartLine> lines = new ArrayList<>();
    private String coupon = "NONE";
    private int tipRupees = 0;

    public Memento save() {
        return new Saved(List.copyOf(lines), coupon, tipRupees);
    }

    public void restore(Memento memento) {
        Saved saved = (Saved) memento;
        lines.clear();
        lines.addAll(saved.lines());
        coupon = saved.coupon();
        tipRupees = saved.tipRupees();
    }
    // add, remove, applyCoupon and setTip are plain edits
}

save copies the three fields into a new Saved. restore does the reverse. The cast (Saved) memento is safe because only Cart can create a Saved. A class outside Cart that tries to open the envelope gets this:

Snoop.java:3: error: Saved has private access in Cart

The compiler refuses, so the seal is real. Adding a field now means editing Cart and nothing else.

Step 2: make the snapshot immutable. A snapshot must never change. There is a trap. Say a cart line is a normal class with a setQty method, and the snapshot copies the list:

        List<CartLine> lines = new ArrayList<>();
        lines.add(new CartLine("MILK", 1));

        List<CartLine> snapshot = new ArrayList<>(lines);  // a copy of the list

        lines.get(0).setQty(3);                            // the customer edits the quantity
        System.out.println("snapshot says MILK x" + snapshot.get(0).qty());

snapshot says MILK x3

The list was copied, but the line inside it was not. Both lists point to the same line object. This is a shallow copy. When the quantity changed to 3, the snapshot changed with it.

The fix is to make CartLine a record, which nothing can change. Sharing it between the cart and its snapshots is then safe:

public record CartLine(String sku, int qty, long pricePaise) { }

List.copyOf(lines) in step 1 copies the list but shares the lines. That is safe and cheap: a snapshot holds one reference per line, not a copy of each line.

Step 3: the caretaker keeps two stacks. A stack is a list where the last item in is the first item out. The undo stack holds earlier states. The redo stack holds states you undid.

public final class UndoHistory {
    private final Deque<Cart.Memento> undoStack = new ArrayDeque<>();
    private final Deque<Cart.Memento> redoStack = new ArrayDeque<>();
    private final int limit;

    public UndoHistory(int limit) { this.limit = limit; }

    /** Call this just before every edit. */
    public void checkpoint(Cart cart) {
        undoStack.push(cart.save());
        if (undoStack.size() > limit) undoStack.removeLast();   // drop the oldest
        redoStack.clear();                                      // a new edit ends the redo path
    }

    public boolean undo(Cart cart) {
        if (undoStack.isEmpty()) return false;
        redoStack.push(cart.save());        // keep today's state so redo can return to it
        cart.restore(undoStack.pop());
        return true;
    }

    public boolean redo(Cart cart) {
        if (redoStack.isEmpty()) return false;
        undoStack.push(cart.save());
        cart.restore(redoStack.pop());
        return true;
    }
}

Read undo slowly. The caretaker first saves today's state onto the redo stack, then restores the top of the undo stack. That order lets redo return to where you were. In checkpoint, a new edit clears the redo stack, because the undone future no longer follows from what you did next.

Step 4: the screen calls the caretaker before each change.

public final class CartScreen {
    private final Cart cart;
    private final UndoHistory history = new UndoHistory(50);

    public CartScreen(Cart cart) { this.cart = cart; }

    public void remove(String sku) { history.checkpoint(cart); cart.remove(sku); }
    public void setTip(int rupees) { history.checkpoint(cart); cart.setTip(rupees); }
    public void undo() { history.undo(cart); }
    public void redo() { history.redo(cart); }
}

The screen has no copy code and no knowledge of the cart's fields. Remove, undo and redo print:

after remove: 1 lines, coupon NONE, tip 0
after undo:   2 lines, coupon NONE, tip 0
after redo:   1 lines, coupon NONE, tip 0

What it costs, and how to bound it

Every snapshot is a full state. For a cart of 20 lines, that is 20 references, which is small. For an editor with a 1 MB document, it is not. If each of 1,000 edits saves its own 1 MB version, the editor holds about 1,000 MB.

A capped undo stack. Keep the newest N snapshots and drop the oldest. In checkpoint, the line undoStack.removeLast() does this. Here the limit is 3 and the customer makes 5 edits:

        Cart cart = new Cart();
        UndoHistory history = new UndoHistory(3);       // keep only 3 snapshots
        for (int i = 1; i <= 5; i++) {
            history.checkpoint(cart);
            cart.add(new CartLine("ITEM" + i, 1, 1000));
        }
        System.out.println("lines now: " + cart.describe());

        int undone = 0;
        while (history.undo(cart)) undone++;
        System.out.println("undos that worked: " + undone);
        System.out.println("lines now: " + cart.describe());

lines now: 5 lines, coupon NONE, tip 0
undos that worked: 3
lines now: 2 lines, coupon NONE, tip 0

Only 3 undos work, so the two oldest edits stay. Choose N so that one snapshot times N fits your memory budget, and tell users that older steps cannot be undone.

Diffs instead of full copies. A diff stores only what changed, such as "at position 120, the text 'abc' was deleted". This saves memory but costs code: you must compute the diff and apply it both forwards and backwards, and one wrong diff corrupts every later state. You are then storing edits and their reverses, which is command-based undo. For 20 cart lines, full copies are simpler and correct.

Memento or command-based undo?

In a mock round, a candidate said: "Memento and Command undo are the same thing. Both go back a step." They go back in different ways, and that decides which to use. The command lesson undid an action by running its reverse. Here is the same removal that way:

public final class RemoveLineCommand implements CartCommand {
    private final Cart cart;
    private final String sku;
    private int index;          // remembered so undo can put the line back in place
    private CartLine removed;

    public RemoveLineCommand(Cart cart, String sku) { this.cart = cart; this.sku = sku; }

    public void execute() {
        index = cart.indexOf(sku);
        removed = cart.lineAt(index);
        cart.removeAt(index);
    }

    public void undo() { cart.insert(index, removed); }
}

The command must remember the index and the line, and undo must put the line back in the same place. That is easy for one kind of change. For ten kinds, you write ten correct reverses.

Choose Memento when the state is small, many kinds of change need undo, or the reverse of a change is hard to write. A coupon changes prices on many lines through rules, so a restore is far easier than a reverse. Choose Command when the state is large and each edit is small, as in a text editor, or when you need the action log anyway.

💡 Tip: Interviewers accept either answer if you give the reason. Say what is large, the state or the edit, and whether you need a restore or a log.

When not to use Memento. A snapshot restores the object's own fields. It cannot take back what the outside world did. If checkout charged a card, restoring the cart does not refund it. That needs a new action. Also skip it when the state is one number: keep the old value in a variable.

Where it appears in interviews. A text editor with undo and redo is the classic. A game with "undo last move" or a save point snapshots the board. A checkout draft saves the cart, address and delivery slot so a customer can return later. Drafts kept on disk need a version number, so an app update can still read old ones.

Practice: save and restore without peeking

The starter is Arjun's first screen, with backup fields of its own. Add a memento type, give Cart a save and a restore, add a caretaker that keeps mementos, and cut the screen's link to the cart's lines.

📌 Summary: Memento lets an object save and restore itself through a sealed, immutable snapshot that a caretaker stores but cannot read. Cap the history to bound memory. Prefer commands when edits are small and states large.

What Arjun learns next

Undo works. Then finance writes to Priya: they need tax, a handling fee and an invoice over a cart that holds groceries, electronics and gift cards. Each item type is handled differently, and every new report touches every item class. That is the Visitor pattern.

Check your understanding

1. Arjun saves a snapshot with `new ArrayList<>(lines)`. The CartLine class has a setQty method. After the customer changes a quantity, Undo shows the new quantity. Why?
2. A text editor holds a 2 MB document and must allow 500 undo steps. Which design fits best?
3. The customer undoes two steps, then removes a different item. What should the Redo button do?
4. Checkout charges the card, then the customer taps Undo, which restores the cart from a memento. What happens to the charge?