program TestQueue;
{$mode objfpc}{$H+}
type
TQueue = class(TObject)
private
FGrow: Integer;
FHeadIndex: Integer;
FQueue: array of Integer;
FTailIndex: Integer;
function GetPeekHead: Integer;
function GetCount: Integer;
function GetPeekTail: Integer;
public
constructor Create(anInitialGrow: Integer=16);
function IsEmpty: Boolean;
function LeaveOK(out UnQueuedValue: Integer): Boolean;
procedure Join(JoiningValue: Integer);
procedure Report;
property Count: Integer read GetCount;
property PeekHead: Integer read GetPeekHead;
property PeekTail: Integer read GetPeekTail;
end;
function TQueue.GetPeekHead: Integer;
begin
if IsEmpty then
Result := -MaxInt
else Result := FQueue[FHeadIndex];
end;
function TQueue.GetCount: Integer;
begin
case FHeadIndex of
-1: Result := 0;
else Result := Succ(FTailIndex - FHeadIndex);
end;
end;
function TQueue.GetPeekTail: Integer;
begin
if IsEmpty then
Result := -MaxInt
else Result := FQueue[FTailIndex];
end;
constructor TQueue.Create(anInitialGrow: Integer);
begin
Assert(anInitialGrow<>0, 'TQueue.Create: capacity must be greater than zero');
FGrow := anInitialGrow;
SetLength(FQueue, anInitialGrow);
FHeadIndex := -1;
FTailIndex := FHeadIndex;
end;
procedure TQueue.Join(JoiningValue: Integer);
begin
case IsEmpty of
True: begin
FTailIndex := 0;
FHeadIndex := 0;
FQueue[FTailIndex] := JoiningValue;
end;
False: begin
if FTailIndex >= High(FQueue) then
SetLength(FQueue, Length(FQueue) + FGrow);
Inc(FTailIndex);
FQueue[FTailIndex] := JoiningValue;
end;
end;
end;
procedure TQueue.Report;
begin
case IsEmpty of
True: Writeln('Empty queue');
False: WriteLn('Count=',Count,' PeekHead=',PeekHead,' PeekTail=',PeekTail);
end;
end;
function TQueue.LeaveOK(out UnQueuedValue: Integer): Boolean;
begin
case IsEmpty of
True: begin
UnQueuedValue := -MaxInt;
Result := False;
end;
False: begin
UnQueuedValue := FQueue[FHeadIndex];
Inc(FHeadIndex);
if Count = 0 then
begin
FHeadIndex := -1;
FTailIndex := FHeadIndex;
if Length(FQueue) <> FGrow then
SetLength(FQueue, FGrow);
end;
Result := True;
end;
end;
end;
function TQueue.IsEmpty: Boolean;
begin
Result := (FHeadIndex = -1) and (FHeadIndex = FTailIndex);
end;
var
q: TQueue;
i, j, k, l, m, n, o, p: Integer;
canLeave: Boolean;
begin
q := TQueue.Create;
with q do
begin
Join(79);
Join(3);
LeaveOK(i);
Join(92);
Join(-40);
Join(100);
LeaveOK(j);
Join(1);
Report;
LeaveOK(k);
LeaveOK(l);
leaveOK(m);
Join(-2);
LeaveOK(n);
WriteLn('i=',i,' j=',j,' k=',k,' l=',l,' m=',m,' n=',n);
WriteLn('q.Count=',q.Count,' isEmpty is ',q.IsEmpty,' peekhead=',q.PeekHead,' peektail=',q.PeekTail);
LeaveOK(o);
canLeave := LeaveOK(p);
WriteLn('o=',o,' canLeave is ',canLeave,' isEmpty is ',q.IsEmpty);
Free;
end;
ReadLn;
end.