Memento Pattern In C++

Introduction:

The Memento design pattern is categorized as a behavioral design pattern that serves the purpose of recording and storing an object's internal state. By doing so, it enables the object to revert back to this specific state at a later point without compromising its encapsulation. This design pattern proves to be highly beneficial especially when incorporating features like undo functionalities, checkpoints, or managing the history within your software system.

Approach 1: Basic Approach

Program:

#include <iostream>
#include <string>
#include <vector>
// Memento
class TextMemento {
private:
    std::string text;
public:
    TextMemento(const std::string& text) : text(text) {}
    std::string getText() const {
        return text;
    }
};
// Originator
class TextEditor {
private:
    std::string text;
public:
    void setText(const std::string& newText) {
        text = newText;
    }
    std::string getText() const {
        return text;
    }
    TextMemento createMemento() const {
        return TextMemento(text);
    }
    void restoreMemento(const TextMemento& memento) {
        text = memento.getText();
    }
};
// Caretaker
class UndoManager {
private:
    std::vector<TextMemento> mementos;
public:
    void addMemento(const TextMemento& memento) {
        mementos.push_back(memento);
    }
    TextMemento getMemento(size_t index) const {
        return mementos[index];
    }
};
int main() {
    TextEditor editor;
    UndoManager undoManager;
    editor.setText("Hello, World!");
    // Save current state
    undoManager.addMemento(editor.createMemento());
    // Change state
    editor.setText("Goodbye, World!");
    // Restore previous state
    editor.restoreMemento(undoManager.getMemento(0));
    std::cout << "Text after undo: " << editor.getText() << std::endl;
    return 0;
}

Output:

Text after undo: Hello, World!

Explanation:

• ✅ TextMemento Class: This class represents the memento in the Memento pattern. It holds the state of the TextEditor object at a certain point in time. In this example, it simply stores a string representing the text content.
• ✅ TextEditor Class (Originator): This class represents the originator in the Memento pattern. It's the object whose state needs to be saved and restored. In this example, TextEditor has a member variable text representing the text content. It provides methods to set and get the text content, as well as methods to create and restore mementos.
• ✅ UndoManager Class (Caretaker): This class is responsible for managing mementos. It holds a collection of TextMemento objects. It provides methods to add mementos and retrieve mementos based on an index.
• ✅ Main Function: An instance of TextEditor and UndoManager is created. The text content of the TextEditor is set to "Hello, World!". A memento representing the current state of the TextEditor is created using the createMemento method of TextEditor. This memento is then added to the UndoManager. The text content of the TextEditor is changed to "Goodbye, World!". Finally, the previous state of the TextEditor is restored by retrieving the souvenir from the UndoManager using the getMemento method and passing it to the restoreMemento method of TextEditor. The text content of the TextEditor is then printed, showing that the state has been successfully restored.

Complexity analysis:

Time Complexity:

Generating a keepsake (TextMemento object) requires duplicating the textual information from the TextEditor, with a time complexity of O(n), where n represents the text's length.

Inserting a record into the UndoManager requires adding an item to a vector, with an average time complexity of O(1).

Obtaining a keepsake from the UndoManager based on its index also maintains a time complexity of O(1).

Restoring a memento entails transferring the textual information from the memento back to the TextEditor, with a time complexity of O(n).

Space Complexity:

Creating a memento (TextMemento object) requires O(n) space complexity, with n representing the text length that is being preserved.

The storage requirements for mementos in the UndoManager are influenced by the quantity of mementos saved. In the scenario where there exist m mementos, the space complexity can be described as O(m * n), with n representing the mean length of text contained within each individual memento.

In general, the space efficiency of the solution is primarily determined by the storage requirements for the snapshots within the UndoManager.

Approach 2: Using Serialization/Deserialization

Introduction:

Instead of introducing a distinct TextMemento class to store the TextEditor's state, an alternative approach involves serializing the TextEditor object's state directly into either a string or binary format. Serialization refers to the conversion of an object into a sequence of bytes, with deserialization representing the inverse operation.

