Saturday, June 18, 2011

Coding an Undo/Redo Stack


The other night I put (what I think are) the finishing touches of an Undo/Redo stack for Photobomb. This is the second time I've written an Undo/Redo stack, the first time being for the TextEditor Quidget. Neither time was I able to find much guidance for how to approach the problem. I handled it slightly differently each time. I thought I'd write up a blog post about how I approached Undo/Redo for Photobomb, in case it helps someone else out.

Generally, the way I conceived the problem was to keep a list of actions that needed to be undone. When an action is undone, then that action needs to be added to a list of actions that can be redone. But what does it mean to store an action in code? I thought of 2 approaches:
  1. Keep a list of actions as functions along arguments to pass to those functions.
  2. Keep a list of "backups" for every change made to an object, and on redo swap out the backup for the actual object.
List of Actions Approach
I took the first approach back when I wrote TextEditor. It was easy to do because the only actions supported by Undo and Redo was that something could be added to the TextBuffer, or something could have been removed. So I very literally stored a list of functions and elements. So on a change, such as when text has been inserted, I store point at which the text was inserted, along with the inserted text:
     cmd = {"action":"delete","offset":iter.get_offset(),"text":text}
self._add_undo(cmd)

The _add_undo function merely ensures that the list does not grow beyond a defined maximum, and adds it to the undo list:
   def _add_undo(self, cmd):
if self.undo_max is not None and len(self.undos) >= self.undo_max:
del(self.undos[0])
self.undos.append(cmd)
The heart of the __add_undo command was to extract the command to undo, and pass it along to _do_action(), and then add the return value of undo to redo stack.
     undo = self.undos[-1]
redo = self._do_action(undo)
self.redos.append(redo)
del(self.undos[-1])
do_action, in turn read the type of action, did the specified action, and returned the opposite action so it could be used for redo.
     if action["action"] == "delete":
self.get_buffer().delete(start_iter, end_iter)
action["action"] = "insert"
elif action["action"] == "insert":
self.get_buffer().insert(start_iter, action["text"])
action["action"] = "delete"
return action
So by keeping a mapping of actions and their opposites, and by using a dictionary to store the information needed to undo or redo the action, this system worked well for simple case of simple text editor.

List of Backup Approach
Not surprisingly, when I approach this problem in Photobomb, I followed the same basic solution path. For example, I set up a list to store undo actions in. I then started storing a code for actions like I used for delete and insert in the text editor. However, I quickly ran into some problems. Photobomb is more complex then TextEditor, and GooCanvas is more complex than TextView/TextBuffer. For example, storing all the info needed for undoing and redoing a clipping path on an object required some more complex code than seemed right for the problem. So, I switched to the second approach.

Here, I store a list of undos, but what I store in the list is objects. A "new" object, as in the object after the change, and the "old" object. Kind of like the backup.

To store an undo in this system, I make a back up of the object, change it, and then add the undo:
       saved_item = self.back_up_item()
self.selected_item.move(delta_x,delta_y)
self.add_undo(self.selected_item, saved_item)
Making the backup entailed duplicating the entailed not just making a copy, but removing the copy from the goocanvas, and storing the z-order. GooCanvas doesn't track z-order for you, so I had to track it myself. Every object on the GooCanvas suface derives from a subclass of the custom PhotobombItem and one of the built in GooCanvas types, such as goocanvas.Image). PhotobombItems have a duplicate function witch return a copy, and a remove function. So getting a copy was easy.
   def back_up_item(self, item=None):
if item is None:
item = self.selected_item
copy = item.duplicate(True, False)
copy.remove()
index = self.z_order.index(item)
self.z_order.insert(index+1,copy)
return copy
I quickly found that it is insufficient to simply store a pair of old and new objects for each undo. This is because an object can be modified twice in a row. And if you store the object itself, rather than a copy of the object, the undo stack will reference the object in whatever is it's current state, so undo can appear to weirdly go backward.

For example if I make an item, call it O1 bigger, I'll store a copy of O1, call the copy O1.1, and O1 as the old and new items, respectively. Then if I make it bigger again, I store another copy of O1, call it O1.2, and O1 *again*. So undoing will go O1 is replaced by O1.2, which looks right, but then undo again and O1 will be replaced by O1.1. But oops, O1 was already replaced, so O1.1 appears, but O1.2 was never replaced.

To guard against this, I looked backward through the undo stack to see where in the current undo stack the object appears last, and I take the current backup of the "old_item" and make that the "new_item" for the previous undo. So, for then making something bigger would store O1.1 and O1 again, but then making it bigger again, it would replace O1 with O1.2 as the "new_item" and then store O1.2 and O1 as the new_item at the top of the undo stack. So undo would replace O1 with O1.2, and then O1.2 with O1.1, and everything seems to work.

That was a pretty long winded explanation for not that much code. Basically, I loop back through the undo stack and update the last occurrence of the object being added with the copy before going ahead and adding the objects to the stack.
   def add_undo(self, new_item, old_item):
