%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Solution to A3: A Card Trick,  CSC148H, Summer96
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%-----------------------------------------------------------------------
% Trick module
%     written by Phil Edmonds, Jun 19,1996
%
% This module stores and manipulates the cards involved in the trick.
%
% Data Structure:  lists of cards are stored as queues implemented by
%   linked lists.  The 21-card deck is a single queue.  When they
%   are laid out in 3 columns, the cards are transfered into three queues,
%   one for each column.  These three queues are stored as an array of
%   queues
%
%
% Imports:  it requires the DeckOfCards module and the Graphics module
%
% Exports:
%     Init        - initializes the data structures
%     SetUp       - initializes and shuffles a full deck of cards and
%                   deals 21 cards into the trick deck
%     LayOut      - lays out the cards in 3 columns
%     PickUp      - picks up the cards with specified column in middle
%     FindCard    - returns the card in the specified position of the deck
%
% Private Operations:
%     qInit, qArrive, qLeave, qJoin - operations for manipulating queues
%
%------------------------------------------------------------------------

unit
module Trick

    import DeckOfCards in "deck.t", Graphics in "graphics.t"
    export Init, LayOut, SetUp, PickUp, FindCard

    const NUM_OF_COLS := 3
    const COL_SIZE := 7

    type cardNode :
        record
            card : DeckOfCards.cardType
            next : ^cardNode
        end record

    type cardQueue :
        record
            front, rear : ^cardNode
            count : int
        end record

    % The set of cards is kept either in layout or in deck.  It is shifted
    % from the deck to the layout by LayOut and shifted back to the deck by
    % PickUp
    %
    var trickLayout : array 1 .. NUM_OF_COLS of cardQueue
    var trickDeck : cardQueue

    %-------------------------------------------------------------------
    % PRIVATE OPERATIONS
    %  The queue is based on the code from Barnard, Holt, and Hume
    %

    %----------------------
    % initialize the queue
    %
    proc qInit (var q : cardQueue)

        q.front := nil
        q.rear := nil

    end qInit

    %------------------------
    % Arrive
    %
    proc qArrive (var q : cardQueue, card : DeckOfCards.cardType)

        % create the new node
        var p : ^cardNode
        new p
        assert p not= nil
        p -> card := card
        p -> next := nil

        % if queue is empty, then item goes at the front
        if q.front = nil then
            q.front := p
            q.rear := p
        else % otherwise it goes at the end
            q.rear -> next := p
            q.rear := p
        end if

    end qArrive

    %--------------------------
    % Leave
    %
    proc qLeave (var q : cardQueue, var card : DeckOfCards.cardType)

        pre q.front not= nil

        % get front element
        card := q.front -> card

        % destroy front element
        var p : ^cardNode := q.front
        q.front := p -> next
        free p

    end qLeave

    %---------------------------
    % Join
    %
    proc qJoin (var q1 : cardQueue, q2 : cardQueue, var joined :
            cardQueue)

        % if the first queue is empty, or both queues are empty
        if q1.front = nil then
            joined.front := q2.front
            joined.rear := q2.rear

            % if only the second queue is empty
        elsif q2.front = nil then
            joined.front := q1.front
            joined.rear := q1.rear

            % if both queues are not empty
        else
            q1.rear -> next := q2.front
            joined.front := q1.front
            joined.rear := q2.rear
        end if

    end qJoin

    %-------------------------------------------------------------------
    % PUBLIC OPERATIONS
    %

    %-----------------------
    % initialize the objects.
    %
    proc Init ()
        for col : 1 .. NUM_OF_COLS
            qInit (trickLayout (col))
        end for
        qInit (trickDeck)
    end Init

    %------------------
    % deal 21 cards into the trick deck
    %
    proc SetUp ()
        DeckOfCards.Init
        DeckOfCards.Shuffle
        for i : 1 .. NUM_OF_COLS * COL_SIZE
            qArrive (trickDeck, DeckOfCards.DealCard ())
        end for
    end SetUp

    %-------------------------
    % lay out the cards in the grid
    %   divides the cards in deck among the three columns
    %
    proc LayOut ()

        var card : DeckOfCards.cardType

        %initialize the layout
        for col : 1 .. NUM_OF_COLS
            qInit (trickLayout (col))
        end for

        %go across columns to display the cards
        for row : 1 .. COL_SIZE
            for col : 1 .. NUM_OF_COLS
                % take card out of the deck and put it in a column
                qLeave (trickDeck, card)
                qArrive (trickLayout (col), card)

                % display the card
                var where : Graphics.coord
                where.x := (col - 1) * (maxx div 6) + 200
                where.y := maxy - row * 30 + 5
                DeckOfCards.DisplayCard (card, where)
            end for
        end for
    end LayOut

    %-----------------------
    % pickup the cards
    %   gathers the cards by joining the three columbns with the 'center'
    %   column sandwiched between the others.
    %
    proc PickUp (center : int)

        var temp : cardQueue
        var left := (center - 2) mod 3 + 1
        var right := (center) mod 3 + 1

        qInit (trickDeck)

        % join left and center
        qJoin (trickLayout (left), trickLayout (center), temp)
        % join this to the right
        qJoin (temp, trickLayout (right), trickDeck)

    end PickUp

    %------------------------------
    % find a desired card in the deck
    %
    function FindCard (cardNumber : int) : DeckOfCards.cardType

        var card : DeckOfCards.cardType
        var p : ^cardNode := trickDeck.front
        var count : int := 0

        loop
            exit when p = nil or count = cardNumber
            card := p -> card
            p := p -> next
            count += 1
        end loop
        result card
    end FindCard


end Trick