Managing Document Editing History Using Stacks in C++

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

• 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 returns std::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 returns std::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.

#include <vector>
#include <string>
#include <optional>

class DocumentHistory {
public: 
    DocumentHistory() = default;

private:
    std::vector<std::string> changes_stack;
    std::vector<std::string> redo_stack;
};

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.