Generic Memento Pattern for Undo-Redo in C#

• Download source files and project demo - 65.9 KB

Introduction

A useful application normally has a conventional feature called "undo" or "undo-redo". It is extremely handy and I can't imagine a cyber world without undo-redo. With that said, it is not easy to implement undo-redo features. Convenience for users and headache for developers usually refer to the same thing. To my knowledge, there are no .NET libraries that have enough capability to handle all undo-redo cases because this feature is very specific to every single application. The purpose of this article is to generalize undo-redo as much as possible and to suggest implementation methodology.

Background

There is a well known design pattern called Memento. It is a common way of storing and restoring application states. I am not going to talk about that in detail. For more information on Memento pattern or application states, start reading from this article on Wikipedia.

The Memento pattern specifies a state. Translating to C# in the traditional way, we get an interface with one property.

interface IMemento
{
   object State
   {
       get;
   }
}  

The above interface is very generic, but it is too generic to contain essential information. It is pretty much just an object, and doesn't give any hints on what to do with it.

An interface that describes behaviors is usually more useful than those describing properties, because they are more flexible and extensible. So my solution to this is redefining the word Memento as "an object that is capable of restoring a target object to one of its previous states". Let's visualize this statement by translating it to C#.

interface IMemento<T>
{
    /// <summary>
    /// Restores target to the state memorized by this memento.
    /// </summary>
    /// <returns>
    /// A memento of the state before restoring
    /// </returns>
    IMemento<T> Restore(T target);
}

Note that the Restore() method returns an IMemento<T> instance; this is to facilitate redo. The return type can be changed to void if redo doesn't have to be supported.

This simple interface (with a single method) may seem useless to you at first glance. Now let's look into how it can be used to facilitate undo and redo. The following are some code snippets from class UndoRedoHistory<T>.

The Undo() method takes the Memento from the top of undo stack and calls Restore. The returned Memento is then pushed onto the redo stack.

/// <summary>
/// Restores the subject to the previous state on the undo stack,
/// and stores the state before undoing to redo stack.
/// </summary>
public void Undo()
{
    inUndoRedo = true;
    IMemento<T> top = undoStack.Pop();
    redoStack.Push(top.Restore(subject));
    inUndoRedo = false;
} 

The Redo() method is just the opposite of the Undo() method.

/// <summary>
/// Restores the subject to the next state on the redo stack,
/// and stores the state before redoing to undo stack.
/// </summary>
public void Redo()
{
    inUndoRedo = true;
    IMemento<T> top = redoStack.Pop();
    undoStack.Push(top.Restore(subject));
    inUndoRedo = false;
} 

The Do() method registers a Memento so that it can be undone. At the same time, the redo stack is cleared.

 /// <summary>
/// Registers a memento with the history, which can be undone.
/// </summary>
public void Do(IMemento<T> m)
{
    if (inUndoRedo)
        throw new InvalidOperationException(
            "Involking do within an undo/redo action.");
    redoStack.Clear();
    undoStack.Push(m);
} 

Using the code

Now that the undo-redo history is in place, the only thing left is to write concrete implementations of IMemento<T>, which is quite application-dependent.

There are two demo projects written to demonstrate the power of this pattern. They have the same functions and user interfaces. Their difference lies in how undo and redo are implemented. I named them "action based undo-redo" and "serialization based undo-redo" respectively.

Action Based Undo-Redo

Every change made to the tracked object is stored in one memento. Mementos are capable of restoring states by carrying out the inverse action.

history.Do(new AddShapeMemento()); // action: add shape
shapepool.Add(GetShape(e));

history.BeginCompoundDo(); //starts a compound memento
foreach (Shape s in toBeRemoved)
{
    int index = shapepool.IndexOf(s);
    history.Do(new RemoveShapeMemento(index, s)); //action: remove shape
    shapepool.RemoveAt(index);
}
history.EndCompoundDo(); //ends a compound memento

The mechanism is very efficient in memory usage. However, the mementos within the undo-redo history are inter-dependent. If one is corrupted, the entire history gets corrupted. What's worse, it is very tedious to implement, as each single action corresponds to its own Memento subtype.

Serialization Based Undo-Redo

The tracking system doesn't care about what changes are made to the tracked object. Whenever there is a change, it stores the complete state of the object by serializing it.

history.Do(new ShapePoolMemento(shapepool)); //store entire shape pool
shapepool.Add(GetShape(e));

history.Do(new ShapePoolMemento(shapepool)); //store entire shape pool
foreach (Shape s in toBeRemoved)
{
    int index = shapepool.IndexOf(s);
    shapepool.RemoveAt(index);
}

As opposed to action based undo-redo, this method is very easy to implement and the mementos are independent of each other. But it has a fatal pitfall - huge memory consumption, if the tracked object is large. As a result, poor time performance will be observed.

Hybrid Undo-Redo (Conceptual)

As you see in the previous examples, the IMemento<T> interface is really flexible to extend. It is also possible, though I didn't implement a demo project, to create a hybrid undo-redo mechanism that combines the power of the two mechanisms mentioned above. The memory consumption and implementation simplicity should be balanced before making design decisions.

Although I'm trying to list as many implementation methods as possible, I won't be surprised if someone comes up and tells me that there is a totally new and much better way of implementing the IMemento<T> interface. So if you do have any good ideas on this, tell me or just leave a note in the comment area at the bottom.

Points of Interest

Compound Memento

You might have already noticed the two strange methods BeginCompoundDo() and EndCompoundDo() in the previous section. They are used to create an internal CompoundMemento<T>, so that all invocations of Do() method occuring between them are grouped together and treated as a single action.

A CompoundMemento<T> is an IMemento<T> with a wrapper Restore(). See code snippet below.

public class CompoundMemento<T> : IMemento<T>
{
    // ...
    private List<imemento /><t>> mementos;
    // ...
    public IMemento<T> Restore(T target)
    {
        CompoundMemento<T> inverse = new CompoundMemento<T>();
        //starts from the last action
        for (int i = mementos.Count - 1; i >= 0; i--)
            inverse.Add(mementos[i].Restore(target));
        return inverse;
    }
}</imemento />

Controlling Capacity

The size of the undo and redo stacks are usually constrained. Unfortunately System.Collections.Generics.Stack<T> doesn't allow us to control it's capacity. So a generic class named RoundStack<T> was implemented for this purpose. It is round as the name suggests. The bottom items of the stack are trimmed off automatically when the capacity exceeds the predefined limit. Space and time overhead is almost zero. Note that no thread safety is ensured, which may be updated later.

History

• 15 March 2007 - First Draft