Undo/Redo Stacks

The BASeBlock Editor has had an Undo/Redo stack for quite a while. The implementation of this logic is relatively simple, but the implementation- or rather, my recent re-implementation- seems like a good subject for a blog post.

Basically, an Undo/Redo Stack Let’s your Program reverse through changes that have been made, and then, if necessary, go forward through those changes. What makes this problem interesting is that, by and large, the core logic is really quite similar. I will attempt to outline the process of creating a Generic Undo/Redo Object that can be used in many contexts.

First, we’ll start with The abstract base class that we will use to represent Undo Elements:

Since we don’t know what, specifically, is being handled, we use this abstract class and provide only very basic methods. The DateTime can be used on appropriate menus or as a sort key, and the Description can be used for any menu text, or other UI elements as needed by the app consuming the class.

This will be used for a generic class, which I will call UndoRedoManager. This will, unsurprisingly, manage the undo and redo operations, or, more specifically, it will manage the data structures dealing with the Undo and Redo information. In order to actually undo, we will need to delegate the task to the caller, on the assumption that they know more about the StackItem. We will call the Events HandleRedo and HandleUndo, and they will take a simple EventArgs. First, we will define the EventArgs class definition.

The Event Argument class is relatively simple; we just have a field for the StackElement, and a field for Cancel, which we will deal with when we fire the event. We use a generic class because we need to support the management of any class type that derives from UndoRedoStackItem, where the appropriate application-specific data will be dealt with and stored.

The “UndoRedoManager” class we will create will be designed as generically as possible. And, to be honest, my original implementation will be a naive one, each Stack Element will be designated as storing a complete “state” for whatever the application is doing. A better approach for applications that have a large amount of state data is to instead store the changes, rather than the entire thing, but that sort of extra functionality is best discussed and designed after we have the basic framework in place.

The first step is to designate what we need to keep track of in the ‘Manager’ Class, as well as our events.

We need a Maximum size, otherwise it’s possible for the stack to fill up with old Undo elements. We keep a stack for Undo as well as Redo elements. The actual public functionality we need to implement is a method to Undo, a Method to Redo, and a Method to “Push” a new element onto the Undo stack (register a change).

We’ll start with the first method that will usually be used: PushUndo. This will accept a parameter that is the type of the generic type parameter. It will need to:

1. Make a Deep copy of the item being pushed.
2. Push that deep copy onto the Undo Stack
3. Trim the stack to the maximum size.
4. Clear the Redo Stack

Here is the code to do that. TrimStack() is private method who’s implementation I will cover shortly:

Most of this is self-explanatory. TrimStack’s implementation is a bit trickier, since the Stack class is a bit less revealing beneath it’s Clothing, but we can seduce it:

TrimStack here is written to take any Stack Type, though, arguably, this isn’t necessary in this current implementation. (No reason, however, to make it more specific, in my opinion)

First, if the stack has fewer elements than the passed maximum, we have no work to do, so we return right off the bat. Making our work quite easy.

If the Stack does have more elements than the maximum, we pop elements until either the stack to trim is empty (for some reason) or the temporary stack has maxelements elements.

The effect here is to grab the top maxelements items. After this, we clear the stack and push the elements we popped.

The task of performing the Undo has the following steps:

1. If CanUndo returns false, return only null.
2. Otherwise, Peek at the top element from the UndoStack.
3. Create a new instance of the EventArgs class with the peeked element.
4. Fire the Undo event with the created EventArgs.
5. If the Event’s Cancel field has not been set, perform a Pop on the Undo Stack, and Push the item we retrieved earlier to the Redo Stack.
6. Return the Item we removed

The idea here is that the Event handler that is tied to the class will do the application-specific activity for the “undo” operation- we don’t know what the data is, nor what it represents, but the program using us will, so we leave them to it. This also enables the less naive implementation concept that I’ll be using later to extend this.

And that is pretty much the core implementation. Of course, as it is, we don’t actually have an implementation for the StackElement class. Since that is something we left up to the client application, let’s create one. Here is a small Windows Form that utilizes the aforementioned classes as well as providing an implementation of the Stack Item for a TextBox:

The Designer class:

Proper code-behind class:

In the above implementation, TextUndoItem is the UndoRedoStackItem implementation I created for textboxes; this stores the selection start and length as well as the full text. The Actual Undo implementation was less trivial than I had hoped; in this case I created a “Managing” class that uses the UndoRedoManager specifically with Textboxes, hooking the appropriate textbox events and implementing a delay after typing stops before Undo’s are pushed onto the stack. This is a very simple implementation of this particular class design; BASeBlock uses a very similar class in it’s Editor, but for the far more complex structures dealt with there, which include several lists of objects.

The extension and addition to this design that I mentioned earlier consists of storing not the entire state, but rather what changed from the previous element. This is unlikely to be a trivial thing to implement.