Functorized Undo/Redo

One day, I was looking for the Undo/Redo algorithm to be used in my future project. Among different resources, I found DDJ, [1], where Al Stevens presented the template-based algorithm of Undo/Redo actions.

As far I got (unfortunately, on the Net there is no article available, just the source code at http://www.ddj.com/ftp/1998/1998_11/cprog118.txt), its implementation addresses mostly document editors. Typical actions are: Insert, Delete, & Replace. The code seemed interesting, but its using was not obvious.

The idea to marry the algorithm with the functor was encouraging. So, this article presents what I eventually got.

Tested Software

The code was tested with MS Visual C++ 2003 and Windows 2000. Generally, you may run the code in any environment: Win32, Unix, ... Your compiler should be good with templates.

Source Code

undo.h: (modified Al Stevens code)

• class UndoItem: a unit of the Undo/Redo action
• class UndoData: encapsulates the containers of UndoItems (undos & redos)

fundo.h:

1. class UndoPar: Is for Undo/Redo parameters (Data)

class UndoPar (
public:
   UndoPar();
   UndoPar(const UndoPar& par);
   UndoPar& operator=(const UndPar& par);

   // rewind current parameter position
   void Rewind() {it_ = buffer_.begin(); }

   template <typename T> void AddPar( T par );
   template <typename T> T    GetPar();

private:
   std::vector<char> buf_;               // parameters buffer
   std::vector<char>::iterator it_;      // current parameter
                                         // position
   static const size_t chunk_sz = 128;   // buffer reallocation
                                         // chunk
}

Data are stored in the buf_ dynamic container. You may vary the size of the reallocation chunk. By default, I set it to 128 bytes.

To store the data:

UndoPar par;
par.Rewind();
par.AddPar<double>(5.);
par.AddPar<int>(2);
par.AddPar<short>(2);

To get data back:

UndoPar par;
par.Rewind();
double d = par.GetPar<double>();
int n    = par.GetPar<int>();
short s  = par.GetPar<short>();

In fact, you may use more complex structure data types instead of ordinary types.

2. class UndoTarget: Is a base class for the classes supporting Undo/Redo functionality.

class UndoTarget
{
   virtual ~UndoTarget() {}
   void fn(bool, UndoPar&);
}
typedef (UndoTarget::* pfnType)(bool, UndoPar&);

3. class Ftor: Functor.While applying operator(), the method that performs Undo/Redo is activated.

class Ftor
{
public:
   Ftor(UndoTarget* pobj, pfnType pfn) : pobj_(pobj),
       pfn_(pfn) {}

   void operator()(bool b, UndoPar& par)
   {
      (pobj_->*pfn_)(b, par);
   }

private:
   UndoTarget* pobj_;
   pfnType     pfn_;
}

4. class UndoRedo: Encapsulates functor to be activated while doing Undo/Redo, and the data to be applied.

class UndoRedo
{
public:
   UndoRedo(Ftor& ftor, UndoPar& par) :
            ftor_(ftor), undopar_(par) {}
   void Undo() {ftor_( false, undopar_ );}
   void Redo() {ftor_( true, undopar_ );}
private:
   Ftor ftor_;
   UndoPar undopar_;    // undo/redo data
}

5. class AppUndos: This class is in charge of Undo/Redo at the application level.

class AppUndos : public UndoData<UndoRedo>
{
public:
   explicit AppUndos(size_t nMaxUndos = MAX_UNDOS) :
      UndoData<UndoRedo>(nMaxUndos) {}

   void AddUndoItem(UndoRedo& f)
   {
      UndoData<UndoRedo>::AddUndoItem( UndoAction(f) );
   }
}

Note that MAX_UNDOS may be any reasonable value.

6. The files AppData.[h,cpp] are the example of the usage of the foregoing classes. They implement the Data class.

class Data : public UndoTarget
{
public:
   Data();
   ~Data() {};

   void f1();
   void f2();

   void Dump( const char* ) const;

   void Undo() { m_undo.UndoLastAction(); }
   void Redo() { m_undo.RedoLastUndo(); }

private:

   // signature of f1_ & f2_ must comply pfnType
   void f1_( bool, UndoPar& );    // false: undo, true: redo
   void f2_( bool, UndoPar& );

   std::vector<double> m_x;
   AppUndos                  m_undo;
};

Suppose our application can execute f1() on the array of the double data, m_x, X = a*(b*X+c)

void Data::f1()
{
   UndoPar par;
   par.Rewind();
   par.AddPar<double>(5.);    // b
   par.AddPar<int>(2);        // a
   par.AddPar<short>(2);      // c

   f1_(true, par);

   UndoRedo ur( Ftor(this, (pfnType)f1_), par );
   m_undo.AddUndoItem( ur ); 
}

f1_() is called:

1. Directly to make caculations.
2. Indirectly (functor is activated) when doing Undo() or Redo().

Installation

Project MyUndo0

Unzip the source code that is supplied. The EXE file is already in the Release folder.

Project MyUndo

This uses Alexandrescu's generalized functors, [2]. You should have the Loki library ([3]) installed. Project Directories Properties assumes that the MyUndo folder is at the same level with Loki Level. SmallObj.cpp is already in the MyUndo folder and includes the "stdafx.h" header.

The test is the Win32 console application. Initially, an array of double values is: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

Function f1 makes X = 2*(5.*X + 2)
Function f2 makes X = 2.45*x + 1

The following sequence is applied:

f1();
f2();
Undo();
Undo();
Redo();
Redo();
Undo();
Undo();

Each data modification is followed by dumping the current values on the console. Logically, with such a sequence applied, we should end up with values equal to those before the calculations.

Conclusion

The presented functorized Undo/Redo classes are really helpful because:

1. They are portable because they're made on pure C++.
2. Their application may vary: data processing, text editors ... (due to a dynamic undo-data buffer allocation that is able to store information of any kind).

References

1. Dr. Dobb's Journal, November 1998
2. Alexandrescu, Andrei. Modern C++ Design: Generic Programming and Design Patterns Applied. Addison-Wesley, 2001
3. Loki's library source code: http://www.awl.com/cseng/titles/0-201-70431-5