Implementing multi-level undo / redo functionality using the example of a spreadsheet prototype

Introduction

The Undo and Redo buttons, which allow you to undo and redo any user actions, as well as view a list of all actions performed, are the de facto standard for such applications as word processors and development environments, graphics editors and CAD 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 developer's point of view, the requirement for the presence of undo is one of the factors affecting the entire project architecture, defined at the earliest stages of the development project.



In open sources there is quite a bit of information about how to practically implement undo / redo functionality. The classic book of 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 this topic on the Internet, but we could not find a sufficiently complete, well-developed example of implementation. In our article we will try to fill this gap and, based on the experience of the author, to demonstrate a detailed example of the architecture of an application supporting undo / redo, which can be taken as a basis for other projects.

The code examples in the article are in Java, 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 different “undo models”: linear - with the cancellation of operations strictly in reverse order, and nonlinear - 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 of the data model , that is, one in which the simultaneous modification of the internal state of the data model in different execution threads is not allowed. The classification of possible undo models is given, for example, in a Wikipedia article .

We naturally assume that the application implements the separation of the data model (Model) from the view (View), and the undo functionality is implemented at the data model level , in the form of the undo () and redo () methods of one of its classes.

Illustrative example

As an illustrative example, the article discusses the data model of an application that prototypes a spreadsheet (in the style of MS Excel / LibreOffice Calc). There is a sheet (for simplicity - only one), consisting of cells, the values ​​and dimensions of which can be changed, rows and columns - interchanged, and all these actions, respectively, are cancelable. Source codes and related 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:

1. worksheet - Worksheet class,
2. rows and columns - Row and Column classes (inherited from the AxisElement class),
3. 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 note briefly the basic principles of the source code. Although the spreadsheet sheet is presented to the user as a two-dimensional data array, the boundaries of which go 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 performance of typical operations. For example, if in early versions of MS Excel, 65,536 columns and rows were allowed to exist, then memory allocation for 65536 ² , i.e. 4 billion cells, would be simply technically impossible in a 32-bit system.

The solution is to use tree-based dictionaries and hash tables to store only the changed values, substituting some default value instead of the value missing in the dictionary.

To store instances of Row and Column , the TreeMap <Integer, Row> rows and TreeMap <Integer, Column> columns dictionaries are used in the Worksheet class. To store Cell instances, use the HashMap <Column, Cell> cells dictionary in the Row class. The values ​​of this hash table are references to Cell objects, and the keys are column objects. This approach to data storage allows you to find the optimal balance between speed and the amount of used memory for all practically necessary operations on the contents of the Worksheet .

Model root class and undone methods

The Worksheet class in our example is central: 1) working 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 It saves the static load (...) method to the stream and restores the state of the entire system from the stream. This class we will call 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.

Also, it should not be difficult to determine the methods that change the state of the model . These are the methods whose call result must be undone. In our example, the following:

• setCellValue (int row, int col, String value) - sets the cell value (for the sake of simplicity, we assume that cells can take only string values!),
• insertValues ​​(int top, int left, String [] [] value) - inserts 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 the columns and rows along with the contents, replacing the contents of the final column / row.

In a real application, of course, they can be much more. Each of them is required to compare the corresponding command class (which will be discussed further), and the methods must be rewritten in a special way.

Undo and redo stacks

In the Undo linear 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 the cancellation of these operations is possible only in the reverse order, and the return - in the forward. Therefore, to store operations subject to cancellation and restoration, it is natural to use two stacks on linked lists, which are part of the root class of the model. When calling a method that changes the state of the model, the Redo stack is cleared, and the Undo stack is replenished with the next value. Executing the Undo command should fetch the value from the Undo stack and transfer it to the Redo stack. Running the Redo command, if it happens, should return the value to the Undo stack again (see the figure).



The contents of these stacks are objects inherited from the Command class, which will be discussed later. Here is a list of public root-class business logic methods giving access to the Undo / Redo functionality:

• undo () - canceling an 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 callback rolls back the changes in the chain until the Undo stack is exhausted. After the stack is exhausted, the method is not called again.
  
• redo () - returns the action canceled by the call to undo, and putting it back on the undo stack. The repeated call rolls operations canceled by Undo until the Redo stack is exhausted, after which the redo () call is ignored. The entire Redo stack is reset after calling any method that changes the state of the model.
• getUndoStack () , getRedoStack () - return entire stacks so that the user can create a list of operations available for undo or redo.
• isUndoActive () , setUndoActive (boolean value) - allows you to deactivate the Undo mechanism (activated by default). It is necessary to 1) improve performance and reduce memory consumption when making very large changes in the state of a document 2) working with a document from external applications via interfaces in which the Undo / Redo functionality is not available.

Team Pattern

Methods that change the state of a model may have different parameters and generally be defined in different classes of the model. Fully encapsulate information about the parameters and the target object of the method, “combing one size fits all”, allows the design pattern “command”. The nontriviality of this pattern is that usually entities in object-oriented code describe some entities . Here, the class does not describe the entity, but the action performed by the method changing the state of the model, “taking away” this prerogative from the method itself.

The class of each command is inherited from the base abstract class Command . By itself, the Command has only three abstract methods: execute , undo and getDescription , which do not have (what is important!) No parameters. This allows you to execute and cancel commands with the undo () and redo () methods of the root class, “knowing nothing” about those 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 canceled actions.



