Implementing infinite undo/redo (Matt Gertz)

Implementing infinite undo/redo (Matt Gertz)

  • Comments 8

(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.

Implementing Undo/Redo

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

        End Sub

    End Class

 

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 introduced 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)

            Else

                ToggleCell(Item.Row, Item.Column, Item.Erased)

            End If

        Next

    End Sub

 

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) _

 As Boolean

 

' ...

 

            If drawErase = True Then

                If Grid(row, col) = 1 Then

                    Grid(row, col) = 0

                    Invalidate(invalRegion)

                    Return True ' We actually toggled a cell

                End If

            Else

                If Grid(row, col) = 0 Then

                    Grid(row, col) = 1

                    Invalidate(invalRegion)

                    Return True ' We actually toggled a cell

                End If

            End If

 

' ...

        Return False ' We didn't make any changes

End Function

 

So now I can add/change the following code in the handler:

            If ToggleCell(row, col, My.Computer.Keyboard.ShiftKeyDown) = True Then

                CurrentDraw = New List(Of GridAction) ' We'll always need a new list in this case

                Dim CurrentCell As New GridAction(row, col, _

My.Computer.Keyboard.ShiftKeyDown) ' Memorize the cell change

                CurrentDraw.Insert(0, CurrentCell) ' Add it to the total stroke

            End If

 

-          For MouseMove, it’s pretty much identical to the changes I made for MouseDown, except that I’ll check to see if CurrentDraw is Nothing and only instantiate the object for it if it’s Nothing.  So, if the user does the MouseDown off-grid but drags the mouse onto the grid, I’ll still have a way to create the action list and actually capture those changes:

            If ToggleCell(row, col, My.Computer.Keyboard.ShiftKeyDown) = True Then

                If CurrentDraw Is Nothing Then

                    CurrentDraw = New List(Of GridAction) ' Create a list to catch

' the pen stroke if none exists

                End If

                Dim CurrentCell As New GridAction(row, col, _

 My.Computer.Keyboard.ShiftKeyDown) ' Memorize the current cell change

                CurrentDraw.Insert(0, CurrentCell) ' Add it to the total stroke

            End If

 

-          Finally, for MouseUp, I need to do everything that MouseMove did (since it’s just barely conceivable that MouseUp might be the first action over the grid), but I then also need to close the list of actions and insert it into the undo stack.  I’ll also need to clear out the cache and reset the redo list (since any new action invalidates a redo), so I’ll add this code to execute regardless of whether or not the cell was toggled:

            If CurrentDraw IsNot Nothing Then

' Time to close out the stroke and add it to the undo list.

                UndoList.Insert(0, CurrentDraw)

                RedoList = New List(Of List(Of GridAction)) ' Redo list is no longer valid -- garbage collect it

                CurrentDraw = Nothing ' Clear the cache

            End If

 

Now, the final thing remaining is to actually add the commands onto a menu!  In the form, I’ll drag over a MenuToolStrip control.  Notice that there’s a little triangle in the upper-left corner of the control.  Clicking that, I’ll choose “Insert Standard Items” from the resulting context menu.  This will insert the typical File menu items (which we’ll use in a later post), the Edit menu items (from which I’ll delete everything except Undo and Redo), the Tools menu items (I’ll rename this to "View" and delete everything under it; I don’t need a Tools menu), and the Help menu items (for which I’ll leave the “About” command and nothing else). 

 

Double-clicking on the Undo menu item, I’ll add the following code to its handler:

        If CanUndo() Then

            ' Get the last set of grid cell changes.

            Dim LastStroke As List(Of GridAction)

            LastStroke = UndoList.Item(0)

            UndoList.RemoveAt(0)

            RedoList.Insert(0, LastStroke)

            DoActions(LastStroke, True) ' Do all the actions inverted (erase becomes draw and vice-versa)

 

            ' Update the menus:

            If Not CanUndo() Then ' Anything left on the stack?

                UndoToolStripMenuItem.Enabled = False

            End If

            RedoToolStripMenuItem.Enabled = True

        End If

 

where CanUndo () is a simple helper that just checked if UndoList.Count > 0 (i.e., if there’s something that can be undone).  Basically, I’m just popping the top action list off the stack, reassigning it to the Redo stack, and then calling DoActions to perform the actual Undo.  By definition, the Redo stack will now need to be enabled (if it wasn’t already), and the Undo menu item disabled if there’s nothing left to undo.

 

I’ll repeat the process for the Redo handler, adding similar (but opposite) code to it, including a “CanRedo” helper and the fact that the second argument to DoActions will be False (which will tell DoActions not to invert the commands).

 

There are a couple of other places where we need to enable the undo/redo menu items – in the form’s load event both should be disabled (since there are no actions yet), and in the MouseUp handler, Undo will get enabled and redo disabled if an actual event happened. 

 

Otherwise, that’s all it takes for undo/redo!  As you can see, there’s really no excuse for not implementing such an incredibly useful feature in an application like this – it’s very easy to put together.  For more complicated drawing programs (i.e., one with color), you’d probably want to add another member to the GridAction class to track the previous color, but otherwise the logic remains the same.  Even if you added the ability to draw rectangles, lines, circles, or other shapes, the logic would not have to change, since those can be treated as single pen strokes.

A couple of other menu items

There are two more quick changes I’ll make before closing this post.  In the View menu, I’ll add a “Show Solution” command, and the implementation of this will just toggle the value of the Boolean variable “ShowSolution” – this controls whether or not the grid cells are filled in, so that the puzzle-maker can print out either a puzzle or the puzzle’s solution:

    Private Sub ShowSolutionToolStripMenuItem_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) _

 Handles ShowSolutionToolStripMenuItem.Click

        Me.ShowSolution = Not Me.ShowSolution

        Me.ShowSolutionToolStripMenuItem.Checked = Me.ShowSolution

        Me.Invalidate()

    End Sub

 

Note that I am invalidating the form to cause repaint to hide or show the solution.  Since this is a “solitary” event, unlike the drawing-by-hand I did last time, I don’t mind invalidating the whole form since I won’t get flickering from repeated invalidations.  I’ll also initialize the menu item in the Form’s load event:

        Me.ShowSolutionToolStripMenuItem.Checked = ShowSolution

 

and will change the ToggleCell code so that if someone draws in the grid while ShowSolution is False, we’ll set it to True and invalidate the grid (since it wouldn’t make sense to draw if you couldn’t see what you’re drawing!).

The other change I’ll do now is to create an About Box (right-click the project, “Add Windows Form,” “About Box”).  I’ll attach it to the “About” command on the Help menu:

    Private Sub AboutToolStripMenuItem_Click(ByVal sender As System.Object, _

ByVal e As System.EventArgs) Handles AboutToolStripMenuItem.Click

        Dim dlg As New VBPBNAboutBox

        dlg.ShowDialog()

    End Sub

 

And then in the project properties (right-click the project and choose “Properties…”) I’ll click the “Assembly Information” button and fill in all of the details about this application – those will automatically populate my About Box.

Next time, I’ll be cover saving and loading the puzzle, and then I’ll wrap this up in the final post by covering how to print the puzzle, to which I’ll attach the final project.  ‘Til then…

--Matt--*

 [Update:  Bill McC caught me out on my laziness and correctly points out that List Of is really inefficient here, and I should be using "Stack Of."  As the logic is otherwise the same, I'll be updating this in the final version.  Also, Aaron pointed out a copy error I had with the check mark on the "Show Solution," which I've fixed in this article.  See the comments for details.  Many thanks to both!!!]

Leave a Comment
  • Please add 7 and 7 and type the answer here:
  • Post
  • Inserting into the start of the list and then removing from the start of the list is really inefficient. It causes array copies for the entire amount in memory effectively doubling the memory requirement and increasing garbage clean ups.

    The sotrage you use should be one that is optimised for Last In is First Out (LIFO), which would be a Stack(Of T)

  • Thanks, good series. I think there might be bug in:

    Me.ShowSolution = Not Me.ShowSolution

    Me.ShowSolutionToolStripMenuItem.Checked = False

    Me.Invalidate()

    I think the middle line ought to be:

    Me.ShowSolutionToolStripMenuItem.Checked = Me.ShowSolution

    Otherwise, the menu item never gets checked.

    Thanks,

    Aaron

  • The Distributed Observer Pattern | The REST Dialogues [Via: (author unknown) ] PainlessSVN - Subversion...

  • Bill:  You are absolutely correct, I am abusing ListOf to be a stack here.  When I wrote the code, I was actually adding it to the end of the list, and then said, "Well, I don't want to always be figuring out what the last element in the list is, so let's be lazy; I'm not going to have to pop the stack very often."  But of course I am inserting fairly often, which is indeed inefficient.  It's a very easy fix which I will take care of before I publish the final version later this week -- thanks for bringing this up.  I'll add a note in the blog.

    Aaron:  Thanks, you are also right.  That was a copy error from some if/then logic that got left behind -- I had gotten the whole thing working using conditionals, and then said "Well, that's stupid -- let's just use the value directly -- but then forgot to complete it for the second line.  D'Oh!  I'll repair that one in the blog itself.

  • OK here's the deal. If you are teaching Visual Basic, programming in Visual Basic for fun or profit

  • OK here's the deal. If you are teaching Visual Basic, programming in Visual Basic for fun or profit,

  • I'm using a LIFO Stack(Of ) without limit, but i think that in a long day of work this could be so much inefficient. And the idea of limiting a stack (to twenty i.e.)  could even be more inefficient, because the action of pop the last element causes: pop the n elements and copy to another one( or an array), eliminate the bottom of the stack and then copy the rest back to the stack, and repeat this procedure for any undo action that the user perform.

    Any better idea ?

  • Not off the top of my head, Freud.  In practice (or at least in my experience), the stacks don't build up a lot of undos before they get flushed by the opposite action followed by new content, so we never really see much inefficiency.  Our own undo-redo stacks in Visual Studio basically work the way I've detailed them in this blog, and while we have a number of performance or memory issues that we concentrate on, this hasn't been a problem areas.  Limiting them to some arbitrary number is, as you say, even problematic.  (The only reason to do it is in low-memory cases, and that's just not an issue in these days.)

Page 1 of 1 (8 items)