Memento

The Memento Pattern is a behavioral design pattern that allows you to capture the current state of an object and save it externally so it can be restored later—all without exposing the object's internal structure or violating its encapsulation. It is the architectural foundation for undo/redo stacks, history tracking, and transaction checkpointing.

1. Learning Objectives

• Understand how the Memento pattern captures and restores state without breaking the Single Responsibility or Open/Closed principles.
• Learn to enforce encapsulation boundary limits using private nested classes (Java), friend relationships (C++), and underscore naming conventions (Python).
• Differentiate between Memento, Command, and State patterns.
• Analyze the memory trade-offs of storing full state snapshots versus incremental state diffs in memory-sensitive systems.
• Implement a thread-safe, history-limited undo/redo manager.

2. Problem & Naive Solution

Imagine you are building a rich text editor. The editor supports operations like typing text, moving the cursor, and changing font sizes. To make the application user-friendly, you need to implement a history manager that supports the classic Undo (Ctrl+Z) and Redo (Ctrl+Y) operations.

The Naive Solution

To save the editor's state, an external history manager needs to grab the editor's contents and state, store them in a history list, and restore them when needed. A naive implementation directly exposes all internal fields of the editor:

3. Issues with the Naive Approach

• Encapsulation Violation: The Editor must make all of its internal state representation variables public (or provide public getters and setters). Any other class in the application can read or modify the editor's text and cursor coordinates, exposing internal data models.
• Tight Coupling: The EditorHistory class is tightly coupled to the internal variables of Editor. If you rename a variable (e.g., changing cursorX to cursorCol), or add a new attribute (like selectionRange), you must modify the backup and restore logic inside EditorHistory.
• Fragile Integrity: An external caretaker class can inadvertently mutate state variables while restoring, or restore an invalid combination of variables, causing the editor to enter an inconsistent runtime state.

4. Pattern Introduction & UML

The Memento Pattern solves this problem by delegating the responsibility of capturing and restoring state back to the object that owns the state (the Originator). It introduces a third object called the Memento, which is a read-only token representing a snapshot of the originator's state. The Caretaker (history manager) holds the mementos but is strictly blocked from reading or altering the contents inside the memento.

UML Diagram

5. Participants

• Originator (Editor): The object whose state needs to be saved. It creates a Memento containing a snapshot of its current state and uses the Memento to restore its state when requested.
• Memento (EditorMemento): The value object containing the state snapshot. It provides a wide interface to the Originator (allowing full access to its stored properties) and a narrow interface to the Caretaker (allowing no access to the stored state).
• Caretaker (CommandHistory): The client that knows *when* and *why* to save or restore the Originator's state. It manages a stack of Mementos but never accesses or inspects the details within them.

6. Theory: Design Choices & Pattern Comparisons

When implementing state recovery systems, you must make a conscious trade-off between the Memento, Command, and State patterns:

Comparing Memento Undo vs. Command Undo

In a Command-based undo system, the history stack stores the operations performed (e.g., "Insert char 'A' at pos 5"). To undo, the system calls unexecute(), which performs the inverse mathematical operation (e.g., "Delete char at pos 5"). While memory-efficient, this requires complex, bug-prone inverse calculations for every operation. Conversely, Memento-based undo systems save a direct state snapshot. Restoring is as simple as overriding variables, making it highly reliable for complex states but introducing higher memory usage.

7. Syntax & Encapsulation Enforcement

To successfully implement Memento, you must ensure that only the Originator can access the Memento's state. Different languages offer distinct mechanisms to enforce this encapsulation:

• Java (Private Nested Classes): The Memento class is defined as a public or package-private class with only private members, nested inside the Originator. The outer Originator class has full access to the nested class's private members, but other classes cannot access them.
• C++ (Friend Classes): The Memento class defines all its constructors and methods as private, but declares the Originator class as a friend class. This restricts instantiation and inspection privileges solely to the Originator.
• Python (Conventions & Private Attributes): Python does not support language-level access modifiers. Encapsulation is achieved by prefixing the Memento class and its properties with a single underscore (_EditorMemento, _content), indicating they are private internals that external objects must not touch.

8. Step-by-Step Implementation

1. Define the Memento Interface/Reference Type: Create a marker interface or reference type that represents the memento to the caretaker.
2. Design the Originator: Add the state fields to the Originator class, along with the standard mutations.
3. Implement the Memento Nested Class: Make this class immutable (all fields declared final/const). The Memento constructor receives the current values of the Originator's state.
4. Add Save/Restore hooks on the Originator: Create a save() method that instantiates the Memento with its current fields, and a restore(Memento) method that extracts the saved state.
5. Create the Caretaker: Implement the history stack. The Caretaker calls originator.save() before modifying the state and pushes the returned Memento to its history stack. To perform an undo, it pops from the stack and calls originator.restore(memento).

9. Complete Code (Mini Project)

Below is a complete implementation of a text editor application with multiple states (text content, cursor position, and current document theme) and an undo/redo manager.

10. Code Walkthrough

Let's walk through the key components of the Java implementation:

