Cancel / Repeat

Question

Give me some thoughts on how to implement undo / redo functionality - like in text editors. What algorithms should I use and what can I read. thank.

Answer 1

I know about the two main divisions of undo types

• STORING STATE: One category of cancellation is where you actually save the state of the story. In this case, what happens is that at each point you save the state in some place in the memory. When you want to cancel, you simply replace the current state and replace it with a state that was already in memory. Here's how to do it with history in Adobe Photoshop or, for example, when opening closed tabs in Google Chrome.

• GENERAL STATE: Another category is where, instead of supporting the states themselves, you just remember what the actions were. when you need to undo, you need to do the inverse of this particular action. For a simple example, when you do Ctrl + B in some text editor that supports cancellation, it is remembered as a Bold action. Now each action is a reflection of its logical appeals. So, when you do Ctrl + Z , it searches from the table of reverse actions and discovers that the undo action is Ctrl + B again. This is done, and you get your previous state. So, here your previous state was not stored in memory, but generated when you need it.

For text editors, creating a state this way is not too computationally intensive, but for programs like Adobe Photoshop, it can be computationally too intensive or simply impossible. For example, for the Blur action, you specify the de-Blur action, but you can never get the initial state because the data is already lost. Thus, depending on the situation - the possibility of a logical reverse action and its feasibility, you need to choose between these two broad categories, and then implement them the way you want. Of course, it is possible to have a hybrid strategy that works for you.

In addition, sometimes, as in Gmail, the time limit is limited because the action (sending mail) is never performed in the first place. So you are not “canceling” there, you are simply “not doing” the action itself.

Answer 2

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

In essence, I define the structure as

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 indicates the stored state of the text. Now, each time you edit the text (pressing the down key, returning to the down key, deleting the down key, cutting / pasting, selection moved by the mouse, etc.), I (re) start the timer, say, for one second. When triggered, the timer saves the current state as a new element in the UndoData array.

When canceling (Ctrl + Z), I return the editor to the state of UndoData[UndoLevel - 1] and reduce UndoLevel by one. By default, UndoLevel is the index of the last member of the UndoData array. When returning (Ctrl + Y or Shift + Ctrl + Z) I return the editor to the state UndoData[UndoLevel + 1] and increase UndoLevel by one. Of course, if the editing timer fires when UndoLevel not equal to the length (minus one) of the UndoData array, I clear all the elements of this array after UndoLevel , as is usually the case on the Microsoft Windows platform. (but Emacs is better, if I remember correctly - the disadvantage of the Microsoft Windows approach is that if you cancel a lot of changes and then accidentally edit the buffer, the previous content (which was canceled) will be lost forever). You might want to skip this array reduction.

In another type of program, for example, in an image editor, the same technique can be applied, but, of course, with a completely different structure of UndoDataItem . A more advanced approach that does not require a lot of memory is to save only changes between 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 know what I mean). In very large files, where each change is small compared to the file size, this will significantly reduce memory usage for canceled data, but it is more difficult to implement and possibly more error prone.

Answer 3

There are several ways to do this, but you can start searching for the Command pattern . Use the list of commands to return (Cancel) or redirect (redo) through your actions. An example in C # can be found here .

Answer 4

A little late, but here we are talking: you specifically turn to text editors, which explains an algorithm that can be adapted to what you are editing. The basic principle is to keep a list of actions / instructions that can be automated to recreate every change you make. Do not make changes to the source file (if it is not empty), save it as a backup.

Save the linked reverse permutation list in the source file. This list is periodically saved to a temporary file until the user saves the changes: when this happens, you apply the changes to the new file, copy the old one and apply the changes at the same time; then rename the source file to backup and change the name of the new file to the correct name. (You can save the saved list of changes or delete it and replace it with the subsequent list of changes.)

Each node in the linked list contains the following information :.

• type of change: you either insert data or delete data: delete used to “change” the data, followed by insert
• file position: may be an offset or a pair of rows / columns
• data buffer: this is the data associated with the action; if insert is the data that was inserted; if delete , data that has been deleted.

To implement Undo , you work backward from the tail of a linked list using a pointer or an index of "current-node": where the change was insert , you do a deletion, but do not update the linked list; and where it was delete , you insert data from the data into the buffer of the linked list. Do this for each Undo command from the user. Redo moves the 'current-node' pointer forward and performs the change according to node. If the user makes changes to the code after canceling, delete all nodes after the current-node indicator in the tail and set the tail equal to the current-node indicator. Then user changes are inserted after the tail. And about that.

Answer 5

My two cents is that you want to use two stacks to track operations. Each time the user performs some operations, your program must place these operations on the "completed" stack. When the user wants to cancel these operations, just pop operations from the "completed" stack to the "recall" stack. When the user wants to repeat these operations, pop the elements from the "recall" of the stack and return them back to the "completed" stack.

Hope this helps.

Answer 6

You can study an example of an existing undo / redo framework, the first Google hit is on codeplex (for .NET) . I do not know whether it is better or worse than in any other structure, there are many of them.

If your goal is to have undo / redo functionality in your application, you can simply select an existing structure that is suitable for your type of application.
If you want to learn how to create your own undo / redo, you can download the source code and look at both the templates and the details, how to connect things.

Answer 7

If the action is reversible. for example, adding 1, moving a player, etc. see using the Command pattern to implement undo / redo . Following the link, you will find detailed examples of how to do this.

If not, use Saved State as described in @Lazer.

Answer 8

For this, a Memento pattern was created.

Before doing this on your own, note that this is pretty common, and the code already exists. For example, if you code in .Net, you can use IEditableObject .