[C#] List for generic undo redo and Mementos

Well rather than storing commands to be acted on object store commands that have objects bound. So instead of having a Restore(T target) member, just have a Restore() member and store the target as part of the concrete object.

[color="#1C2837"]Well rather than storing commands to be acted on object store commands that have objects bound. So instead of having a Restore(T target) member, just have a Restore() member and store the target as part of the concrete object.
[color="#1c2837"][/quote]

[color="#1c2837"]I'm a little confused by that.

[color="#1c2837"]If I just have Restore for the IMemento:

[color="#1c2837"]
public interface IMemento<T>
{
IMemento<T> Restore();
}


[color="#1c2837"]then I can't store a global list of IMementos that can be done/undone despite the different object types they refer to, as the T would need to refer to a single object type.

Don't parameterize the interface. Store a base interface type.

Could you please give an example? I'm not sure how that would work with the UndoRedoHistory class:



[Serializable]
public class UndoRedoHistory<T>
{
/// <summary>
/// The subject that this undo redo history is about
/// </summary>
protected T subject;

private const int DEFAULT_CAPACITY = 100;

private bool supportRedo = true;
private bool inUndoRedo = false;

[NonSerialized]
private CompoundMemento<T> tempMemento = null;

/// <summary>
/// Undo stack with capacity
/// </summary>
protected RoundStack<IMemento<T>> undoStack;

/// <summary>
/// Redo stack with capacity
/// </summary>
protected RoundStack<IMemento<T>> redoStack;

/// <summary>
/// Creates <see cref="UndoRedoHistory<T>"/> with default capacity.
/// </summary>
/// <param name="subject"></param>
public UndoRedoHistory(T subject)
: this(subject, DEFAULT_CAPACITY)
{
}

/// <summary>
/// Creates <see cref="UndoRedoHistory<T>"/> with given capacity.
/// </summary>
/// <param name="subject"></param>
/// <param name="capacity"></param>
public UndoRedoHistory(T subject, int capacity)
{
this.subject = subject;
undoStack = new RoundStack<IMemento<T>>(capacity);
redoStack = new RoundStack<IMemento<T>>(capacity);
}

/// <summary>
/// Gets a value indicating if the history is in the process of undoing or redoing.
/// </summary>
/// <remarks>
/// This property is extremely useful to prevent undesired "Do" being executed.
/// That could occur in the following scenario:
/// event X causees a Do action and certain Undo / Redo action causes event X,
/// i.e. Undo / Redo causes a Do action, which will render history in a incorrect state.
/// So whenever <see cref="Do(IMemento<T>)"/> is called, the status of <see cref="InUndoRedo"/>
/// should aways be checked first. Example:
///
/// void SomeEventHandler()
/// {
/// if(!history.InUndoRedo)
/// history.Do(...);
/// }
///
///
public bool InUndoRedo
{
get { return inUndoRedo; }
}

///

/// Gets number of undo actions available
///

public int UndoCount
{
get { return undoStack.Count; }
}

///

/// Gets number of redo actions available
///

public int RedoCount
{
get { return redoStack.Count; }
}

///

/// Gets or sets whether the history supports redo.
///

public bool SupportRedo
{
get { return supportRedo; }
set { supportRedo = value; }
}

///

/// Begins a complex memento for grouping.
///

///
/// Thrown if previous grouping wasn't ended. See .
///
///
public void BeginCompoundDo()
{
if (tempMemento != null)
{
throw new InvalidOperationException("BeginCompoundDo cannot be called again until EndCompoundDo has been successfully called.");
}

tempMemento = new CompoundMemento();
}

///

/// Ends grouping by pushing the complext memento created by into the undo stack.
///

///
/// For details on how grouping works, see .
///
///
/// Thrown if grouping wasn't started. See .
/// ///
public void EndCompoundDo()
{
if (tempMemento == null)
{
throw new InvalidOperationException("BeginCompoundDo must be called successfully before EndCompoundDo can be called.");
}

_Do(tempMemento);
tempMemento = null;
}

///

/// Pushes an memento into the undo stack, any time the state of changes.
///

///
///
/// This method MUST be properly involked by programmers right before (preferably) or right after
/// the state of is changed.
/// Whenever is called, the status of
/// should aways be checked first. See details at .
/// This method causes redo stack to be cleared.
///
///
///
///
public void Do(IMemento m)
{
if (inUndoRedo)
{
throw new InvalidOperationException("Invoking Do within an undo/redo action.");
}

if (tempMemento == null)
{
_Do(m);
}
else
{
tempMemento.Add(m);
}
}

///

/// Internal DO action with no error checking
///

///
private void _Do(IMemento m)
{
redoStack.Clear();
undoStack.Push(m);
}

///

/// Restores the subject to the previous state on the undo stack, and stores the state before undoing to redo stack.
/// Method can be called before calling this method.
///

///
public void Undo()
{
if (tempMemento != null)
{
throw new InvalidOperationException("The complex memento wasn't commited.");
}

inUndoRedo = true;
IMemento top = undoStack.Pop();
redoStack.Push(top.Restore(subject));
inUndoRedo = false;
}

///

/// Restores the subject to the next state on the redo stack, and stores the state before redoing to undo stack.
/// Method can be called before calling this method.
///

///
public void Redo()
{
if (tempMemento != null)
{
throw new InvalidOperationException("The complex memento wasn't commited.");
}

inUndoRedo = true;
IMemento top = redoStack.Pop();
undoStack.Push(top.Restore(subject));
inUndoRedo = false;
}

///

/// Checks if there are any stored state available on the undo stack.
///

public bool CanUndo
{
get { return (undoStack.Count != 0); }
}

///

/// Checks if there are any stored state available on the redo stack.
///

public bool CanRedo
{
get { return (redoStack.Count != 0); }
}

///

/// Clear the entire undo and redo stacks.
///

public void Clear()
{
undoStack.Clear();
redoStack.Clear();
}

///

/// Gets, without removing, the top memento on the undo stack.
///

///
public IMemento PeekUndo()
{
return undoStack.Count > 0 ? undoStack.Peek() : null;
}

///

/// Gets, without removing, the top memento on the redo stack.
///

///
public IMemento PeekRedo()
{
return redoStack.Count > 0 ? redoStack.Peek() : null;
}
}

What SiCrane means is that make your undo/redo class object oblivious. Don't store the tile handle, but rather do something like this (below code doesn't use templates):



