Can't get my head around implementing an Undo/Redo functionality, should I use a Stack?

I'm getting kind of confused right now, having one of those days I guess.

I need to implement an Undo and Redo functionality for a form. For simplicities sake, let's say that I only save the control which was modified and the value it had when it left Fo开发者_如何学运维cus.

How do I save this information in a way that lets me go back or forth in the 'timeline'.

I thought about using a Stack, but while I was testing my little demo, I had a mild aneurysm and here I am.

Code needed, not really but would help. I'm more interested in the algorithm I'd need to implement. Any suggestions?

Yes, you would use a stack. There are a couple ways to do it; read these references:

http://en.wikipedia.org/wiki/Command_pattern

http://en.wikipedia.org/wiki/Memento_pattern

Each has its pros/cons.

A stack is perfect if you push a "change" onto it, and when undo pop a "change" from it. You then push that popped change into another stack representing redo. At some point in the future, hopefully on save, you clear both stacks.

It's not actually as simple as that, as you need to record the type of change, understand the old and new values etc. So when you pop from the undo stack, the thing you pop must describe what the prior value was and what control it was set to.

Inverse for the redo stack, it needs to understand what the new value was and where it went. But yes, the idea of two stacks is a good start for a homebrew undo-redo.

A good example of a business object based undo is CSLA.NET, which has UndoableBase:

http://www.lhotka.net/cslanet/

http://www.koders.com/csharp/fidCF6AB2CF035B830FF6E40AA22C8AE7B135BE1FC0.aspx?s=serializationinfo

However this records a snapshot of an object's state, so it would be more advanced that your form-based concept. However, CSLA.NET offers full data binding support so a data bound object inheriting from UndoableBase would naturally support undo (not redo) in the UI.

I would use an IUndoableAction interface. The implementations could store whatever data they needed to be done and undone. Then yes, I would use a Stack to hold them.

interface IUndoableAction
{
    void Do();
    void Undo();
}
Stack<IUndoableAction> Actions;

Each kind of action would implement the Do and Undo methods.

Then, somewhere there would be these two methods:

    void PerformAction(IUndoableActionaction)
    {
        Actions.Push(action);
        action.Do();
    }

    void Undo()
    {
        var action = Actions.Pop();
        action.Undo();
    }

As for what to store in the action classes, some actions could just store the old value. However, once I had an action to swap two rows in a spreadsheet. I didn't store the values of every cell in both rows -- I just stored the row indices so they could be swapped back. It could be easy to fill up tons of memory if you stored all of that state for every action.

Then you want a Redo stack as well, and when you undo an action it is pushed onto the redo stack. The redo stack will need to be cleared when a new action is performed, so things don't get out of order.

Probably the most straightforward is to have the undo/redo stack combination.

An alternative is to have an array or list of actions, and just increment/decrement a pointer to an index in the array. When an action is undone, the index is moved back by one, and when the action is redone, the index is moved forward by one. The advantage here is that you don't require a pop-and-then-push sequence for each action.

Things to consider:

• If you undo several times, and then perform an action, all of the redo actions must be eliminated.
• Make sure you check the boundaries and ensure that there is an action available to undo/redo before trying to perform the undo/redo.