Implementing multiple undo's

This is a discussion on Implementing multiple undo's within the Windows Programming forums, part of the Platform Specific Boards category; I am trying to come up with a way to implement multiple undo's in my current project. I thought of ...

  1. #1
    Registered User Bajanine's Avatar
    Join Date
    Dec 2001
    Location
    The most peaks over 10,000 feet!
    Posts
    396

    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?
    Attached Images Attached Images   
    Last edited by Bajanine; 09-19-2007 at 07:20 PM. Reason: Clarification
    Favorite Quote:

    >For that reason someone invented C++.
    BLASPHEMY! Begone from my C board, you foul lover of objects, before the gods of C cast you into the void as punishment for your weakness! There is no penance for saying such things in my presence. You are henceforth excommunicated. Never return to this house, filthy heretic!



  2. #2
    Registered User
    Join Date
    Dec 2005
    Location
    Canada
    Posts
    267
    deque

    OS: Windows 7, XUbuntu 11.10, Arch Linux
    IDE: CodeBlocks
    Compiler: GCC

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,845
    A linked list sounds like a good idea for a first attempt.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  4. #4
    Registered Abuser
    Join Date
    Jun 2006
    Location
    Toronto
    Posts
    591
    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!

  5. #5
    Registered User Bajanine's Avatar
    Join Date
    Dec 2001
    Location
    The most peaks over 10,000 feet!
    Posts
    396
    Thanks for the responses.
    Favorite Quote:

    >For that reason someone invented C++.
    BLASPHEMY! Begone from my C board, you foul lover of objects, before the gods of C cast you into the void as punishment for your weakness! There is no penance for saying such things in my presence. You are henceforth excommunicated. Never return to this house, filthy heretic!



Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 16
    Last Post: 06-08-2009, 04:03 PM
  2. why Multiple define error ...
    By nilathinesh in forum C Programming
    Replies: 2
    Last Post: 10-19-2006, 07:31 AM
  3. Phantom redefinition
    By CodeMonkey in forum C++ Programming
    Replies: 6
    Last Post: 06-12-2005, 06:42 PM
  4. Linker errors - Multiple Source files
    By nkhambal in forum C Programming
    Replies: 3
    Last Post: 04-24-2005, 03:41 AM
  5. Replies: 1
    Last Post: 05-01-2003, 03:52 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21