July 27, 2016 at 11:33Undo and Redo - analysis and implementation
Hello, 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 purpose of which is to cancel the action and cancel the cancellation, respectively, I decided to deploy all my thoughts, ideas and ideas in this article, even if they are partially or completely incorrect (therefore, if possible and of interest, write your comments in the commentary). Although on the Internet you can easily find good (and not so) libraries and examples of implementations, I found a more general idea of these things not so soon, and even then, only in response to StackOverflow, and that was not enough for me. In everything found there are moments that pleased me, there are also which upset me. Perhaps it’s worth canceling all the sorrows and joys ... in order to return to them again ... "Back ... to the future"!
Interesting? Welcome!
Red or blue? You will need to come to this kind of question after you decide to implement Undo / Redo in the application. I explain: there are two main ways to implement step-by-step undo, for which I assigned the following names: operation-oriented and value-oriented . The first method is based on the creation of operations (or transactions), which have two methods - to do and return everything as it was. The second method does not store any operations - it only records values that have changed at a certain point in time. Both the first and second methods have their pros and cons.
UPD: To keep fewer questions in the future, I remind you that Undo / Redo is intended more for storing 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 has little to do with the goal of Undo / Redo . However, if you really need to - do it, but it's better not to.
Implemented on the basis of the pattern of "Team» ( the Command ).
This method is to store operations in a special stack. The stack has a position (you can say an iterator) that indicates the last operation. When an operation is added to the stack, it will be executed (redo), the position is incremented. To cancel the operation, the stack calls the undo command from the last operation, and then shifts the position of the last operation lower (shifts, but does not delete). If you need to return an action - a shift above, the execution of redo. If, after cancellation, a new operation is added, that is, two solutions: either replace operations above the position with new ones (and then it will be impossible to return to the previous ones), or start a new “branch” on the stack, but the question arises - which branch should I go to then? However, the answer to this question is already not necessary for me to search, since it depends on the requirements for the program.
And so, for Undo / Redo itself, 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) it will be possible to make functions of combining operations into one, in order, for example, to cancel not each letter individually, but words and sentences, when the letters become such, and the like. Therefore, it is also advisable to assign a certain type for each operation, with a difference of which it will not be possible to glue the 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.
It is implemented on the basis of the “Keeper” pattern ( Memento ).
The principle of the method is to know about all possible variables that can change, and at the beginning of possible changes to put the stack “on record”, and at the end - to commit the changes.
However, all changes must be recorded. If only changes made by the user are recorded, but no dependency changes are recorded, then when you cancel / return the dependencies will remain unchanged. Of course, you can call the recalculation of dependencies every time in a tricky way, but this is more like the first method and it will be more convenient then. Implementation methods will be described below, but for now let's look at the advantages and disadvantages.
Pros:
Minuses:
You can also read this Wiki article about the Guardian pattern (Memento) .
If we talk about exacting memory, then this method will eat a lot. Imagine a situation where when typing only one character, the entire document was saved. And so every time. Presented? Now forget about this method and don’t remember anymore, because it’s not Undo / Redo, but backups.
UPD: And no, here I did not mean the Memento pattern, which can also save, in addition to a partial, a complete snapshot of the 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 you still can’t avoid it, then it’s rather vl-or, and in some situations, when the entire document is changed very rarely and in a complex way, you can refuse to record such changes (tell the user that rollback of changes after this operation will be unavailable).
Here, the developers tried their best. With Qt, you can easily and easily implement Undo / Redo. Write down the recipe. We will 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 advisable to redefine id () to determine the type of operation, so that later in the redefined mergeWith (const QUndoCommand * command) you can check for compatibility between both operations. After that we create an object of class QUndoStack, and put all new operations into it. For convenience, you can take QAction * undo and QAction * redofrom the functions of the stack, which can then be added to the menu, or attached to a button. And if you need to use several stacks, then QUndoGroup will help, 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. A very convenient implementation of op-or undo / redo.
I implemented the simplest example on Qt.
Oops ... Qt did not provide such an option. Even a keyword search for “Qt memento” yielded nothing. Well, okay, there is quite enough there, 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 “Memento” for me), or you will have to implement it yourself. Basically, everything is implemented based on templates. All this can be found without problems. For example, I found this project on GitHub. Here two ideas are realized at once, you can take and see, test.
For me, C # and .NET are still dark forests of distant Siberia, but nevertheless, I really need it. Therefore, it is worth telling at least that I managed to google.
The best examples for me were:
Soon, such an old article was found .
Perhaps you can find something, and perhaps on the basis of this you can take and write your ingenious code for yourbike . Go ahead.
In general, for this kind of tasks in .NET there is an IEditableObject interface , but you will 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 the sake of which even an entire article was written in Habrahabr. Read, fall in love, write.
There are two more examples, but I did not like them at all:
And so, what you need to know in order to choose between two implementation methods only one? Firstly, the implementation of your project, is it written (will it be?) Based on commands, or just a change in the set of values (if neither one or the other - I think it's better to rewrite the project). Secondly, the requirements for memory and performance, because it is possible because of them it is necessary 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? You will need to come to this kind of question after you decide to implement Undo / Redo in the application. I explain: there are two main ways to implement step-by-step undo, for which I assigned the following names: operation-oriented and value-oriented . The first method is based on the creation of operations (or transactions), which have two methods - to do and return everything as it was. The second method does not store any operations - it only records values that have changed at a certain point in time. Both the first and second methods have their pros and cons.
UPD: To keep fewer questions in the future, I remind you that Undo / Redo is intended more for storing 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 has little to do with the goal of Undo / Redo . However, if you really need to - do it, but it's better not to.
Method 1: operation-oriented
Implemented on the basis of the pattern of "Team» ( the Command ).
This method is to store operations in a special stack. The stack has a position (you can say an iterator) that indicates the last operation. When an operation is added to the stack, it will be executed (redo), the position is incremented. To cancel the operation, the stack calls the undo command from the last operation, and then shifts the position of the last operation lower (shifts, but does not delete). If you need to return an action - a shift above, the execution of redo. If, after cancellation, a new operation is added, that is, two solutions: either replace operations above the position with new ones (and then it will be impossible to return to the previous ones), or start a new “branch” on the stack, but the question arises - which branch should I go to then? However, the answer to this question is already not necessary for me to search, since it depends on the requirements for the program.
And so, for Undo / Redo itself, 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) it will be possible to make functions of combining operations into one, in order, for example, to cancel not each letter individually, but words and sentences, when the letters become such, and the like. Therefore, it is also advisable to assign a certain type for each operation, with a difference of which it will not be possible to glue the operations.
And so, the pros:
- With the correct construction of operations, the chances of suffering business logic are low, since operations are performed in which BL
magiccan also be used , only for undo you need to perform actions in the reverse order, and the actions themselves must be inverse (except when one object changes , and others depend on the first, then in this case at the end both undo and redo will need a recount). - Less memory demanding - only operations are recorded, but not the values of variables. If during the operation the recount mechanism is called for almost everything and everything - these changes do not get into the memory, and when canceled, the recount will be needed again.
- More flexible way Undo / Redo.
Minuses:
- We have to implement two whole functions. With incorrect construction of actions in one or both functions, the 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 on 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
It is implemented on the basis of the “Keeper” pattern ( Memento ).
The principle of the method is to know about all possible variables that can change, and at the beginning of possible changes to put the stack “on record”, and at the end - to commit the changes.
However, all changes must be recorded. If only changes made by the user are recorded, but no dependency changes are recorded, then when you cancel / return the dependencies will remain unchanged. Of course, you can call the recalculation of dependencies every time in a tricky way, but this is more like the first method and it will be more convenient then. Implementation methods will be described below, but for now let's look at the advantages and disadvantages.
Pros:
- It does not need recounts - it is not demanding on performance.
- Business logic does not suffer - everything counted just falls into place again.
- An easier way to Undo / Redo.
Minuses:
- More memory intensive, since all dependent objects are saved (otherwise, performance or business logic suffers).
- Not capable of invoking certain operations, since there is only a "memory recovery".
You can also read this Wiki article about the Guardian pattern (Memento) .
Bad method 3: full snapshot
If we talk about exacting memory, then this method will eat a lot. Imagine a situation where when typing only one character, the entire document was saved. And so every time. Presented? Now forget about this method and don’t remember anymore, because it’s not Undo / Redo, but backups.
UPD: And no, here I did not mean the Memento pattern, which can also save, in addition to a partial, a complete snapshot of the 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 you still can’t avoid it, then it’s rather vl-or, and in some situations, when the entire document is changed very rarely and in a complex way, you can refuse to record such changes (tell the user that rollback of changes after this operation will be unavailable).
Implementation methods
C ++: Qt
Operation-oriented
Here, the developers tried their best. With Qt, you can easily and easily implement Undo / Redo. Write down the recipe. We will 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 advisable to redefine id () to determine the type of operation, so that later in the redefined mergeWith (const QUndoCommand * command) you can check for compatibility between both operations. After that we create an object of class QUndoStack, and put all new operations into it. For convenience, you can take QAction * undo and QAction * redofrom the functions of the stack, which can then be added to the menu, or attached to a button. And if you need to use several stacks, then QUndoGroup will help, 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. A very convenient implementation of op-or undo / redo.
I implemented the simplest example on Qt.
I want to see!
Here is the class diagram that I came to (most likely, I’m very mistaken about the direction of the arrows ...):
A certain “server” is also mentioned here, in case it will also be present and interact with your client application. And here are the sources (consider that everything was written "on the knee").
A certain “server” is also mentioned here, in case it will also be present and interact with your client application. And here are the sources (consider that everything was written "on the knee").
Value-oriented
Oops ... Qt did not provide such an option. Even a keyword search for “Qt memento” yielded nothing. Well, okay, there is quite enough there, 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 “Memento” for me), or you will have to implement it yourself. Basically, everything is implemented based on templates. All this can be found without problems. For example, I found this project on GitHub. Here two ideas are realized at once, you can take and see, test.
C #: .NET
For me, C # and .NET are still dark forests of distant Siberia, but nevertheless, I 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 pattern of commands on .NET.
- And just a good example of Undo / Redo using Generics.
Soon, such an old article was found .
Perhaps you can find something, and perhaps on the basis of this you can take and write your ingenious code for your
Value-oriented
In general, for this kind of tasks in .NET there is an IEditableObject interface , but you will 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 the sake of which even an entire article was written in Habrahabr. Read, fall in love, write.
There are two more examples, but I did not like them at all:
Conclusion
And so, what you need to know in order to choose between two implementation methods only one? Firstly, the implementation of your project, is it written (will it be?) Based on commands, or just a change in the set of values (if neither one or the other - I think it's better to rewrite the project). Secondly, the requirements for memory and performance, because it is possible because of them it is necessary 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!
