Generic queues

If you have read the previous post, discusses generic Linked List, in this post I will present you generic queues.

In the chess game, the board is stored in a LIFO<TBoard> queue, so you can play deeper and deeper and easily undo/redo the board state.

It can be found in BB.Collection.Queue

Interface:

TQueue<T> = abstract class(TInterfacedObject, IStack<T>)
  private
    FItems: TLinkedList<T>;
    FCapacity: cardinal;

    function DoPush(aItem: T): integer;
  protected
    procedure QueueEmpty;
    procedure SetCapacity(aValue: cardinal); virtual;
    function IsFull: boolean;
    function Last(out aItem: T): boolean;
    function First(out aItem: T): boolean;
  public
    constructor Create; overload; virtual;
    constructor Create(aCapacity: integer); overload;
    destructor Destroy; override;
    function Push(aItem: T): integer; overload; virtual;
    function Pop: T; virtual; abstract;
    function TryPop(out aItem: T): boolean;
    procedure Clear;
    function IsEmpty: boolean; inline;
    function Count: integer; inline;
    function Extract(aIndex: integer): T;
    procedure Remove(aItem: T);

    property Capacity: cardinal read FCapacity write SetCapacity;
  end;

  TLIFO<T> = class(TQueue<T>)
  public
    constructor Create; override;
    function Pop: T; override;
  end;

  TFIFO<T> = class(TQueue<T>)
  public
    constructor Create; override;
    function Pop: T; override;
  end;

  TCircularQueue<T> = class(TQueue<T>)
  public
    function Push(aItem: T): integer; override;
  end;

Again nothing special, the classes inherit from abstract class TQueue<T> and internally they use Linked List for storing the data.

Implementation:

{ TQueue }

procedure TQueue<T>.Clear;
begin
  FItems.Clear;
end;

function TQueue<T>.Count: integer;
begin
  result := FItems.Count;
end;

constructor TQueue<T>.Create(aCapacity: integer);
begin
  Create;
  FCapacity := aCapacity;
end;

constructor TQueue<T>.Create;
begin
  inherited Create;

  FItems := TLinkedList<T>.Create;
  FCapacity := INFINITE;
end;

destructor TQueue<T>.Destroy;
begin
  FItems.Free;

  inherited;
end;

function TQueue<T>.Extract(aIndex: integer): T;
begin
  result := FItems[aIndex];
  FItems.Delete(result);
end;

function TQueue<T>.First(out aItem: T): boolean;
begin
  result := FItems.First;
  if result then
    aItem := FItems.GetCurrent;
end;

function TQueue<T>.IsEmpty: boolean;
begin
  result := Count = 0;
end;

procedure TQueue<T>.QueueEmpty;
begin
  raise Exception.Create('Queue empty');
end;

procedure TQueue<T>.Remove(aItem: T);
begin
  FItems.Delete(aItem);
end;

function TQueue<T>.DoPush(aItem: T): integer;
begin
  FItems.Add(aItem);
  result := Count - 1;
end;

function TQueue<T>.IsFull: boolean;
begin
  result := cardinal(Count) >= FCapacity;
end;

function TQueue<T>.Last(out aItem: T): boolean;
begin
  result := FItems.Last;
  if result then
    aItem := FItems.GetCurrent;
end;

function TQueue<T>.Push(aItem: T): integer;
begin
  if IsFull then
    raise Exception.Create('The stack has reach its limit');
  result := DoPush(aItem);
end;

procedure TQueue<T>.SetCapacity(aValue: cardinal);
begin
  FCapacity := aValue;
end;

function TQueue<T>.TryPop(out aItem: T): boolean;
begin
  result := Count > 0;
  if result then
    aItem := Pop;
end;

{ TLIFO }

constructor TLIFO<T>.Create;
begin
  inherited;

  FItems.SearchType := stFromLast;
end;

function TLIFO<T>.Pop: T;
begin
  if not Last(result) then
    QueueEmpty;

  Remove(result);
end;

{ TFIFO }

constructor TFIFO<T>.Create;
begin
  inherited;

  FItems.SearchType := stFromFirst;
end;

function TFIFO<T>.Pop: T;
begin
  if not First(result) then
    QueueEmpty;

  Remove(result);
end;

{ TCircularQueue }

function TCircularQueue<T>.Push(aItem: T): integer;
begin
  if IsFull then
    Pop;
  result := DoPush(aItem);
end;

end.