Undolist List with transparent Undo & Redo functionality

It’s been two months, but I finally found some time to post something in this blog :)

Background

As a programming exercise for the University we have to create a simple Paint-like program in C#. It has some tools (lines, rectangles, ellipses, text), it must be able to save/load to a custom format that represents the current drawing and it must be able to export to common image formats.

As representation of the current sketch I use a List<T> structure. The objects that were last added to the list are draw ‘above’ objects added previously. A bonus task was to add an Undo/Redo functionality, which I will explain in this post.

Objectives

What I wanted to create was a transparent data structure that could just replace the existing List<T> structure, without having to add additional statements to keep the Undo/Redo state. Furthermore the structure should be usable in a wide variety of cases.

What I did (summary)

First I created a class that represents the List<T> functionality called UndoList<T>. This class has a private class called UndoAction<U>, which represents something that happened to the original list. The UndoList<T> class has a List<UndoAction<T>> member that represents the stack of changes. To be able to provide a Redo functionality, there is a pointer member that points to the last change (I will come to this later).

UndoAction

This class is very simple. It contains the action performed (ActionType) and the actual object that was Added/Removed:

private class UndoAction<U>
{
    public ActionType Type { get; private set; }
    public U Value { get; private set; }

    public UndoAction(ActionType type, U value)
    {
        this.Type = type;
        this.Value = value;
    }
}

UndoList

This class has to be able to do the simple list operations: list[i], list.Add(), list.RemoveAt() and List.Clear(). These functionalities are very easy to implement:

public void Add(T value)
{
    list.Add(value); //add the value to the actual list
    addUndoAction(new UndoAction<T>(ActionType.Add, value)); //add an entry to the Undo list
}

public void RemoveAt(int index)
{
    addUndoAction(new UndoAction<T>(ActionType.Remove, list[index]));
    list.RemoveAt(index);
}

public void Clear()
{
    foreach (T value in list)
        addUndoAction(new UndoAction<T>(ActionType.Remove, value));
    list.Clear();
}

public T this[int index]
{
    get
    {
        return list[index];
    }
    set
    {
        list[index] = value;
    }
}

To provide the functionality of the foreach loop, UndoList<T> needs to be a subclass of System.Collections.IEnumerable. Implementing this interface is really easy for us: we simply return the Enumerator of the actual List<T> member which contains the representation of the sketch.

Implementing the IEnumerable interface goes like this:

public class UndoList<T> : IEnumerable
{
    private List<T> list; //the actual list with data

    public IEnumerator GetEnumerator()
    {
        return list.GetEnumerator();
    }

    //other members
}

The pointer member

If we were only required to provide an Undo functionality, we could just use a list with UndoAction<U> entries. When the Undo() function is called, undo the action and remove the last entry of the list. For Redo() to work, we either need to keep track of the Undo’s we did (which comes down to keeping track of a list that is used to keep track of another list) or we need to use a pointer. The pointer member of the UndoList<T> class points to the last action that was added to the List<UndoAction<T>> list. When Undo() is called, the action will be undone and after that the pointer is decreased. We can do this until the pointer equals -1, which means there is no action left to undo. After you called Undo() a few times and you then call Redo(), the pointer will be increased and after that, the action will be applied to the list with data (see Undo() and Redo() functions for code).

Final words

This class is a good example of how templates can be used in a meaningful way and I learned quite some things from it. I made the source available under the MIT License, you can get it here.

This class has very minimal functionality of the List<T> class. Sorting has no Undo/Redo and Clear() makes it look like every element was removed one-by-one. Feel free to improve on this :)

mrexodia