% File "pq.tu".
%
%
%       This file defines a priority queue module as in the textbook, but
% with the following adaptation: the declaration of "elementType" has
% been altered so as to make this a generic queue.  Now elements of
% ^anyclass are stored on the queue.  (see pages 293-295 of BHH)


unit
class PriorityQueue

    export Init, Finalize, Arrive, Leave, InspectFront,
        Length, IsEmpty, IsFull



    % Instance variables (and related types)
    %-------------------

    type elementType : ^anyclass
    type prtyType : int

    type node :
        record
            element : elementType
            prty : prtyType
            next : ^node
        end record

    var front : ^node
    var count : int


    % Initialize
    %----------------------------------------------------------------
    % Initialize the priority queue so it can be used. Make it to be empty.

    procedure Init
        front := nil
        count := 0
    end Init


    % Finalize
    %----------------------------------------------------------------
    % Clear the priority queue, freeing any space allocated for its elements.

    procedure Finalize
        % Free space for all nodes in the linked list.
        loop
            exit when front = nil
            var p : ^node := front
            front := p -> next
            free p
        end loop
    end Finalize


    % Arrive
    %----------------------------------------------------------------
    % Insert element with its priority prty into the priority
    % queue.

    procedure Arrive (element : elementType, prty : prtyType)

        var p : ^node
        new p
        assert p not= nil % Queue must not overflow.

        p -> element := element
        p -> prty := prty

        if front = nil or prty < front -> prty then
            % It goes in front.
            p -> next := front
            front := p
        else
            % Find out where it goes and stick it there.
            var prev : ^node := front
            var where : ^node

            loop % Find where to insert this element.
                where := prev -> next
                exit when where = nil or prty < where -> prty
                prev := where
            end loop
            prev -> next := p
            p -> next := where
        end if

        count += 1
    end Arrive


    % Leave
    %----------------------------------------------------------------
    % Remove element from the front of the priority queue.
    % This will be the element with the lowest priority value in
    % the queue.
    % (and the one longest in the queue at that priority).
    % The priority queue must not be empty.

    procedure Leave (var element : elementType, var prty : prtyType)
        pre front not= nil

        element := front -> element
        prty := front -> prty
        var p : ^node := front
        front := p -> next
        free p

        count -= 1
    end Leave


    % InspectFront
    %----------------------------------------------------------------
    % Return element from front of priority queue, without
    % changing the priority queue. The queue must not be empty.

    function InspectFront : elementType
        pre front not= nil

        result front -> element
    end InspectFront


    % Length
    %----------------------------------------------------------------
    % Return number of elements in priority queue.

    function Length : int
        result count
    end Length


    % IsEmpty
    %----------------------------------------------------------------
    % Return true if the priority queue contains no elements.

    function IsEmpty : boolean
        result front = nil
    end IsEmpty


    % IsFull
    %----------------------------------------------------------------
    % Return true if the priority queue cannot hold any more elements.

    function IsFull : boolean
        var p : ^node
        new p
        if p = nil then
            result true
        else
            free p
            result false
        end if
    end IsFull

end PriorityQueue