Fast undo/redo with memento/command pattern?

Question

I'm writing a painting/graphics Java application for a mobile phone (so memory is limited). The application state is essentially three 1000x500 bitmaps (i.e. layers of a painting). Loading three bitmaps takes about 2 or 3 seconds.

I'm trying to write an undo engine but I just cannot work out a good way to do it. The typical approaches are:

• Use the command pattern: When you undo, you reload the state of the initial file and then playback all the commands processed so far except for the final one. Doing this naively though means waiting 2 or 3 seconds to load the initial state which is too slow. There isn't enough memory to store the initial state in memory either.

• Use the memento pattern: When you undo, you replace the part of the current state that was changed with the old state. This means every action needs to save bitmaps of the old state to disk because there just isn't enough memory on a mobile device to store this in memory. As saving bitmaps takes time, how do I cope if the user decides to e.g. paint many brush strokes in quick succession? I cannot make them wait.

All my solutions involve complex hybrids of the above patterns.

Can anyone suggest a solution that would allow me to have reasonably fast undo/redo for my application?

Answer 1

There is a third common method of handling undo. That is to store the differences between the two states within the Undo object. You can do this as actual differences (i.e. as which pixels have changed and what they changed to) but that is probably nearly as wasteful of memory as storing the bitmap at every stage.

Alternatively you can use the command pattern approach, but instead of re-running the commands when you undo, you store the inverse of the command - i.e. if the user increased the red value by ten, then the undo command is to decrease it by ten. To undo you simply execute the inverse command. Some commands are hard to find an inverse for, such as "convert to black and white" but by mixing an underlying bitmap with a number of filters which are turned on or off by command you can probably do it.

As yet another suggestion, use the command approach you mentioned but keep a bitmap for the previous step. When the user does undo immediately display the cached bitmap from the previous (n-1) step and then start calculating the bitmap for n-2 so that you are ready for when he presses undo again.