#include "QueueAr.h"

/**
 * Construct the queue.
 */
template <class Object>
Queue<Object>::Queue( ) : theArray( 1 )
{
    makeEmpty( );
}

/**
 * Test if the queue is logically empty.
 * Return true if empty, false, otherwise.
 */
template <class Object>
bool Queue<Object>::isEmpty( ) const
{
    return currentSize == 0;
}

/**
 * Make the queue logically empty.
 */
template <class Object>
void Queue<Object>::makeEmpty( )
{
    currentSize = 0;
    front = 0;
    back = theArray.size( ) - 1;
}

/**
 * Get the least recently inserted item in the queue.
 * Return the least recently inserted item in the queue
 * or throw Underflow if empty.
 */
template <class Object>
const Object & Queue<Object>::getFront( ) const
{
    if( isEmpty( ) )
        throw UnderflowException( );
    return theArray[ front ];
}

/**
 * Return and remove the least recently inserted item from the queue.
 * Throw Underflow if empty.
 */
template <class Object>
Object Queue<Object>::dequeue( )
{
    if( isEmpty( ) )
        throw UnderflowException( );

    currentSize--;
    Object frontItem = theArray[ front ];
    increment( front );
    return frontItem;
}

/**
 * Insert x into the queue.
 */
template <class Object>
void Queue<Object>::enqueue( const Object & x )
{
    if( currentSize == theArray.size( ) )
        doubleQueue( );
    increment( back );
    theArray[ back ] = x;
    currentSize++;
}

/**
 * Internal method to double capacity.
 */
template <class Object>
void Queue<Object>::doubleQueue( )
{
    theArray.resize( theArray.size( ) * 2 + 1 );
    if( front != 0 )
    {
        for( int i = 0; i < front; i++ )
            theArray[ i + currentSize ] = theArray[ i ];
        back += currentSize;
    }
}

/**
 * Internal method to increment x with wraparound.
 */
template <class Object>
void Queue<Object>::increment( int & x ) const
{
    if( ++x == theArray.size( ) )
        x = 0;
}