/**
 * Queue.java - a queue of Objects
 *
 * @author Todd Neller
 * @version 1.0
 *

Copyright (C) 2003 Todd Neller

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

Information about the GNU General Public License is available online at:
  http://www.gnu.org/licenses/
To receive a copy of the GNU General Public License, write to the Free
Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
02111-1307, USA.

 */

public class Queue{

    /**
     * variable <code>INITIAL_CAPACITY</code> - initial capacity of the queue
     */
    private final int INITIAL_CAPACITY = 1;


    /**
     * variable <code>data</code> - array containing queue items
     */
    private Object[] data = new Object[INITIAL_CAPACITY]; // 


    /**
     * variable <code>head</code> - array index of queue head, the
     * position of the first element */
    private int head = 0; 


    /**
     * variable <code>tail</code> - array index of queue tail, the
     * first position after the last element.  The next enqueued item
     * will be placed at this position.  */
    private int tail = 0;


    /**
     * variable <code>items</code> - number of items in queue
     */
    private int items = 0;

    
    /**
     * <code>isEmpty</code> - return whether or not the queue is empty
     *
     * @return a <code>boolean</code> value - whether or not the queue
     * is empty */
    public boolean isEmpty() 
    {
	return (items == 0);
    }


    /**
     * <code>enqueue</code> - insert the given item at the queue tail.
     *
     * @param item an <code>Object</code> value */
    public void enqueue(Object item) 
    {
	// IMPLEMENT:

	// grow data array if necessary; make the new size (2 * length
	// + 1) (Why not just 2 * length?  Under what circumstance(s)
	// is the +1 necessary?)
	
	// enqueue new item

    }
    

    /**
     * <code>dequeue</code> - remove and return the head item of the
     * queue.  If the queue is empty, returns null.
     *
     * @return an <code>Object</code> value - head item of the queue,
     * or null if empty*/
    public Object dequeue() 
    {
	// IMPLEMENT:

	// check for empty queue case

	// shrink data array to half of size if using less than half
	
	// remove and return dequeued object

	return null; // needed for compilation; replace when implementing
    }

    /**
     * <code>resize</code> - resizes the queue array to the given new
     * size.  If the size is less than the current number of items, no
     * action is taken.
     *
     * @param newSize an <code>int</code> value - the new size of the
     * queue array; should be >= items */
    private void resize(int newSize) 
    {
	// IMPLEMENT:

	// check for newSize < items case 

	// create the new object array and copy old array contents to
	// new array

	// replace old array with new array

	// update head/tail as needed

    }
    

    /**
     * <code>size</code> - return the number of items in the queue
     *
     * @return an <code>int</code> value - number of items in the
     * queue */
    public int size() 
    {
	return items;
    }
    

    /**
     * <code>toString</code> - return a String representation of the
     * queue.
     *
     * @return a <code>String</code> value */
    public String toString() 
    {
	StringBuffer sb = new StringBuffer();
	sb.append('[');
	int i = head;
	for (int count = 0; count < items; count++) {
	    sb.append(data[i]);
	    i++;
	    if (i == data.length)
		i = 0;
	    if (count < items - 1)
		sb.append(", ");
	}
	sb.append(']');
	return sb.toString();
    }


    /**
     * <code>test</code> - a random test harness that randomly
     * enqueues/dequeues a sequence of Integer objects, checking the
     * correctness of each dequeue result.  */
    public static void test() 
    {
	final int TEST_ITERS = 10000;
	java.util.Random random = new java.util.Random(0);
	int nextInt = 0;
	int lastDequeued = -1;
	Queue q = new Queue();
	for (int i = 0; i < TEST_ITERS; i++) {
	    System.out.println("Queue (size " + q.size() + "): " + q);
	    if (random.nextBoolean()) {
		// enqueue test
		System.out.println("Enqueue");
		q.enqueue(new Integer(nextInt));
		nextInt++;
	    }
	    else {
		// dequeue test
		System.out.println("Dequeue");
		Integer iObj = (Integer) q.dequeue();
		if (iObj == null) {
		    if (nextInt != lastDequeued + 1) {
			System.err.println("Invalid null dequeue");
			System.exit(1);
		    }
		}
		else {
		    int iVal = iObj.intValue();
		    if (iVal != lastDequeued + 1) {
			System.err.println("Expecting " + (lastDequeued + 1) + ", dequeued " + iVal);
			System.exit(1);
		    }
		    lastDequeued = iVal;
		}    
	    }
	}
    }
    

    public static void main(String[] args)
    {
	test(); // test the functionality of this class
    }
    
} // Queue