Design Pattern for Undo Engine

I'm writing a structural modeling tool for a civil enginering application. I have one huge model class representing the entire building, which include collections of nodes, line elements, loads, etc. which are also custom classes.

I have already coded an undo engine which saves a deep-copy after each modification to the model. Now I started thinking if I could have coded differently. Instead of saving the deep-copies, I could perhaps save a list of each modifier action with a corresponding reverse modifier. So that I could apply the reverse modifiers to the current model to undo, or the modifiers to redo.

I can imagine how you would carry out simple commands that change object properties, etc. But how about complex commands? Like inserting new node objects to the model and adding some line objects which keep references to the new nodes.

How would one go about implementing that?

Most examples I've seen use a variant of the Command-Pattern for this. Every user-action that's undoable gets its own command instance with all the information to execute the action and roll it back. You can then maintain a list of all the commands that have been executed and you can roll them back one by one.

I think both memento and command are not practical when you are dealing with a model of the size and scope that the OP implies. They would work, but it would be a lot of work to maintain and extend.

For this type of problem, I think you need to build in support to your data model to support differential checkpoints for every object involved in the model. I've done this once and it worked very slick. The biggest thing you have to do is avoid the direct use of pointers or references in the model.

Every reference to another object uses some identifier (like an integer). Whenever the object is needed, you lookup the current definition of the object from a table. The table contains a linked list for each object that contains all the previous versions, along with information regarding which checkpoint they were active for.

Implementing undo/redo is simple: Do your action and establish a new checkpoint; rollback all object versions to the previous checkpoint.

It takes some discipline in the code, but has many advantages: you don't need deep copies since you are doing differential storage of the model state; you can scope the amount of memory you want to use (very important for things like CAD models) by either number of redos or memory used; very scalable and low-maintenance for the functions that operate on the model since they don't need to do anything to implement undo/redo.

If you're talking GoF, the Memento pattern specifically addresses undo.

As others have stated, the command pattern is a very powerful method of implementing Undo/Redo. But there is important advantage I would like to mention to the command pattern.

When implementing undo/redo using the command pattern, you can avoid large amounts of duplicated code by abstracting (to a degree) the operations performed on the data and utilize those operations in the undo/redo system. For example in a text editor cut and paste are complementary commands (aside from the management of the clipboard). In other words, the undo operation for a cut is paste and the undo operation for a paste is cut. This applies to much simpler operations as typing and deleting text.

The key here is that you can use your undo/redo system as the primary command system for your editor. Instead of writing the system such as "create undo object, modify the document" you can "create undo object, execute redo operation on undo object to modify the document".

Now, admittedly, many people are thinking to themselves "Well duh, isn't part of the point of the command pattern?" Yes, but I've seen too many command systems that have two sets of commands, one for immediate operations and another set for undo/redo. I'm not saying that there won't be commands that are specific to immediate operations and undo/redo, but reducing the duplication will make the code more maintainable.

You might want to refer to the Paint.NET code for their undo - they've got a really nice undo system. It's probably a bit simpler than what you'll need, but it might give you some ideas and guidelines.

-Adam