#ensure proper undos for multiple edits of the same object
if len(self.undos) > 0:
for item in self.undos[::-1]:
if item["new_item"] is new_item:
item["new_item"] = old_item
break
self.undos.append({"new_item":new_item,
"old_item":old_item})
self.redos = []
Note that I also reset the redo stack whenever the undo stack is modified.

So what does undo and redo do? They function in a very similar manner to the undo/redo functions in the text editor. First, they get they item from the top of the stack and stick it on the other stack. So for undo:
     undo = self.undos[-1]
self.redos.append(undo)
del(self.undos[-1])
Then they remove the new item, and restore the backup (assuming they both exist). If there is no backup, that means the item was just created, so removing the item is sufficient. Conversely, if there is no new item, then it means the item was deleted, so adding it back to the canvas is sufficient. Finally, the function has to position the new item in the z-order and then select the new item.
     if undo["new_item"] is not None:
undo["new_item"].remove()
if undo["old_item"] is not None:
undo["old_item"].set_property("parent",self.__root)
next_item = self._find_item_above(undo["old_item"])
if next_item is not None:
#position in z-order
undo["old_item"].lower(next_item)
self.selected_item = undo["old_item"]
self.__reset_selection()
Redo does essentially the same thing, only removes old_items and restores new_items. There was about 100% code duplication between the undo and redo functions. However, I decided to keep the duplicate code in place because I was worried that if I have to go back and fix bugs in a year or so, I'd need the code to be crystal clear about what it did. I can always refactor into a common function later, but for now, I felt that the duplicated code was just easier to read and understand.

Now, calling these functions is easy in cases where a menu item was used to change on object, as there was one and only one change to store in the undo stack. But sometimes it's not so easy. For example, Photobomb has what I call "Press and Hold Buttons". To make an item bigger, for example, you can use the Bigger menu item, or you can hold down the Bigger button until the selected object is the size that you want and release the button. The button emits a signal called "tick" every 100 milliseconds, which is bound to an action, in the case, the "self.bigger" function. This causes the item to get bigger many many times (about 10 times per second, in fact) but the user is going to think of it as one action to be undone.

In order to handle this case, I created two signal handlers, one for the press event and one for the released signal of a button. All the Press and Hold buttons use these handlers. The press signal handler creates an immediate copy of the item, and then connects the tick and the released signals. Occasionally, the released handler gets called twice, which causes some confusion, so I track the tick signal to make sure that the released signal is only handled once.
   def pah_button_pressed(self, button, action):
old_item = self.back_up_item()
tick_signal_id = button.connect("tick",action)
button.connect("released",self.pah_button_released, (tick_signal_id, old_item))
Then in the released signal, I add the new item and the old_item to the undo stack, assuming it hasn't been already.
   def pah_button_released(self, button, args):
tick_signal_id, old_item = args
#work around released signals being called multiple times
if tick_signal_id in self.__disconnected_tick_signals:
return
self.__disconnected_tick_signals.append(tick_signal_id)
button.disconnect(tick_signal_id)
if self.selected_item is not None:
self.add_undo(self.selected_item, old_item)
Now only 1 undo is added when a Press and Hold Button is used.

Another challenge to overcome in this system was handling the user changing selection by clicking on an item versus when the user clicked and dragged an item. The latter should be added to the undo stack, but not the former.

Fortunately, this can be handled with a similar pattern. The mouse_down signal handler creates a copy of the item, and passes it to the mouse_up signal handler.
           old_item = self.back_up_item(clicked_item)
self.__mouse_up_handler = self.__goo_canvas.connect("button_release_event",self.drag_stop, old_item)
Then the drag_stop function checks if the item was actually moved before adding to the undo stack. If the item hasn't been moved, then the selection has simply changed.

Finishing Touch
One last finishing touch is to ensure that the undo and redo menu items are only sensitive if there is anything in the undo and/or redo stacks. Photobomb handles this by connecting to the activate signal of the edit menu, and then checking if there is anything in the undo and redo lists, and setting the sensitivity accordingly.
   def edit_menu_reveal(self, widget, data=None):
active_undos = len(self.undos) > 0
active_redos = len(self.redos) > 0
self.builder.get_object("menuitem_undo").set_sensitive(active_undos)
self.builder.get_object("menuitem_redo").set_sensitive(active_redos)

There is a lot of ineractivity in photobomb, and this creates a bit of complexity in handling undo/redo. You can see all the code in context in the photobomb trunk.

