best practice for Undo Redo implementation [closed

Question

I need to implement Undo/Redo frame work for my window application(editor like powerpoint), what should be the best practice to follow, how would be handle all property changes of my objects and it reflection on UI.

Answer 1

The classic practice is to follow the Command Pattern.

You can encapsulate any object that performs an action with a command, and have it perform the reverse action with an Undo() method. You store all the actions in a stack for an easy way of rewinding through them.

Answer 2

There are two classic patterns to use. The first is the memento pattern which is used to store snapshots of your complete object state. This is perhaps more system intensive than the command pattern, but it allows rollback very simply to an older snapshot. You could store the snapshots on disk a la PaintShop/PhotoShop or keep them in memory for smaller objects that don't require persistence. What you're doing is exactly what this pattern was designed for, so it should fit the bill slightly better than the Command Pattern suggested by others.

Also, an additional note is that because it doesn't require you to have reciprocal commands to undo something that was previously done, it means that any potentially one way functions [such as hashing or encryption] which can't be undone trivially using reciprocal commands can still be undone very simply by just rolling back to an older snapshot.

Also as pointed out, the command pattern which is potentially less resource intensive, so I will concede that in specific cases where:

• There is a large object state to be persisted and/or
• There are no destructive methods and
• Where reciprocal commands can be used very trivially to reverse any action taken

the command pattern may be a better fit [but not necessarily, it will depend very much on the situation]. In other cases, I would use the memento pattern.

I would probably refrain from using a mashup of the two because I tend to care about the developer that's going to come in behind me and maintain my code as well as it being my ethical responsibility to my employer to make that process as simple and inexpensive as possible. I see a mashup of the two patterns easily becoming an unmaintainable rat hole of discomfort that would be expensive to maintain.

Answer 3

There are three approaches here that are viable. Memento Pattern (Snapshots), Command Pattern and State Diffing. They all have advantages and disadvantages.

I would go with State Diffing if you can get away with it as it combines memory reduction with ease of implementation and maintainability.

Note that the VoxelShop mentioned in the article is open source. So you can take a look at the complexity of the command pattern here: https://github.com/simlu/voxelshop/tree/develop/src/main/java/com/vitco/app/core/data/history

Below is excerpt from the article:

Memento Pattern

Pros

• Implementation is independent of the applied action. Once implemented we can add actions without worrying about breaking history.
• It is fast to advance to a predefined position in history. This is interesting when the actions applied between current and desired history position are computationally expensive.

Cons

• Memory Requirements can be significantly higher compared to other approaches.
• Loading time can be slow if the snapshots are large.

Command Pattern

Pros

• Memory footprint is small. We only need to store the changes to the model and if these are small, then the history stack is also small.

Cons

• We can not go to an arbitrary position directly, but rather need to un-apply the history stack until we get there. This can be time consuming.
• Every action and it's reverse needs to be encapsulated in an object. If your action is non trivial this can be difficult. Mistakes in the (reverse) action are really hard to debug and can easily result in fatal crashes. Even simple looking actions usually involve a good amount of complexity. E.g. in case of the 3D Editor, the object for adding to the model needs to store what was added, what color was currently selected, what was overwritten, if mirror mode active etc.
• Can be challenging to implement and memory intensive when actions do not have a simple reverse, e.g when blurring an image.

State Diffing

Pros

• Implementation is independent of the applied action. Once the history functionality is added we can add actions without worrying about breaking history.
• Memory Requirements is usually much lower than for the Snapshot approach and in a lot of cases comparable to the Command Pattern approach. However this highly depends on the type of actions applied. E.g. inverting the color of an image using the Command Pattern should be very cheap, while State Diffing would save the whole image. Conversely when drawing a long free-form line, the Command Pattern approach might use more memory if it chained history entries for each pixel.

Cons / Limitations

• We can not go to an arbitrary position directly, but rather need to un-apply the history stack until we get there.
• We need to compute the diff between states. This can be expensive.
• Implementing the xor diff between model states might be hard to implement depending on your data model.

Reference:

https://www.linkedin.com/pulse/solving-history-hard-problem-lukas-siemon

Answer 4

Take a look at the Command Pattern. You have to encapsulate every change to your model into separate command objects.

Answer 5

I wrote a really flexible system to keep track of changes. I have a drawing program which implements 2 types of changes:

• add/remove a shape
• property change of a shape

Base class:

public abstract class Actie
{
    public Actie(Vorm[] Vormen)
    {
        vormen = Vormen;
    }

    private Vorm[] vormen = new Vorm[] { };
    public Vorm[] Vormen
    {
        get { return vormen; }
    }

    public abstract void Undo();
    public abstract void Redo();
}

Derived class for adding shapes:

public class VormenToegevoegdActie : Actie
{
    public VormenToegevoegdActie(Vorm[] Vormen, Tekening tek)
        : base(Vormen)
    {
        this.tek = tek;
    }

    private Tekening tek;
    public override void Redo()
    {
        tek.Vormen.CanRaiseEvents = false;
        tek.Vormen.AddRange(Vormen);
        tek.Vormen.CanRaiseEvents = true;
    }

    public override void Undo()
    {
        tek.Vormen.CanRaiseEvents = false;
        foreach(Vorm v in Vormen)
            tek.Vormen.Remove(v);
        tek.Vormen.CanRaiseEvents = true;
    }
}

Derived class for removing shapes:

public class VormenVerwijderdActie : Actie
{
    public VormenVerwijderdActie(Vorm[] Vormen, Tekening tek)
        : base(Vormen)
    {
        this.tek = tek;
    }

    private Tekening tek;
    public override void Redo()
    {
        tek.Vormen.CanRaiseEvents = false;
        foreach(Vorm v in Vormen)
            tek.Vormen.Remove(v);
        tek.Vormen.CanRaiseEvents = true;
    }

    public override void Undo()
    {
        tek.Vormen.CanRaiseEvents = false;
        foreach(Vorm v in Vormen)
            tek.Vormen.Add(v);
        tek.Vormen.CanRaiseEvents = true;
    }
}

Derived class for property changes:

public class PropertyChangedActie : Actie
{
    public PropertyChangedActie(Vorm[] Vormen, string PropertyName, object OldValue, object NewValue)
        : base(Vormen)
    {
        propertyName = PropertyName;
        oldValue = OldValue;
        newValue = NewValue;
    }

    private object oldValue;
    public object OldValue
    {
        get { return oldValue; }
    }

    private object newValue;
    public object NewValue
    {
        get { return newValue; }
    }

    private string propertyName;
    public string PropertyName
    {
        get { return propertyName; }
    }

    public override void Undo()
    {
        //Type t = base.Vorm.GetType();
        PropertyInfo info = Vormen.First().GetType().GetProperty(propertyName);
        foreach(Vorm v in Vormen)
        {
            v.CanRaiseVeranderdEvent = false;
            info.SetValue(v, oldValue, null);
            v.CanRaiseVeranderdEvent = true;
        }
    }
    public override void Redo()
    {
        //Type t = base.Vorm.GetType();
        PropertyInfo info = Vormen.First().GetType().GetProperty(propertyName);
        foreach(Vorm v in Vormen)
        {
            v.CanRaiseVeranderdEvent = false;
            info.SetValue(v, newValue, null);
            v.CanRaiseVeranderdEvent = true;
        }
    }
}

With each time Vormen = the array of items that are submitted to the change. And it should be used like this:

Declaration of the stacks:

Stack<Actie> UndoStack = new Stack<Actie>();
Stack<Actie> RedoStack = new Stack<Actie>();

Adding a new shape (eg. Point)

VormenToegevoegdActie vta = new VormenToegevoegdActie(new Vorm[] { NieuweVorm }, this);
UndoStack.Push(vta);
RedoStack.Clear();

Removing a selected shape

VormenVerwijderdActie vva = new VormenVerwijderdActie(to_remove, this);
UndoStack.Push(vva);
RedoStack.Clear();

Registering a property change

PropertyChangedActie ppa = new PropertyChangedActie(new Vorm[] { (Vorm)e.Object }, e.PropName, e.OldValue, e.NewValue);
UndoStack.Push(ppa);
RedoStack.Clear();

Finally the Undo/Redo action

public void Undo()
{
    Actie a = UndoStack.Pop();
    RedoStack.Push(a);
    a.Undo();
}

public void Redo()
{
    Actie a = RedoStack.Pop();
    UndoStack.Push(a);
    a.Redo();
}

I think this is the most effective way of implementing a undo-redo algorithm. For an example, look at this page on my website: DrawIt.

I implemented the undo redo stuff at around line 479 of the file Tekening.cs. You can download the source code. It can be implemented by any kind of application.