Implementing infinite undo/redo (Matt Gertz)
(This is the second part in my series on creating a Paint-by-Numbers designer application.)
This is the first application that I’ve built specifically for this blog, where I’m actually writing the code while I’m writing the blog. (For example, the Euchre game that I blogged about was something I’d written a couple of years ago, so there were no surprises for me when writing the posts about it.) As such, for this series I’m spending a lot more time documenting what my thoughts are while coding than I normally do, and it’s very interesting have that all down in print. It particularly requires me to think hard about modular code, because I don’t know precisely what I’ll be writing in blogpost n + 1, and yet I have to show code in blogpost n and I don’t want there to have to be major changes in methods that I’ve already posted. It turns out that I mostly did well in the last post, but in order to accommodate the undo/redo in an elegant way, I needed to make minor changes to the ToggleCell() method as well as to the mouse event handlers. But I’m getting ahead of myself…
Undo/redo is actually pretty darn easy to implement, particular in this case where a cell has a binary value (either it gets set or reset – there’s no ambiguity). There are three ways that developers handle undo/redo:
1. Don’t support it at all. This sounds lame, but, despite what I said above, there are cases where undo/redo is just too complicated or impossible – real-time operating system scenarios, modifications to data that are subsequently acted upon, and so on.
2. Support one level of undo/redo – that is, you can undo the last thing you did (and then redo it if you like), but nothing prior to that. In the extreme case, the redo command doesn’t exist at all, and undo just toggles between rolling back the last action and redoing it.
3. Support “infinite” undo/redo, where the list of actions is bounded only by the available memory, and a full stack of undo/redo is available. Sometimes the undo/redo toolbar items have dropdowns associated with them displaying all of the changes that have been made, so that you can undo back to a known state in the middle of the stack by just one mouse click.
If you can support (2), then with just some extra memory you can support (3) – there’s very little additional logic needed. What I’ll be demonstrating in this post is a type (3) undo/redo mechanism. I won’t have dropdowns (because entries like “colored Cell(4,5)” are not particularly useful), but I will be batching cell changes together which will speed things up for the user.
As a user, I probably would consider a pen stroke as one complete action – I would be annoyed if I had to choose “Undo” for each and every pixel in that pen stroke. Consequently, I’m going to be grouping grid cell changes so that they’re bounded by a MouseDown and MouseUp event – when “Undo” is chosen, every cell that changed in the last drawing stroke will be reset to its prior state. How do we cache this information? Well, let’s start with the per-cell action – one pixel in the pen stroke, as you might say. A class such as the following completely identifies anything that happened to that cell:
Private Class GridAction
Public Row As Integer
Public Column As Integer
Public Erased As Boolean
Public Sub New(ByVal r As Integer, ByVal c As Integer, ByVal e As Boolean)
Row = r
Column = c
Erased = e
I’ve made this class a subclass of my grid form. It contains the row & column information of the cell, as well as what happened to it (erased or not). When I perform an “undo” on this action, I just do the opposite of what was done to it before, whereas a redo will execute it precisely as it was executed before. Now, I need to cache a list of these actions from the MouseDown to the MouseUp, and I’ll use a List to do this:
Private CurrentDraw As List(Of GridAction)
And that will contain all of the “pixels” in the “pen stroke” – this the smallest level that undo/redo will work on. Finally, I need to have a list of these “strokes” for the undo stack and the redo stack:
Private UndoList As New List(Of List(Of GridAction))
Private RedoList As New List(Of List(Of GridAction))
Yep, they are lists of lists, and I will treat them as if they were stacks (i.e., items will be inserted at position 0, and retrieved from there as well). Note that I’m using generic lists introdu
ced in VB 2005 – they allow me to quickly create a list for an arbitrary class without having to write any class-specific code or having to cast them to/from Object.
For undo, the plan is to pop the first item off the undo list, iterate through its GridActions and issue ToggleCell calls to un-draw or un-erase the given cells. However, while ToggleCell does take a row and a column for arguments, it doesn’t take an argument for draw/erase. This is because I coded it thinking that ToggleCell would only ever be called by the mouse events, and thus could check for itself as to whether or not an erase was intended (by checking the status of the shift key). This assumption turns out to be erroneous, so I’ll change ToggleCell to take an extra argument (changes are underlined):
Private Sub ToggleCell(ByVal row As Integer, ByVal col As Integer, _
ByVal drawErase As Boolean)
then remove the line in ToggleCell which checks the shift key and instead change the Mouse event handler to pass that argument to ToggleCell:
ToggleCell(row, col, My.Computer.Keyboard.ShiftKeyDown)
and now I can write code to iterate through a given GridAction List:
Private Sub DoActions(ByRef stroke As List(Of GridAction), ByVal Inverted As Boolean)
For Each Item As GridAction In stroke
If Inverted = True Then
ToggleCell(Item.Row, Item.Column, Not Item.Erased)
ToggleCell(Item.Row, Item.Column, Item.Erased)
which will be called by the undo/redo commands with the “Inverted” argument set according to whether we’re doing the opposite (i.e., undo) or not (i.e., redo).
I now need to write code to get the changes into the undo stack. In my last post, I wrote one handler to cover all of the mouse events because they essentially did the same things, but I outsmarted myself – in the case of undo/redo, MouseDown, MouseMove, and MouseUp all have different parts to play. So, the first thing I’ll do is to clone the original handler for each of the three events. Now, I can specialize the handling:
– For MouseDown, I’m at the beginning of a “pen stroke,” so you might think that I’d just create a new List of GridActions, put the first change into it, and leave it at that. However, I don’t want to create empty undo units, so if the MouseDown happens over an area of the form which isn’t part of the grid, I want to ignore it. To help me determine this, I’m going to tweak ToggleCell again, changing it from a Sub into a Function which will return True if a cell was actually changed:
Private Function ToggleCell(ByVal row As Integer, _
ByVal col As Integer, ByVal drawErase As Boolean) _
If drawErase = True Then
If Grid(row, col) = 1 Then
Grid(row, col) = 0
Return True ‘ We actually toggled a cell
If Grid(row, col) = 0 Then
Grid(row, col) = 1
Return True ‘ We actually toggled a cell
Return False ‘ We didn’t make any changes
So now I can add/change the following code in the handler: