Thread: Implementing multiple undo's

I am trying to come up with a way to implement multiple undo's in my current project. I thought of keeping track of the "undo's" in a temp file but a linked list sounds better to me.

How do you guys do it?
Thanks in advance for pointing me in right direction.

The first screen shot is before the user deletes anything.

The second screen shot is after the user deletes a several elements.

/edit
So what is the best way to undo the elements the user deleted?

deque

A linked list sounds like a good idea for a first attempt.

My first (and only thus far) attempt at implementing undo, was, as salem said, with a linked list (stack). It worked (and is still working) incredibly well and is very easy to extend. What you do is have a simple linked list structure (double makes things a bit easier): next and previous pointers, and a pointer to void (generic data). You can add other members such as Id to describe what kind of data the void * holds.
In your scenario, when a user deletes an item, you would create a new undo structure in memory, set the Id member (a byte or integer) to a constant value you define (i.e. UNDO_ACTION_DELETE_ITEM) and set the "data" member (void *) to your item data (depending on whether you transparently delete data from the GUI form (i.e. remove its graphical representation but keep its internal) or completely remove it, either point to the original data, or make a copy of it respectively.
For completeness sake, you may also want to include meta-data about the item, such as its place in the list or table or whichever GUI format you are using to display the data to the user.
You can either choose to "tack" this metadata on unintuitively (i.e. allocate memory for the item data, then some more for the metadata), then the Id member would tell you how and in what order to retreive the data/metadata from the memory block. Or you can add it intuitively by defining another sub-structure that has members to explicitly hold the item data and index data in seperate members.
The first method is prone to more errors, but the second method means you may have to create a new structure for every single action type the user can perform. On one extreme, you can have all item data and metadata in one contiguous memory location, in which case your undo structure might look something like this:

Code:

typedef struct _undoNode
{
    void *data;
    struct _undoNode *next,
                     *prev;
} undo_t;

or on the other extreme, you could have item data and each metadata held in a seperate member, like this:

Code:

typedef struct _undoNode
{
    char Id;
    int index;
    <type> metadata2
    <type> metadata3
    <type> metadata4
    ...
    void *item_data;
    struct _undoNode *next,
                     *prev;
} undo_t;

Which you choose is a decision based on how many items share common types of metadata, and how many metadata you have. In my personal implementation I chose a cross between the two, adding extra members to the undo structure that I knew every action would need, saving the first method for meta-data that was specific only to a certain action type.

Classically, you want to maintain a pointer to the tail (top) of the undo stack and it is also convenient for error/empty checking to maintain one to the top (head) as well. You may need to create these as static if you are operating within a GUI callback routine. Follow the basics of stacks (eat from the top, place on the top): everytime a user performs an undo-able action, create a new undo structure, fill out the members with pertinant data/metadata and place it on the top of the stack. When the user performs an undo, restore the data contained in the top undo structure and remove it from the top of the stack.
Implementing a redo is similiarly easy, just maintain two stacks, as you process/remove from the undo stack, simply move the undo node from the top of the undo stack to the top of the redo stack (if you've got good data structure, you may not even have to change the undo structure's member data). Just becareful that, after tossing around and deleting data and moving undo nodes, that pointers still point to valid data (which is why copying data may come in hand, though space conservation and propogating changes are big disadvantages of this).
If this is your first time implementing an undo, expirement around with it and have fun! I learned a hell of a lot on the do's and don'ts of undo implementation via stacks just by running head-long into brick walls, fun and painfully educating!

Thanks for the responses.