Undo/Redo Manager Techniques

Hello everyone,

this topic is relatively new territory for me. I’m wondering what techniques or approaches there are for an undo/redo manager?

Let’s say there is a drawing program and och would like to retrace all steps (draw objects, resize, change text/color etc).

How would you proceed in this case? Are there any patterns for this? Efficiency and performance would be very important.

Has anyone dealt with this before? What needs to be done? Thoughts, suggestions?

P.S. I know that Jim Mckay offers TheBigUndo class.

Its not easy as it needs a ground up design before you start to code anything.

Every action your app can perform needs to have a descriptor and parameters, which correspond to methods
eg

  • Select x1,y1,x2,y2 … calls a method called select with 4 parameters
  • Copy
  • Paste
  • Paste to x1,y1
  • Select color
  • Flood fill x1,y1

These instructions can be stored in an array, as work is performed.

To undo, you start with a blank, or ‘the file you loaded’
Then you replay all the commands in the array APART FROM THE LAST by calling the methods.
And remove the last item in the array. (or leave it there but wind back a pointer into the array… because if you do that you can also handle ‘Redo’)

These commands are what you might expose to Applescript or OLE in windows.

The simpler alternative is an image level undo, where you just keep saving the work at various stages into the temporary folder and wind back as needed.
It’s expensive in disc space, and you ought to empty the temp folder when your app closes.
It also doesnt undo selection areas or choices of ‘tools’

Thanks @Jeff_Tullin for your detailed post. I have already thought something similar. What I’m wondering is whether, for a DTP (Desktop Publishing Document) document with, say, 1000 pages, the array approach is effective. My feeling is that it could fill up memory quickly and slow down the performance of the system.

The array approach is normally efficient in terms of memory, compared to keeping copies of the whole document in memory/disc

It has to be even smarter when it comes to embedded external stuff… imagine handling the undo for a picture - originally copied in some other app then pasted into yours.
That ‘array’ would need to keep a copy of the pasted data somewhere too…
for that reason, I can imagine a scenario where the array takes the form of a database in temp rather than an array in memory.

2 Likes

True.

I think the Command Pattern is a good source to start with, beside the Memento Pattern.

if you store change font from 10 to 16 points.
the undo would be change font from 16 to 10 points.

I used a different technique in an app. Instead of storing a list of commands, I would simply snapshot the entire project when a change had been made. Each snapshot is timestamped and given a description of what the edit change was, e.g. “Set font to 16 points for items 1 to 43”.

Pros:

  • you don’t have to write explicit “undo” code for each operation, or worry about the details of exactly how to change something back again. Since “undo” is just restoring to a shapshot, it can be a generic function.
  • destructive or non-reversible edits are not a problem. For example some edits such as “Set font to 16 points for items 1 to 43” is not something which can be undone by executing a command in reverse. You’d have to store it as 43 separate commands, which increases complexity, etc.

Cons:

  • the snapshots can be slow and big, so you have to be really concerned with copying your data structures as efficiently as possible. I spent a lot of time profiling my code to make it as fast as possible, and paid special attention to doing shallow copies whenever possible. For example, if one of my data items held a picture, when doing the snapshot I would not duplicate the picture object, only the URL to the picture.

I found the end result to be pretty easy to use - here’s an example of what the user would see:

I too store an array of “changes”, holding a reference to the object, property name and previous property value.

At one time I experimented with storing this to disk when the user saves. However I found very few users who used this, and the performance hit when saving / loading the document got quite bad.

1 Like

Modern macOS apps have this persistent versioning feature built in, but Xojo doesn’t support it (and even if it did, it wouldn’t be cross platform or work the same way.

I, too, didn’t bother. In my app, when the user “Saves”, it clears the Undo/Redo stack.

1 Like

I’m still using UndoToolkit from Scott Forbes (https://www.mactech.com/2002/08/25/undo-toolkit-4-5-1-for-realbasic/). The original code is under GPL but I bought a commercial license. So - if you want - you could have a look at the code.

1 Like

My undo/redo approach is slightly different. I have an array of dictionaries and a CurrentIndex property.
Each action that makes changes adds a new dictionary to the array and increments CurrentIndex. This dictionary contains 3 sub-dictionaries: “Before”, “After” and “Common” (these are the name of the keys of the root dictionary).
The “Common” dictionary contains keys as string. One key is mandatory: “KindOfAction”. This one holds the action that was done (paste, drag, change a property, move, etc.).
Other keys in the “Common” dictionary holds data pertaining to both undo and redo (like an identifier for the target item or action-specific data that are common for undo and redo).
The “Before” and “After” dictionaries contain the properties that have changed. For undoing, I take the value in the “Before” dictionary; for redoing, the one in the “After” one.
For example, when changing the colour of a line, the “Common” dictionary would contain “KindOfAction”=“ChangeProperty” and “PropertyDesc”=“LineColour”. The “Before” dictionary contains “Colour”=RGB(0,255,0) and the “After” dictionary contains “Colour”=RGB(0,0,255) (if the line was green and went blue).
Each action obviously defines its set of properties (mandatory or not).

One thing I had to do is to add an index reference to each object to uniquely reference it). That’s because if you delete an item, undo the deletion and redo it, storing the object as a direct reference in the dictionary breaks (that’s not the same object in memory than it used to be). So each object has an ID as integer that will never change and is unique across all the objects in the same document.

The CurrentIndex property keeps track of where we are in the stack, for the next undo/redo. When changing the direction (either from undo to redo or the other way around), don’t forget you won’t increment/decrement as you would when the direction is the same (logical, but important).

In various places of your code, where appropriate, you add a new dictionary to the stack, with the sub-dictionaries filled. For that, I keep a reference to the current dictionary (the one that hasn’t been completed yet) fill it (with according methods) and terminate/append the dictionary. Something like this (this is my own implementation, to be translated):

AddToDictionary “Common”,“KindOfAction”,“Move”
AddToDictionary “Common”,“Objects”,GetIndexOfSelectedItems
AddToDictionary “Before”,“Location”,GetPropertyOfSelectedItems(Properties.Location)
AddToDictionary “After”,“Location”,NewPosition //or an array, or delta value, depending on your application
TerminateActionStack

Sub AddToDictionary(DictionaryName as string,PropertyName as string,PropertyValues as variant)
if CurrentAction=nil then
CurrentAction=New Dictionary
CurrentAction.value(“After”)=new Dictionary
CurrentAction.value(“Before”)=new Dictionary
CurrentAction.value(“Common”)=new Dictionary
end if
//Add the property (key) and its value to the corresponding dictionary
End Sub

Sub TerminateActionStack()
Redim UndoStack(CurrentIndex-1) 'Discard newest changes that were undone
UndoStack.Add CurrentAction
CurrentAction=nil 'Be ready when another part of the code adds an action (this will be a new one)
End Sub

Just an example, but it works for me.

1 Like

Thanks @Sam_Rowlands and @Mike_D for your suggestion. Sounds interesting. I’ll look at this.

That would be nice @Beatrix_Willius. I’d be happy if you can e-Mail me (you have my Mail). Thanks.

@Arnaud_N if I read your way it doesn’t look that different from the Command Pattern. I’ll investigate it. Thanks.