Another Way to Implement Undo and Redo Operations in C and C++

Why I Wrote This

While developing a 3d modelling application for the Windows platform, I got the idea of integrating filestream operations with the undo/redo feature. Like Jacob going to Egypt, it seemed like a good idea at the time, but later it created a lot of problems. Since that time, I've decided that this method, while having its merits, is cumbersome and error-prone. Hence I've written this.

The Problem

Your application maintains a project consisting of multiple interrelated objects. You need an undo function, or else nobody will want to use your application—perhaps not even you. How do you implement it?

A Rather Different Solution from the One Offered in the Other Article I've Written about This

Simply build the ability to maintain object histories into each class. 'Tain't hard.

The general approach

  1. To each object class—that is, the classes for every object maintained in the document—add a list header (called history). You can make this a doubly-linked list if you want, although a singly-linked list will probably work.
  2. Craft a class for each type of object in the project which maintains a single instance of the object's history. Call it ObjHistory. This class should hold all of the data that is directly specified by the user; data that is derived from user settings can be re-derived as needed. In addition, ObjHistory will need a link, an unsigned integer named version for identifying which version of the object this represents, and a typing field to indicate whether this history entry represents the original creation, a modification, or a deletion.
  3. Add the following member functions to each object class:
  4. To the project class, add the following members:

When an object is deleted by user editing, do not delete it from memory, but merely flag it so that commencing with that change, the object is no longer valid, move it to the deleted objects list, and adjust the other objects which refer to it accordingly.

For objects created during an edit, start out with a historical entry that signifies an invalid object.

When the user selects undo:

  1. If curVersion==0, exit the undo function; all changes have been undone.
  2. Call mergeDeleted().
  3. Decrement the curVersion member;
  4. Call restoreVersion(curVersion) for each object.
  5. Call removeDeleted().

When the user selects redo:

  1. If curVersion==highVersion, do nothing; there are no undone changes.
  2. Call mergeDeleted().
  3. Increment the curVersion member;
  4. Call restoreVersion(curVersion) for each object.
  5. Call removeDeleted().

When loading an old project from file, the program should call takeSnapshot(0) for each object. This will force each object to be stored as the oldest version of itself.

You will want to have a way to detect orphan objects, that is, objects which are created, then deleted from the project, and then the user undoes past the edit which created the object, and makes another edit. This last edit will cause all of the undone history to be deleted from memory, resulting in an object flagged as deleted, with only a null entry in its history list. These objects can be deleted from memory (and not just the project). I found that the best time to detect this is inside the takeSnap() call for each object; if the object is flagged as deleted, and the most recent entry is the original dummy entry, flag the object for deletion from memory. Then, in the function which removes deleted objects from the active object lists, check the delete-from-memory flag, and if it's set, delete the object from memory.

Implementation in C

The ObjHistory object

This code fragment gives an overall idea of the needed structure: 


    enum EntryType { ET_NUL, ET_CHG, ET_DEL };

    struct ObjHistory {
        struct doubleLink link;
        unsigned int      histVersion;
        enum EntryType    type;
        struct ObjData    data;
    };

The struct doubleLink link is for making the ObjHistory structure part of a doubly-linked list. I do this because you can remove objects from a doubly-linked list without going through the whole list (or even knowing where the list header is located), which makes encapsulation easier. I suspect that a singly-linked list would probaby work just as well, too.

type records whether the entry marks the time before an object's creation, one of the changes to the object at a given edit, or its deletion from the project.

ObjData is a structure containing all of the data that would be saved to file. It's a good idea to have a like structure in the object itself, so that you can easily copy the data back and forth. The copy in the object is the working copy, and receives all of the edits.

Your data object structures will look like this: 


    struct myObject {
        struct doubleLink           link;
        struct doubleListHeader     history;
        struct ObjData              data;
    };

The link field is for linking the object in the project. The history field is for maintaining the list of historical objects.

Implementation in C++

As can be expected, the major difference is that you can use the various features of C++ to better manage your code. For instance, you can override the assignment operator (=), the comparison operator (== or !=), and probably the constructor and destructor for each ObjData type so that you can centralize the managment of dynamic data in that object.

Other Issues

  • Interdependency is no longer an issue. Objects retain their position in memory—even when they're deleted from the user's viewpoint—and consequently pointers to them do not need to be updated. Objects stay where they are in memory until there is no possible need for them, at which time they are deleted from memory.

    And Now...

    Go back and read the first article on this. That stuff's insane! This second method, methinks, is definitely better. It makes archiving the responsibility of each object, so the functions that handle this on a project level are far, far simpler, while the object-level functions are not particularly more complicated.


    Got comments?

    Send them to John at evilsnack at hotmail dot com

    Return to John's Freeloading Home Page

    Hosted by www.Geocities.ws

    1