473,289 Members | 1,947 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,289 software developers and data experts.

undo/redo algo

Hi,

I am looking for a good algorithm (in C/C++) for implementing undo/
redo on a data structure.

The data structure is basically a n-children tree somewhat of the
form :

class /* or struct */ node {
char *info1;
char *info2;
char *info3;
node *children;
node2 *pets;
node3 *furniture;
node *myparent;
}

and node2, node3 etc are also defined in more or less similar fashions
but are not same as node.

Now, we have a data structure of the above format and we provide a
user interface such that user can
modify any field in the tree.
So user can :
1) change char* fields to some other strings or make them NULL for any
node.
2) Add pets, children or furniture to any node.

And it is desired to have an undo/redo functionality for each of the
above operations.

What is the most efficient way in which this can be done ?

1) Saving each state to a file will be very time consuming.
2) Replicating each state in memory will also be very time consuming
and memory inefficient.

How can we store the changes in an incremental fashion ?
Do we need to add something more to the above structures for storing
incremental changes ?

Sep 19 '07 #1
7 5362
Note :
User can also delete any pets, children or furniture.
Or user can modify the pets, children or furnitures' respective "info"
fields.

Sep 19 '07 #2
http://en.wikipedia.org/wiki/Command_pattern

If this is what you meant by command pattern, then I dont think I get
your solution.

Sep 19 '07 #3
I mean the text on "command pattern" was just too idealistic and I am
unable to relate it closely to my problem.
Any light shedding would be helpful. :)

Sep 19 '07 #4
call_me_anything wrote:
I mean the text on "command pattern" was just too idealistic and I am
unable to relate it closely to my problem.
Any light shedding would be helpful. :)
Basically you're going to want an interface that every action uses, e.g:

class Command {
public:
virtual void apply() = 0;
virtual void undo() = 0;
};

You'll also need two stacks - one stack to store things that can have
been done, and can be undone in the future, and another one to store
things that have been undone, and can be re-done in the future.

Then you'll want to implement the Command interface we defined
previously for each action, e.g. for re-naming a node we want to store
the old name so that our undo() method can set the name back to what it
was previously. We also need to save the new name in the command so that
apply() can set the new name when it gets called.

class RenameNodeCommand : public Command {
public:
virtual void apply() {
n->name = new_name;
}

virtual void undo() {
n->name = old_name;
}

private:
Node *n;
const std::string new_name;
const std::string old_name;
};

Then you just need to orchestrate it such that every time the user
clicks/presses/types a new name an instance of RenameNodeCommand is
created to perform this action and is saved on the undo stack.

Obviously this is a slightly simplified example, but hopefully it shows
the basic principle...

Alan
Sep 19 '07 #5
One more doubt here :

We plan to support multiple changes here like
"change the name of all pets starting with abc to badpets_<original-
name>"

And the application expects all such commands by means of a string
input.
It will parse the string and find out what to do.

So if the user says
change all "abc" to "ABC"
then says
change all "def" to "ABC"

And then asks to undo, how does we keep track of undoing only those
ABCs which came from def.
I guess all the editing applications do such kind of things (for eg.
notepad and Vi)
How do they handle it efficiently without consuming huge memory or
disk space ?

Sep 19 '07 #6
call_me_anything wrote:
One more doubt here :

We plan to support multiple changes here like
"change the name of all pets starting with abc to badpets_<original-
name>"

And the application expects all such commands by means of a string
input.
It will parse the string and find out what to do.

So if the user says
change all "abc" to "ABC"
then says
change all "def" to "ABC"
If you want to make multiple changes seem atomic I think I'd do
something like making another implementation of the Command interface
that just stores a collection of commands, and then calls their
apply()/undo() methods from its own apply()/undo() methods:

class CommandCollection : public Command {
std::vector<Command*cmds;
public:
virtual void apply() {
//for each Command* in cmds call apply()
}

virtual void undo() {
//for each Command* in cmds call undo()
}
}
And then asks to undo, how does we keep track of undoing only those
ABCs which came from def.
I guess all the editing applications do such kind of things (for eg.
notepad and Vi)
How do they handle it efficiently without consuming huge memory or
disk space ?
Then when you get the command "change all def to abc" you do the
following pseudo code:

1) find all the nodes with def you want to change to abc.
2) create a new CommandColletion.
3) for each node you decided you want to change create a
RenameNodeCommand instance, and add the RenameNodeCommand instance to
the CommandCollection.
4) push the CommandCollection you created onto your undo stack and call
apply() on the CommandCollection to actually make the changes.

Then when you get your next command e.g. "change all ABC to abc" you
repeat the above process. After doing that you will now have two
CommandCollection objects on your undo stack that when you pop them off
and call undo() on them will return the state to how it was before those
commands were executed...

Alan
Sep 19 '07 #7
On Sep 19, 7:00 pm, "Alf P. Steinbach" <al...@start.nowrote:

[...]
Check out "command pattern".
I beleive it's the memento pattern which you want.
While your at it, replace all the pointer stuff with standard library
and Boost classes such as std::string (for strings) and
boost::shared_ptr where you really need pointers, and make sure you
don't have circular references in the resulting structure.
I'd certainly agree with using std::string where ever possible,
but the memento pattern is a very good example of a case where
boost::shared_ptr is not appropriate. Most of the pointers are
used only for navigation, and lifetime of the objects involved
is (or should be) explicit, and not based on random pointer use.

--
James Kanze (GABI Software) email:ja*********@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

Sep 20 '07 #8

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

1
by: Jay | last post by:
I need to implement an undo and redo for an entire row in a listview containing approximately 10 columns. I'm not sure of the best way to implement this. The only thing that I've thought of is a...
5
by: Mickel Grönroos | last post by:
Hello everybody I'm developing a tool in Tkinter and would like to add Undo and Redo commands to my Edit menu. Does somebody know if anybody has implemented standard Undo/Redo as a Python...
6
by: lkrubner | last post by:
I'm offering users the ability to type weblog posts into a form and post them. They type the text into a TEXTAREA which is on a form. The form, when submitted, hits a PHP script. Before it is...
2
by: Tony Nelson | last post by:
I'm looking for a "pythonic" GTK Undo library/class. It would have a framework for Undo/Redo, and would provide Undo/Redo for TextView, Entry, and containers and other classes. In a "batteries...
3
by: babylon | last post by:
any facilities in csharp that can help me implmenting undo/redo in my application? thx
3
by: Teis Draiby | last post by:
I'm looking for some information (books, articles, tutorials) on how to implement a multiple undo/redo framework. I'm a beginner in this so I prefer information specifically targeting C# with code...
2
by: Christian H | last post by:
Hello, I've tried to find information about how to implement an Undo/Redo pattern. This article describes such a pattern: http://www.codeproject.com/csharp/PcObjectUndo.asp , but is a little bit...
1
by: anupam roy | last post by:
Hi All, I want to perform basic Edit menu functionalities on my custom design surface. While all the Cut/Copy/Paste/Deelete/Select functionalities working fine with code below,Undo/Redo standard...
0
by: MeoLessi9 | last post by:
I have VirtualBox installed on Windows 11 and now I would like to install Kali on a virtual machine. However, on the official website, I see two options: "Installer images" and "Virtual machines"....
0
by: Aftab Ahmad | last post by:
Hello Experts! I have written a code in MS Access for a cmd called "WhatsApp Message" to open WhatsApp using that very code but the problem is that it gives a popup message everytime I clicked on...
0
by: Aftab Ahmad | last post by:
So, I have written a code for a cmd called "Send WhatsApp Message" to open and send WhatsApp messaage. The code is given below. Dim IE As Object Set IE =...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: marcoviolo | last post by:
Dear all, I would like to implement on my worksheet an vlookup dynamic , that consider a change of pivot excel via win32com, from an external excel (without open it) and save the new file into a...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.