Generic Undo/Redo Stack in C#
By
Steve on
Wednesday, July 31, 2013
Updated
Friday, April 22, 2016
Viewed
58,018 times. (
0 times today.)
While working on PieceWorx Writing Studio, I needed to implement a customized undo/redo stack for the RichTextBox. The RichTextBox does support Undo/Redo, but with all of the behind-the-scenes operations I was performing on the content of the RichTextBox, the built-in undo stack ends up not being suitable.
Some operations require replacing the entire RTF content which clears the undo/redo stack. This was a problem.
So I needed something else.
This article does not present an undo/redo implementation for RichTextBox, but lays the groundwork with a generic Undo/Redo stack implementation.
Video Version of this Article
The nice folks over at Webucator.com offered to create an instructional video based on this article. If you want to see exactly how to implement this solution in Visual Studio please check it out.
Existing Solutions
If you search the web you'll find a lot of complicated descriptions and implementations for Undo/Redo stacks.
Eventually, I decided to ignore them all and code something simple.
For this article I present a simple generic implementation of an Undo/Redo stack which can easily be adapted for working with different types of objects and different types of actions.
I'll start with the code and then we can talk about how you might expand on this for your scenario.
Scenario
But before I dive into the code, let me explain the example scenario I'll be using for this article. While Undo/Redo stacks are often thought of in association with a text editor, the main example I'm going to use in this article will not be text operations on a string, but mathematical operations on an integer.
The two concepts are analogous. If there is demand (leave me a comment) I'll present an example for how to apply this solution to operations on a string.
In addition, you'll see that the solution would work equally well operating directly on a RichTextBox itself rather than just a string.
ICommand
I did not set out to implement the Gang of Four Command pattern which is what many implementations call upon. However, I suspect someone could analyze the code below and point out how it does, in fact, satisfy the Command pattern. For the time being, I'm not interested in ferreting out the nuances of invokers, receivers, clients and commands. The only concept I'll use directly will be "command."
A command is some action that you are going to add to your Undo stack. For example, appending a letter to a string, deleting a letter, adding a value to an existing integer or subtracting one. The concrete commands would be Append, Delete, Add, Subtract, etc.
The first thing I'll present then is the ICommand interface.
public interface ICommand<T>
{
T Do(T input);
T Undo(T input);
}
This looks simple enough. Any command can do something and then undo the something that it just did.
Take a look, now, at the generic type parameter, T. Notice that it is both the input and return type for the Do and Undo methods.
T is the thing the Do and Undo commands will operate on. The Do and Undo commands will then return the modified T object or a new T object that will replace the one that was passed in.
Integers and strings are immutable so clearly the return object will be a new integer or a new string.
But suppose T is a RichTextBox, then you will probably return the same RichTextBox after the command has made its changes.
Okay, then. Moving on.
AddIntCommand
Let's create a concrete instance of ICommand which adds an integer value to an existing integer.
public class AddIntCommand: ICommand<int>
{
private int _Value;
public int Value
{
get
{
return _Value;
}
set
{
_Value = value;
}
}
public AddIntCommand()
{
_Value = 0;
}
public AddIntCommand(int value)
{
_Value = value;
}
public int Do(int input)
{
return input + _Value;
}
public int Undo(int input)
{
return input - _Value;
}
}
When instantiating AddIntCommand, it is initialized with an integer value. Or, if you like, you can use the default constructor and set the Value via the property. This is the value that will be added when the command is executed.
Notice that the Do command adds _Value to the input. The Undo command subtracts _Value from the input. Makes sense.
UndoRedoStack
Alright, we're almost done. Really!
The last piece is the class that will store and manage all the command operations, the UndoRedoStack.
Here is the code. I'll explain it below.
public class UndoRedoStack<T>
{
private Stack<ICommand<T>> _Undo;
private Stack<ICommand<T>> _Redo;
public int UndoCount
{
get
{
return _Undo.Count;
}
}
public int RedoCount
{
get
{
return _Redo.Count;
}
}
public UndoRedoStack()
{
Reset();
}
public void Reset()
{
_Undo = new Stack<ICommand<T>>();
_Redo = new Stack<ICommand<T>>();
}
public T Do(ICommand<T> cmd, T input)
{
T output = cmd.Do(input);
_Undo.Push(cmd);
_Redo.Clear(); // Once we issue a new command, the redo stack clears
return output;
}
public T Undo(T input)
{
if (_Undo.Count > 0)
{
ICommand<T> cmd = _Undo.Pop();
T output = cmd.Undo(input);
_Redo.Push(cmd);
return output;
}
else
{
return input;
}
}
public T Redo(T input)
{
if (_Redo.Count > 0)
{
ICommand<T> cmd = _Redo.Pop();
T output = cmd.Do(input);
_Undo.Push(cmd);
return output;
}
else
{
return input;
}
}
}
The UndoRedoStack is pretty simple. It's only data members are two Stacks. One we call the Undo stack. The other we call the Redo stack.
The Undo stack is where the history of all executed commands is stored. The Redo stack is where we put a command when it is undone. This allows us the ability to redo that command if we decided we didn't really want it undone.
I added the UndoCount and RedoCount properties just for convenience and for use in unit testing.
Finally, the methods on the UndoRedoStack are the following:
Examples
Let's look at some examples.
Execute the add command four times.
// Instantiate our undo/redo stack for operations on an integer value
UndoRedoStack<int> ur = new UndoRedoStack<int>();
// Perform four commands and add to the undo stack at the same time
int count = 0;
count = ur.Do(new AddIntCommand(10), count);
count = ur.Do(new AddIntCommand(11), count);
count = ur.Do(new AddIntCommand(12), count);
count = ur.Do(new AddIntCommand(13), count);
In this example, we are performing commands on the integer parameter count. Each command will add a value to count. We first add 10 and get the result. Then we add 11 to that result, 12 to that result, etc.
The final number is 46.
0 + 10 + 11 + 12 + 13 = 46
Now, let's undo the last two commands. This will subtract 13 and subtract 12 as follows.
Undo Last Two Commands
count = ur.Undo(count);
count = ur.Undo(count);
The result now is 21.
0 + 10 + 11 + 12 + 13 - 13 - 12 = 21
Let's redo the last two commands
Redo Last Two Commands
count = ur.Redo(count);
count = ur.Redo(count);
The result is now back to 46.
0 + 10 + 11 + 12 + 13 - 13 - 12 + 12 + 13 = 46
We could do this all day, but I think you get the picture.
Look below for a full scale unit test method where you can explore examples like this in your own code.
Expanding Your Solutions
Clearly most Undo/Redo scenarios will not involve a single command like AddIntCommand. You will need to create additional concrete commands similar to AddIntCommand.
You can imagine creating SubtractIntCommand or MultIntCommand, etc.
Here is the code for SubtractIntCommand which is very similar, of course, to AddIntCommand.
See the unit test code below for examples using both AddIntCommand and SubtractIntCommand.
SubtractIntCommand
public class SubtractIntCommand: ICommand<int>
{
private int _Value;
public int Value
{
get
{
return _Value;
}
set
{
_Value = value;
}
}
public SubtractIntCommand()
{
_Value = 0;
}
public SubtractIntCommand(int value)
{
_Value = value;
}
public int Do(int input)
{
return input - _Value;
}
public int Undo(int input)
{
return input + _Value;
}
}
}
Undo/Redo For Strings
Meanwhile, if you decide to expand on this article and create an UndoRedoStack for strings you'll need to create some commands like Append, Insert, Delete, Replace or whatever. Then you might have something that can be used as follows.
// Instantiate our undo/redo stack for operations on a string value
UndoRedoStack<string> ur = new UndoRedoStack<string>();
// Perform some commands and add to the undo stack at the same time
string text = "";
text = ur.Do(new AppendCommand("Four "), text);
text= ur.Do(new AppendCommand("score "), text);
text= ur.Do(new AppendCommand("and "), text);
text= ur.Do(new AppendCommand("six "), text);
text= ur.Do(new AppendCommand("years "), text);
// Oops. Undo.
text= ur.Undo(text);
text= ur.Undo(text);
// Continue appending.
text= ur.Do(new AppendCommand("seven "), text);
text= ur.Do(new AppendCommand("years "), text);
text= ur.Do(new AppendCommand("ago, "), text);
A potentially helpful addition to the UndoRedoStack class is a set of methods that will add the command to the internal undo stack without executing the command.
That will be needed when implementing a stack for, say, a RichTextBox. The RichTextBox executes its own commands. For example, suppose you type a letter. The RichTextBox updates the text with the letter, you don't have to do that. But you still want to store that command in your UndoRedoStack so it can be undone or redone later.
For this, I implement a parallel set of methods to Do, Undo, Redo which do exactly the same thing, but don't execute the command.
Just copy the following methods into the UndoRedoStack class.
Push, UnPush and RePush are used when you execute, undo or redo the command yourself outside of the UndoRedoStack.
public void Push(ICommand<T> cmd)
{
_Undo.Push(cmd);
_Redo.Clear(); // Anytime we push a new command, the redo stack clears
}
public ICommand<T> UnPush()
{
if (_Undo.Count > 0)
{
ICommand<T> cmd = _Undo.Pop();
_Redo.Push(cmd);
return cmd;
}
else
{
return null;
}
}
public ICommand<T> RePush(T input)
{
if (_Redo.Count > 0)
{
ICommand<T> cmd = _Redo.Pop();
_Undo.Push(cmd);
return cmd;
}
else
{
return null;
}
}
In the case of a RichTextBox, you might use Push rather than Do to add the the command to the UndoRedoStack. This is because the RichTextBox is already executing that command. All you have to do is store the command in the UndoRedoStack.
But you would likely still call Undo or Redo on the UndoRedoStack in this scenario rather than UnPush or RePush.
See, we are not using the built in Undo/Redo on the RichTextBox so we have to execute or revert those actions ourselves. The RichTextBox is no longer performing these actions for us.
So, there you have it. A simple generic formulation of an Undo/Redo stack which allows you to create and manage any number of commands which can operate on any type of object suitable for your particular scenario.
Unit Tests
Unit Test of UndoRedoStack with AddIntCommand and SubtractIntCommand
using System;
using System.Text;
using System.Collections.Generic;
using System.Linq;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using Cambia.CoreLib;
namespace Cambia.CoreLib.Test
{
[TestClass]
public class UndoRedoStackTests
{
[TestMethod]
public void BasicAddInt()
{
// Instantiate our undo/redo stack
UndoRedoStack<int> ur = new UndoRedoStack<int>();
// Perform four commands and verify the correct value for our count variable
int count = 0;
count = ur.Do(new AddIntCommand(10), count);
Assert.AreEqual(10, count);
count = ur.Do(new AddIntCommand(11), count);
Assert.AreEqual(21, count);
count = ur.Do(new AddIntCommand(12), count);
Assert.AreEqual(33, count);
count = ur.Do(new AddIntCommand(13), count);
Assert.AreEqual(46, count);
// Verify that there are four commands in the undo stack
Assert.AreEqual(4, ur.UndoCount);
// Undo three of the commands and verify the correct value for the count variable
count = ur.Undo(count);
Assert.AreEqual(33, count);
count = ur.Undo(count);
Assert.AreEqual(21, count);
count = ur.Undo(count);
Assert.AreEqual(10, count);
// Verify that we now have one command in the undo stack and three in the redo stack
Assert.AreEqual(1, ur.UndoCount);
Assert.AreEqual(3, ur.RedoCount);
// Redo the three commands we just undid
count = ur.Redo(count);
Assert.AreEqual(21, count);
count = ur.Redo(count);
Assert.AreEqual(33, count);
count = ur.Redo(count);
Assert.AreEqual(46, count);
// We're out of redo's now so we should just continue to get the same output value
count = ur.Redo(count);
Assert.AreEqual(46, count);
count = ur.Redo(count);
Assert.AreEqual(46, count);
// Verify that the redo stack is really empty
Assert.AreEqual(0, ur.RedoCount);
// Now undo all commands in the undo stack and verify nothing change after that
count = ur.Undo(count);
count = ur.Undo(count);
count = ur.Undo(count);
count = ur.Undo(count);
// OK, we're out of undo's now so we should continue to get the same output value
count = ur.Undo(count);
Assert.AreEqual(0, count);
count = ur.Undo(count);
Assert.AreEqual(0, count);
// See if our Stack counts are correct
Assert.AreEqual(0, ur.UndoCount);
Assert.AreEqual(4, ur.RedoCount);
// Finally, verify that the redo stack gets cleared after a new command
// is added to the undo stack.
count = ur.Do(new AddIntCommand(0), count);
Assert.AreEqual(1, ur.UndoCount);
Assert.AreEqual(0, ur.RedoCount);
}
[TestMethod]
public void BasicAddSubtractInt()
{
// Instantiate our undo/redo stack
UndoRedoStack<int> ur = new UndoRedoStack<int>();
// Perform four commands and verify the correct value for our count variable
int count = 0;
count = ur.Do(new AddIntCommand(10), count);
Assert.AreEqual(10, count);
count = ur.Do(new SubtractIntCommand(5), count);
Assert.AreEqual(5, count);
count = ur.Do(new AddIntCommand(10), count);
Assert.AreEqual(15, count);
count = ur.Do(new SubtractIntCommand(3), count);
Assert.AreEqual(12, count);
// Verify that there are four commands in the undo stack
Assert.AreEqual(4, ur.UndoCount);
// Undo three of the commands and verify the correct value for the count variable
count = ur.Undo(count);
Assert.AreEqual(15, count);
count = ur.Undo(count);
Assert.AreEqual(5, count);
count = ur.Undo(count);
Assert.AreEqual(10, count);
// Verify that we now have one command in the undo stack and three in the redo stack
Assert.AreEqual(1, ur.UndoCount);
Assert.AreEqual(3, ur.RedoCount);
// Redo the three commands we just undid
count = ur.Redo(count);
Assert.AreEqual(5, count);
count = ur.Redo(count);
Assert.AreEqual(15, count);
count = ur.Redo(count);
Assert.AreEqual(12, count);
// We're out of redo's now so we should just continue to get the same output value
count = ur.Redo(count);
Assert.AreEqual(12, count);
count = ur.Redo(count);
Assert.AreEqual(12, count);
// Verify that the redo stack is really empty
Assert.AreEqual(0, ur.RedoCount);
// Now undo all commands in the undo stack and verify nothing change after that
count = ur.Undo(count);
count = ur.Undo(count);
count = ur.Undo(count);
count = ur.Undo(count);
// OK, we're out of undo's now so we should continue to get the same output value
count = ur.Undo(count);
Assert.AreEqual(0, count);
count = ur.Undo(count);
Assert.AreEqual(0, count);
// See if our Stack counts are correct
Assert.AreEqual(0, ur.UndoCount);
Assert.AreEqual(4, ur.RedoCount);
// Finally, verify that the redo stack gets cleared after a new command
// is added to the undo stack.
count = ur.Do(new AddIntCommand(0), count);
Assert.AreEqual(1, ur.UndoCount);
Assert.AreEqual(0, ur.RedoCount);
}
}
}