Delphi - TStack Capacity confusion

Question

I have been working with TStack to try and implement a simple Undo/Redo feature in my program. The thought behind this is that as an action is performed the current state of the program is saved - i.e. pushed to the stack. When the user clicks undo the last state of the program is reloaded - i.e. popped from the stack.

The flaw in this idea is that the stack cannot go on growing forever meaning that after a capacity value is reached, the oldest items (those at the bottom of the stack) should be removed as new items are pushed on top.

The TStack object in Delphi contains a Capacity property which I assumed would automatically perform this 'clean-up' but when I overload the stack (e.g. push 11 items to one with capcity 10) the capacity updates to accomodate for more items.

Can anyone offer me any advice on how to use TStack more effectively in this instance? I understand that an alternative would be to use an array structure but I like the prospective ease of using stacks.

Regards

Answer 1

In reality the TStack is powered by a dynamic array.
If you really wanted to you could abuse this fact to have the stack remove items from the bottom, but now you'd be fighting the stack.

I think it's a better idea just to use a circular list.

A simple design might work like this.

type
  TCircularList<T> = class(TObject);
  private
    FStorage: TList<T>;
    FCapacity: cardinal;  //duplication for performance reasons
    FCurrentIndex: cardinal;
  protected
    function GetItem(index: cardinal): T;
    procedure SetItem(index: cardinal; const Value: T);
  public
    constructor Create(Size: cardinal = 10);
    destructor Destroy; override;
    procedure Add(const Item: T);
    property Items[index: cardinal]: T read GetItem write SetItem; default;
  end;

constructor TCircularList<T>.Create(Size: cardinal = 10);
begin
  inherited Create;
  Assert(Size >= 2);
  FStorage:= TList<T>.Create;
  FCapacity:= Size;
  FStorage.Capacity:= Size;
end;

destructor TCircularList<T>.Destroy;
begin
  FStorage.Free;
  inherited;
end;

procedure TCircularList<T>.Add(const Item: T);
begin
  FCurrentIndex:= (FCurrentIndex + 1) mod FCapacity;
  FStorage[FCurrentIndex]:= Item;
end;

function TCircularList<T>.GetItem(index: cardinal): T;
var
  cIndex: cardinal;
begin
  cIndex:= Index mod FCapacity;
  Result:= FStorage[index]; 
end;

procedure TCircularList<T>.SetItem(index: cardinal; const Value: T);
var
  cIndex: cardinal;
begin
  cIndex:= index mod FCapacity;
  FStorage[index]:= Value;
end;

Obviously you'd need a few more methods like a last and delete method, but I leave that up to you, you should be able to extrapolate from here.

Usability remarks
I have to say that from a UX perspective I think the idea of an undo/redo function sucks.
Why not have a list of snapshots, you that you can go backwards and forwards in time, much like the situation would be if you saved a number of backup files on disk.
The undo function requires you to memorize exactly what you've done the last x steps which does not scale very well.
I also don't understand why there must be a limit, why not allow as much undo/snapshots as memory/disk space permits?