To generate a keepsake, serialize the condition of the TextEditor instance into a binary or string format and save it for later retrieval.

To recover the previous state, you will need to deserialize the serialized state and convert it back into a TextEditor object.

Program:

#include <iostream>
#include <string>
#include <sstream>
// Originator
class TextEditor {
private:
    std::string text;
public:
    void setText(const std::string& newText) {
        text = newText;
    }
    std::string getText() const {
        return text;
    }
    std::string createMemento() const {
        // Serialize the state (text content) into a string
        return text;
    }
    void restoreMemento(const std::string& serializedState) {
        // Deserialize the serialized state back into the text content
        text = serializedState;
    }
};
// Caretaker (Not needed in this approach)
int main() {
    TextEditor editor;
    editor.setText("Hello, World!");
    // Save current state by serializing
    std::string memento = editor.createMemento();
    // Change state
    editor.setText("Goodbye, World!");
    // Restore previous state by deserializing
    editor.restoreMemento(memento);
    std::cout << "Text after undo: " << editor.getText() << std::endl;
    return 0;
}

Output:

Text after undo: Hello, World!

Explanation:

• ✅ TextEditor Class (Originator): The TextEditor class represents the originator in the Memento pattern. It has a private member variable text which stores the text content. The setText method allows setting the text content, and the getText method retrieves the current text content. Instead of creating a separate memento class, the createMemento method directly serializes the state (text content) into a string and returns it. The restoreMemento method takes a serialized state (string) as an argument and deserializes it back into the text content of the TextEditor.
• ✅ Main Function: An instance of TextEditor is created. The text content of the TextEditor is set to "Hello, World!" using the setText method. The createMemento method of TextEditor is called to save the current state. The serialized state is stored in a string variable memento. The text content of the TextEditor is changed to "Goodbye, World!" using the setText method. The restoreMemento method of TextEditor is called with the serialized state (memento) as an argument to restore the previous state. Finally, the text content of the TextEditor after undo is printed.

Complexity analysis:

Time Complexity:

Transforming the state of the TextEditor instance into a string requires duplicating the text data, resulting in a time complexity of O(n), where n represents the text's length.

Restoring the serialized state into the TextEditor object includes duplicating the text content, leading to a time complexity of O(n).

Retrieving and updating the text content of the TextEditor object are simple tasks with a constant time complexity of O(1).

In this strategy, the time complexity of operations is mainly influenced by the size of the text data.

Space Complexity:

Serializing the state of the TextEditor object into a string requires O(n) space complexity, where n represents the length of the text content being stored.

Likewise, the space efficiency of reconstructing the serialized state into the TextEditor instance is also O(n).

Storing the serialized state (memento) in a string variable incurs a space complexity of O(n), with n representing the size of the serialized state.

The space requirements of the TextEditor instance and additional variables are insignificant in comparison to the serialized state.

In general, the space efficiency of this method is primarily influenced by the storage space required for maintaining the serialized state.

Approach 3: Using Command Pattern with Undo Stack

Introduction

Instead of directly preserving and restoring the state of the TextEditor, you could implement the Command pattern in conjunction with an undo stack.

Each user interaction (like inputting, removing, or altering text) is wrapped within a command entity. Every command entity is aware of how to execute the action and reverse it.

When a user initiates an operation, a relevant command object is generated and carried out. The state of the command object before execution can act as a memento implicitly.

The performed command instances are kept in an undo stack. To reverse an action, the command instances are removed from the undo stack, and their undo functions are invoked.

Program:

