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]

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

 

[Alf P. Steinbach]

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

Check out "command pattern".

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.

Cheers, & hth.,

- Alf

 

[call_me_anything]

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]

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.

 

[call_me_anything]

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 ?

 

[Alan Woodland]

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

 

[Alan Woodland]

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

 

[James Kanze]

[...]

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.