UndoManager

Undo is more difficult to implement than it appears at first glance.

A typical implementation of an undo manager will store a list of undo data (the UndoList) and a list of redo data (the RedoList).

Undoing an action will pop the last action from the UndoList and push it onto a RedoList. Redo will perform the reverse - pop from the RedoList, push onto the UndoList.

At its simplest, undo / redo data will contain the 'before' and 'after' states of some object in the application, and the function command that will operate on that data.

So for example, if an action adds the next character 'd' to the Collection "MyCollection" (which currently contains 'a', 'b' and 'c'), the undo data might look like this:

Before: Collection c1 = "a, b, c"
After: Collection c2 = "a, b, c, d"
Command: func(Collection before, Collection after)
{
   MyCollection = after;
}

If we ask the undo manager to undo this action, 'func' gets called with 'before = c2', and 'after = c1'. If asked to redo the action, the 'before' and 'after' are switched, so 'before = c1' and 'after = c2'.

Easy, right?

Some questions: How do we create c1 and c2? Are they each a clone of "MyCollection"? What if the collection contains something a bit more complicated than characters, say class objects? What if the objects are collections themselves? Should c1 and c2 be shallow copies or deep copies of MyCollection? How expensive is it to deep copy c1?

In adding 10 items to the collection (say 'a' through 'j'), the first undo action will consist of an empty collection, and a collection containing 'a'. The undo action for adding 'b' to the collection will contain a collection containing an 'a' and a collection containing an 'a' and a 'b'. The next action will contain {'a', 'b'} and {'a', 'b', 'c'}. By the 10th action, there will be 100 items in the undo manager (({}, {a}) + ({a},{a,b}) + ... + ({a..i},{a..j})). Not so bad with characters, but what if you have more complex classes?

And what if those class objects are registered with callbacks elsewhere in the code to have things happen to them in certain situations? Should each instance of the class object in the undo manager remain registered? Should items added to the undo manager have their callbacks revoked and reinstated when the relevant undo / redo command is called?

So instead of storing 'before' and 'after' undo data, an alternative would be to store the data and command required to change the data from the 'before' state to the 'after' state (and the command and data required to change the data back) - 'undo' data and 'redo' data respectively.

So in the character collection example above, the first undo data might look something like this:

UndoData: Item index = 4
RedoData: Character chr = 'd'
UndoCommand: func(UndoData und)
{
   MyCollection.Remove(und.index)
}
RedoCommand: func(RedoData red)
{
   MyCollection.Add(red.chr)
}

Easy, right?

Some thoughts: The UndoCommand is essentially a "delete function", and the RedoCommand is essentially an "add function".

So when creating the "add action", let's pass the "add function" and the "delete function" as the UndoCommand and the RedoCommand respectively.

When creating a "delete action", let's pass the "delete function" and the "add function" as the UndoCommand and the RedoCommand respectively.

So what was 2 functions before the undo manager (the "add action" and the "delete action") has become 4 functions with the undo manager (the "add action", the "add function", the "delete action" and the "delete function").

Every action has been split into a "put these commands into the undo manager" function, and an "execute the action" function. That's a whole lotta work to retro-fit the undomanager into an existing app.

Final situation to think about. How do you undo continuous changes? I use the mouse to drag a UI object from point A to point Z, but before I release the mouse button I've dragged the UI object through every point in between. Do we store every intermediate point in the undo manager, or just the start and end points?

It's a rhetorical question; of course I'm only going to store the start and end points. How?

Without an undo manager, every mouse-move event could simply set the UI object's x and y co-ordinates.

Mouse::Move(int x, int y)
{
   ui_object.SetPosition(x, y);
}

UIObject::SetPosition(int x, int y)
{
   this.X = x;
   this.Y = y;
}

How do we make moving a UI object undoable? We're going to need to split the action up into distinct parts.

While we're dragging the object, we would like to see it being displayed in its current location, so the X and Y values will still need to be changing continuously. What we'll need to do is remember the start location when we begin dragging, and the end location when we finish dragging, then add those locations to the undo manager, along with appropriate functions for setting them.

We end up with something like this:

Mouse::BeginDrag()
{
   Point startPos = ui_object.currentPos;
}

Mouse::Move()
{
   ui_object.SetPosition(x, y);
}

Mouse::EndDrag()
{
   Point endPos = ui_object.currentPos;

   if (startPos != endPos)
   {
      UndoAction act;

      act.UndoData = startPos;
      act.RedoData = endPos;
      act.UndoCommand = UIObject::SetPosition;
      act.RedoCommand = UIObject::SetPosition;
   }
}

So what seems like it should be a simple enough mechanism, actually turns out to be pretty darn complicated...