data structure used to implement UNDO and REDO option
Data StructuresDesign PatternsUndo RedoData Structures Problem Overview
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.?
Data Structures Solutions
Solution 1 - Data Structures
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.
Solution 2 - Data Structures
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.
Solution 3 - Data Structures
Objective-C Cocoa has a well documented anwser named NSUndoManager.
Solution 4 - Data Structures
You can use Command Pattern to achive Undo/Redo
Check these samples:
Solution 5 - Data Structures
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',))