Click here to Skip to main content
15,860,972 members
Articles / Programming Languages / C#
Article

Generic Memento Pattern for Undo-Redo in C#

Rate me:
Please Sign up or sign in to vote.
4.81/5 (89 votes)
16 Mar 20074 min read 240.9K   5.3K   169   38
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.

C#
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#.

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.

C#
/// <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.

C#
/// <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.

C#
 /// <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.

C#
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.

C#
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.

C#
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


Written By
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!! Pin
Member 1058866125-Mar-14 5:50
Member 1058866125-Mar-14 5:50 
QuestionVery nice contribution, thank you lot. Pin
Member 103452052-Dec-13 7:37
Member 103452052-Dec-13 7:37 
GeneralMy vote of 5 Pin
Alaa Hadid17-Aug-13 7:27
Alaa Hadid17-Aug-13 7:27 
GeneralMy vote of 5 Pin
Pankaj Nikam10-Apr-13 19:48
professionalPankaj Nikam10-Apr-13 19:48 
GeneralUser drawn points with mouse for undo and redo Pin
MrKyaw20-Feb-12 15:08
MrKyaw20-Feb-12 15:08 
NewsImplement Undo in c# vb net Pin
Member 381005018-Dec-10 5:44
Member 381005018-Dec-10 5:44 
GeneralMy vote of 5 Pin
Bigdeak24-Aug-10 21:10
Bigdeak24-Aug-10 21:10 
GeneralExcellent Contribution! Pin
bl_miles3-Jun-10 14:40
bl_miles3-Jun-10 14:40 
GeneralThanks for shareing this code... Pin
rejectkosta19-Apr-10 4:48
rejectkosta19-Apr-10 4:48 
GeneralPretty sure this is the best C# VS2005 compatible Undo/Redo example out there. Pin
jimmyw40428-Oct-09 5:17
jimmyw40428-Oct-09 5:17 
GeneralMemory Leaks Pin
Atul C14-Jan-09 6:01
Atul C14-Jan-09 6:01 
GeneralRe: Memory Leaks Pin
Sean Yixiang Lu14-Jan-09 15:06
Sean Yixiang Lu14-Jan-09 15:06 
I don't think there are leaks. Calling the GC() method doesn't force the garbage collector to actually run the collection.
try minimize your window and restore it again.



Never trust a computer you can't throw out a window.

GeneralRe: Memory Leaks Pin
Atul C20-Jan-09 9:11
Atul C20-Jan-09 9:11 
GeneralTreeView nodes Pin
Gavrilovici Corneliu14-Jul-08 5:29
Gavrilovici Corneliu14-Jul-08 5:29 
QuestionNewbie question Pin
ismirwurscht29-May-07 5:10
ismirwurscht29-May-07 5:10 
AnswerRe: Newbie question [modified] Pin
Sean Yixiang Lu29-May-07 7:24
Sean Yixiang Lu29-May-07 7:24 
GeneralRe: Newbie question Pin
ismirwurscht29-May-07 19:27
ismirwurscht29-May-07 19:27 
GeneralRe: Newbie question Pin
Sean Yixiang Lu29-May-07 20:17
Sean Yixiang Lu29-May-07 20:17 
AnswerRe: Newbie question Pin
ismirwurscht29-May-07 23:47
ismirwurscht29-May-07 23:47 
GeneralRe: Newbie question Pin
neyerMat11-May-12 5:59
neyerMat11-May-12 5:59 
GeneralSmall bug report Pin
Anderson C Gaudio25-May-07 3:48
Anderson C Gaudio25-May-07 3:48 
GeneralRe: Small bug report Pin
Sean Yixiang Lu29-May-07 7:27
Sean Yixiang Lu29-May-07 7:27 
GeneralRe: Small bug report Pin
GeorgeMc5-Nov-12 1:48
GeorgeMc5-Nov-12 1:48 
GeneralVS 2003 .Net 1.1 Sample Pin
Buddhi Dananjaya3-May-07 1:55
Buddhi Dananjaya3-May-07 1:55 
AnswerRe: VS 2003 .Net 1.1 Sample Pin
Sean Yixiang Lu3-May-07 3:22
Sean Yixiang Lu3-May-07 3:22 

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

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