unit LinkedQC;
//*******************************************************
// List-based queue class.
//*******************************************************
// Copyright (C) 1998 John Wiley & Sons, Inc.
// All rights reserved. See additional copyright
// information in Readme.txt.
//*******************************************************

interface

uses
    Dialogs, SysUtils, Classes;

type
    // The linked list cells.
    String10 = String[10];
    PLinkedQCell = ^TLinkedQCell;
    TLinkedQCell = record
        Value    : String10;     // The data.
        NextCell : PLinkedQCell; // The next cell.
        PrevCell : PLinkedQCell; // The previous cell.
    end;

    // The linked queue class.
    TLinkedQueue = class(TObject)
        private
            TopSentinel    : TLinkedQCell; // The top sentinel (not a pointer).
            BottomSentinel : TLinkedQCell; // The bottom sentinel (not a pointer).

        public
            constructor Create;
            destructor Destroy; override;
            procedure EnterQueue(new_value : String10);
            function LeaveQueue : String10;
            function QueueEmpty : Boolean;
            function TextValue : String;
            procedure EmptyQueue;
    end;

implementation

// Initialize the sentinels to point to each other.
constructor TLinkedQueue.Create;
begin
    // Allocate memory and perform inherited initialization.
    inherited Create;

    // Point the sentinels at each other.
    TopSentinel.NextCell := @BottomSentinel;
    BottomSentinel.PrevCell := @TopSentinel;
end;

// Free any allocated memory.
destructor TLinkedQueue.Destroy;
begin
    EmptyQueue;
    inherited Destroy;
end;

// Add an item to the queue.
procedure TLinkedQueue.EnterQueue(new_value : String10);
var
    new_cell : PLinkedQCell;
begin
    // Create the new cell.
    New(new_cell);
    new_cell^.Value := new_value;

    // Insert the cell at the end of the queue.
    new_cell^.NextCell := @BottomSentinel;
    new_cell^.PrevCell := BottomSentinel.PrevCell;
    BottomSentinel.PrevCell^.NextCell := new_cell;
    BottomSentinel.PrevCell := new_cell;
end;

// Remove the first item from the queue.
function TLinkedQueue.LeaveQueue : String10;
var
    target : PLinkedQCell;
begin
    if (QueueEmpty) then
        raise EInvalidOperation.Create(
            'The queue is empty.');

    // Save the return value.
    target := TopSentinel.NextCell;
    LeaveQueue := target^.Value;

    // Remove the first cell from the queue.
    TopSentinel.NextCell := target^.NextCell;
    target^.NextCell^.PrevCell := @TopSentinel;

    // Free the target cell's memory.
    Dispose(target);
end;

// Return true if the queue is empty.
function TLinkedQueue.QueueEmpty : Boolean;
begin
    QueueEmpty :=
        (TopSentinel.NextCell = @BottomSentinel);
end;

// Return a string representing all of the queue's entries.
function TLinkedQueue.TextValue : String;
const
    CR = #13#10;
var
    cell_ptr : PLinkedQCell;
begin
    Result := '';
    cell_ptr := TopSentinel.NextCell;
    while (cell_ptr <> @BottomSentinel) do
    begin
        Result := Result + cell_ptr^.Value + CR;
        cell_ptr := cell_ptr^.NextCell;
    end;
end;

// Remove all items from the queue.
procedure TLinkedQueue.EmptyQueue;
var
    target : PLinkedQCell;
begin
    while (TopSentinel.NextCell <> @BottomSentinel) do
    begin
        target := TopSentinel.NextCell;
        TopSentinel.NextCell := target^.NextCell;
        Dispose(target);
    end;
end;

end.
