data structure used to implement UNDO and REDO option

Question

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

Nebraska

Answer 1

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.

Pendley

Also it's important to always clear the Redo stack if you push another command. – Kibbutznik

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.) – Lourielouse

Answer 2

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.

Multivalent

You're right. If you add more info about how it interacts with the command pattern, this would be a great answer. – Guimar

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? – Walliw

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. – Multivalent

Answer 3

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

Orbadiah

Answer 4

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

Nananne

Answer 5

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',))

Wethington