undo/redo algo

[call_me_anything]

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 ?

[call_me_anything]

Re: undo/redo algo

Note :
User can also delete any pets, children or furniture.
Or user can modify the pets, children or furnitures' respective "info"
fields.

[call_me_anything]

Re: undo/redo algo

http://en.wikipedia.org/wiki/Command_pattern

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

[call_me_anything]

Re: undo/redo algo

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. :)

[Alan Woodland]

Re: undo/redo algo

call_me_anythin g 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 RenameNodeComma nd : 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 RenameNodeComma nd 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

[call_me_anything]

Re: undo/redo algo

One more doubt here :

We plan to support multiple changes here like
"change the name of all pets starting with abc to badpets_<origin al-
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 ?

[Alan Woodland]

Re: undo/redo algo

call_me_anythin g wrote:

One more doubt here :
>
We plan to support multiple changes here like
"change the name of all pets starting with abc to badpets_<origin al-
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 CommandCollecti on : public Command {
std::vector<Com mand*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 CommandColletio n.
3) for each node you decided you want to change create a
RenameNodeComma nd instance, and add the RenameNodeComma nd instance to
the CommandCollecti on.
4) push the CommandCollecti on you created onto your undo stack and call
apply() on the CommandCollecti on 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
CommandCollecti on 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

[James Kanze]

Re: undo/redo algo

On Sep 19, 7:00 pm, "Alf P. Steinbach" <al...@start.no wrote:

[...]

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_p tr 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_p tr 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:james.kan ze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientier ter Datenverarbeitu ng
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34