February 15, 2016 at 11:53Implementation of multilevel undo / redo functionality using an example of a spreadsheet prototype
Introduction
The Undo and Redo buttons, which allow you to cancel and return any user actions, as well as see a list of all the actions performed in the list, are the de facto standard for applications such as word processors and development environments, graphics and CAD editors, systems editing and editing sound and video. They are so familiar to the user that the latter perceives their presence as a given, just one functionality along with dozens of others. But from the point of view of the developer, the requirement for the presence of undo is one of the factors affecting the entire architecture of the project, which is determined at the very early stages of the development project.
In open sources, there is quite a bit of information on how to practically implement the undo / redo functionality. Classical book by E. Gamma et al.“Object-oriented programming techniques. Design Patterns ” briefly mentions the suitability of the“ team ”pattern for this purpose; there is a lot of general information on the subject on the Internet, but we were not able to find a sufficiently complete, well-developed implementation example. In our article, we will try to fill this gap and, based on the experience of the author, demonstrate a detailed example of an application architecture that supports undo / redo, which can be taken as the basis for other projects.
The code examples in the article are given in the Java language, but there is nothing Java-specific in them and all the ideas presented here are suitable for any object-oriented language (the author himself first implemented them in Delphi).
It should be noted that for various needs and types of applications, there are various "undo models": linear - with the cancellation of operations strictly in the reverse order, and non-linear - with the cancellation of arbitrary operations from the history of the actions performed. We will talk about the implementation of linear Undo in a system with synchronized modifications to the data model , that is, one in which simultaneous modification of the internal state of the data model in different execution threads is not allowed. A classification of possible undo models is provided, for example, in a Wikipedia article .
Naturally, we assume that the application implements the separation of the data model (Model) from the view (View), and the functionality of undo is implemented at the level of the data model, in the form of the undo () and redo () methods of one of its classes.
Illustrative example
As an illustrative example, the article considers the data model of an application prototyping a spreadsheet (in the style of MS Excel / LibreOffice Calc). There is a sheet (for simplicity - only one), consisting of cells whose values and sizes can be changed, rows and columns - to be interchanged, and all these actions, respectively, are canceled. Source codes and corresponding unit tests are available at https://github.com/inponomarev/undoredo and can be compiled and executed using Maven.
The main entities in our example are:
- worksheet - class Worksheet ,
- rows and columns - Row and Column classes (descendants of the AxisElement class ),
- cells - class Cell .
The resulting simple data model is presented in the class diagram in the figure below:
Without going into details of the implementation of spreadsheets, we briefly outline the basic principles of the source code device. Although a spreadsheet sheet is presented to the user as a two-dimensional data array whose boundaries extend far beyond the screen, the use of a two-dimensional array for the data model is not justified either in terms of memory consumption or in terms of the speed of typical operations. For example, if in earlier versions of MS Excel 65536 columns and rows were allowed, then allocating memory for 65536 2 , i.e. 4 billion cells, would be just technically impossible in a 32-bit system.
The solution is to use dictionaries based on trees and hash tables to store only the changed values, substituting a default value for the value that is not in the dictionary.
To store Row and Column instances , TreeMap dictionaries are used.
Model root class and cancelable methods
The Worksheet class in our example is central: 1) work with all other business logic objects begins with obtaining an instance of this particular class, 2) instances of other classes can work only in the context of the Worksheet object , 3) through the save (...) method and The static method load (...) it saves to the stream and restores the state of the entire system from the stream. We will call this class the root class of the model . As a rule, when developing applications in the Model-View-Controller architecture, there is no difficulty in determining what is the root class of the model. It is he who is supplied with methods specific to the functionality of Undo / Redo.
Definition should also not be difficult.methods that change the state of the model . These are methods whose call result must be undone by undo. In our example, the following:
- setCellValue (int row, int col, String value) - sets the cell value (for simplicity, we believe that cells can only accept string values!),
- insertValues (int top, int left, String [] [] value) - pastes into the cells the values of a two-dimensional array (for example, obtained from the clipboard),
- setRowHeight (int row, int height) , setColWidth (int col, int width) - set the row height and column width,
- insertColumnLeft (int colNum) , insertRowAbove (int rowNum) - insert columns and rows,
- deleteColumn (int colNum) , deleteRow (int rowNum) - delete columns and rows,
- moveColumn (int from, int to) , moveRow (int from, int to) - move columns and rows along with the contents, replacing the contents of the final column / row.
In a real application, of course, there can be many more. Each of them needs to compare the corresponding class of the team (which will be discussed later), and the methods must be rewritten in a special way.
Undo and Redo Stacks
In the linear Undo model, operations are canceled in such a way as to preserve the sequence of actions performed on the document. For example, if a column was first added to the document, and then its width was changed, then canceling these operations is possible only in the reverse order, and returning is direct. Therefore, to store operations to be canceled and restored, it is natural to use two stacks on linked lists, which are part of the model root class. When the method that changes the state of the model is called, the Redo stack is reset, and the Undo stack is replenished with the next value. Running the Undo command should push the value out of the Undo stack and push it to the Redo stack. The execution of the Redo command, if any, should again return the value to the Undo stack (see. Fig.).
The contents of these stacks are the descendant objects of the Command class , which will be discussed later. Here is a list of public methods of the root class of business logic that provide access to the functionality of Undo / Redo:
- undo () - undo the action performed by calling any method that changes the state of the model, and transferring it to the Redo stack:
Command cmd = undoStack.pop(); cmd.undo(); redoStack.push(cmd);
Each repeated call rolls back the changes in the chain until the Undo stack is exhausted, after the exhaustion of the stack, the repeated call to the method produces nothing. - redo () - return an action that was canceled by calling undo, and pushing it back onto the undo stack. The repeated call rolls over operations undone by Undo until the Redo stack is exhausted, after which the call to redo () is ignored. The entire Redo stack is reset after calling any method that changes the state of the model.
- getUndoStack () , getRedoStack () - return the entire stacks so that the user can create a list of operations available for cancellation or retry.
- isUndoActive () , setUndoActive (boolean value) - allows to deactivate the Undo mechanism (activated by default). It is necessary for 1) improving performance and reducing memory consumption when making very large changes in the state of a document 2) working with a document from external applications through interfaces in which the Undo / Redo functionality is not available.
Team pattern
Methods that change the state of a model can have different parameters and generally be defined in different classes of the model. Completely encapsulate information about the parameters and the target object of the method, “comb all under one comb”, allows the design pattern “team”. The non-triviality of this pattern lies in the fact that some entities typically describe classes in object-oriented code . Here, the class describes not the essence, but the action performed by the method that changes the state of the model, "taking" this prerogative from the method itself.
The class of each command inherits from the base abstract class Command . Command itself has only three abstract methods: execute , undoand getDescription , which have (what is important!) no parameters. This allows you to execute and cancel commands using the undo () and redo () methods of the root class that “know nothing” about operations that are performed or canceled. The getDescription () method should return a text description of the action: this description will be available to the user in the list of actions to be canceled.
The heirs of the Command class , in addition to implementing its abstract methods, can contain any number of additional fields containing information about the command launch parameters and information necessary to cancel an already executed command and display a text description of the executed command. The execute () methodshould contain the code that is usually contained in a method that changes the state of the model, only instead of the method parameters this code should use the fields of the command class. Note that the team operates on the internal state of the model object in the same way as its own method did before. Therefore, the team must have access to the hidden (private) fields of the model object. In Java, this is convenient if you make the Command descendant class nested in the corresponding model class. In our application, for example, the SetSize command is nested in the AxisElement model class , the rest of the commands are nested in Worksheet .
The undo () method , in turn, should be able to undo the consequences of calling the execute () method. All the information necessary for this should be stored in the fields of the team class. The matter is simplified if we understand that at the time the undo () method is called, the state of the business logic objects will always be identical to what it was immediately after the execution of the corresponding execute () method . If since then the user has performed other operations, then before he gets to undo () of the current command, he will have to execute undo () for all the commands that were called after it. In practice, understanding this principle greatly facilitates the writing of the undo () method and reduces the amount of information stored in the command.
Consider the implementation of the command that sets the value of the cell:
final class SetCellValue extends Command {
private final int row;
private final int col;
private String val;
public SetCellValue(int row, int col, String newValue) {
this.row = row;
this.col = col;
this.val = newValue;
}
@Override
public String getDescription() {
return ("Ввод данных");
}
private void changeVal() {
String oldValue = getCellValue(row, col);
Row r = rows.get(row);
Column c = columns.get(col);
//.... получение объекта cell по row и col...
cell.setValue(val);
//....
val = oldValue;
}
@Override
public void execute() {
changeVal();
}
@Override
public void undo() {
changeVal();
}
}
As you can see, the class has variables for storing the cell address and its value. Moreover, in order to save memory, only one variable can be used to save the value: the new one if the execute () method has not been executed yet, or the old one if the execute () method has already been executed. That is, the fact that the execute () and undo () methods are executed in sequence is used here. The getDescription () method can use class variables to provide a more detailed description of the command.
Undo Method Template
How are commands used in cancelable methods? If usually such methods, taking into account their parameters, simply perform some actions on the model, then in a system with undo all of them must strictly perform the following three operations:
- create an instance of the corresponding command ( Command descendant class ),
- initialize command fields with method parameters and, possibly, additional information,
- execute the execute (Command cmd) method of the root object, passing the newly created and initialized command as a parameter.
In our example, the implementation of the setCellValue method looks like this:
public void setCellValue(int row, int col, String value) {
Command cmd = new SetCellValue(row, col, value);
execute(cmd);
}
All the other cancelable methods look similar.
The execute (Command cmd) method of the root class executes the command action, dumping the redo stack and pushing the command onto the undo stack:
undoStack.push(cmd);
redoStack.clear();
cmd.execute();
From this moment, the team becomes part of the chain of canceled / repeated actions. As mentioned above, calling the undo () method in the root class calls the undo () method of the command at the top of the Undo stack and transfers it to the Redo stack. Calling the redo () method of the root class, in turn, executes the execute () method of the command at the top of the Redo stack and pushes it onto the Undo stack.
Reusing Command Classes
So, for tasks that in the usual case require writing one method, on systems with undo you need to create a whole class, which leads to fair fears about the amount of code and the complexity of its support: in real projects, the number of canceled methods is tens.
In fact, command classes can be significantly less due to their universalization and the use of one command class for several canceled methods. For example, the main code of the SetCellValue class , in fact, can be used for any methods that require changing one value of a variable. It is possible to make a command class more universal both by adding additional fields, and by parameterizing the class.
For example, consider the universal delete command, which is used to delete both rows and columns of a table:
final class Delete extends Command {
private final int num;
private final T deleted;
private final TreeMap map;
Delete(TreeMap map, int num) {
this.num = num;
this.map = map;
deleted = map.get(num);
}
@Override
public String getDescription() {
return String.format("Удаление %s %d", map == columns ? "столбца" : "строки", num);
}
@Override
public void execute() {
internalDelete(map, num);
}
@Override
public void undo() {
internalInsert(map, num);
map.put(num, deleted);
}
}
private static void
internalDelete(TreeMap map, int num) {
//...
//удаление из словаря записи с ключом num
//и сдвиг всех записей с ключом > num на минус одну позицию
//...
}
private static void
internalInsert(TreeMap map, int num) {
//...
//сдвиг всех записей с ключом >= num на плюс одну позицию
//...
}
}
Its use in the deleteColumn and deleteRow methods is as follows:
public void deleteColumn(int colNum) {
Command cmd = new Delete(columns, colNum);
execute(cmd);
}
public void deleteRow(int rowNum) {
Command cmd = new Delete(rows, rowNum);
execute(cmd);
}
Macros
Sometimes it may turn out that a method call that changes state is too small a unit to be stored on the Undo stack. Consider the procedure insertValues (int top, int left, String [] [] value) to paste values from a two-dimensional list (for example, from the clipboard) into a document. This procedure in a loop updates the document cells one by one with the values of the cells from the buffer. Thus, if we insert a piece of a 4 × 4 table, then, from the point of view of the Undo mechanism, we make 16 changes to the document cells. This means that if the user wants to cancel the result of the insert, then the Undo button will have to be pressed 16 times, while in the table, 16 cells will restore their previous values one after another.
Of course, this is wrong: the results of operations such as this should be canceled and restored as a whole, and displayed in a single line in the list of canceled operations. To make this possible, macros are used.
The idea of implementing a macro is simple: it is just a special descendant of the Command class , containing a chain of other commands inside it, as shown in the figure:
The execute () method of the MacroCommand class runs through its own list of commands and executes their execute () methods . When calling the undo () method of the same macro, it runs through the same list of commands in the reverse order and calls their undo () methods .
Macro methods similar to the clipboard paste method in applications built in the Model / View / Controller architecture, as a rule, are not part of the model, but are implemented at the controller level. Often they represent only the automation of some routine work, the need for which, depending on the type of user interface, may or may not exist. In addition, often there is a need to group several user actions into one: for example, text editors group user input of words and sentences into one macro action, instead of clogging the undo stack with entries for entering each individual letter.
Therefore, macro support can and should be implemented at an abstract level, in an application-independent manner. This is done by adding the public methods beginMacro (String description) and endMacro () to the model root class . Methods are called before and after the completion of macro actions. By calling beginMacro (...) with a string parameter, the value of which will then be available to the user in the list of canceled operations, we generate an object of type MacroCommand and temporarily replace the Undo stack with the internal macro stack. Thus, after calling beginMacro, any subsequent transfer of the command to the execute (...) methodthe root class does not directly write it to the Undo stack, but to the internal stack of the current macro (which, in turn, is already written to the Undo stack). The endMacro () call returns everything to its place. Multilevel nesting of macros into each other is also allowed.
Track unsaved changes
Having undo functionality provides a reliable way to track unsaved changes to a document. This is necessary to implement the correct behavior of the "Save" button in the application:
- the “Save” button should be active if and only if unsaved changes are present (otherwise there is no need to save: the document has not been changed),
- when closing a document, it makes sense to ask the user if he wants to save the changes only if unsaved changes are present.
In our example, the presence of unsaved changes is returned by the isModified () method . It is implemented as follows: each time the save (...) method is called, the current top of the Undo stack is stored in the lastSavedPoint variable . When the isModified method is called, the current top of the Undo stack is compared with the lastSavedPoint value : if they are equal, then there are no unsaved changes. With the undo mechanism disabled, the isModified () method always returns true .
Conclusion
We examined the basic principles for implementing a linear multi-level Undo / Redo using an example that, in our opinion, is universal enough to serve as a template for other projects.
It is not surprising that the functionality of undo and redo makes quite serious demands on the architecture of the application and the professionalism of the developers. But such things as strict adherence to the Model / View / Controller architecture and a well-designed model (writing each of the methods that change the state of the model in a system with undo is "more expensive"), despite some laboriousness, pays off for the high quality and reliability of the program being created, which ultimately will result in the satisfaction of its users.
* * *
Full source codes and corresponding unit tests of the example discussed in the article are available at https://github.com/inponomarev/undoredo and can be compiled and executed using Maven.