Undo - Redo using State (update 2)

Problem/Question/Abstract:

Do you need to implement undo and redo in your application?  Here is a simple method, with source, that does the job for small data (up to 20 or 100K in memory)

Answer:

There are 2 methods of Undo-Redo that I know of. The first is saving the current state of the system into a list before it is modified. There would be a GetState and SetState method of your editor.  The second method is to store commands, where each command can undo and redo itself.

Saving state is a good choice when your editor data is small such as 10 to 20K and your editor has many capabilities. Saving state is a simple solution. If you are doing image editing then you could get by with using a file to store your undo and redo information. A vector graphics editor would be a good choice here because vectors do not need much storage space.

The more complex solution of storing commands requires much more coding but is nessesary when your editor edits large amounts of data and storing its state would be too time consuming. A word processor is an example.

I have coded an Undo-Redo State class.. here is how it works. There is the main class that holds the state snapshots (TUndoRedoState), then there is the interface "IState" that has 2 methods, GetState and SetState. I implemented this by making my editor form implement the IState interface.

The main class is created and passed the IState interface. Calling Undo and Redo makes calls to GetState and SetState. If you do not like the way I use an interface then you can easily change the class to accept method pointers to some GetState and SetState method, but I prefer the Interface.

{
  Author William Egge, egge@eggcentric.com
         http://www.eggcentric.com

  Download this working example at http://www.eggcentric.com/UndoRedoState.htm

  This is a demo of using TUndoRedoState.
  Created June 13, 2001

  Enjoy!
}
unit Frm_UndoRedoExample;

interface

uses
  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
  StdCtrls, Buttons, ExtCtrls, UndoRedoState, _State;

type
  // Make this form implement the IState interface to be used
  // by the UndoRedoState object.
  TForm_UndoRedoExample = class(TForm, IState)
    FDrawSurface: TImage;
    FRedoBtn: TSpeedButton;
    FUndoBtn: TSpeedButton;
    FDirections: TLabel;
    procedure Ev_FormCreate(Sender: TObject);
    procedure Ev_FUndoBtnClick(Sender: TObject);
    procedure Ev_FRedoBtnClick(Sender: TObject);
    procedure Ev_FDrawSurfaceMouseDown(Sender: TObject; Button: TMouseButton;
      Shift: TShiftState; X, Y: Integer);
    procedure Ev_FDrawSurfaceMouseMove(Sender: TObject; Shift: TShiftState; X,
      Y: Integer);
    procedure Ev_FDrawSurfaceMouseUp(Sender: TObject; Button: TMouseButton;
      Shift: TShiftState; X, Y: Integer);
    procedure Ev_FormDestroy(Sender: TObject);
  private
    { Private declarations }
    FUndoRedo: TUndoRedoState;
    FMouseDown: Boolean;
  public
    { Public declarations }
    // Methods that implement the IState interface
    procedure GetState(S: TStream);
    procedure SetState(S: TStream);
  end;

var
  Form_UndoRedoExample: TForm_UndoRedoExample;

implementation

{$R *.DFM}

procedure TForm_UndoRedoExample.GetState(S: TStream);
begin
  FDrawSurface.Picture.Bitmap.SaveToStream(S);
end;

procedure TForm_UndoRedoExample.SetState(S: TStream);
begin
  FDrawSurface.Picture.Bitmap.LoadFromStream(S);
end;

procedure TForm_UndoRedoExample.Ev_FormCreate(Sender: TObject);
begin
  // Create a bitmap to draw on
  with FDrawSurface.Picture.Bitmap do
  begin
    Width := FDrawSurface.Width;
    Height := FDrawSurface.Height;
  end;

  // Create the UndoRedo object, this form implements the state interface
  FUndoRedo := TUndoRedoState.Create(Self);
end;

procedure TForm_UndoRedoExample.Ev_FUndoBtnClick(Sender: TObject);
begin
  FUndoRedo.Undo;
end;

procedure TForm_UndoRedoExample.Ev_FRedoBtnClick(Sender: TObject);
begin
  FUndoRedo.Redo;
end;

procedure TForm_UndoRedoExample.Ev_FDrawSurfaceMouseDown(Sender: TObject;
  Button: TMouseButton; Shift: TShiftState; X, Y: Integer);
begin
  // It is possible to get 2 mouse down events with no mouse up event, but rarely
  // Get out when this happens and let mouse up reset it to false.
  if FMouseDown then
    Exit;

  FMouseDown := True;
  FUndoRedo.BeginModify;

  // Set our start point where you first click
  FDrawSurface.Canvas.MoveTo(X, Y);
end;

procedure TForm_UndoRedoExample.Ev_FDrawSurfaceMouseMove(Sender: TObject;
  Shift: TShiftState; X, Y: Integer);
begin
  // Draw
  if FMouseDown then
    FDrawSurface.Canvas.LineTo(X, Y);
end;

procedure TForm_UndoRedoExample.Ev_FDrawSurfaceMouseUp(Sender: TObject;
  Button: TMouseButton; Shift: TShiftState; X, Y: Integer);
begin
  // Finished Editing
  if FMouseDown then
  begin
    FUndoRedo.EndModify;
    FMouseDown := False;
  end;
end;

procedure TForm_UndoRedoExample.Ev_FormDestroy(Sender: TObject);
begin
  FUndoRedo.Free;
end;

end.

Full Source of UndoRedoState.pas and _State.pas:
2 units:

unit _State;

interface
uses
  Classes;

type
  IState = interface
    procedure GetState(S: TStream);
    procedure SetState(S: TStream);
  end;

implementation

end.

[ver 2, update: fixed problem where setting state the stream needed to be set back to position 0 before calling setState]

unit UndoRedoState;
{
  Author William Egge
         egge@eggcentric.com
         http://www.eggcentric.com
}

interface
uses
  _State, Classes, SysUtils;

// A value of 0 for MaxMemoryUsage means unlimited (default).
type
  TUndoRedoState = class
  private
    FState: IState;
    FUndoRedoList: TList;
    FModifyCount: Integer;
    FUndoPos: Integer;
    FTailState: TStream;
    FMaxMemoryUsage: LongWord;
    FCurrMemUsage: LongWord;
    function CreateCurrentState: TStream;
    procedure SetMaxMemoryUsage(const Value: LongWord);
    procedure TruncToMem;
  public
    constructor Create(AState: IState);
    property MaxMemoryUsage: LongWord read FMaxMemoryUsage write SetMaxMemoryUsage;
    procedure BeginModify;
    procedure EndModify;
    procedure Undo;
    procedure Redo;
    destructor Destroy; override;
  end;

implementation

{ TUndoRedoState }

procedure TUndoRedoState.BeginModify;
var
  I: Integer;
  S: TStream;
begin
  Inc(FModifyCount);
  if FModifyCount = 1 then
  begin
    for I := FUndoRedoList.Count - 1 downto FUndoPos + 1 do
    begin
      S := FUndoRedoList[I];
      Dec(FCurrMemUsage, S.Size);
      FUndoRedoList.Delete(I);
      S.Free;
    end;
    S := CreateCurrentState;
    Inc(FCurrMemUsage, S.Size);
    FUndoRedoList.Add(S);
    FUndoPos := FUndoRedoList.Count - 1;
    if FTailState <> nil then
    begin
      Dec(FCurrMemUsage, FTailState.Size);
      FreeAndNil(FTailState);
    end;
    TruncToMem;
  end;
end;

constructor TUndoRedoState.Create(AState: IState);
begin
  Assert(AState <> nil, 'AState should not be nil for '
    + '"TUndoRedoState.Create(AState: IState)"');

  inherited Create;
  FState := AState;
  FUndoRedoList := TList.Create;
  FUndoPos := -1;
end;

function TUndoRedoState.CreateCurrentState: TStream;
begin
  Result := TMemoryStream.Create;
  try
    FState.GetState(Result);
  except
    Result.Free;
    raise;
  end;
end;

destructor TUndoRedoState.Destroy;
var
  I: Integer;
begin
  FState := nil;
  for I := 0 to FUndoRedoList.Count - 1 do
    TObject(FUndoRedoList[I]).Free;

  FTailState.Free;

  inherited Destroy;
end;

procedure TUndoRedoState.EndModify;
begin
  Assert(FModifyCount > 0, 'TUndoRedoState.EndModify: EndModify was called '
    + 'more times than BeginModify');

  Dec(FModifyCount);
end;

procedure TUndoRedoState.Redo;
var
  FRedoPos: Integer;
  S: TStream;
begin
  Assert(FModifyCount = 0, 'TUndoRedoState.Redo: should not be called while '
    + 'modifying');

  if (FUndoRedoList.Count > 0) and (FUndoPos < (FUndoRedoList.Count - 1)) then
  begin
    FRedoPos := FUndoPos + 2;
    if FRedoPos > (FUndoRedoList.Count - 1) then
    begin
      FTailState.Position := 0;
      FState.SetState(FTailState);
      Dec(FCurrMemUsage, FTailState.Size);
      FreeAndNil(FTailState);
    end
    else
    begin
      S := FUndoRedoList[FRedoPos];
      S.Position := 0;
      FState.SetState(S);
    end;
    Inc(FUndoPos);
  end;
end;

procedure TUndoRedoState.SetMaxMemoryUsage(const Value: LongWord);
begin
  FMaxMemoryUsage := Value;
end;

procedure TUndoRedoState.TruncToMem;
var
  S: TStream;
begin
  if (FMaxMemoryUsage > 0) and (FCurrMemUsage > FMaxMemoryUsage) then
  begin
    while (FUndoRedoList.Count > 0) and (FCurrMemUsage > FMaxMemoryUsage) do
    begin
      S := FUndoRedoList[0];
      FUndoRedoList.Delete(0);
      Dec(FCurrMemUsage, S.Size);
      Dec(FUndoPos);
      S.Free;
    end;

    if (FUndoRedoList.Count = 0) and (FCurrMemUsage > FMaxMemoryUsage) then
      if FTailState <> nil then
      begin
        Dec(FCurrMemUsage, FTailState.Size);
        FreeAndNil(FTailState);
      end;
  end;
end;

procedure TUndoRedoState.Undo;
var
  S: TStream;
begin
  Assert(FModifyCount = 0, 'TUndoRedoState.Undo: should not be called while '
    + 'modifying');

  if FUndoPos >= 0 then
  begin
    if FUndoPos = (FUndoRedoList.Count - 1) then
    begin
      FTailState := CreateCurrentState;
      Inc(FCurrMemUsage, FTailState.Size);
    end;
    S := FUndoRedoList[FUndoPos];
    S.Position := 0;
    Dec(FUndoPos);
    FState.SetState(S);
    TruncToMem;
  end;
end;

end.


Component Download: http://www.eggcentric.com/UndoRedoState.zip