Lesson 5
Managing Document Editing History with Stacks
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(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.

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.

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

Step 2: Implement the 'apply_change' method

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

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

Step 3: Implement the 'undo' method

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

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

Step 4: Implement the 'redo' method

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

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

Step 5: Implement the 'get_changes' method

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

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

The Final Implementation

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

Ruby
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
Testing the DocumentHistory Class

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

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

Why Stacks

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.

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.