• Nested Class Structure: Notice that EditorMemento is defined directly inside TextEditor. Since EditorMemento's fields and constructor are private, no class other than TextEditor can instantiate it or extract its private attributes.
• Narrow Interface to Caretaker: The HistoryManager receives instances of TextEditor.EditorMemento. However, because it has no access to EditorMemento's internal structure, the history manager is treated as an opaque custodian—it holds the token but cannot inspect it.
• Wide Interface to Originator: Within the TextEditor.restore() method, the outer class reads the private fields (memento.text, memento.cursorX, etc.) directly, enabling seamless state overrides.
• Standard Redo Eviction: Whenever backup() is invoked (meaning the user has typed something new), the redo stack is wiped (redoStack.clear()), ensuring standard, linear branch history.

11. Execution Flow

1. Setup: The caretaker (HistoryManager) binds to the originator (TextEditor).
2. State Modification Prep: Before executing a change (like .type()), the client calls history.backup().
3. Snapshot Creation: history.backup() triggers editor.save(), which creates a new EditorMemento object on the heap containing deep or immutable copies of the editor's text, cursor position, and theme. This Memento is pushed to the caretaker's undoStack.
4. Execution: The editor's state changes.
5. Undo Invocations: The client calls history.undo(). The caretaker saves the current editor state to the redoStack (for potential redo), pops the top memento from the undoStack, and forwards it to editor.restore(previousState).
6. Restoring: The editor extracts the variables directly from the memento, resetting its state.

12. Internal Working (JVM Heap & Stack)

Let's visualize the runtime memory allocation inside the JVM when using the Memento Pattern:

• Originator Reference: The TextEditor instance resides on the heap. Its fields reference primitive values or strings (which are stored in the String Constant Pool or heap).
• Caretaker Reference Stack: The HistoryManager holds a Stack collection object on the heap. The stack elements are object references pointing to different EditorMemento instances.
• Immutable Objects: Since EditorMemento only contains final variables, once it is constructed on the heap, its values cannot be altered. If the caretaker pops an item and restores the originator, and that snapshot is no longer in any list, the garbage collector will mark that memento instance for deletion on its next pass.
• String Reuse: Java's immutable Strings are highly advantageous here. Storing multiple mementos containing strings that do not change avoids duplicating character arrays on the heap, optimizing memory.

13. Complexity Analysis

• Time Complexity:
  • save(): $O(S)$ where $S$ is the size of the state. If copying strings or arrays, it scales with state length. For primitive properties, it is $O(1)$.
  • restore(): $O(S)$ to copy values back to the originator.
  • undo()/redo() stack push/pop: $O(1)$.
• Space Complexity: $O(N \cdot S)$ where $N$ is the number of saved history states and $S$ is the size of each state. If history is unbounded, it can lead to high memory consumption.

14. Best Practices

• Enforce Immutability: Memento states must be immutable. Ensure all fields are private and final, and do not provide setter methods.
• Bound the Caretaker History: Never use an unbounded stack in production. Set a maximum size (e.g., limit history to 50 operations) and eject oldest states using a deque to prevent memory leaks.
• Implement State Serialization: In large desktop apps or game design, serialize the Memento objects to disk or file database to release RAM during long-running sessions.
• Consider Incremental Diffs: If the state size is large (e.g., high-definition canvases or documents), store only the incremental diffs (deltas) between states instead of full snapshots to reduce memory usage.

15. Common Mistakes

• Exposing Public Memento API: Exposing getters/setters on the Memento class, allowing other parts of the application to read and modify the saved states directly.
• Deep Copy Omissions: Saving mutable objects (like arrays or maps) in the Memento without copying them first. If the originator modifies the list after saving, the saved snapshot will change too.
• Heap Overflow: Keeping millions of full-state snapshots in memory indefinitely without setting history limits.

16. Framework & Real-world Usage

• Java Swing Undo/Redo: The swing packages utilize javax.swing.undo.UndoableEdit and UndoManager to capture, track, and restore states of UI components.
• Database Transactions: Databases implement Savepoints. When you create a savepoint in SQL (SAVEPOINT sp1), the transaction manager checkpoints the state. You can revert changes using ROLLBACK TO sp1 without aborting the entire transaction.
• Git Version Control: Git commits act as Mementos. Each commit represents a point-in-time snapshot of the repository, managed by a branch reference history (Caretaker).

17. Interview Discussion

18. Practice Exercises

• Easy: Build a basic calculator with an undo feature that rolls back calculations (add, subtract, multiply, divide).
• Medium: Design a ProfileSettings backup wizard where a user configures their profile across 3 steps. Let them go back to any step to restore previous settings.
• Hard: Implement a multi-state Board Game History manager (like Chess). The board should store positions, active players, and timers, and support traversing back and forth through moves.

19. Challenge Problem

Design an In-Memory Database Transaction Manager. The database contains key-value pairs. Write a system that supports nested transactions:

• begin(): Starts a transaction.
• put(key, value): Inserts or updates a value.
• commit(): Merges the current transaction changes into the database.
• rollback(): Reverts the database state to the point immediately before begin().

Make sure your transaction manager allows nested transactions (e.g., calling begin(), performing writes, starting another transaction, and rolling back only the inner transaction). Use the Memento Pattern to backup database states at transaction boundaries.

20. Summary & Cheat Sheet

21. Quiz

22. Next Lesson Preview

This completes our deep-dive into Behavioral Design Patterns. In the next module, we will explore Module 11 — Concurrency & Multithreading. We will learn how to design thread-safe applications, understand thread execution lifecycles, and handle memory visibility issues in multi-threaded CPU environments!