BlackWaspTM

This web site uses cookies. By using the site you accept the cookie policy.This message is for compliance with the UK ICO law.

Algorithms and Data Structures
.NET 2.0+

Generic Multi-Level Undo and Redo

Most modern software applications include undo and redo features. Undo allows one or more activities to be reverted. Redo allows previous undo actions to be reversed. This article explains how to create a generic, multi-level undo and redo class.

Undo and Redo

Almost all software includes some form of undo functionality. In its most basic form, an undo system allows the last action performed by a user to be cancelled. For example, whilst editing a document a user may accidentally delete a substantial amount of text. Without an undo system this text would need to be retyped. With a single level undo function, the deletion could be reverted and the text would reappear.

A multi-level undo system increases the number of activities that may be reversed. Each important action is recorded internally and the user may invoke the undo function several times to cycle backwards through previous states. Multi-level undo is often paired with a redo command. When an action is undone, the redo function returns the document to the state before the undo. The two functions allow you to move forwards and backwards through the history of a document.

Generic Undo / Redo Class

In this article we will implement a multi-level undo and redo system. It includes a generic class that is a wrapper, or decorator, for another class or structure. This class provides a method that allows you to save the current state of the wrapped object to a history. Further methods allow you to cycle forwards and backwards through the historical states to support undo and redo. The system is based upon the Memento design pattern with the mementos created using binary serialization. This adds one restriction to the types that can be wrapped; they must support binary serialization.

The diagram below shows the classes and interfaces of the undo / redo system:

Multi-Level Undo UML

The UML diagram shows two interfaces and two classes. The interfaces are not required but make automated testing, specifically faking and mocking, much easier. The types are:

  • IUndoable<T>. Defines the interface for wrapping types to support undo and redo functionality.
  • Undoable<T>. Implements the generic wrapper for undoable data. This includes holding the current value and historical undo and redo states.
  • IUndoState<T>. Defines the interface for the mementos that hold historical states. This interface defines a single property that returns the state data. This interface is internal as it should not be used externally to the project.
  • UndoState<T>. Internal class that implements IUndoState<T> using binary serialization to store the state data in a byte array.

Implementing UndoState<T>

Let's start by implementing the internal UndoState<T> class and associated interface. The interface includes a single property that returns the stored state. The type is a generic interface and the State property returns an object of the type defined in the interface's type parameter, "T".

Create the interface as shown below:

internal interface IUndoState<T>
{
    T State { get; }
}

Creating the Class

The Undoable<T> class implements the above interface. Add the class definition and reference to the interface as follows:

internal class UndoState<T> : IUndoState<T>
{
}

When a state is stored, it is serialized to a byte array using binary serialization. This ensures that changes to the original object are not reflected in the historical data. Binary serialization ensures that the entire object graph is stored. You should ensure that the objects that are being wrapped are not so large that the undo states use unnecessarily high levels of memory. To declare the byte array and the BinaryFormatter that will be used for serialization, add the following variables to the class:

BinaryFormatter _formatter;
byte[] _stateData;

You'll also need to add the following using directives:

using System.IO;
using System.Runtime.Serialization.Formatters.Binary;

Constructor

The state in an UndoState object will never change once set. It makes sense to set the state when the object is instantiated. We can use a constructor that accepts the current state in a parameter, initialises the binary formatter and serializes the data into the byte array. This is shown below. Note the use of a memory-based stream for the serialization, as this can be easily converted to an array.

Add the following constructor to the class:

internal UndoState(T state)
{
    _formatter = new BinaryFormatter();
    using (MemoryStream stream = new MemoryStream())
    {
        _formatter.Serialize(stream, state);
        _stateData = stream.ToArray();
    }
}
6 July 2011