Applying Stacks to Document Edit History Management

Lesson 5

Introduction

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, 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.

Introducing Methods

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.

apply_change(self, change: str) -> None: 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(self) -> str | None: 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 None.
redo(self) -> str | None: 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 None.
get_changes(self) -> list[str]: This method returns a list of all applied changes in the order they were applied.

Methods Implementation with Stacks

To implement these methods efficiently, we'll use two stacks. We use stacks to keep track of applied changes and undone changes because of their LIFO (Last In, First Out) property. 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.

Step 1: Define the class and initialize the stacks

Let's implement the solution step-by-step. Firstly, we define our class and set up the initial state.

Python
1class DocumentHistory:
2    def __init__(self):
3        self.changes_stack = []
4        self.redo_stack = []

Here, DocumentHistory is the class, and we initialize an empty list named changes_stack to act as our stack of applied changes and another empty list named redo_stack to act as our stack for undone changes.

Step 2: Implement the 'apply_change' method

Next, we put into effect the method to apply changes.

Python
1class DocumentHistory:
2    def __init__(self):
3        self.changes_stack = []
4        self.redo_stack = []
5
6    def apply_change(self, change: str) -> None:
7        self.changes_stack.append(change)
8        self.redo_stack.clear()

With apply_change, we take a string change and append it to the changes_stack list. Additionally, we clear the redo_stack to ensure that once a new change is applied, any previously undone changes cannot be redone.

Step 3: Implement the 'undo' method

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

Python
1class DocumentHistory:
2    def __init__(self):
3        self.changes_stack = []
4        self.redo_stack = []
5
6    def apply_change(self, change: str) -> None:
7        self.changes_stack.append(change)
8        self.redo_stack.clear()
9    
10    def undo(self) -> str | None:
11        if not self.changes_stack:
12            return None
13        change = self.changes_stack.pop()
14        self.redo_stack.append(change)
15        return change

Here, undo checks if the changes_stack list is empty. If it is, it returns None. Otherwise, it pops the last item from the list, simulating a stack pop operation, pushes it to the redo_stack, and returns the undone change.

Step 4: Implement the 'redo' method

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

Python
1class DocumentHistory:
2    def __init__(self):
3        self.changes_stack = []
4        self.redo_stack = []
5
6    def apply_change(self, change: str) -> None:
7        self.changes_stack.append(change)
8        self.redo_stack.clear()
9    
10    def undo(self) -> str | None:
11        if not self.changes_stack:
12            return None
13        change = self.changes_stack.pop()
14        self.redo_stack.append(change)
15        return change
16
17    def redo(self) -> str | None:
18        if not self.redo_stack:
19            return None
20        change = self.redo_stack.pop()  # Redo the last undone change
21        self.changes_stack.append(change)
22        return change

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

Step 5: Implement the 'get_changes' method

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

Python
1class DocumentHistory:
2    def __init__(self):
3        self.changes_stack = []
4        self.redo_stack = []
5
6    def apply_change(self, change: str) -> None:
7        self.changes_stack.append(change)
8        self.redo_stack.clear()
9    
10    def undo(self) -> str | None:
11        if not self.changes_stack:
12            return None
13        change = self.changes_stack.pop()
14        self.redo_stack.append(change)
15        return change
16
17    def redo(self) -> str | None:
18        if not self.redo_stack:
19            return None
20        change = self.redo_stack.pop()  # Redo the last undone change
21        self.changes_stack.append(change)
22        return change
23
24    def get_changes(self) -> list[str]:
25        return self.changes_stack[:]

The get_changes method simply returns a copy of the changes_stack list, which includes all changes applied to the document in the order they were applied.

The Final Implementation

Here is the final implementation of our DocumentHistory class, combining all the methods we've discussed:

Python
1class DocumentHistory:
2    def __init__(self):
3        self.changes_stack = []
4        self.redo_stack = []
5
6    def apply_change(self, change: str) -> None:
7        self.changes_stack.append(change)
8        self.redo_stack.clear()
9    
10    def undo(self) -> str | None:
11        if not self.changes_stack:
12            return None
13        change = self.changes_stack.pop()
14        self.redo_stack.append(change)
15        return change
16
17    def redo(self) -> str | None:
18        if not self.redo_stack:
19            return None
20        change = self.redo_stack.pop()  # Redo the last undone change
21        self.changes_stack.append(change)
22        return change
23
24    def get_changes(self) -> list[str]:
25        return self.changes_stack[:]

Let's test this with an example:

Python
1doc_hist = DocumentHistory()
2
3# Apply changes
4doc_hist.apply_change("Added header")
5doc_hist.apply_change("Added footer")
6print(doc_hist.get_changes())  # Output: ['Added header', 'Added footer']
7
8# Undo last change
9print(doc_hist.undo())  # Output: "Added footer"
10print(doc_hist.get_changes())  # Output: ['Added header']
11
12# Redo last undone change
13print(doc_hist.redo())  # Output: 'Added footer' 
14print(doc_hist.get_changes())  # Output: ['Added header', 'Added footer']
15
16# Undo all changes
17print(doc_hist.undo())  # Output: 'Added footer'
18print(doc_hist.undo())  # Output: 'Added header'
19print(doc_hist.get_changes())  # Output: []
20
21# Try undoing when no changes are left
22print(doc_hist.undo())  # Output: None
23
24# Redo changes
25print(doc_hist.redo())  # Output: 'Added header'
26print(doc_hist.redo())  # Output: 'Added footer'
27print(doc_hist.get_changes())  # Output: ['Added header', 'Added footer']
28
29# Try redoing when no changes are left to redo
30print(doc_hist.redo())  # Output: None

Summary

In today's lesson, we learned how to manage a document's editing history using stacks. 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!

Enjoy this lesson? Now it's time to practice with Cosmo!

Practice is how you turn knowledge into actual skills.