Welcome! Today, we will delve into managing a document's editing history using stacks. Imagine building a text editor; you would need to handle actions like adding text and undoing and redoing those changes. We will see how these features can be efficiently implemented using stacks. By the end of this lesson, you will possess an in-depth understanding of applying stacks in practical scenarios.

Before starting the coding portion, let's dissect the methods we will implement. These methods will manage a document's edit history, allowing us to apply changes, undo them, and redo them effectively.

• applyChange(change): This method applies a change to the document. The change, represented as a string, is stored in a way that allows us to remember the order of applied changes. Any previously undone changes are discarded.
• undo(): This method undoes the most recent change and allows us to store it for possible redo. It returns the change that was undone. If there are no changes available to undo, it returns null.
• redo(): This method redoes the most recent undone change, making it active again. It returns the change that was redone. If there are no changes available to redo, it returns null.
• getChanges(): This method returns an array of all applied changes in the order they were applied.

To implement these methods efficiently, we'll use two stacks. Stacks are ideal for this task due to their LIFO (Last In, First Out) property, where the most recent change is always at the top, making it easy to undo and redo.

Let's break down each method's implementation and study how they interact with the stacks.

First, we define our class and set up the initial state with type annotations.

TypeScript
Copy to clipboard
1class DocumentHistory {
2    private changesStack: string[];
3    private redoStack: string[];
4
5    constructor() {
6        this.changesStack = [];
7        this.redoStack = [];
8    }
9}

Here, DocumentHistory is the class, and we initialize an empty array named changesStack and another named redoStack, each explicitly typed as an array of strings (string[]). These arrays will be used to store the history of applied and undone changes, respectively.

Next, we implement the method to apply changes with appropriate type annotations.

TypeScript
Copy to clipboard
1applyChange(change: string): void {
2    this.changesStack.push(change);
3    this.redoStack = [];
4}
5

With applyChange, we take the string change and push it to the changesStack array. Additionally, we clear the redoStack to ensure that once a new change is applied, any previously undone changes cannot be redone.

Now, we implement the method to undo the most recent change.

TypeScript
Copy to clipboard
1undo(): string | null {
2    if (this.changesStack.length === 0) {
3        return null;
4    }
5    const change: string = this.changesStack.pop()!;
6    this.redoStack.push(change);
7    return change;
8}

Here, undo checks if the changesStack array is empty. If it is, it returns null. Otherwise, it pops the last item from the array, simulating a stack pop operation, pushes it to the redoStack, and returns the undone change.

Now we'll create the method to redo the most recent undone change.

TypeScript
Copy to clipboard
1redo(): string | null {
2    if (this.redoStack.length === 0) {
3        return null;
4    }
5    const change: string = this.redoStack.pop()!;
6    this.changesStack.push(change);
7    return change;
8}

The redo method checks if the redoStack is empty. If it is, it returns null. Otherwise, it pops the last item from the stack, simulating a LIFO operation, pushes it back to the changesStack, and returns the redone change.

Lastly, we implement the method to retrieve all applied changes.

TypeScript
Copy to clipboard
1getChanges(): string[] {
2    // Copying the array to avoid external modifications
3    return [...this.changesStack];
4}
5

The getChanges method simply returns a copy of the changesStack array, which includes all changes applied to the document in the order they were applied. Copying the array avoids external modifications, ensuring that the original changesStack remains intact.

With all the necessary methods implemented, let's test this with an example:

TypeScript
Copy to clipboard
1const docHist: DocumentHistory = new DocumentHistory();
2
3// Apply changes
4docHist.applyChange("Added header");
5docHist.applyChange("Added footer");
6console.log(docHist.getChanges());  // Output: ['Added header', 'Added footer']
7
8// Undo last change
9console.log(docHist.undo());  // Output: "Added footer"
10console.log(docHist.getChanges());  // Output: ['Added header']
11
12// Redo last undone change
13console.log(docHist.redo());  // Output: "Added footer" 
14console.log(docHist.getChanges());  // Output: ['Added header', 'Added footer']
15
16// Undo all changes
17console.log(docHist.undo());  // Output: "Added footer"
18console.log(docHist.undo());  // Output: "Added header"
19console.log(docHist.getChanges());  // Output: []
20
21// Try undoing when no changes are left
22console.log(docHist.undo());  // Output: null
23
24// Redo changes
25console.log(docHist.redo());  // Output: "Added header"
26console.log(docHist.redo());  // Output: "Added footer"
27console.log(docHist.getChanges());  // Output: ['Added header', 'Added footer']
28
29// Try redoing when no changes are left to redo
30console.log(docHist.redo());  // Output: null

In today's lesson, we learned how to manage a document's editing history using stacks with TypeScript's type safety features. We implemented methods to apply changes, undo the last change, redo the most recent undone change, and retrieve all applied changes. This exercise provided us with practical experience in using stacks to efficiently track and revert operations in a real-life scenario. Keep practicing similar challenges to deepen your understanding of data structures in various applications. Fantastic job today, and keep up the good work!