sandque.pas

来自「模拟2维沙堆效果」· PAS 代码 · 共 134 行

unit SandQue;
// A generic queue, used to store sand grains

interface

type
  PQueueElem = ^TQueueElem;  // Generic element holding user item
  TQueueElem = record
    Item: Pointer;           // The stored user-defined item
    Next: PQueueElem;        // Next element
  end;

  TQueue = class
  public
    Size: Longint;   // We want to be able to store a LOT of grains
    constructor Create;
    destructor Destroy; override;
    procedure Enqueue(Itm: Pointer);
    function Dequeue(var Itm: Pointer): Boolean;
    function Peek(Idx: Word; var Itm: Pointer): Boolean;
  private
    Top, Bottom, Current: PQueueElem;
    Position: Word;
  end;

implementation

{----------------------- TQueue -----------------------}

constructor TQueue.Create;
begin
  inherited Create;
  Size := 0;                 // Queue is empty
  Position := 0;
  Top := nil;
  Bottom := nil;
  Current := nil;
end;


destructor TQueue.Destroy;
var
  Itm: Pointer;
begin
  { Remove any remaining elements before destroying the queue.
    Note that user items are NOT disposed as TQueue doesn't know their
    types. Therefore user should always empty the queue himself and
    dispose the items before destroying the queue. }
  while Size > 0 do
    Dequeue(Itm);
  inherited Destroy;
end;


procedure TQueue.Enqueue(Itm: Pointer);
var
  P: PQueueElem;             // We need a record for the user item
begin
  New(P);
  P^.Item := Itm;
  P^.Next := nil;
  if Size = 0 then
  begin
    Top := P;
    Bottom := P;
    Current := P;
  end;
  Bottom^.Next := P;
  Bottom := P;
  Inc(Position);
  Inc(Size);
end;


function TQueue.Dequeue(var Itm: Pointer): Boolean;
var
  P: PQueueElem;
begin
  Dequeue := False;
  if Size > 0 then           // Same as: if Top <> NIL
  begin
    Itm := Top^.Item;
    P := Top;
    Top := Top^.Next;
    if Current = Itm then
    begin
      Current := Top;
      if Top = nil then
        Position := 0
      else
        Position := 1;
    end
    else
      Dec(Position);
    Dispose(P);
    Dec(Size);
    Dequeue := True;
  end;
end;


function TQueue.Peek(Idx: Word; var Itm: Pointer): Boolean;
var
  P: PQueueElem;
  I: Word;
begin
  Itm := nil;
  Peek := False;

  if Idx <= Size then        // Does the element exist?
  begin
    if Position <= Idx then
    begin
      P := Current;          // Traverse from current position
      for I := 1 to Idx-Position do
        P := P^.Next;
    end
    else
    begin
      P := Top;              // Traverse from start
      for I := 1 to Idx-1 do
        P := P^.Next;
    end;

    Itm := P^.Item;
    Current := P;
    Position := Idx;
    Peek := True;
  end;
end;

end.