The heirs of the Command class, in addition to the implementation of its abstract methods, can contain as many additional fields as possible 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. In this case, the execute () method must contain the code that is usually contained in the method that changes the state of the model, but 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 just as it used to do its own method. Therefore, the team must have access to the hidden fields of the model object. In the Java language, this is convenient to achieve if you make the successor class Command 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 the Worksheet .

The undo () method, in turn, should be able to undo the consequences of calling the execute () method. All necessary information for this should be stored in the fields of the team class. The matter is simplified if we understand that at the time of calling the undo () method, the state of business logic objects will always be identical to what it was immediately after the execution of the corresponding execute () method. If the user has performed other operations since then, then before he gets to the undo () of the current command, he will have to execute undo () for all commands that have been called after her. In practice, the understanding of 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 setting 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 we see, there are variables in the class for storing the cell address and its value. And in order to save memory, you can do only one variable to save the value: new if the execute () method has not yet been executed, or old if the execute () method has already been completed. That is, the fact that the execute () and undo () methods are executed in turn is used here. The getDescription () method can use class variables to make the command description more detailed.

Cancel Method Template

How are commands used in abolished 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 strictly must perform the following three operations:

1. create an instance of the corresponding command (heir class Command ),
2. initialize the command fields with method parameters and possibly additional information
3. 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); } 

Approximately all other canceled methods look the same.

The root class's execute (Command cmd) method performs the command action, clears the redo stack, and puts the command on the undo stack:

  undoStack.push(cmd); redoStack.clear(); cmd.execute(); 

From this point on, the team becomes part of a chain of undo / redo 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 root class's redo () method, in turn, executes the execute () method of the command at the top of the Redo stack and transfers it to the Undo stack.

Command Class Reuse

So, for tasks that normally require writing one method, systems with undo need to create a whole class, which leads to fair concerns about the amount of code and the complexity of its support: in real projects, the number of canceled methods is in the tens.

In fact, there can be significantly less command-classes due to their universalization and the use of one command-class for several methods being abolished. For example, the main code of the SetCellValue class, in fact, can be used for any methods in which you want to change one value of a variable. You can make the command class more universal both by adding additional fields and by parametrizing the class.

For example, consider the universal delete command, which is used to delete both rows and columns in a table:

  final class Delete<T extends AxisElement> extends Command { private final int num; private final T deleted; private final TreeMap<Integer, T> map; Delete(TreeMap<Integer, T> 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 <T extends AxisElement> void internalDelete(TreeMap<Integer, T> map, int num) { //... //      num //      > num     //... } private static <T extends AxisElement> void internalInsert(TreeMap<Integer, T> map, int num) { //... //     >= num     //... } } 

Its use in the deleteColumn and deleteRow methods is as follows:

  public void deleteColumn(int colNum) { Command cmd = new Delete<Column>(columns, colNum); execute(cmd); } public void deleteRow(int rowNum) { Command cmd = new Delete<Row>(rows, rowNum); execute(cmd); } 

Macros

Sometimes it may turn out that a call to a state-changing method is too small a unit to be stored in the Undo stack. Consider the procedure insertValues ​​(int top, int left, String [] [] value) inserting values ​​from a two-dimensional list (for example, from the clipboard) into a document. This procedure, in a loop, one after another, updates the cells of the document 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 cells of the document. This means that if the user wants to undo the result of the insertion, then he will have to press the Undo button 16 times, while in the table one after the other 16 cells will restore their previous values.

Of course, this is wrong: the results of operations like this should be canceled and restored as a whole, and displayed in the list of canceled operations in one line. In order to make this possible, macros are applied.

The idea of ​​implementing a macro is simple: it is just a special inheritor of the class Command , containing within itself a chain of other commands, as shown in fig .:



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 like 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, it often becomes necessary to group several user actions into one: for example, text editors group the user into entering a single macro-action, instead of littering the undo-stack with entries about entering each individual letter.

Therefore, support for macros can and should be implemented at an abstract level, independent of the application. This is done by adding the public methods beginMacro (String description) and endMacro () to the root class of the model. Methods are invoked before and after macro actions. 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 an internal macro stack. Thus, after a call to beginMacro, any subsequent transfer of a command to the execute (...) method of the root class results in its writing not directly to the Undo stack, but to the internal stack of the current macro command (which, in turn, is written to the Undo stack ). The call to endMacro () returns everything to its place. Multilevel attachment of macros into each other is also allowed.

Tracking Unsaved Changes

The presence of 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:

1. 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),
2. when closing a document, it makes sense to ask the user whether 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: with each call to the save (...) method, 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, there are no unsaved changes. When the undo mechanism is deactivated, the isModified () method always returns true .

Conclusion

We looked at the basic principles of implementing linear multilevel Undo / Redo with 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 application architecture and the professionalism of the developers. But such things as strict adherence to the Model / View / Controller architecture and a well-thought-out model (writing each of the methods that change the state of the model in a system with undo “costs more”), despite some labor intensity, pays off with the high quality and reliability of the program being created which ultimately will result in the satisfaction of its users.

* * *

The complete source codes and the 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.