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.
-
void apply_change(const std::string& change): This method applies a change to the document. Thechange, 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. -
std::optional<std::string> 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 returnsstd::nullopt. -
std::optional<std::string> 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 returnsstd::nullopt. -
std::vector<std::string> get_changes() const: This method returns a list of all applied changes in the order they were applied.
To implement these methods efficiently, we'll use two stacks implemented using vectors. We use vectors to simulate stack behavior due to their dynamic resizing and efficient element insertion/removal from the end. Stacks are ideal 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.
C++1#include <vector> 2#include <string> 3#include <optional> 4 5class DocumentHistory { 6public: 7 DocumentHistory() = default; 8 9private: 10 std::vector<std::string> changes_stack; 11 std::vector<std::string> redo_stack; 12};
Here, DocumentHistory is the class, and we initialize an empty vector named changes_stack to act as our stack of applied changes and another empty vector named redo_stack to act as our stack for undone changes. The #include directives are used for necessary libraries.
Next, we put into effect the method to apply changes.
C++1#include <vector> 2#include <string> 3#include <optional> 4 5class DocumentHistory { 6public: 7 DocumentHistory() = default; 8 9 void apply_change(const std::string& change) { 10 changes_stack.push_back(change); 11 redo_stack.clear(); 12 } 13 14private: 15 std::vector<std::string> changes_stack; 16 std::vector<std::string> redo_stack; 17};
With apply_change, we take a string change and append it to the changes_stack vector. 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.
C++1#include <vector> 2#include <string> 3#include <optional> 4 5class DocumentHistory { 6public: 7 DocumentHistory() = default; 8 9 void apply_change(const std::string& change) { 10 changes_stack.push_back(change); 11 redo_stack.clear(); 12 } 13 14 std::optional<std::string> undo() { 15 if (changes_stack.empty()) { 16 return std::nullopt; 17 } 18 std::string change = changes_stack.back(); 19 changes_stack.pop_back(); 20 redo_stack.push_back(change); 21 return change; 22 } 23 24private: 25 std::vector<std::string> changes_stack; 26 std::vector<std::string> redo_stack; 27};
Here, undo checks if the changes_stack vector is empty. If it is, it returns an empty std::optional. Otherwise, it pops the last item from the vector, simulating a stack pop 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.
C++1#include <vector> 2#include <string> 3#include <optional> 4 5class DocumentHistory { 6public: 7 DocumentHistory() = default; 8 9 void apply_change(const std::string& change) { 10 changes_stack.push_back(change); 11 redo_stack.clear(); 12 } 13 14 std::optional<std::string> undo() { 15 if (changes_stack.empty()) { 16 return std::nullopt; 17 } 18 std::string change = changes_stack.back(); 19 changes_stack.pop_back(); 20 redo_stack.push_back(change); 21 return change; 22 } 23 24 std::optional<std::string> redo() { 25 if (redo_stack.empty()) { 26 return std::nullopt; 27 } 28 std::string change = redo_stack.back(); 29 redo_stack.pop_back(); 30 changes_stack.push_back(change); 31 return change; 32 } 33 34private: 35 std::vector<std::string> changes_stack; 36 std::vector<std::string> redo_stack; 37};
The redo method checks if the redo_stack is empty. If it is, it returns an empty std::optional. Otherwise, it pops the last item from the vector, 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.
C++1#include <vector> 2#include <string> 3#include <optional> 4#include <algorithm> // to use std::copy 5 6class DocumentHistory { 7public: 8 DocumentHistory() = default; 9 10 void apply_change(const std::string& change) { 11 changes_stack.push_back(change); 12 redo_stack.clear(); 13 } 14 15 std::optional<std::string> undo() { 16 if (changes_stack.empty()) { 17 return std::nullopt; 18 } 19 std::string change = changes_stack.back(); 20 changes_stack.pop_back(); 21 redo_stack.push_back(change); 22 return change; 23 } 24 25 std::optional<std::string> redo() { 26 if (redo_stack.empty()) { 27 return std::nullopt; 28 } 29 std::string change = redo_stack.back(); 30 redo_stack.pop_back(); 31 changes_stack.push_back(change); 32 return change; 33 } 34 35 std::vector<std::string> get_changes() const { 36 return changes_stack; 37 } 38 39private: 40 std::vector<std::string> changes_stack; 41 std::vector<std::string> redo_stack; 42};
The get_changes method simply returns a copy of the changes_stack vector, which includes all changes applied to the document in the order they were applied.
Let's test this final implementation of DocumentHistory with an example:
C++1#include <iostream> 2#include "DocumentHistory.h" 3 4int main() { 5 DocumentHistory doc_hist; 6 7 // Apply changes 8 doc_hist.apply_change("Added header"); 9 doc_hist.apply_change("Added footer"); 10 for (const auto& change : doc_hist.get_changes()) { 11 std::cout << change << std::endl; // Output: Added header, Added footer 12 } 13 14 // Undo last change 15 std::cout << doc_hist.undo().value_or("None") << std::endl; // Output: Added footer 16 for (const auto& change : doc_hist.get_changes()) { 17 std::cout << change << std::endl; // Output: Added header 18 } 19 20 // Redo last undone change 21 std::cout << doc_hist.redo().value_or("None") << std::endl; // Output: Added footer 22 for (const auto& change : doc_hist.get_changes()) { 23 std::cout << change << std::endl; // Output: Added header, Added footer 24 } 25 26 // Undo all changes 27 std::cout << doc_hist.undo().value_or("None") << std::endl; // Output: Added footer 28 std::cout << doc_hist.undo().value_or("None") << std::endl; // Output: Added header 29 for (const auto& change : doc_hist.get_changes()) { 30 std::cout << change << std::endl; // Output: (empty) 31 } 32 33 // Try undoing when no changes are left 34 std::cout << doc_hist.undo().value_or("None") << std::endl; // Output: None 35 36 // Redo changes 37 std::cout << doc_hist.redo().value_or("None") << std::endl; // Output: Added header 38 std::cout << doc_hist.redo().value_or("None") << std::endl; // Output: Added footer 39 for (const auto& change : doc_hist.get_changes()) { 40 std::cout << change << std::endl; // Output: Added header, Added footer 41 } 42 43 // Try redoing when no changes are left to redo 44 std::cout << doc_hist.redo().value_or("None") << std::endl; // Output: None 45 46 return 0; 47}
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!