Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

data structure used to implement UNDO and REDO option

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

like image 906
SyncMaster Avatar asked Mar 31 '09 14:03

SyncMaster


People also ask

How do you implement undo and redo?

If “UNDO” string is encountered, pop the top element from Undo stack and push it to Redo stack. If “REDO” string is encountered, pop the top element of Redo stack and push it into the Undo stack. If “READ” string is encountered, print all the elements of the Undo stack in reverse order.

What type of linked list is used for undo and redo?

Application of Doubly Linked Lists: Redo and undo functionality. Use of Back and forward button in a browser.

Which data structure can be used to implement the undo operation of a text editor?

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.

Is undo and redo a stack?

The best way to look at undo/redo is two stacks of operations the user has performed: The Undo stack is the "history" of what they've done. The redo stack is the breadcrumbs back to the initial state before they started undoing.


2 Answers

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.

like image 182
Jason Punyon Avatar answered Sep 23 '22 10:09

Jason Punyon


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.

like image 36
Hank Gay Avatar answered Sep 24 '22 10:09

Hank Gay