class BaseClass {};

class Tile : public BaseClass {}

class UndoCommand
{
//used for create/undo operations to know which type of object to instantiate
UINT iObjectType;
//use std::map or a custom storage holder to store the basic arguments needed to re-create an object if needed. Store only the minimum amount of information required here.
ArgList pList;
//a handle to the object; you can use this for caching (eg when you remove the object from the active list in your app, but don't deallocate it to speed up undo/redo operations
//by simply copying the object pointer to the undo stack; you can also use this for simple operations that do not affect memory operations, eg when translating, rotating or scaling
//an object (or changing one of its parameters) to speed things up a lot)
BaseClass* objHandle;
//something basic like UNDO_DELETE, UNDO_CREATE_ UNDO_TRANSLATE, UNDO_MODIFYPROPERTY, etc
UINT iCommand;
}


Your interface should not be generic and each memento target bundled in the memento.

With that change the UndoRedo class also does not require to be a generic and can handle any memento from anywhere for any instance.


public interface IMemento
{
IMemento Restore();
}



class AddTileMemento : IMemento
{
private int index;
Tile[] target;
public AddTileMemento(Tile[] target, int index)
{
this.target = target;
this.index = index;
}

public override IMemento Restore()
{
Tile removed = target[index];

IMemento inverse = new RemoveTileMemento(target, index, removed);

target[index] = null;

return inverse;
}
}


class RemoveTileMemento : IMemento
{
private int index;
private Tile removed;
Tile[] target;
public RemoveTileMemento(Tile[] target, int index, Tile removed)
{
this.target = target;
this.index = index;
this.removed = removed;
}

public override IMemento Restore()
{
IMemento inverse = new AddTileMemento(target, index);

target[index] = removed;

return inverse;
}
}


Thanks Gorg. When thinking of a C# implementation I came up with something similar but I wasn't sure if this is what SiCrane and irreversible were getting at.

Things that made me think I was doing it wrong:



UINT iObjectType;
UINT iCommand;


These could be implemented as enums.

What would happen if I was translating more than one tile?

I could store the indices for each tile and recreate them or I would have to create a copy of the array each time it changed so the previous indices could be restored, but that would no doubt consume a lot of memory.

I'm not sure how this translates to C# either:




//a handle to the object; you can use this for caching (eg when you remove the object from the active list in your app, but don't deallocate it to speed up undo/redo operations
//by simply copying the object pointer to the undo stack; you can also use this for simple operations that do not affect memory operations, eg when translating, rotating or scaling
//an object (or changing one of its parameters) to speed things up a lot)
BaseClass* objHandle;


These could be implemented as enums.

How you store these is up to you - you can use enums, define lists, strings or whatnot.

What would happen if I was translating more than one tile?

One way would be to store selection as an undo action and undo the moving as group undo of two user actions: (1) deselect range->select range (if the last action the user did was to deselect the range), (2) move tiles. The main thing you have to decide on is how undo commands are automatically grouped (normally you'll want a group to end when the user commits a change, such as removing/creating/translating/scaling/rotating and object and store all other commands (select/deselect/move caret for text controls etc) as soft commands that are always executed as a group until a real command is encountered. In this case the translation itself is stored as a translation action with zero additional information. However, instead of the regular selection.pos += moveAmount you implement its inverse selection.pos -= moveAmount.

I'm not sure how this translates to C# either:

Sorry, I can't help you with C# . The undo mechanism, however, remains the same no matter what language you implement it in.

Command Pattern.

Instead of modifying state directly, all actions are applied by creating commands. Each of these derives from base interface:interface Command {
void perform();
void undo();
};

Let's say you want to draw a tile:
class SetTileCommand : Command {
void perform() {
oldColor = map.get(x, y);
map.set(x, y, newColor);
}
void undo() {
map.set(x, y, oldColor);
}
Map map;
private Color oldColor;
private Color newColor;
private int x;
private int y;
};


It should be obvious how undo now becomes merely a list of these commands. To undo, call unto() on them as far as needed.


Such approach tends to be better for coarse-grained actions, but a few thousand actions should not be a big deal.

For fancy and advanced undo, you would introduce coalescing - if several actions of same type are applied consecutively, you can merge them into a single super action. A generic solution might involve reflection or you could just manually code it. Something like:class GroupedSetTileAction {

...
List<int> x;
List<int> y;
List<int> oldColor;
List<int> newColor;
...
};

Then, when applying an action, if it's the same type as previous, you append to previous action, otherwise you create a new command.

Can you just make your history list of type "List

Can you just make your history list of type "List

Don't do this. The scenario presented by the OP has a clear solution that follows the open/closed principle. With the solution, you can add new commands without modifying the UndoRedo class. In your example, you cannot.

Can you just make your history list of type "List

About only reason to ever query type of object is to work around broken APIs.

For everything else, there is polymorphism. Instead of object, one has Undoable (or similar) class/interface:interface Undoable {
void undo();
};

List<Undoable> undoList;
...
Undoable u = ...
u.undo();

The Command Pattern makes more sense to me than the Memento Pattern. I will attempt to implement that this weekend.

Thanks Antheus.