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
-~----------~----~----~----~------~----~------~--~---
