Command pattern with linked tree structure (using pointers)

Question

I am developing an editor for some kind of binary tree structure and I need to have an undo function. I thought about using the command pattern to achieve this. However, I was yet unable to find a way to use the command pattern with my binary tree structure.

The binary tree structure is made up via pointers. So a node knows its parent and its children. When I now want to add a node I would construct a NodeAdd object with the parent as parameter and pass it to the UndoStack. In order to remove an existing node a NodeRemove object would be passed to the UndoStack with a pointer to the Node as parameter. Both, the NodeAdd and NodeRemove would have to implement undo() and redo() (where redo() is called when the object is put on the UndoStack).

The problem I am facing is, dealing with the situation when a node removal and then the addition of this same node should be undone:

1. redo NodeAdd
2. redo NodeRemove
3. undo NodeRemove
4. undo NodeAdd

Once the redo NodeRemove is executed the Node object is destroyed. In the undo NodeRemove a new Node object can be constructed again, but undo NodeAdd could not be executed as it does not have the pointer to the newly constructed Node.

I think I am trying to use the command pattern in the wrong way. I probably should destroy or construct the Node objects rather within the commands' constructor/destructor than within undo()/redo(). Unfortunately, I have no idea how to do this with this kind of structure and all examples and advices I could find are related to text editing or editing something where you have not a dynamic structure with pointers.

Any ideas how to approach this problem?

Answer 1

One option would be to have your Command objects refer to their operands by some unique identifier (say an index represented as a size_t) instead of by memory address which, as you've discovered, can fluctuate.

Then, by maintaining an unordered_map< size_t, Node* > somewhere (say a static member of Node for example), your Command objects can obtain the current embodiment of a given Node and add/remove/manipulate it as necessary.

Answer 2

The command pattern is probably not sufficient for the undo. For undo, you should use the memento pattern.

Answer 3

Patterns can be combined, even within themselves. Give your Commands both an execute method and an undo method. When a Command is invoked put an instance into a two way Chain of Responsibility, have an undo and redo direction and methods.