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 returnsnil
. -
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 returnsnil
. -
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.
Ruby1class 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.
Ruby1class 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.
Ruby1class 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.
Ruby1class 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.
Ruby1class 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:
Ruby1class 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:
Ruby1doc_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!