Managing Document Editing History Using Stacks in Java

Lesson 5

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.

applyChange(String 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 a 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.

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. First, we define our class and set up the initial state.

Java
1import java.util.Stack;
2
3class DocumentHistory {
4    private Stack<String> changesStack;
5    private Stack<String> redoStack;
6
7    public DocumentHistory() {
8        changesStack = new Stack<>();
9        redoStack = new Stack<>();
10    }
11}
12
13public class Solution {
14    public static void main(String[] args) {
15        DocumentHistory documentHistory = new DocumentHistory();
16        System.out.println("DocumentHistory initialized.");
17    }
18}

Here, DocumentHistory is the class, and we initialize a Stack<String> named changesStack to act as our stack of applied changes and another Stack<String> named redoStack to act as our stack for undone changes.

Step 2: Implement the applyChange Method

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

Java
1import java.util.Stack;
2
3class DocumentHistory {
4    private Stack<String> changesStack;
5    private Stack<String> redoStack;
6
7    public DocumentHistory() {
8        changesStack = new Stack<>();
9        redoStack = new Stack<>();
10    }
11
12    public void applyChange(String change) {
13        changesStack.push(change);
14        redoStack.clear();
15    }
16}
17
18public class Solution {
19    public static void main(String[] args) {
20        DocumentHistory documentHistory = new DocumentHistory();
21        documentHistory.applyChange("Initial text");
22        System.out.println("Change applied.");
23    }
24}

With applyChange, we take the string change and push it to the changesStack stack. Additionally, we clear the redoStack 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.

Java
1import java.util.Stack;
2
3class DocumentHistory {
4    private Stack<String> changesStack;
5    private Stack<String> redoStack;
6
7    public DocumentHistory() {
8        changesStack = new Stack<>();
9        redoStack = new Stack<>();
10    }
11
12    public void applyChange(String change) {
13        changesStack.push(change);
14        redoStack.clear();
15    }
16
17    public String undo() {
18        if (changesStack.isEmpty()) {
19            return null;
20        }
21        String change = changesStack.pop();
22        redoStack.push(change);
23        return change;
24    }
25}
26
27public class Solution {
28    public static void main(String[] args) {
29        DocumentHistory documentHistory = new DocumentHistory();
30        documentHistory.applyChange("Initial text");
31        documentHistory.applyChange("Added more text");
32        String undoneChange = documentHistory.undo();
33        System.out.println(undoneChange != null ? "Undone Change: " + undoneChange : "No change to undo.");
34    }
35}

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

Step 4: Implement the redo Method

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

Java
1import java.util.Stack;
2
3class DocumentHistory {
4    private Stack<String> changesStack;
5    private Stack<String> redoStack;
6
7    public DocumentHistory() {
8        changesStack = new Stack<>();
9        redoStack = new Stack<>();
10    }
11
12    public void applyChange(String change) {
13        changesStack.push(change);
14        redoStack.clear();
15    }
16
17    public String undo() {
18        if (changesStack.isEmpty()) {
19            return null;
20        }
21        String change = changesStack.pop();
22        redoStack.push(change);
23        return change;
24    }
25
26    public String redo() {
27        if (redoStack.isEmpty()) {
28            return null;
29        }
30        String change = redoStack.pop();
31        changesStack.push(change);
32        return change;
33    }
34}
35
36public class Solution {
37    public static void main(String[] args) {
38        DocumentHistory documentHistory = new DocumentHistory();
39        documentHistory.applyChange("Initial text");
40        documentHistory.applyChange("Added more text");
41        String undoneChange = documentHistory.undo();
42        System.out.println(undoneChange != null ? "Undone Change: " + undoneChange : "No change to undo.");
43        
44        String redoneChange = documentHistory.redo();
45        System.out.println(redoneChange != null ? "Redone Change: " + redoneChange : "No change to redo.");
46    }
47}

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.

Step 5: Implement the getChanges Method

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

Java
1import java.util.Stack;
2
3class DocumentHistory {
4    private Stack<String> changesStack;
5    private Stack<String> redoStack;
6
7    public DocumentHistory() {
8        changesStack = new Stack<>();
9        redoStack = new Stack<>();
10    }
11
12    public void applyChange(String change) {
13        changesStack.push(change);
14        redoStack.clear();
15    }
16
17    public String undo() {
18        if (changesStack.isEmpty()) {
19            return null;
20        }
21        String change = changesStack.pop();
22        redoStack.push(change);
23        return change;
24    }
25
26    public String redo() {
27        if (redoStack.isEmpty()) {
28            return null;
29        }
30        String change = redoStack.pop();
31        changesStack.push(change);
32        return change;
33    }
34
35    public String[] getChanges() {
36        return changesStack.toArray(new String[0]);
37    }
38}
39
40public class Solution {
41    public static void main(String[] args) {
42        DocumentHistory documentHistory = new DocumentHistory();
43        documentHistory.applyChange("Initial text");
44        documentHistory.applyChange("Added more text");
45        
46        documentHistory.undo();
47        documentHistory.redo();
48        
49        String[] changes = documentHistory.getChanges();
50        System.out.println("Changes: " + String.join(", ", changes));
51    }
52}

The getChanges method simply returns an array of all elements in the changesStack, which includes all changes applied to the document in the order they were applied.

Here, changesStack.toArray(new String[0]) is used to convert the stack to an array of String. This approach uses new String[0] as a zero-length array, allowing the toArray method to dynamically allocate an array of the appropriate size. By passing a zero-length array, Java's toArray internally optimizes by allocating an array of the required size, which can lead to slight performance improvements compared to using an array of a different length.

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