algorithm - Undo/Redo implementation

Question

Give me some thoughts how to implement undo/redo functionality - like we have in text editors. What algorithms should I use and what I may read. thanks.

Answer 1

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.