Introduction
Multi-level
undo/redo should be a basic capability for today's software. There are many
ways to implement multi-level undo/redo. However, a general and reusable
mechanism is to use a Command Pattern, information of which could be
found in a famous book, Design Patterns, Elements of Reusable
Object-Oriented Software. Here I'll present an implementation for C++ and
discuss problems when implementing Command Pattern in C++. A sample is
also provided.
The Framework
The
C++ undo/redo framework presented here is composed of two classes: Command and CommandManagerT
(a template class). The two classes are written in C++ and STL.
class Command
Command is an abstract class for a command
(also called an action), it encapsulates user request and states (if
necessary). Its definition is as following:
class Command
{
public:
virtual bool Execute() = 0;
virtual bool Unexecute() = 0;
virtual ~Command() { }
};
The Execute
method of Command class actually executes the user request, and Unexecute
method undoes the operation performed by Execute method.
Derive your subclasses to implement desired commands.
class CommandManager
CommandManager manages the command history. It
contains two stacks, an undo stack and a redo stack.
Every time you need to do a command, you construct a command object and call
CommandManager.DoCommand method, passing the object as the parameter. Call
CommandManager's Undo and Redo methods to undo and redo.
Problems and Solution
A big problem when implement the Command Pattern in programming languages that
have no garbage collection such as C++ is memory management. For example, in
the sample drawing project (will be discussed later), when we need to delete a
glyph from the document, we cannot just call "delete" on the glyph, because it
must remains in memory in order to let undo/redo work correctly (of course, you
can use some mechanisms to overcome this problem, but keep the object in memory
is a more straightforward and simple way). Thus we need a way to manage the
objects. This problem is not unique; many undo/redo applications have similar
conditions.
A general method is to use reference counting on the objects. That is, when more
than one objects reference to an object, the object should remain in memory;
when on objects reference to it, it should be removed from memory. This is also
the way COM uses to manage memory. To grasp how it works, let's see a sample.
In this sample, we'll perform two operations in the drawing program: add a glyph
and then delete it. Let's see step by step.
Step 1:
In the AddCommand, we'll create a new glyph, and then add it to the
document (in the command's Execute method). Now there will be two
objects referencing to the glyph, the document and the add command. See graph below.
Step 2:
Now we delete the glyph. A ClearCommand will be created and it will remove
the glyph from the document in its Execute
method. Now, the document object no longer reference to the object, but the
two command objects reference to it.
To enable reference counting, what we have to do is to add two methods to the
glyph object: AddRef and Release. The calling rule is: when an
object needs to reference to the object, it should call its AddRef method;
when it no longer reference to it, it should call its Release method.
Be careful when using reference counting because it can cause problems that are
not easy to find out. The key is that you must keep a clear mind.
The Sample Project
The sample project is a simple drawing program. When you press left button in the
client rectangle, it will add an ellipse; when you press right button, it'll
add a text label; when you press "Delete" key, it'll delete the last added
glyph. The program supports undo and redo.
Conclusion
In this article, I presented a basic undo/redo framework for C++, and also talked
about problems when implementing undo/redo in C++. The source code and the
sample project are very self-explanatory. Hope you'll find this article
helpful. Happy coding!
