Integrating Undo and Redo Operations with Project Loading and Saving in C/C++

Why I Wrote This

I'm developing a 3d modelling application for the Windows platform, and soon became aware of the need for an undo/redo function. I did a Google search for whatever articles may exist online on this topic, and came up with nothing useful. 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?

One solution

One solution is to maintain multiple complete versions of the project in memory. While this is an effective solution, for major projects this will be too memory-intensive to be practical (or even possible), and the effect of memory overload on system performance is well-known to any power user.

It's also inefficient. To copy a project of 10,000 objects in order to preserve the prior state of one of those objects is a waste of memory. Which leads us to:

A better solution

You can design the application to record the original state of the project and all subsequent changes, using a series of Delta objects. A Delta object's purpose is to record the changes to a single object in a project.

When implemented effectively, this is a very promising approach. One complicating factor is the presence of inter-object references using memory pointers; for instance, in a modeller I'm working on, each edge has a pointer to its vertices and the faces bordering on that edge, and each face has pointers to the vertices at their corners and the edges along their sides. When an edge is changed, a lot of the cross-references have to be updated, and for multiple levels of changes, keeping track of the cross-referencing will be a major headache.

A satisfactory solution requires that the Deltas make no record of the specific memory locations of cross-referenced objects.

An improved solution

What you need is an way of preserving the old states of objects in a way that inter-object references are symbolic instead of memory-dependent.

This is where the file saving and loading features come in, because they already perform this function. Your application will at some point be equipped to generate a symbolic representation of the data objects, and to interpret these same representations. Therefore you can use this stream format in the Delta objects, and avoid duplication of effort. Essentially, by integrating the functions which load projects, save projects, and add, change, or delete objects, you can easily implement an infinite level of undos and redos.

A solution improved again

It is also very helpful to have a way to group the Delta objects together, so that everything from a single user operation (such as copying a handful of objects) can be affected by the same undo or redo operation.

The solution offered in the first version of this document was the atom Delta, which was a Delta that was placed in the list of Delta objects to mark divisions between logical groups of changes. When implementing the undo/redo function for my 3d modelling application, I found that there were too many opportunities for errors by trying to make each Delta at the exact moment the project data changed.

Part of the problem was that even if a change to an object is well-encapsulated, not all changes require a Delta object. For instance, if I click on vertex and drag it across the screen, each mouse move entails a change to the vertex's location, but only the final location requires a Delta object. Figuring out where these Deltas needed to be and not to be was getting too complicated and led to an enormous number of bugs.

In the new approach, the application takes a snapshot of the project at specific times; each snapshot is stored in what I called a Snap object. Snap objects are kept in a doubly-linked list attached to the object that manages the project. To keep memory use down I implemented a scheme in which only changes from one snapshot to the next were recorded in the latter Snap. The end result was a method that was far easier to debug.

The general approach

1. Assign a unique tag to each object.
2. Have a function which generates the save stream for a given object. If your application saves data to file, you already have this.
3. Have a function which reads the save stream for a given object. Again, if your application saves data to file, you have this, too.
4. Develop a Delta object. The Delta object contains:
   • A linking structure, for keeping it in a linked list;
   • A variable to maintain the type of Delta;
   • A copy of the tag of the data object affected by the Delta;
   • A string containing a save stream for the affected object.
   You need the following types of Deltas:
   • An add Delta, which represents changes that consist of objects being added for the first time;
   • A delete Delta, which represents objects being removed.
5. Develop a Snap object. The Snap object contains:
   • A linking structure, for keeping it in a linked list;
   • A linked list header for keeping the Deltas added to it.
6. The load function should:
   • Create a Snap object;
   • Open the save file;
   • Read the stream version of each object into memory;
   • Create an add Delta for each object in the stream, store each object's save stream in that Delta, and add that Delta to the Snap object;
   • Step through the Snap's Delta list and create the project's data objects in memory.
7. The save function should:
   • Delete all existing Snaps;
   • Create a new Snap object;
   • Create a Delta for all existing objects in the project;
   • Open the output stream and write the Deltas to that stream.
8. The application should maintain a pointer to the current Snap object. This reflects the current state of the project (as the user sees it), including the results of all undo and redo operations.
9. When the user makes a change to the project, the application should:
   • Delete all Snaps following the current Snap, but preserve all Snaps that precede the current Snap (any undone changes are now lost).
   • Create a new Snap object.
   • Create an add Delta for each object in the project. Generate the save stream for that object, storing it in the Delta. Add each Delta to the new Snap.
   • Build a history Snap, which is a record of the last Delta to affect each object (including objects no longer in existence).
   • For each object, if its Delta in the last Snap has the same stream data as the reference Delta, then the object has not changed (or was changed back in the same editing action); the second Delta is unneeded and can be removed from the Snap.
   • If an object has a non-delete Delta in the Snap history, but is no longer in the project, then it must have been deleted; add a delete Delta to the new Snap.
   • The third possibility is that an object's Delta in the Snap history has a different stream from its Delta in the latest Snap; in that case make the latter Delta into a change Delta.
10. When the user closes the project:
    • Check to see if any Snaps precede the current Snap.
    • If there are no previous Snaps, then all changes have either been saved or undone. The project can be deleted from memory.
    • If there are any previous Snaps, alert the user and ask whether the user wants to save the file abandon the changes, or forget about closing altogether.
    • Snaps that are later in the Snap list represent undone changes. Presume the user doesn't want to save them.
11. When the user attempts an undo:
    • Step backwards through the Snap list to the next prior Snap.
    • Restore deleted objects.
    • Replace changed objects with the previous version (in a previous Snap)
    • Remove added objects.
12. When the user attempts a redo (that is, reapplies a change that was undone):
    • Step forward in the Snap chain to the next Snap.
    • Restore the added objects;
    • Replace the changed objects;
    • Remove the deleted objects.

Implementation in C

Tags

All of the project data objects require an additional member to uniquely identify them. An unsigned 32-bit integer (providing you-know-how-many different tags) will be more than sufficient for any project I can think of. If you need more than that many tags, I hope you're getting paid well for your efforts.

You will require a way to generate a unique tag when called. This will happen every time the user directs creation of a new data object. The best way to generate tags is to start at a given number and number them sequentially from there.

If your application has more than one type of object, the object type will become part of the identification of each object (so that the first object of type A and the first object of type B are distinct objects). The following example code is for an application that has only one object type.

The following code samples also assume that the objects in your application are not interdependent. This issue is discussed later in this article.

The Delta object

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

struct Delta { struct doubleLink link; short deltaType; TAG objectTag; char *streamData; }; #define DELTA_ADD 0 #define DELTA_CHANGE 1 #define DELTA_DELETE 2

The struct doubleLink link is for making the Delta structure is part of a doubly-linked list. I do this because you can remove objects from a double-linked list without going through the whole list (or even knowing where the list header is located), which makes encapsulation easier.

deltaType holds the type of the Delta. This could be a type char, but word alignment improves performance on most hardware.

streamData will be a pointer to a snippet of stream data, in the format used by your save file.

If your stream format doesn't use delimiters (ie, there is no consistent character that marks the end of object streams), you will need to add a member to indicate the length of the data referenced by streamData.

The Snap object

The Snap object is even simpler:

struct Snap { struct doubleLink link; struct doubleLinkHeader deltaList; };

Again, the Snap object is part of a doubly-linked list. In addition, it contains the header for a doubly-linked list of its own, to hold all of the Delta objects.

Support functions for Delta and Snap objects

Some of these are merely declared and not defined. The function definitions are left as an exercise for the reader.

struct Snap *createSnap(struct Project *); void destroySnap(struct Snap *); struct Snap *firstSnap(struct Project *); struct Snap *currentSnap(struct Project *); struct Snap *nextSnap(struct Snap *); struct Snap *lastSnap(struct Snap *);

createSnap() creates an empty Snap object and adds it to end of the Snap list in the referenced Project object. The Project object is the object maintained by your application to keep track of all of a project's data, and it should have a doubly-linked list header for the Snap objects.

destroySnap() delinks a Snap from its owner's Snap list, destroys all of the Deltas in the Snap, and then frees the memory occupied by the Snap.

firstSnap() returns a pointer to the referenced Project's first Snap (or NULL, if there are no Snaps in the Project).

currentSnap() returns a pointer to the referenced Project's current Snap (or NULL, if there are no Snaps in the Project). Executing undo and redo operations will step forward and backwards in the Snap list. The application needs to keep track of where it is in the list.

nextSnap() returns a pointer to the Snap that follows the given Snap (or NULL, if the given Snap is last).

lastSnap() returns a pointer to the Snap that precedes the given Snap (or NULL, if the given Snap is first).

struct Delta *createDelta(struct Snap *); void destroyDelta(struct Delta *); void addStream(struct Delta *,struct myObject *); void readStream(struct Delta *,FILESTREAM); void writeStream(struct Delta *,FILESTREAM); struct Delta *firstDelta(struct Snap *); struct Delta *nextDelta(struct Delta *); void copyDeltaData(struct Delta *,const struct Delta *); int newObjectTag(struct Project *); int nextObjectTag(struct Project *); void resetObjectTag(struct Project *);

createDelta() creates a blank Delta object and adds it to the referenced Snap object.

destroyDelta() de-links the Delta from its owning Snap and then frees the Delta's memory.

addStream() adds the file stream data for a given object from your project to the referenced Delta object. Here MyObject stands for the type(s) of object(s) used in your application. You will probably have one version of this function for each type of object.

readStream() reads a single object's filestream into a Delta object.

writeStream() writes a single Delta object's data to a filestream.

firstDelta() returns the first Delta in a given Snap object (or NULL, if the Snap is empty).

nextDelta() returns the Delta that follows the given Delta (or NULL, if the Delta is last).

copyDeltaData() takes the data from the second referenced Delta and copies it over that of the first Delta, but does not change the linking of the first Delta.

newObjectTag() returns the tag of the next object to be created in your project, and increments the tag counter in the Project structure.

nextObjectTag() returns the tag of the next object to be created in your project (but does not increment the count).

resetObjectTag() resets the tag counter to 0.

struct Snap *takeSnap(struct Project *p) { struct Delta *delta; struct Snap *snap; struct MyObject *object; snap=createSnap(p); for(object=firstObject(p);object!=NULL;object=nextObject(object)) { delta=createDelta(snap); delta->deltaType=DELTA_ADD; delta->objectTag=object->Tag; addStream(delta,object); } }

takeSnap() creates a Snap object, and then steps through the project and creates a Delta object for every object in the project.

Saving projects

The project save function will look more like this:

