//--------------------------------------------------------------------
//
//  Laboratory 6                                        queuearr.cpp
//
//  SOLUTION: Array implementation of the Queue ADT
//
//--------------------------------------------------------------------

#include <assert.h>
#include "queuearr.h"

//--------------------------------------------------------------------

template < class QE >
Queue<QE>:: Queue ( int maxNumber )

// Creates an empty queue. Allocates enough memory for maxNumber
// elements (defaults to defMaxQueueSize).

  : maxSize(maxNumber),
    front(-1),
    rear(-1)
{
    element = new QE [ maxSize ];
    assert ( element != 0 );
}

//--------------------------------------------------------------------

template < class QE >
Queue<QE>:: ~Queue ()

// Frees the memory used by a queue.

{
    delete [] element;
}

//--------------------------------------------------------------------

template < class QE >
void Queue<QE>:: enqueue ( const QE &newElement )

// Inserts newElement at the rear of a queue.

{
    assert ( (rear+1) % maxSize != front );
                                // Requires that the queue is not full
    rear = ( ++rear ) % maxSize;
    element[rear] = newElement;
    if ( front == -1 )
       front = 0;
}

//--------------------------------------------------------------------

template < class QE >
QE Queue<QE>:: dequeue ()

// Removes the least recently added (front) element from a queue and
// returns it.

{
    QE temp;   // Stores the rear element

    assert ( front != -1 );    // Requires that the queue is not empty

    temp = element[front];
    if ( front == rear )
    {
       front = -1;
       rear  = -1;
    }
    else
       front = ( ++front ) % maxSize;

    return temp;
}

//--------------------------------------------------------------------

template < class QE >
void Queue<QE>:: clear ()

// Removes all the elements from a queue.

{
    front = -1;
    rear  = -1;
}

//--------------------------------------------------------------------

template < class QE >
int Queue<QE>:: empty () const

// Returns 1 if a queue is empty. Otherwise, returns 0.

{
    return ( front == -1 );
}

//--------------------------------------------------------------------

template < class QE >
int Queue<QE>:: full () const

// Returns 1 if a queue is full. Otherwise, returns 0.

{
    return ( ( rear + 1 ) % maxSize == front );
}

//--------------------------------------------------------------------

template < class QE >
void Queue<QE>:: showStructure () const

// Array implementation. Outputs the elements in a queue. If the
// queue is empty, outputs "Empty queue". This operation is intended
// for testing and debugging purposes only.

{
    int j;   // Loop counter

    if ( front == -1 )
       cout << "Empty queue" << endl;
    else
    {
       cout << "front = " << front << "  rear = " << rear << endl;
       for ( j = 0 ; j < maxSize ; j++ )
           cout << j << "\t";
       cout << endl;
       if ( rear >= front )
          for ( j = 0 ; j < maxSize ; j++ )
              if ( ( j >= front ) && ( j <= rear ) )
                 cout << element[j] << "\t";
              else
                 cout << " \t";
       else
          for ( j = 0 ; j < maxSize ; j++ )
              if ( ( j >= front ) || ( j <= rear ) )
                 cout << element[j] << "\t";
              else
                 cout << " \t";
       cout << endl;
    }
}