Undo/Redo implementation

One way to implement a basic undo/redo feature is to use both the memento and command design patterns.

Memento aims at keeping the state of an object to be restored later for example. This memento should be as small as possible in an optimisation purpose.

The command pattern encapsulates in an object (a command) some instructions to execute when required.

Based on these two concepts you can write a basic undo/redo history, like the following one coded in TypeScript (extracted and adapted from the front-end library Interacto).

Such a history relies on two stacks:

• the stack for objects that can be undone
• the stack for objects that can be redone

Comments are provided within the algorithm. Just note that on an undo operation, the redo stack must be cleared! The reason is to let the application in a stable state: if you go back in past to redo some actions you made, your former actions will not exist any more as you change the future.

export class UndoHistory {
    /** The undoable objects. */
    private readonly undos: Array<Undoable>;

    /** The redoable objects. */
    private readonly redos: Array<Undoable>;

    /** The maximal number of undo. */
    private sizeMax: number;

    public constructor() {
        this.sizeMax = 0;
        this.undos = [];
        this.redos = [];
        this.sizeMax = 30;
    }

    /** Adds an undoable object to the collector. */
    public add(undoable: Undoable): void {
        if (this.sizeMax > 0) {
            // Cleaning the oldest undoable object
            if (this.undos.length === this.sizeMax) {
                this.undos.shift();
            }

            this.undos.push(undoable);
            // You must clear the redo stack!
            this.clearRedo();
        }
    }

    private clearRedo(): void {
        if (this.redos.length > 0) {
            this.redos.length = 0;
        }
    }

    /** Undoes the last undoable object. */
    public undo(): void {
        const undoable = this.undos.pop();
        if (undoable !== undefined) {
            undoable.undo();
            this.redos.push(undoable);
        }
    }

    /** Redoes the last undoable object. */
    public redo(): void {
        const undoable = this.redos.pop();
        if (undoable !== undefined) {
            undoable.redo();
            this.undos.push(undoable);
        }
    }
}

The Undoable interface is quite simple:

export interface Undoable {
    /** Undoes the command */
    undo(): void;
    /** Redoes the undone command */
    redo(): void;
}

You can now write undoable commands that operate on your application.

For example (still based on Interacto examples), you can write a command like this one:

export class ClearTextCmd implements Undoable {
   // The memento that saves the previous state of the text data
   private memento: string;

   public constructor(private text: TextData) {}
   
   // Executes the command
   public execute() void {
     // Creating the memento
     this.memento = this.text.text;
     // Applying the changes (in many 
     // cases do and redo are similar, but the memento creation)
     redo();
   }

   public undo(): void {
     this.text.text = this.memento;
   }

   public redo(): void {
     this.text.text = '';
   }
}

You can now execute and add the command to the UndoHistory instance:

const cmd = new ClearTextCmd(...);
//...
undoHistory.add(cmd);

Finally, you can bind an undo button (or a shortcut) to this history (same thing for redo).

Such examples are detailed on the Interacto documentation page.

Edit:

Note that there exists several undo/redo algorithms. I detailed the classic linear one. For code editors, researchers proposed the 'selective undo algorithm' (research article). Undo/redo algorithms for collaborative editing are also specific (research article).