void saveProject(Project *p,FILESTREAM f) { struct Snap *snap,*nextsnap; struct Delta *delta; // get rid of the Snaps associated with a project snap=firstSnap(p); while(snap!=NULL) { nextsnap=nextSnap(snap); destroySnap(snap); snap=nextsnap; } // reindex all of the project's objects -- an efficiency measure resetObjectTag(p); for(object=firstObject(p);object!=NULL;object=nextObject(object) { object->tag=newObjectTag(p); } // create a snap build new Delta list based on project contents snap=takeSnap(p); //write the data to the save file for(delta=firstDelta(snap);delta!=NULL;delta=nextDelta(delta)) { writeStream(delta,f); } }

Loading projects

The project load function will look more like this:

void loadProject(Project *p,FILEHANDLE f) { struct Snap *snap; struct Delta *Delta; // create an empty Snap and add it to a project snap=createSnap(p); // Set tag generation to start at zero resetObjectTag(p); // build new Delta list based on file stream while(EOF(f)!=TRUE) { delta=createDelta(snap); delta->deltaType=DELTA_ADD; delta->objectTag=newObjectTag(p); readStream(delta,f); } // build objects from Deltas for(delta=firstDelta(snap);delta!=NULL;delta=nextDelta(d)) { restoreObjectByDelta(delta); } }

Here's a tip: After loading all of the objects from a file, and rebuilding the objects, destroy the Snap object and make a new one. This will ensure that all of Delta stream data in memory was created by the currently-running version of the application.

The reason you want to do this is because you will probably make changes to your application that require some change to the way file streams are written by the application. Since you care enough about user-friendliness to have read thus far in this article, your application is probably designed to read the data from previous versions of the application. If you read the old format stream data into your Delta objects, and leave that data there, you have the chance of having old format data and new format data in memory at the same time. When the time comes to compare the Delta objects (which you'll need to do), comparing the Delta stream data for two different stream formats is a major headache, whereas if the Deltas were both created by the current version of the program, a simple byte-by-byte comparison of the streams will suffice to tell if they were built for the same object (or not).

All it requires is a call to destroySnap() followed by a call to takeSnap().

You need to decide if objects will be explicitly tagged in the file, or if they will be tagged by the order of appearance in the file:

• Tagging them in the file makes the files longer, but reconstructing the tag during a load is easier; you simply get the tag from the file stream.
• If they are tagged by the order within the file, then you will need to re-tag all of the model's objects as part of any save (as the example code shows). You must then write the objects in tag order; in the example code, the Deltas are made in the same order that tags are assigned, so there should be no problem.
• If the objects have no interdependency, there is no need to worry about this; BUT you may want to add interdependency later, so keep this issue in mind.

Recording edit changes

This is where it gets complicated.

// This function looks through a Snap's Delta list for a Delta with the // same object tag. struct Delta *lookupDeltaByTag(struct Snap *snap,stuct Delta *delta) { struct Delta *duplicate; if(delta==NULL) return NULL; // ECNH (Error Checking Never Hurts) for(duplicate=firstDelta(snap);duplicate!=NULL;duplicate=nextDelta(duplicate)) { if(delta=>objectTag==duplicate->objectTag) return duplicate; } return NULL; } // this takes takes data from one Snap and adds it to another, replacing old data // in the other, or copying it as need be void addToHistorySnap(struct Snap *h_snap,struct Snap *u_snap) { struct Delta *h_delta,*u_delta; for(u_delta=firstDelta(u_snap);u_delta!=NULL;u_delta=nextDelta(u_delta)) { // see if new delta has match in old Snap h_delta=lookupDeltaByTag(h_snap,u_delta); if(h_delta==NULL) { // nope, create an entry h_delta=createDelta(h_snap); } copyDeltaData(h_delta,u_delta); } } // Call this function after completing all of the object modifications // required by a single user edit action. void recordEditSnap(struct Project *p) { struct Snap *snap,*next_snap; struct MyObject *object; struct Delta *delta,*other_delta; struct Delta **history; int i; // destroy all Snaps that follow the most recent one snap=currentSnap(p); // get the most recent Snap snap=nextSnap(snap); // now get the next one while(snap!=NULL) { next_snap=nextSnap(snap); destroySnap(snap); snap=next_snap; } takeSnap(p); // take a Snapshot of everything // Everything from here to the end of the function exists solely to minimize the memory used // by the list of Snaps. It is probable that most of the objects in a project will not be // affected by a given edit, and these should be left out of the Snap. // create an array to hold pointers to the Deltas history=(struct Delta **)calloc(nextTag(p),sizeof(struct Delta *)); // add all *prior* Snaps to the history for(snap=firstSnap(p);snap!=currentSnap(p);snap=nextSnap(snap)) { for(delta=firstDelta(snap);delta!=NULL;delta=nextDelta(snap)) { history[delta->objectTag]=delta; } } // compare current Snap to contents of history array. snap=currentSnap(p); delta=firstDelta(snap); while(delta!=NULL) { next_delta=nextDelta(delta); // need to find next one if current is deleted other_delta=history[delta->objectTag]; if(other_delta) { // an object was in the history, and is still here // clear the entry so that we know it's reflected in latest Snap history[delta->objectTag]=NULL; if(compareStreams(delta,other_delta)==0) { // The two deltas are the same. Kill the new one. destroyDelta(delta); } else { // The data was changed. delta->deltaType=DELTA_CHANGE; } } delta=next_delta; } // All redundant Deltas have been removed from the new Snap. Now we // need to make a delete Delta for all objects that have been removed. // Since all objects that are still around have been cleared from the // history array, any non-NULL entries in the history array reflect an // object that was deleted at some point before the new Snap. for(i=0;ideltaType!=DELTA_DELETE) { // and it wasn't deleted before delta=createDelta(snap); delta->Tag=i; delta->deltaType=DELTA_DELETE; } } } free(history); // no longer needed }

If you have different object types you will need a history array for each type.

Undo operation

When there is an Snap object prior to the current one in the Delta chain, the undo option should be turned on for the project.

If the user selects that option, here is a basic framework of the code to handle it:

void ProcessUndo(Project *p) { struct Snap *snap,*last_snap; struct Delta *delta,*previous; snap=currentSnap(p); if(snap==NULL) return; // ECNH last_snap=lastSnap(snap); // get the prior snap if(last_snap==NULL) return; // there was no previous Snap // These are broken out into separate Delta types to handle the // problem of object cross-referencing. // apply deltas in reverse for(delta=firstDelta(snap);delta!=NULL;delta=nextDelta(delta)) { switch(delta->DeltaType) { case DELTA_DELETE: previous=findPreviousVersion(delta); restoreObjectByDelta(previous); break; case DELTA_CHANGE: previous=findPreviousVersion(delta); replaceObjectByDelta(previous); break; case DELTA_ADD: removeObjectByDelta(previous); break; } } setCurrentSnap(p,last_snap); }

Redo operation

When there is a Snap object after the current one in the Snap chain, there is at least one undone change, and therefore the redo option should be turned on for the project.

If the user selects that option, here is a basic framework of the code to handle it:

void ProcessRedo(Project *p) { struct Snap *snap,*next_snap; struct Delta *delta,*next_delta; snap=currentSnap(p); if(snap==NULL) return; snap=nextSnap(snap); if(snap==NULL) return; // apply deltas for(delta=firstDelta(snap);delta!=NULL;delta=nextDelta(delta)) { switch(delta->DeltaType) { case DELTA_DELETE: removeObjectByDelta(delta); break; case DELTA_CHANGE: replaceObjectByDelta(delta); break; case DELTA_ADD: restoreObjectByDelta(delta); break; } } setCurrentSnap(p,snap); }

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.

You can have different constructors for data objects: One with a Delta object as the argument (used for undo and redo operations), and the other with regular project data as the argument set, for regular project edits.

Other Issues

It isn't too hard to modify the strategy outlined here so that the entire prior history of a project is always accessible, even after an arbitrary number of loads and saves.

You can get even crazier and define a forking Snap chain, which preserves changes that are undone and then made irrelevant by a later edit. This would allow the user to revisit abandoned ideas.

You can also date-stamp the atom Deltas, so that the progress of a project over time is easily tracked, and user-stamp them as well, allowing the contributions of different authors to be tracked.

The modifications are left as an exercise for the interested student.

Cross-referencing between objects is still an issue that need to be carefully mananged:

• You can adjust the order of Deltas within a Snap, putting the add Deltas first (with dependent objects in this group after the objects they depend on), the change Deltas in the middle, and the delete Deltas last (with the dependent objects in this group coming before the objects they depend on). Then have the undo function step backwards through the Delta chain.
• You can also solve the interdependency problem by constructing your objects so that interdependencies can be resolved separately from object creation. This allows an object to be created prior to the objects upon which it depends. Then you can reconstruct the objects in the same order the Snap holds them, and end it with a call to the function that resolves all interdependencies in one fell swoop. You will need a way to distinguish the objects with resolved interdependencies from those that have unresolved interdependencies.
• The simplest way to solve the problem is to delete and rebuild the entire project, using the Snap data. This is not much more difficult than loading the project from file, so it shouldn't be that hard to implement. It may sound as if there's a performance issue with this, but since there are no I/O operations involved, it should go quite quickly. If it takes 1000 clock cycles to destroy and create an object, then a modern processor can rebuild thousands of objects in less time than the display takes to scan the display. To the user, it appears to happen in no time at all. If you have an enormous number of objects, or object creation takes a long time, the other ways may be preferable.