Can them be implemented using stacks? Two stacks, one is called ls and
the other is rs.
I agree. Two things are needed, 1st, for each trackable action, a
reverse action should be recorded in order to perform the undo action.
The action itself must be recoreded as well for redo action. 2nd, two
stacks are needed to keep track on the last action performed.
For the 2nd thing, it is easy, push actions to one stack, once undo
request arrives, pop it out to the other stack, if redo request
arrives, pop action from the other stack and push it into the first
stack and so on.
For the 1st thing, it is good the make each atom action as an object
and the object has a function called "Perform()" in order to perform
the action of the object and has a function called "Undo()" in order
to eliminate all the affects this action causes.
One thing can be trivial, assume action A is done and then action B is
done. But B has affect on A. Now you want to undo B, you need to
remain A unchanged. An example is when drawing in Viso, when two
straight lines across but not interconnected with each other, the one
on top has a change, showing it is not interconnected with the other
line. In this way the latter drawn line has affect on the previous
line. But once the latter drawn line is undo, the previous line must
return to normal status. This can be a little be tricky. You need some
advanced design patterns in order to fully implement undo/redo in a
highly interacted environment.
On Sep 20, 9:34 am, Gene <[EMAIL PROTECTED]> wrote:
> On Sep 19, 2:47 pm, let_the_best_man_win <[EMAIL PROTECTED]> wrote:
>
>
>
> > 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.
> > 3) User can also delete any pets, children or furniture.
> > 4) Or user can modify the pets, children or furnitures' respective
> > "info" fields.
>
> > 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 ?
>
> The usual way is to implement the operations you need and their
> inverses as objects (data structures). Then implement an "interpeter"
> that accepts an object and "executes" the respective operation, in
> this case on your tree. Then implement an "inverter" that takes an
> object for a given operation and returns its inverse. To execute an
> operation A, construct an A object, pass it to the interpreter, and
> then push it on an operation stack. To undo, pop the top element B of
> the stack, use the inverter to compute inverse(B), and then pass this
> to the interpreter. Optionally, you can then push B on a "redo"
> list. Designing the operation data structures is often very
> interesting. OO implementation with a "Command" object hierarchy and
> dispatching functions for Invert and Execute make all this very clean.
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