33 comments:

  1. Apple has an interesting piece of technology called "Undo Manager". It's worthwhile to learn from how they approach and solved this problem. The same undo code is reused in virtually all osx and ios apps.

    http://developer.apple.com/library/ios/#documentation/Cocoa/Conceptual/UndoArchitecture/UndoArchitecture.html

    ReplyDelete
  2. Hey Rick,

    Nice post.

    I'm thinking that a @undoable decorator would look really neat in the Photobomb code, but of course that won't work for the case where you pass old_foo around in the signals :(

    As for text, last time I needed undo/redo support I just switched to gtksourceview2, but I suppose you found that to be overkill.

    I'm surprised how little code it is. Must be because the only time I looked at an history implementation that was Swing's (where, you can probably guess, every single action has its own class with undo and redo methods -.-).

    A little tips for your implementation though, the standard library provides "deque" in the collections module which implements the "keep my list at size X throwing out old stuff when needed" :).

    ReplyDelete
  3. I'll probably have to write something similar in Javascript in the next few weeks. The list of backup approach is more in line with the code base, so I might go this way.

    In both cases, I think I would prefer to have only one stack. Instead of popping items when undoing, I would keep a pointer of the current action and move it down (or up for a redo). And when I want to push a new item, if the pointer is not on top, I would pop everything above it before pushing.

    ReplyDelete
  4. nice post, it really helps in my problem

    ReplyDelete
  5. I like the valuable information you provide in your articles. I will bookmark your blog and check again here frequently. I'm quite certain I will learn many new stuff right here! Best of luck for the next! Thank you for share. clipping path clipping path service Remove Background

    ReplyDelete
  6. The post is very educational and i get more experience to the post. Hopefully it help me professional work. Thanks for tech me.

    clipping path service
    clipping path
    color correctoin service

    ReplyDelete
  7. Great post and nice writing . thanks for sharing with us .
    Clipping Path | Image Background Remove

    ReplyDelete
  8. Fantastic site, I could definitely go to your web page once more…acquired some really nice info
    clipping path
    Raster To vector
    clipping path service

    ReplyDelete
  9. Thank you so much fr this good idea. excellent sir, thanks
    visit my post

    ReplyDelete
  10. I am very interested to learn coding but can't find resourceful content.
    background remove

    ReplyDelete
  11. it is very nice post...
    https://clippingexpertasia.com/background-removal-service

    ReplyDelete
  12. This is an amazing article. I am reading your article and I have really enjoyed. Thanks for sharing your nice article. Clipping Expert Asia is the leading photo editing company around the world. This company provides valuable services these are very important for graphic designers, photo editor, photographer, and every photo related or graphic design related people, etc. We give the primary offer to every client, which provide these services at a competitive price from Clipping Expert Asia. Especially we provide high-quality background removal service that ensures to make the product images appealing and professional.
    background enhancement service

    ReplyDelete
  13. This comment has been removed by the author.

    ReplyDelete
  14. I will probably write something similar in JavaScript over the next few weeks. The backup method list code is more consistent with Bed, so I can go this route. Join us my design JavaScript website clipping path Photoshop

    ReplyDelete
  15. I am very much impressed from your post. This is amazing information...Your blog is very creative and the information on this blog is very useful information thanks for sharing this post.......Clipping Expert Asia suppliers around the globe and modest rates, the work is submitted by the conveyance time. We offer our worldwide customers: Background Removal, Image Manipulation, Clipping Path, Photo Retouching, Photo Neck Joint, Jewelry Photo Retouching, Color Correction, Image Masking services. https://clippingexpertasia.com/ is one of the best images editing service Provider Company. We work all over the world. We mainly work in the USA, UK, UAE, Australia, Denmark, Germany, France, Poland, Switzerland, Canada & Brazil.

    ReplyDelete
  16. The Best Photoshop Clipping Path Service Provider Company. We are Offering eCommerce Product Photo Editing, Deep Etching, Cut Out Image Services and others.
    Clipping Path Center Inc

    ReplyDelete
  17. Amazing post, thanks for lots of your amazing and excellent post. I might though, is yours did a strong analysis of this content. I know the Clipping Path United ( photo editing company ) giving the best quality clippingpath Service world-wide.

    ReplyDelete
  18. nice post..Thanks for the post. Follow us to know more
    Clipping path service

    ReplyDelete
  19. When people think of sex, they often think of orgasm as the ultimate way to achieve pleasure. (Playmates Porn movies Models with their experimenting sex positions). Female orgasm, in particular, is often seen to be proof of sexual success. To achieve High-end Sexual Arousal - visit
    Porn Movies and Videos
    XXX Sex HD Videos
    Wild Porn Movies

    ReplyDelete
  20. Photography is my potion, from my childhood life I am doing work in this setor. Love to write blogs on photography tips and tutorials also publish on various platforms. Last 5 years, I am working dedicatedly in this industry. Here I would like to share my Professional knowledge which has proper guidelines to enhance my newbie photography career. Thank you
    https://www.clippingworld.com/multi-clipping-path-service/

    ReplyDelete
  21. Clip Asia is commonly known for providing Clipping Path Service. Image Editing Service that consists of for Image Clipping Path Service, White Background for Image, Shadow | Reflection, Masking, Color Adjustment, Coloring, Invisible Mannequin, Retouching, Jewelry Image Editing, Dust Removal, Product Image Editing, Image Cropping | Resizing, Ghost Mannequin Services.

    ReplyDelete
  22. Amazing post, thanks for lots of your amazing and excellent post. I might though, is yours did a strong analysis of this content. Read more Azure trainings in hyderabad

    ReplyDelete
  23. Excellent weblog, many thanks a lot for your awesome posts! leer mas
    our web site sclinbio,com

    ReplyDelete
  24. Excellent weblog, many thanks a lot for your awesome posts! leer mas
    our web site https:/sclinbio,com/

    ReplyDelete