#include <iostream>
#include <string>
#include <stack>
#include <memory> // Include <memory> for std::unique_ptr
// Command Interface
class Command {
public:
    virtual ~Command() {}
    virtual void execute() = 0;
    virtual void undo() = 0;
};
// Concrete Command: Command to set text
class SetTextCommand : public Command {
private:
    std::string newText;
    std::string& oldText;
public:
    SetTextCommand(std::string& oldText, const std::string& newText) : oldText(oldText), newText(newText) {}
    void execute() override {
        oldText = newText;
    }
    void undo() override {
        oldText.swap(newText);
    }
};
// Originator
class TextEditor {
private:
    std::string text;
    std::stack<std::unique_ptr<Command>> undoStack;
public:
    void setText(const std::string& newText) {
        std::unique_ptr<Command> command = std::make_unique<SetTextCommand>(text, newText);
        command->execute();
        undoStack.push(std::move(command));
    }
    void undo() {
        if (!undoStack.empty()) {
            undoStack.top()->undo();
            undoStack.pop();
        }
    }
    std::string getText() const {
        return text;
    }
};
int main() {
    TextEditor editor;
    editor.setText("Hello, World!");
    editor.setText("Goodbye, World!");
    editor.undo();
    std::cout << "Text after undo: " << editor.getText() << std::endl;
    return 0;
}

Output:

Text after undo: Goodbye, World!

Explanation:

• ✅ Command Interface: The Command interface is defined with two pure virtual functions: execute and undo. This interface represents a command that can be executed and undone.
• ✅ Concrete Command: SetTextCommand: SetTextCommand is a concrete implementation of the Command interface. It encapsulates the action of setting text in the TextEditor. It stores the old text content and the new text content. The execute method sets the text content of the TextEditor to the new text. The undo method swaps the old and new text content, effectively undoing the action.
• ✅ TextEditor Class (Originator): The TextEditor class represents the originator in the Memento pattern. It has a private member variable text which stores the text content. It maintains a stack of commands (undoStack) representing executed actions. The setText method creates a SetTextCommand object with the old text and new text, executes the command, and pushes it onto the undoStack. The undo method pops the top command from the undoStack and calls its undo method to revert the action.
• ✅ Main Function: An instance of TextEditor is created. The setText method is called to set the text content to "Hello, World!". Another call to setText changes the text content to "Goodbye, World!". The undo method is called to undo the last action. Finally, the text content of the TextEditor after undo is printed.

Complexity analysis:

Time Complexity:

Creating text content through the setText function requires the instantiation of a SetTextCommand instance, performing the command to establish the text, and adding the command to the undo stack. The time complexity for these actions is O(1).

Reversing a previous action by employing the undo function requires removing the foremost command from the undo stack and executing its undo function. The time complexity for both actions remains constant at O(1).

In general, the time complexity for both applying text changes and reverting actions remains constant, regardless of the size of the text data.

Space Complexity:

The space efficiency of the TextEditor class remains constant since it solely holds a string for the text content and a stack for managing undo commands.

Each individual command object that is kept in the undo stack utilizes extra memory. Nevertheless, given that solely the commands that have been executed are retained, the space complexity of the undo stack is determined by the quantity of executed commands rather than the size of the text data.

Thus, the space efficiency of the undo stack amounts to O(k), with k representing the quantity of commands that have been executed.

The primary factor influencing the space complexity of this implementation is the quantity of commands stored in the undo stack.

Properties of Memento Pattern in C++:

Originator:

• ✅ The Originator is the object whose state needs to be saved and restored. It contains the state that needs to be preserved.
• ✅ In C++, the Originator class typically provides methods to set and get its internal state, as well as methods to create and restore mementos.
• ✅ It's responsible for creating mementos that capture its internal state and for restoring its state from a memento.

Memento:

• ✅ The Memento is an object that holds the state of the Originator. It acts as a snapshot of the Originator's state at a particular point in time.
• ✅ In C++, the Memento class typically provides methods to access and possibly modify the state it holds, but it doesn't expose the internal representation of the state.
• ✅ It's designed to be immutable or to prevent modification of its state after creation, ensuring that the Originator's state remains unchanged.

Caretaker:

• ✅ The Caretaker is responsible for managing mementos. It keeps track of the mementos and provides operations to save and retrieve them.
• ✅ In C++, the Caretaker class may maintain a collection (e.g., a stack or list) of mementos and provide methods to add, retrieve, and possibly remove mementos.
• ✅ It's responsible for deciding when to create mementos and when to restore the Originator's state from a memento.