53

I want to implement UNDO and REDO option(as we see in MS word etc). Can you suggest me a data structure for it, and how can i implement it.?

cdiggins
  • 17,602
  • 7
  • 105
  • 102
SyncMaster
  • 9,754
  • 34
  • 94
  • 137

5 Answers5

112

It isn't a data structure but a design pattern. You're looking for the Command Pattern.

The standard is to keep the Command objects in a stack to support multi level undo. In order to support redo, a second stack keeps all the commands you've Undone. So when you pop the undo stack to undo a command, you push the same command you popped into the redo stack. You do the same thing in reverse when you redo a command. You pop the redo stack and push the popped command back into the undo stack.

Restore the Data Dumps
  • 38,967
  • 12
  • 96
  • 122
  • 40
    Also it's important to always clear the Redo stack if you push another command. – Game_Overture Apr 23 '09 at 01:27
  • 4
    I feel like the command pattern is not necessarily how you implement undo, it's just one option, nor is it the answer to the OP's question. The undo/redo stacks is the answer. (Though I suppose he did mention MSWord.) – Dave Cousineau Dec 01 '15 at 17:08
40

Actually, the standard pattern for this functionality (Gang of Four, even) is Memento.

Also, while most programs use Undo/Redo stacks, afficionados of certain text editors prefer Undo/Redo trees so that they don't lose their entire history if they undo a few commands, try a new one, and change their minds.

Hank Gay
  • 70,339
  • 36
  • 160
  • 222
  • 3
    You're right. If you add more info about how it interacts with the command pattern, this would be a great answer. – Kieveli Jan 05 '10 at 18:57
  • Try to clear the usage of Memento, Is Memento used to store the state of the objects before and after the operation for undoo/redo? – NileshChauhan May 02 '12 at 16:37
  • 1
    The object that produces the Memento uses it to return itself to that state. The Memento itself should be treated as if it were opaque. Stuffing the entire state into the Memento seems like an obvious implementation choice, but it could just as easily be a diff, or an id into a backing store, or something else. – Hank Gay May 02 '12 at 19:45
3

Objective-C Cocoa has a well documented anwser named NSUndoManager.

mouviciel
  • 66,855
  • 13
  • 106
  • 140
2

This is a classic case of Command Pattern. Following is a sample implementation of undo feature in Python :

from os import rename
class RenameFileCommand(object):
    def __init__(self, src_file, target_file):
        self.src_file=src_file
        self.target_file=target_file


    def execute(self):
        rename(self.src_file, self.target_file)

    def undo(self):
        rename(self.target_file,self.src_file)



class History(object):
    def __init__(self):
        self.commands=list()
    def execute(self, command):
        command.execute()
        self.commands.append(command)

    def undo(self):
        self.commands.pop().undo()


if __name__=='__main__':
    hist=History()
    hist.execute(RenameFileCommand( 'test1.txt', 'tmp.txt', ))
    hist.undo()
    hist.execute(RenameFileCommand( 'tmp2.txt', 'test2.txt',))
Red John
  • 167
  • 10
2

You can use Command Pattern to achive Undo/Redo

Check these samples:

http://www.codeproject.com/csharp/undoredobuffer.asp

http://www.dofactory.com/Patterns/PatternCommand.aspx

Manrico Corazzi
  • 11,299
  • 10
  • 48
  • 62
NinethSense
  • 8,824
  • 2
  • 23
  • 23