unit HeadedQC;
//*******************************************************
// Linked 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 customer record.
    TCustomer = record
        TimeNeeded, WaitStart, WaitEnd : Longint;
        Id                             : Integer;
    end;
    PCustomer = ^TCustomer;

    // The linked list cells.
    PMultiQCell = ^TMultiQCell;
    TMultiQCell = record
        Customer : PCustomer;   // Pointer to customer data.
        NextCell : PMultiQCell; // The next cell.
        PrevCell : PMultiQCell; // The previous cell.
    end;

    // The linked queue class.
    TMultiQueue = class(TObject)
        private
            TopSentinel    : TMultiQCell; // The top sentinel (not a pointer).
            BottomSentinel : TMultiQCell; // The bottom sentinel (not a pointer).
            NumItems       : Integer;     // For convenience.

        public
            constructor Create;
            destructor Destroy; override;
            procedure EnterQueue(new_cust : PCustomer);
            function LeaveQueue : PCustomer;
            function QueueEmpty : Boolean;
            function TextValue : String;
            procedure ClearQueue;
            function Count : Integer;
    end;

implementation

// Initialize the sentinels to point to each other.
constructor TMultiQueue.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 TMultiQueue.Destroy;
begin
    ClearQueue;
    inherited Destroy;
end;

// Add an item to the queue.
procedure TMultiQueue.EnterQueue(new_cust : PCustomer);
var
    new_cell : PMultiQCell;
begin
    // Create the new cell.
    New(new_cell);
    new_cell^.Customer := new_cust;

    // 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;

    NumItems := NumItems + 1;
end;

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

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

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

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

    NumItems := NumItems - 1;
end;

// Return true if the queue is empty.
function TMultiQueue.QueueEmpty : Boolean;
begin
    QueueEmpty := (Count < 1);
end;

// Return a string representing all of the queue's entries.
function TMultiQueue.TextValue : String;
var
    cell_ptr : PMultiQCell;
begin
    Result := '';
    cell_ptr := TopSentinel.NextCell;
    while (cell_ptr <> @BottomSentinel) do
    begin
        Result := Result +
            IntToStr(cell_ptr^.Customer^.Id) + ' ';
        cell_ptr := cell_ptr^.NextCell;
    end;
end;

// Empty the queue.
// This includes disposing of customer records.
procedure TMultiQueue.ClearQueue;
begin
    while (not QueueEmpty) do Dispose(LeaveQueue);
end;

function TMultiQueue.Count : Integer;
begin
    Count := NumItems;
end;

end.
