Click here to Skip to main content
Click here to Skip to main content

Generic Memento Pattern for Undo-Redo in C#

, 16 Mar 2007
Rate this:
Please Sign up or sign in to vote.
Improved Memento pattern particularly designed to support undo and redo.

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

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

About the Author

Sean Yixiang Lu
Software Developer
Singapore Singapore
This guy loves computer programming, software design and development. He is interested and specialized in C family languages, especially C#, Java, Objective-C and D Programming Language. Ruby and Python are starting to interest him as well.

Comments and Discussions

 
AnswerRe: VS 2003 .Net 1.1 Sample PinmemberLu Yixiang3-May-07 3:22 
GeneralSimple and Elegant PinmemberPman752-May-07 5:58 
Generalundo-redo for listview Pinmembermm3107-Apr-07 11:25 
AnswerRe: undo-redo for listview PinmemberLu Yixiang14-Apr-07 6:46 
GeneralGreat! PinmemberD_Guidi22-Mar-07 5:42 
GeneralGreat Job PinmemberC#.Net3.022-Mar-07 2:57 
GeneralRe: Great Job PinmemberLu Yixiang22-Mar-07 3:37 
GeneralHybrid undo/redo idea PinmemberLookSharp21-Mar-07 18:26 
Many thanks for the article - I've often wondered about a good way to do undo/redo (but never actually explored the idea).
 
Serialization (generally) outputs a text version of the binary state of the object. Text is nice to manipulate: consider that source code control systems often use file deltas to save only the changes, not the whole text, of a source file check-in.
 
A hybrid Memento could easily do the same: use a good difference engine to identify the inserted / deleted / modified parts of the full text representation of the binary state of the app; and store for each new IMemento the only the (set of) difference(s).
 
A further improvement on memory consumption, at the expense of performance, might be to compress successive mementos. Text often compresses very well - especially when it has a number of characteristic patterns (like XML does, as most applications do with the type information about the objects that are a part of the application's state).
 
A further optimization might be to recognize any hierarchical structure to the data of the application, and instead of maintaining a 'flat' serialized representation of the application, use true objects to contain the "serialization" - as follows:
Any unique data to an element is serialized to text, contained in a "serialization object" that corresponds to that element only;
All contained elements are 'serialized' as distinct objects, that are referenced by their parent object.
 
For example, a Family Tree application, might implement a "Couple" node and a "Person" node; Couple nodes have start and end dates (marriage; divorce or death of one or both partners), plus other node-specific information like images of the two people, the place where the marriage/divorce/etc. was registered, the guests, etc.;
Children of that Couple node are stored as (an ordered, if needed) collection of contained (references to) Person nodes.
Now, any edit to the Couple node only results in a serialized value delta of that node's specific data.
 
How this idea differs from an action oriented Memento (which at first look it appears to resemble) is that it tracks the results of the actions, not the actions themselves.
 
Pure Action Idea
Most (all?) apps have a finite set of actions - represented by mouse actions (drag, click, etc.) and/or menu options.
 
If each possible type of action is implemented by an object - (that derives from IActionable, perhaps and, required, IMemento) that exposes IActionable.Execute(object []Parameters) then the controller (in the model/view/controller pattern) is simply an engine that accepts an IActionable and an array of values (list indexes; mouse positions; mouse button information; etc.) and invokes the object's Execute method.
 
The controller then passes the IActionable object and its parameter array to the History mechanism which, when it needs to undo or redo the action, calls either IMemento.Undo or IMemento.Redo (this saves it from having to know about IActionable, since Redo will call Execute applying the stored parameters).
 
To facilitate Undo I might make the Execute method return an Object that encapsulates the "before touch points" - i.e. the before values of the affected pieces of state that the action is about to change. This would be stored with the Action object and its Execute parameters in the History mechanism.
 
LookSharp
"Use what talents you possess; The woods would be very silent if no birds sang there except those that sang best." (William Blake)
GeneralRe: Hybrid undo/redo idea PinmemberLu Yixiang22-Mar-07 3:38 
GeneralVery nice. PinmemberAndyKernahan15-Mar-07 10:41 
GeneralSimple, Clear, and Immediately Useful PinmemberKeith Rule15-Mar-07 6:44 
AnswerRe: Simple, Clear, and Immediately Useful PinmemberLu Yixiang19-Mar-07 1:58 
GeneralRe: Simple, Clear, and Immediately Useful Pinmembersdfgasdfsfgsdfg22-Mar-07 16:56 
GeneralGood Pinmembernorm .net15-Mar-07 4:42 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web04 | 2.8.140721.1 | Last Updated 16 Mar 2007
Article Copyright 2007 by Sean Yixiang Lu
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid