Efficient undo/redo for Photoshop-like mobile app

I'm trying to write a painting app for a mobile device (Android) that will have a bit more functionality than MS Paint (e.g. various b开发者_StackOverflow社区rushes and brush settings, selections, layers) but won't be as complex as Photoshop. I need my app to have a decent undo/redo feature. Unlimited undo/redo is probably not possible. I'd be happy with being able to undo about the last minute worth of user actions (maybe about 20 actions).

The main approaches I know of for undo/redo is:

1. save the whole state or just the bits that changed after each operation. Undoing involves updating the state by restoring snapshots. Pros: simple to implement Cons: memory intensive.

2. use the command pattern where each command has a "do action" and "undo action" method. To undo, you just call the undo action of the previous commands. Pros: memory efficient, Cons: much more complex to implement.

My pathological undo/redo scenarios I have to consider is:

• the user paints over the whole canvas in one go, where you would want this whole operation to be undone when the user clicks undo. With option 1, we'd need to store a bitmap the size of the whole canvas.

• the user draws something, imports image 1.jpg onto the canvas, does some more drawing, 1.jpg is then deleted/modified at some point by another application and then the user wants to undo then redo all their actions in the paint application. I'm really not sure how to undo correctly here without saving a copy of any imported image while it's on the undo stack.

Can anyone give any recommendations about how best to implement undo/redo on a mobile device where memory and processor speed are low? I like the simplicity of 1 and 3 but it seems like the only realistic option is 2. I'm not sure how to cope with my second pathological example with this option though.

On the iPhone, Core Data has built in support for undo and redo. Just make your data model reflect the objects drawn and you can easily roll it back and forward between saves. Usually you would save the procedures and objects used to create the graphic instead of the graphic itself.

Edit:

OK, but this is just a little API support for implementing number 2 and won't help with the examples I gave.

The key idea to making this work is that you don't configure your data model to modal and persist the graphical output of the program, you configure it to modal and persist the process of creating the graphical output.

The naive way of creating a graphical program would be to set up the data flow like:

Input_UI-->Display_UI-->Data_Model

The user manipulates the Input_UI which directly alters the onscreen graphics of the Display_UI. Only when the user saved would the Data_Model come into play. This type of data flow makes undo/redo (and other things) very hard to implement especially in a painting e.g. compositing program. Every single operation has to know how to undo itself and has to be able operate on the altered graphic.

The better way is to set up a data flow like this:

Input_UI-->Data_Model-->Display_UI

The user manipulates the Input_UI which communicates to the Data_Model which manipulations the user chose. The Data_Model records the process e.g. "add file jpg.1 at rect {0,0,100,100}". A change to the Data_Model sends a notification to the Display_UI which reads the changed data and implements the process described.

The Data_Model rolls itself back and the Display_UI simply draws what the Data_Model tells it to. The Display_UI doesn't have to understand the undo process at all.

In a drawing program you would create logical layers of individual graphical objects so that redoing is just a matter of removing layers in the reverse order they were added. For painting/composition programs, you have to start at the last save point and recreate the graphic going forward until the last-1 step.

So, in your examples for a compositing program:

• The Data_Model stores the coordinates of the selected area (the entire canvas) which is still just "rect {0,0,canvas.width,canvas.height}" and then the operation "fill with black". For undo, the Display_UI whips the image back to the last save point and then invisibly applies the changes made up to last-1.
• You just need to save a cache of the image up until the next save. At that point, the Data_Modal commits all the changes and exports the composition to a file. The next time the app starts, it begins with the image from the last time. If you want infinite undo, then yes you have to save the imported image permanently.

The way to approach this is to ignore the GUI and instead think about how you would design an app to be run from the command line with out any GUI input or output. The Data_Modal would work just the same. It would save the text commands and the data (e.g. imported images) for creating the output image, not just a snapshot of the image on screen.

I like the simplicity of 1 and 3 but it seems like the only realistic option is 2.

I'm not sure what "3" is, since you only appear to have two options in your question.

With respect to the memory consumption of #1, it's only an issue if you use memory. Only hold onto history in memory for as long as it takes an AsyncTask (or possibly a regular background thread working off a LinkedBlockingQueue) to write them to the SD card. No SD card -- no undo/redo. On an undo, if your history has already written it to disk, reload it from disk. Just be sure to clean up the SD card (delete history on a clean exit, delete all lingering files on next startup).

Bear in mind that I have never written a painting application, let alone on Android, and so there may yet be performance problems (e.g., undo may take a second to load the bitmap off of the SD card).