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.

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(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 nil.

• 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 nil.

• get_changes: 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. 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.

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

Ruby
Copy to clipboard
1class DocumentHistory
2  def initialize
3    @changes_stack = []
4    @redo_stack = []
5  end
6end

Here, DocumentHistory is the class, and we initialize @changes_stack to act as our stack of applied changes and @redo_stack to act as our stack for undone changes.

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

Ruby
Copy to clipboard
1class DocumentHistory
2  def initialize
3    @changes_stack = []
4    @redo_stack = []
5  end
6
7  def apply_change(change)
8    @changes_stack.push(change)
9    @redo_stack.clear
10  end
11end

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

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

Ruby
Copy to clipboard
1class DocumentHistory
2  def initialize
3    @changes_stack = []
4    @redo_stack = []
5  end
6
7  def apply_change(change)
8    @changes_stack.push(change)
9    @redo_stack.clear
10  end
11
12  def undo
13    return nil if @changes_stack.empty?
14    change = @changes_stack.pop
15    @redo_stack.push(change)
16    change
17  end
18end

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

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

Ruby
Copy to clipboard
1class DocumentHistory
2  def initialize
3    @changes_stack = []
4    @redo_stack = []
5  end
6
7  def apply_change(change)
8    @changes_stack.push(change)
9    @redo_stack.clear
10  end
11
12  def undo
13    return nil if @changes_stack.empty?
14    change = @changes_stack.pop
15    @redo_stack.push(change)
16    change
17  end
18
19  def redo
20    return nil if @redo_stack.empty?
21    change = @redo_stack.pop
22    @changes_stack.push(change)
23    change
24  end
25end

The redo method checks if the @redo_stack is empty. If it is, it returns nil. 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.

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

Ruby
Copy to clipboard
1class DocumentHistory
2  def initialize
3    @changes_stack = []
4    @redo_stack = []
5  end
6
7  def apply_change(change)
8    @changes_stack.push(change)
9    @redo_stack.clear
10  end
11
12  def undo
13    return nil if @changes_stack.empty?
14    change = @changes_stack.pop
15    @redo_stack.push(change)
16    change
17  end
18
19  def redo
20    return nil if @redo_stack.empty?
21    change = @redo_stack.pop
22    @changes_stack.push(change)
23    change
24  end
25
26  def get_changes
27    @changes_stack.dup
28  end
29end

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

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

Ruby
Copy to clipboard
1class DocumentHistory
2  def initialize
3    @changes_stack = []
4    @redo_stack = []
5  end
6
7  def apply_change(change)
8    @changes_stack.push(change)
9    @redo_stack.clear
10  end
11
12  def undo
13    return nil if @changes_stack.empty?
14    change = @changes_stack.pop
15    @redo_stack.push(change)
16    change
17  end
18
19  def redo
20    return nil if @redo_stack.empty?
21    change = @redo_stack.pop
22    @changes_stack.push(change)
23    change
24  end
25
26  def get_changes
27    @changes_stack.dup
28  end
29end

Let's test our DocumentHistory class with an example scenario to showcase its functionality:

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

By walking through this example, you've observed how stacks effectively manage changes in a document's editing history.

Stacks are an excellent choice for managing a document's editing history due to their Last In, First Out (LIFO) behavior. This property allows us to efficiently track the most recent changes and reverse them in the correct order. By using stacks:

• Undo operations become straightforward as the most recent change is always at the top of the stack, ready to be reversed.
• Redo functionality is equally efficient, as undone changes can be stored in another stack and re-applied in the same order they were undone.
• Simplified tracking ensures that we maintain the proper sequence of actions without needing complex data structures or algorithms.

Stacks are lightweight, easy to implement, and provide a clean solution for scenarios requiring reversible or ordered operations, like document editing or browser history navigation.

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!