Undo and Redo - analysis and implementation
Hi, Habr! In connection with my real task, to analyze the capabilities of Qt and .NET for the implementation of the so-called “Back” (Undo) and “Forward” (Redo), the goal of which is to cancel the action and cancel the cancellation, respectively, I decided to deploy all my thoughts, ideas and ideas this article, even if they are partially or completely incorrect (therefore, if possible, and in the interest, write comments in the comments). Although it is easy to find good (and not so) libraries and examples of implementations on the Internet, I found a more general idea of these things not so soon, and even then, only in response to StackOverflow , but this was not enough for me. In everything found there are moments that pleased me, there are and which upset me. Perhaps, it is worth canceling all the sorrows and joys ... in order to return to them again ... "Back ... to the future"!
Interesting? Welcome!
Red or blue? Approximately it will be necessary to come to such question, after decided to implement in the Undo / Redo application. I explain: there are two main ways to implement step-by-step cancellation, for which I assigned the following names: operation-oriented and value-oriented . The first method is based on creating transactions (or transactions) that have two methods — to do it and return it as it was. The second method does not store any operations - it only records the values that have changed at a certain point in time. Both the first and second methods have their pros and cons.
')
UPD: To further have fewer questions, I remind you that Undo / Redo is intended more to store information from previous versions of a document (for example) during editing . It will take a long time to write data to the database or to disk, and this already has little to do with the goal of Undo / Redo . However, if you really need to - do it, but better not.
It is implemented on the basis of the “Command” pattern ( Command ).
This method is to store operations in a special stack. The stack has a position (we can say an iterator) that points to the last operation. When an operation is added to the stack, it will be executed (redo), the position is incremented. To cancel an operation, the stack invokes the undo command from the last operation, and then shifts the position of the last operation below (shifts, but does not delete). If you need to return the action - the shift is higher, the redo execution. If after the cancellation, a new operation is added, then there are two solutions: either replacing operations above the position with new ones (and then it will be impossible to return to the previous ones), or start a new “branch” in the stack, but this raises the question - which branch will you go to next? However, I don’t need to look for the answer to this question, since it depends on the requirements for the program.
And so, for the very simple Undo / Redo we need: a base class (interface) with purely virtual (abstract) functions undo () and redo (), also a class that will store pointers to objects derived from the base class and, of course , the classes themselves, in which the undo () and redo () functions will be redefined. It is also possible (in some cases, even very necessary) to make the functions of combining operations into one, in order, say, to cancel not every letter separately, but words and sentences, when the letters become such, and so on. Therefore, it is also desirable for each operation to assign a certain type, with the difference that it will not be possible to glue operations.
And so, the pros:
Minuses:
You can also read this article on the Wiki about the command pattern (Command) , which is used to implement this method of Undo / Redo, as well as this article on Habrahabr.
Implemented on the basis of the pattern "Keeper" ( Memento ).
The principle of the method is to know about all possible variables that may change, and at the beginning of possible changes put the stack “on the record”, and at the end make commit changes.
However, all changes must be recorded. If only the changes made by the user are recorded, but the changes in the dependencies were not recorded, then when you cancel / return, the dependencies will remain unchanged. Of course, it is possible in a tricky way to cause a recalculation of dependencies every time, but this is more like the first method and more convenient then it will be. On the methods of implementation will be discussed below, but for now let's look at the advantages and disadvantages.
Pros:
Minuses:
You can also read this article on the Wiki about the Guardian pattern (Memento) .
If there is anything to say about the demands of memory, then this method will eat a lot. Imagine a situation where, while typing only one character, the entire document was saved. And so every time. Submitted? And now forget about this method and do not remember any more, for this is not Undo / Redo, but backups.
UPD: And no, here I did not mean the Memento pattern, which can also save, in addition to the partial, a complete snapshot of changes / values. This means that it is not advisable to save a snapshot of the entire document when only a couple of values have changed. If, after all, this cannot be avoided, then it is rather vl-or , and in some situations, when the entire document is very rarely and complicated, you can refuse to record such changes (tell the user that the rollback of changes after this operation will be unavailable ).
Here, the developers have tried their best. With Qt, you can easily and easily implement Undo / Redo. Write the recipe. We need: QUndoStack , QUndoCommand , as well as QUndoView and QUndoGroup to taste. First, we inherit our own classes from QUndoCommand, in which undo () and redo () should be redefined, it is also desirable to redefine id () to determine the type of operation, so that later in the redefined mergeWith (const QUndoCommand * command) we can check both compatibility operations. After this, we create an object of the QUndoStack class, and put all new operations into it. For convenience, you can take QAction * undo and QAction * redo from the functions of the stack, which you can then add to the menu, or attach to a button. And if you need to use several stacks, then QUndoGroup will help with this, if you need to display a list of operations: QUndoView.
Also, in QUndoStack, you can mark a clear state, which, for example, can mean whether the document is saved to disk, etc. Quite a convenient implementation of op-or undo / redo.
I implemented the simplest example on Qt.
Oops ... Qt did not provide this option. Even a search for the keywords "Qt memento" did not give anything. Well, okay, there and this is quite enough, and if not enough, you can use native methods.
Since Qt did not consider it necessary to add a value-oriented Undo / Redo, so you will need to look for either ready-made implementations (where you can find the magic word for me “Memento”), or you have to implement it yourself. Basically everything is implemented on the basis of templates. All this can be easily found. I, for example, found this project on GitHub. Two ideas are implemented here at once, you can take it and see it, test it.
For me, C # and .NET meanwhile dark forests of distant Siberia, but nevertheless, I really, really need it. Therefore it is worth telling at least that I managed to google.
The best examples for me were:
Soon there was such an old article .
Perhaps, something you can find, and perhaps on the basis of this, take and write yourbike a brilliant code. Go for it.
In general, for such tasks in .NET there is an IEditableObject interface, but you have to implement a lot of things from scratch, although there is an example implementation directly on MSDN. Nevertheless, I really liked the DejaVu library, for which even the whole article was written on Habrahabr. Read, fall in love, write.
There are two more examples, but I didn’t like them at all:
And so, what you need to know to choose between two methods of implementation, only one? First, the implementation of your project, whether it will (will?) Be based on commands, or just a change in the set of values (if neither one nor the other - I think it is better to rewrite the project). Secondly, the requirements for memory and performance, because perhaps it is because of them will have to abandon one option in favor of another. Thirdly, you need to know exactly what should be preserved and how, and what should not at all. That's basically it.
Good luck in the future!
Interesting? Welcome!
Study
Red or blue? Approximately it will be necessary to come to such question, after decided to implement in the Undo / Redo application. I explain: there are two main ways to implement step-by-step cancellation, for which I assigned the following names: operation-oriented and value-oriented . The first method is based on creating transactions (or transactions) that have two methods — to do it and return it as it was. The second method does not store any operations - it only records the values that have changed at a certain point in time. Both the first and second methods have their pros and cons.
')
UPD: To further have fewer questions, I remind you that Undo / Redo is intended more to store information from previous versions of a document (for example) during editing . It will take a long time to write data to the database or to disk, and this already has little to do with the goal of Undo / Redo . However, if you really need to - do it, but better not.
Method 1: operation-oriented
It is implemented on the basis of the “Command” pattern ( Command ).
This method is to store operations in a special stack. The stack has a position (we can say an iterator) that points to the last operation. When an operation is added to the stack, it will be executed (redo), the position is incremented. To cancel an operation, the stack invokes the undo command from the last operation, and then shifts the position of the last operation below (shifts, but does not delete). If you need to return the action - the shift is higher, the redo execution. If after the cancellation, a new operation is added, then there are two solutions: either replacing operations above the position with new ones (and then it will be impossible to return to the previous ones), or start a new “branch” in the stack, but this raises the question - which branch will you go to next? However, I don’t need to look for the answer to this question, since it depends on the requirements for the program.
And so, for the very simple Undo / Redo we need: a base class (interface) with purely virtual (abstract) functions undo () and redo (), also a class that will store pointers to objects derived from the base class and, of course , the classes themselves, in which the undo () and redo () functions will be redefined. It is also possible (in some cases, even very necessary) to make the functions of combining operations into one, in order, say, to cancel not every letter separately, but words and sentences, when the letters become such, and so on. Therefore, it is also desirable for each operation to assign a certain type, with the difference that it will not be possible to glue operations.
And so, the pros:
- With the right construction of operations, the chances of business logic being low are low, since it is the operations in which the BL
magiccan also be involved, only for undo, you need to perform the actions in the reverse order, and the actions themselves must be reversed (except for the moments when one object changes). , and others depend on the first, then in this case at the end both undo and redo will need recalculation). - Less memory consuming - only operations are recorded, but not the values of variables. If during the operation a mechanism of recalculation of almost everything and everything is called - these changes do not fall into memory, and if canceled, a recalculation will be needed again.
- More flexible way undo / redo.
Minuses:
- It is necessary to realize the whole two functions. If you build actions in one or both functions incorrectly, business logic does not have a chance to work correctly with Undo / Redo.
- If operations cause recalculation of dependencies and the like, then this approach will be demanding of performance.
You can also read this article on the Wiki about the command pattern (Command) , which is used to implement this method of Undo / Redo, as well as this article on Habrahabr.
Method 2: value-oriented
Implemented on the basis of the pattern "Keeper" ( Memento ).
The principle of the method is to know about all possible variables that may change, and at the beginning of possible changes put the stack “on the record”, and at the end make commit changes.
However, all changes must be recorded. If only the changes made by the user are recorded, but the changes in the dependencies were not recorded, then when you cancel / return, the dependencies will remain unchanged. Of course, it is possible in a tricky way to cause a recalculation of dependencies every time, but this is more like the first method and more convenient then it will be. On the methods of implementation will be discussed below, but for now let's look at the advantages and disadvantages.
Pros:
- Does not need recalculations - is not picky about performance.
- Business logic does not suffer - everything that is calculated simply falls back into place.
- An easier way to undo / redo.
Minuses:
- More demanding of memory, since all dependent objects are saved (otherwise, either performance or business logic suffers).
- Not able to call certain operations, as there is only a "memory recovery".
You can also read this article on the Wiki about the Guardian pattern (Memento) .
Bad method 3: full snapshot
If there is anything to say about the demands of memory, then this method will eat a lot. Imagine a situation where, while typing only one character, the entire document was saved. And so every time. Submitted? And now forget about this method and do not remember any more, for this is not Undo / Redo, but backups.
UPD: And no, here I did not mean the Memento pattern, which can also save, in addition to the partial, a complete snapshot of changes / values. This means that it is not advisable to save a snapshot of the entire document when only a couple of values have changed. If, after all, this cannot be avoided, then it is rather vl-or , and in some situations, when the entire document is very rarely and complicated, you can refuse to record such changes (tell the user that the rollback of changes after this operation will be unavailable ).
Ways of implementation
C ++: Qt
Operation-oriented
Here, the developers have tried their best. With Qt, you can easily and easily implement Undo / Redo. Write the recipe. We need: QUndoStack , QUndoCommand , as well as QUndoView and QUndoGroup to taste. First, we inherit our own classes from QUndoCommand, in which undo () and redo () should be redefined, it is also desirable to redefine id () to determine the type of operation, so that later in the redefined mergeWith (const QUndoCommand * command) we can check both compatibility operations. After this, we create an object of the QUndoStack class, and put all new operations into it. For convenience, you can take QAction * undo and QAction * redo from the functions of the stack, which you can then add to the menu, or attach to a button. And if you need to use several stacks, then QUndoGroup will help with this, if you need to display a list of operations: QUndoView.
Also, in QUndoStack, you can mark a clear state, which, for example, can mean whether the document is saved to disk, etc. Quite a convenient implementation of op-or undo / redo.
I implemented the simplest example on Qt.
I want to see!
Here is the class diagram to which I arrived (most likely, I am greatly mistaken about the direction of the arrows ...):
A “server” is also mentioned here, in case it also is present and interacts with your client application. And here is the source (consider that I wrote everything “on my knee”).
A “server” is also mentioned here, in case it also is present and interacts with your client application. And here is the source (consider that I wrote everything “on my knee”).
Value-oriented
Oops ... Qt did not provide this option. Even a search for the keywords "Qt memento" did not give anything. Well, okay, there and this is quite enough, and if not enough, you can use native methods.
C ++: Native
Since Qt did not consider it necessary to add a value-oriented Undo / Redo, so you will need to look for either ready-made implementations (where you can find the magic word for me “Memento”), or you have to implement it yourself. Basically everything is implemented on the basis of templates. All this can be easily found. I, for example, found this project on GitHub. Two ideas are implemented here at once, you can take it and see it, test it.
C #: .NET
For me, C # and .NET meanwhile dark forests of distant Siberia, but nevertheless, I really, really need it. Therefore it is worth telling at least that I managed to google.
Operation-oriented
The best examples for me were:
- Good article on Habrahabr.
- An interesting post about the command pattern on .NET.
- And just a good example of Undo / Redo using Generics.
Soon there was such an old article .
Perhaps, something you can find, and perhaps on the basis of this, take and write your
Value-oriented
In general, for such tasks in .NET there is an IEditableObject interface, but you have to implement a lot of things from scratch, although there is an example implementation directly on MSDN. Nevertheless, I really liked the DejaVu library, for which even the whole article was written on Habrahabr. Read, fall in love, write.
There are two more examples, but I didn’t like them at all:
Conclusion
And so, what you need to know to choose between two methods of implementation, only one? First, the implementation of your project, whether it will (will?) Be based on commands, or just a change in the set of values (if neither one nor the other - I think it is better to rewrite the project). Secondly, the requirements for memory and performance, because perhaps it is because of them will have to abandon one option in favor of another. Thirdly, you need to know exactly what should be preserved and how, and what should not at all. That's basically it.
Good luck in the future!
Source: https://habr.com/ru/post/306398/
All Articles