// QueueArray class


/**
 * Array-based implementation of the queue.
 *
 * @author Mark Allen Weiss
 * @author Albert J. Wong
 *
 * Modified by Albert J. Wong October 2003
 *   - Fixed style
 *   - Threw exceptions on underflow
 *   - Weiss has one memory leak in this. The leak is left in.
 *     Finding and fixing it is left as an exercise to the students.
 *   - Created and used generic interface for Queue
 */
public class QueueArray implements Queue {
	/**
	 * Construct the queue.
	 */
	public QueueArray() {
		this( DEFAULT_CAPACITY );
	}



	/**
	 * Construct the queue.
	 */
	public QueueArray( int capacity ) {
		data = new Object[ capacity ];
		makeEmpty( );
	}



	/**
	 * Test if the queue is logically empty.
	 *
	 * @return 	true if empty, false otherwise.
	 */
	public boolean isEmpty() {
		return size == 0;
	}



	/**
	 * Test if the queue is logically full.
	 *
	 * @return 	true if full, false otherwise.
	 */
	public boolean isFull() {
		return size == data.length;
	}


	/**
	 * Make the queue logically empty.
	 */
	public void makeEmpty() {
		size = 0;
		front = 0;
		back = -1;
	}


	/**
	 * Get the least recently inserted item in the queue.
	 * Does not alter the queue.
	 *
	 * @return 	the least recently inserted item in the queue
	 * @exception 	UnderflowException	Thrown if queue is empty.
	 */
	public Object getFront() {
		if( isEmpty() ) {
			throw new UnderflowException();
		}

		return data[front];
	}


	/**
	 * Return and remove the least recently inserted item from the queue.
	 *
	 * @return the least recently inserted item in the queue
	 * @exception UnderflowException	Thrown if queue is empty.
	 */
	public Object dequeue() {
		if( isEmpty() ) {
			throw new UnderflowException();
		}

	    	size--;

		Object frontItem = data[ front ];
		data[front] = null;
		front = increment( front );

		return frontItem;
	}


	/**
	 * Insert a new item into the queue.
	 *
	 * @param x the item to insert.
	 * @exception OverflowException		Thrown if queue is full.
	 */
	public void enqueue( Object x ) {
		if( isFull() ) {
			throw new OverflowException( );
		}

		back = increment( back );
		data[ back ] = x;
		size++;
	}


	/**
	 * Internal method to increment with wraparound.
	 *
	 * @param x any index in data's range.
	 * @return x+1, or 0, if x is at the end of data.
	 */
	private int increment( int x ) {
	    if( ++x == data.length )
		x = 0;
	    return x;
	}



	/// The array that holds the items in the queue
	private Object []	data;

	/// The number of elements in the queue
	private int		size;

	/// The index at which the front of the queue is located
	private int		front;

	/// The index at which the back of the queue is located
	private int		back;


	/// The default capacity of the queue
	static final int DEFAULT_CAPACITY = 10;


	/**
	 * Main function for a simple unit test of the queue.
	 */
	public static void main( String[] args ) {
		QueueArray q = new QueueArray( );

		try
		{
			for( int i = 0; i < 10; i++ ) {
				q.enqueue( new Integer( i ) );
			}
		} catch( OverflowException e ) { 
			System.out.println( "Unexpected overflow" ); 
		}

		while( !q.isEmpty() ) {
			System.out.println( q.dequeue() );
		}
	}    
}