Click here to Skip to main content
Click here to Skip to main content
Go to top

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

Share

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

 
GeneralMost Excellently Done!! PinmemberMember 1058866125-Mar-14 5:50 
QuestionVery nice contribution, thank you lot. PinmemberMember 103452052-Dec-13 7:37 
GeneralMy vote of 5 PinmemberAla Hadid17-Aug-13 7:27 
GeneralMy vote of 5 PinmemberPankaj Nikam10-Apr-13 19:48 
GeneralUser drawn points with mouse for undo and redo PinmemberMrKyaw20-Feb-12 15:08 
NewsImplement Undo in c# vb net PinmemberMember 381005018-Dec-10 5:44 
GeneralMy vote of 5 PinmemberBigdeak24-Aug-10 21:10 
GeneralExcellent Contribution! Pinmemberbl_miles3-Jun-10 14:40 
GeneralThanks for shareing this code... Pinmemberrejectkosta19-Apr-10 4:48 
GeneralPretty sure this is the best C# VS2005 compatible Undo/Redo example out there. Pinmemberjimmyw40428-Oct-09 5:17 
GeneralMemory Leaks PinmemberMember 216081714-Jan-09 6:01 
GeneralRe: Memory Leaks PinmemberLu Yixiang14-Jan-09 15:06 
GeneralRe: Memory Leaks PinmemberMember 216081720-Jan-09 9:11 
I did some more tests. I agree, there are no memory leaks.
Thanks
GeneralTreeView nodes PinmemberGavrilovici Corneliu14-Jul-08 5:29 
QuestionNewbie question Pinmemberismirwurscht29-May-07 5:10 
AnswerRe: Newbie question [modified] PinmemberLu Yixiang29-May-07 7:24 
GeneralRe: Newbie question Pinmemberismirwurscht29-May-07 19:27 
GeneralRe: Newbie question PinmemberLu Yixiang29-May-07 20:17 
AnswerRe: Newbie question Pinmemberismirwurscht29-May-07 23:47 
GeneralRe: Newbie question PinmemberneyerMat11-May-12 5:59 
GeneralSmall bug report PinmemberAnderson C Gaudio25-May-07 3:48 
GeneralRe: Small bug report PinmemberLu Yixiang29-May-07 7:27 
GeneralRe: Small bug report PinmemberGeorgeMc5-Nov-12 1:48 
GeneralVS 2003 .Net 1.1 Sample PinmemberBuddhi Dananjaya3-May-07 1:55 
AnswerRe: VS 2003 .Net 1.1 Sample PinmemberLu Yixiang3-May-07 3:22 

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