Undo/Redo implementation [closed]

I know about two major divisions of the types of undo's

• SAVE STATE: One category of undo is where you actually save history states. In this case what happens is that at every point you keep on saving the state in some location of memory. When you want to do an undo, you just swap out the current state and swap in the state which was already there in the memory. This is how it is done with History in Adobe Photoshop or reopening closed tabs in Google Chrome, for example.

• GENERATE STATE: The other category is where instead of maintaining the states themselves, you just remember what the actions were. when you need to undo, you need to do a logical reverse of that particular action. For a simple example, when you do a Ctrl+B in some text editor that supports undo's, it is remembered as a Bold action. Now with each action is a mapping of its logical reverses. So, when you do a Ctrl+Z, it looks up from a inverse actions table and finds that the undo action is a Ctrl+B again. That is performed and you get your previous state. So, here your previous state was not stored in memory but generated when you needed it.

For text editors, generating the state this way is not too computation intensive but for programs like Adobe Photoshop, it might be too computationally intensive or just plain impossible. For example - for a Blur action, you will specify a de-Blur action, but that can never get you to the original state because the data is already lost. So, depending on the situation - possibility of a logical inverse action and the feasibility of it, you need to choose between these two broad categories, and then implement them the way you want. Ofcourse, it is possible to have a hybrid strategy that works for you.

Also, sometimes, like in Gmail, a time limited undo is possible because the action (sending the mail) is never done in the first place. So, you are not "undo"ing there, you are just "not doing" the action itself.

I have written two text editors from scratch, and they both employ a very primitive form of undo/redo functionality. By "primitive", I mean that the functionality was very easy to implement, but that it is uneconomical in very large files (say >> 10 MB). However, the system is very flexible; for instance, it supports unlimited levels of undo.

Basically, I define a structure like

type
  TUndoDataItem = record
    text: /array of/ string;
    selBegin: integer;
    selEnd: integer;
    scrollPos: TPoint;
  end;

and then define an array

var
  UndoData: array of TUndoDataItem;

Then each member of this array specifies a saved state of the text. Now, on each edit of the text (character key down, backspace down, delete key down, cut/paste, selection moved by mouse etc.), I (re)start a timer of (say) one second. When triggered, the timer saves the current state as a new member of the UndoData array.

On undo (Ctrl+Z), I restore the editor to the state UndoData[UndoLevel - 1] and decrease the UndoLevel by one. By default, UndoLevel is equal to the index of the last member of the UndoData array. On redo (Ctrl+Y or Shift+Ctrl+Z), I restore the editor to the state UndoData[UndoLevel + 1] and increase the UndoLevel by one. Of course, if the edit timer is triggered when UndoLevel is not equal to the length (minus one) of the UndoData array, I clear all items of this array after UndoLevel, as is common on the Microsoft Windows platform (but Emacs is better, if I recall correctly -- the disadvantage of the Microsoft Windows approach is that, if you undo a lot of changes and then accidentally edit the buffer, the previous content (that was undid) is permanently lost). You might want to skip this reduction of the array.

In a different type of program, for instance, an image editor, the same technique can be applied, but, of course, with a completely different UndoDataItem structure. A more advanced approach, which does not require as much memory, is to save only the changes between the undo levels (that is, instead of saving "alpha\nbeta\gamma" and "alpha\nbeta\ngamma\ndelta", you could save "alpha\nbeta\ngamma" and "ADD \ndelta", if you see what I mean). In very large files where each change is small compared to the file size, this will greatly decrease the memory usage of the undo data, but it is trickier to implement, and possibly more error-prone.

There are several ways to do this, but you could start looking at the Command pattern. Use a list of commands to move back (Undo) or forward (redo) through your actions. An example in C# can be found here.

A bit late, but here goes: You specifically refer to text editors, what follow explains an algorithm that can be adapted to whatever it is you are editing. The principle involved is to keep a list of actions/instructions that can be automated to recreate each change you made. Do not make changes to the original file (if not empty), keep it as a back-up.

Keep a forward-backward linked-list of changes you make to the original file. This list is saved intermittently to a temporary file, until the user actually Saves the changes: when this happens you apply the changes to a new file, copying the old one and simultaneously applying the changes; then rename the original file to a backup, and change the new file's name to the correct name. (You can either keep the saved change-list, or delete it and replace with a subsequent list of changes.)

Each node in the linked-list contain the following info:.

• type of change: you either insert data, or you delete data: to "change" data means a delete followed by an insert
• position in file: can be an offset or line/column-pair
• data buffer: this is the data involved with the action; if insert it is the data that was inserted; if delete, the data that was deleted.

To implement Undo, you work backward from the tail of the linked-list, using a 'current-node' pointer or index: where the change was insert, you do a delete but without updating the linked-list; and where it was a delete you insert the data from the data in the linked-list buffer. Do this for each 'Undo'-command from the user. Redo moves the 'current-node' pointer forward and executes the change as per the node. Should the user make a change to the code after undoing, delete all nodes after the'current-node' indicator to the tail, and set tail equal to the 'current-node' indicator. The user's new changes are then inserted after the tail. And that's about it.