% File "queue.tu".
% The module CarQueue maintains a queue of cars.

unit
module CarQueue

    import Car in "car.tu"
    export enqueue, dequeue, isEmpty, isFull, printQueue


    % By defining elementType, we can avoid referring specifically to
    % carType throughout the module.  However, a few car-specific
    % things do appear in the module, preventing it from being an
    % implemenation of a general queue.
    type elementType : Car.carType


    % Implementation: a "circular" array.

    % The capacity of the queue is determined by an input parameter.
    put "Enter maximum number of elements the queue can hold: " ..
    var maxLength : int
    get maxLength
    put maxLength

    % The queue elements are stored from position head up to position tail
    % in the array (eg, position 1 up to position 4).  The front of the
    % queue is at position head; the rear at position tail.  If head and
    % tail are equal, there must be one element in the queue.  As elements
    % are added to and taken out of the queue, the head and tail positions
    % advance through the array (eg head could be at position 3 and tail at
    % position 7).  If the tail hits the end of the array, we "wrap around",
    % that is, the next entry is added at the beginning.  We can thus view
    % the array as circular.
    %     If tail is one position before head (eg tail is at 14 and head is
    % at 15), then either the queue is full, or it's empty -- the two
    % conditions look the same, but the variable size distinguishes them.
    var queue : array 1 .. maxLength of elementType
    var head : int := 1
    var tail : int := maxLength
    var size : int := 0



    % enqueue
    %----------------------------------------------------------------
    % Add element newElement to the end of the queue.  Return true
    % if successful, false otherwise.  (Failure occurs if the array
    % is already full.)

    function enqueue (newElement : elementType) : boolean

        % If the array is full, we can't add the new element.
        if size = maxLength then
            result false
        else
            % Increase the tail position, but wrap around if necessary.
            tail += 1
            if tail > maxLength then
                tail := 1
            end if

            % Insert the new element at the tail of the queue, and update
            % the queue's size.
            queue (tail) := newElement
            size += 1
            result true
        end if

    end enqueue



    % dequeue
    %----------------------------------------------------------------
    % Remove the first element from the front of the queue and
    % return it.
    % Precondition: isEmpty must not be true.

    function dequeue : elementType

        % Extract the element at the head of the queue, to be returned.
        var res : elementType
        res := queue (head)

        % Increase the head position by 1 and wrap around if necessary.
        head += 1
        if head > maxLength then
            head := 1
        end if

        % Update the queue's size and return the extracted element.
        size -= 1
        result res

    end dequeue



    % isEmpty
    %----------------------------------------------------------------
    % Return true iff the queue is empty.

    function isEmpty : boolean
        result size = 0
    end isEmpty



    % isFull
    %----------------------------------------------------------------
    % Return true iff the queue is full.

    function isFull : boolean
        result size = maxLength
    end isFull



    % clear
    %----------------------------------------------------------------
    % Initialize the queue to be empty.

    proc clear
        head := 1
        tail := maxLength
        size := 0
    end clear



    % printQueue
    %----------------------------------------------------------------
    % Print all elements of the queue, each on a separate line, prefixed
    % by the given string.
    %     This subprogram is specific to car queues (rather than general
    % queues) because it must use a subprogram from the car module
    % for specifically printing cars.

    procedure printQueue (prefix : string)

        % Only if the queue is not empty do we have some printing to do.
        if size not= 0 then

            % Start at the head of the queue.
            var i : int := head

            loop
                % Print the next element.
                Car.printCar (prefix, queue (i))
                put ""

                % If this was the last queue element, then stop.
                exit when i = tail

                % Otherwise, advance to the next queue element, wrapping
                % around if necessary.
                i += 1
                if i > maxLength then
                    i := 1
                end if
            end loop

        end if

    end printQueue

end CarQueue