unit PriorQC;
//*******************************************************
// Linked list-based priority 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];
    PPriorityQCell = ^TPriorityQCell;
    TPriorityQCell = record
        Value    : String10;       // The data.
        Priority : Longint;        // The item's priority.
        NextCell : PPriorityQCell; // The next cell.
    end;

    // The priority queue class.
    TPriorityQueue = class(TObject)
        private
            TopSentinel    : TPriorityQCell; // The top sentinel (not a pointer).
            BottomSentinel : TPriorityQCell; // The bottom sentinel (not a pointer).

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

implementation

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

    // Point the top sentinel at the bottom sentinel.
    TopSentinel.NextCell := @BottomSentinel;

    // Give BottomSentinel the smallest priority.
    BottomSentinel.Priority := -2147483647;
end;

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

// Add an item to the queue.
procedure TPriorityQueue.EnterQueue(new_value : String10; new_priority : Longint);
var
    new_cell, cell_ptr, next_cell : PPriorityQCell;
begin
    // Create the new cell.
    New(new_cell);
    new_cell^.Value := new_value;
    new_cell^.Priority := new_priority;

    // See where the new cell belongs.
    cell_ptr := @TopSentinel;
    next_cell := cell_ptr^.NextCell;
    while (next_cell^.Priority > new_priority) do
    begin
        cell_ptr := next_cell;
        next_cell := cell_ptr^.NextCell;
    end;

    // Insert the new cell.
    cell_ptr^.NextCell := new_cell;
    new_cell^.NextCell := next_cell;
end;

// Remove the first item from the queue.
function TPriorityQueue.LeaveQueue : String10;
var
    target : PPriorityQCell;
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;

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

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

// Return a string representing all of the queue's entries.
function TPriorityQueue.TextValue : String;
const
    CR = #13#10;
var
    cell_ptr : PPriorityQCell;
begin
    Result := '';
    cell_ptr := TopSentinel.NextCell;
    while (cell_ptr <> @BottomSentinel) do
    begin
        Result := Result + Format('%s (%d)' + CR,
            [cell_ptr^.Value, cell_ptr^.Priority]);
        cell_ptr := cell_ptr^.NextCell;
    end;
end;

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

end.
