/* --------------------------------------------------------------------

PriorityQueue class

Copyright (c) 1996 by Christopher R. Waterson. All Rights Reserved.
Permission to use, copy, modify, and distribute this software
and its documentation for NON-COMMERCIAL purposes and without
fee is hereby granted provided that this copyright notice
appears in all copies.

$Id$

File:		PriorityQueue.java
Synopsis:	A generic PriorityQueue class
Author:		Christopher R. Waterson <waterson@eecs.umich.edu>
Created:	16 June 1996
Updated:	Christopher R. Waterson <waterson@eecs.umich.edu>
Last Modified:	31 October 1996

-------------------------------------------------------------------- */

package eightpuzzle;

import java.util.*;

/**
 * A generic priority queue impelemented as a heap. Objects may be added to the
 * queue with <B>addElement</B>, and removed from the top of the queue using
 * <B>removeTopElement</B>. Order is enforced in the queue using a Sorter object.
 *
 * Elements are sorted so that the "largest" items (i.e., those that are
 * greaterThan other elements) are at the front of the queue.
 */

public class PriorityQueue {
	/**
	 * The contents of the PriorityQueue, as a <B>Vector</B>.
	 */

	protected Vector m_contents;


	/**
	 * The Sorter used to enforce order in the queue.
	 */

	protected Sorter m_sorter;


	/**
	 * Create a new, empty PriorityQueue. Uses the <B>Vector</B> class' defaults
	 * for initial size and incremental growth.
	 *
	 * @param sorter The Sorter object used to enforce order in the queue.
	 */

	public PriorityQueue(Sorter sorter) {
		m_sorter = sorter;
		m_contents = new Vector();
	}


	/**
	 * Create a new, empty PriorityQueue initialized to hold the specified number
	 * of elements
	 *
	 * @param initSize The initial size of the PriorityQueue
	 * @param sorter The Sorter object used to enforce order in the queue.
	 */

	public PriorityQueue(Sorter sorter, int initSize) {
		m_sorter = sorter;
		m_contents = new Vector(initSize);
	}


	/**
	 * Create a new, empty PriorityQueue initialized to hold the specified number
	 * of elements, and to grow the specified amount when the intial capacity
	 * is exceeded.
	 *
	 * @param sorter The Sorter object used to enforce order in the queue.
	 * @param initSize The initial size of the PriorityQueue
	 * @param increment The incremental amount by which to increase the
	 * size of the PriorityQueue when its initial capacity is exceeded.
	 */

	public PriorityQueue(Sorter sorter, int initSize, int increment) {
		m_sorter = sorter;
		m_contents = new Vector(initSize, increment);
	}



	/**
	 * Ensure the PriorityQueue's integrity by recursively travelling <EM>up</EM>
	 * the PriorityQueue (following parent links). At each point in the tree, if
	 * the child's contents are <B>greaterThan</B> the parent's contents, the contents
	 * are swapped and <B>upPriorityQueue</B> is recursively invoked on the parent
	 * node.
	 *
	 * @param childIndex - the index of the child node to validate.
	 */

	protected void upPriorityQueue(int childIndex) {
		// If we've reached the root, the we're done.
		if (childIndex == 0) return;

		// Locate the parent node in the PriorityQueue. The "-1" is to ensure that both nodes
		// 1 and 2 have parent of zero, etc.
		int parentIndex = (childIndex - 1) / 2;

		Object childObject = m_contents.elementAt(childIndex);
		Object parentObject = m_contents.elementAt(parentIndex);

		// If the child is greaterThan the parent, then swap the two and recursively
		// propogate the change upwards in the PriorityQueue.
		if ( m_sorter.greaterThan(childObject, parentObject) ) {
			m_contents.setElementAt(parentObject, childIndex);
			m_contents.setElementAt(childObject, parentIndex);

			upPriorityQueue(parentIndex);
		}
	}



	/**
	 * Ensure the PriorityQueue's integrity by recursively travelling </EM>down</EM>
	 * the PriorityQueue (following child links). At each point in the tree, if the child's
	 * contents are <B>greaterThan</B> the parent's contents, the contents
	 * are swapped and <B>upPriorityQueue</B> is recursively invoked on the child
	 * node.
	 *
	 * @param parentIndex - the index of the parent node to validate.
	 */

	protected void downPriorityQueue(int parentIndex) {
		int childIndex = (2 * parentIndex) + 1;

		// If we've moved off the end of the PriorityQueue, then just return
		if (childIndex >= m_contents.size()) return;

		// Otherwise, grab the element at child
		Object childObject = m_contents.elementAt(childIndex);

		// Find the larger of the left and right kids (if the right kid exists)
		if (childIndex + 1 < m_contents.size()) {
			Object rightChildObject = m_contents.elementAt(childIndex + 1);

			if ( m_sorter.greaterThan(rightChildObject, childObject) ) {
				childObject = rightChildObject;
				++childIndex;
			}
		}

		// Get the object at the parent.
		Object parentObject = m_contents.elementAt(parentIndex);

		// If the child is greaterThan the parent, the swap the two and recursively
		// propogate the change downwards in the PriorityQueue.
		if ( m_sorter.greaterThan(childObject, parentObject) ) {
			m_contents.setElementAt(parentObject, childIndex);
			m_contents.setElementAt(childObject, parentIndex);

			downPriorityQueue(childIndex);
		}
	}


	/**
	 * Insert a new element into the PriorityQueue.
	 *
	 * @param object The object to insert into the PriorityQueue.
	 */

	public void addElement(Object object) {
		m_contents.addElement(object);
		upPriorityQueue(m_contents.size() - 1);
	}



	/**
	 * Is the PriorityQueue empty?
	 *
	 * @return true if the PriorityQueue is empty, false otherwise.
	 */

	public boolean hasMoreElements() {
		return (m_contents.size() > 0);
	}


	/**
	 * Remove the object at the top of the PriorityQueue, which is the largest element
	 * in the PriorityQueue.
	 *
	 * @return the top element in the PriorityQueue.
	 * @throws java.lang.ArrayIndexOutOfBoundsExecption if the PriorityQueue is empty.
	 */

	public Object removeTopElement()
	throws ArrayIndexOutOfBoundsException {
		// Get the top element off the queue
		Object topElement = m_contents.elementAt(0);

		// Get the last element in the PriorityQueue
		Object lastElement = m_contents.elementAt(m_contents.size() - 1);
		m_contents.removeElementAt(m_contents.size() - 1);

		if (m_contents.size() > 0) {
			// Re-insert the lastElement back at the top of the PriorityQueue.
			m_contents.setElementAt(lastElement, 0);
			downPriorityQueue(0);
		}

		// Return the top element from the queue.
		return topElement;
	}


	/**
	 * Returns the size of the PriorityQueue
	 *
	 * @return the current number of elements in the PriorityQueue.
	 */

	public int size() {
		return m_contents.size();
	}



	/**
	 * Return the PriorityQueue as a string.
	 */

	public String toString() {
		return m_contents.toString();
	}
}