stdpquos.java

国外的数据结构与算法分析用书

/* StdPqUos.java
 * ---------------------------------------------
 * Copyright (c) 2002 University of Saskatchewan
 * All Rights Reserved
 * --------------------------------------------- */
 
 package dslib.util;
 
 import dslib.dispenser.PqUos;
 import dslib.dictionary.bintree.*;
 import dslib.exception.*;

/**	A useful, standard priority queue.  minItem
	and maxItem refer to the smallest and largest items in the structure,
	that can be deleted.  There are also methods to insert items and
	check for empty */
public class StdPqUos extends PqUos
{

	/**	Construct an empty priority queue. <br>
		Analysis: Time = O(1) */
	public StdPqUos()
	{
		rep = new HtBalBasicDictUos();
		count = 0;
	}

	/**	Is the priority queue empty?. <br>  
		Analysis: Time = O(1) */
	public boolean isEmpty()
	{
		return ((HtBalBasicDictUos)rep).isEmpty();
	}

	/**	Is the queue full?. <br>
		Analysis: Time = O(1) */
	public boolean isFull()
	{
		return false;
	}

	/**	The smallest item in the priority queue. <br> 
		Analysis: Time = O(log n) where n is the number of items in the Priority Queue <br> 
		PRECONDITION: <br>
		<ul>
			!isEmpty() 
		</ul> */
	public Object minItem() throws ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot return an item from an empty queue.");

		HtBalTreeIteratorUos cursor =  ((HtBalBasicDictUos) rep).newIterator();
		
		cursor.goRoot();
		Object lastItem = cursor.item();
		cursor.goLeft();

		while (!cursor.below())
		{
			lastItem = cursor.item();
			cursor.goLeft();
		}
		return lastItem;			
	}

	/**	The largest item in the priority queue. <br> 
		Analysis: Time = O(log n) where n is the number of items in the Priority Queue <br> 
		PRECONDITION: <br>
		<ul>
			!isEmpty() 
		</ul> */
	public Object maxItem() throws ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot return an item from an empty queue.");

		HtBalTreeIteratorUos cursor =  ((HtBalBasicDictUos) rep).newIterator();
		
		cursor.goRoot();
		Object lastItem = cursor.item();
		cursor.goRight();

		while (!cursor.below())
		{
			lastItem = cursor.item();
			cursor.goRight();
		}
		return lastItem;			
	}

	/**	The maximum priority item. <br>
		Analysis: Time = O(1)
		PRECONDITION: <br>
		<ul>
			itemExists() 
		</ul> */
	public Object item() throws NoCurrentItemUosException
	{
		return maxItem();
	}
	
	/**	Is there an item in the priority queue?. <br>   
		Analysis: Time = O(1) */
	public boolean itemExists()
	{
		return !isEmpty();
	}

	/**	Number of items in the queue. */
	protected int count;

	/**	Number of items in the queue. <br>
		Analysis: Time = O(1) */
	public int count()
	{
		return count;
	}

	/**	Inserts an object into the queue. <br> 
	Analysis: Time = O(log n) where n is the number of items in the Priority Queue <br> 
	PRECONDITION: <br>
	<ul>
		x instanceof Comparable 
	</ul>
	@param x new item to be inserted in the queue */
	public void insert(Object x) throws ItemNotComparableUosException
	{
		if (!(x instanceof Comparable))
			throw new ItemNotComparableUosException("Cannot insert an item that is not Comparable.");
				
		((HtBalBasicDictUos)rep).insert(x);
		count++;
	}
  

	/**	Delete the smallest item in the priority queue. <br>
		Analysis: Time = O(lgN) where N is the number of items in the Priority Queue <br>  
		PRECONDITION: <br>
		<ul>
			!isEmpty() 
		</ul> */
	public void deleteMin() throws ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot return an item from an empty queue.");

		((HtBalBasicDictUos)rep).delete(minItem());
		count--;
	}

	/**	Delete the largest item in the priority queue. <br> 
		Analysis: Time = O(lgN) where N is the number of items in the Priority Queue <br> 
		PRECONDITION: <br>
		<ul>
			!isEmpty() 
		</ul> */
	public void deleteMax() throws ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot return an item from an empty queue.");

		((HtBalBasicDictUos)rep).delete(maxItem());
		count--;
	}

	/**	Deletes the maximum priority item. <br>
		Analysis: Time = O(lgN) where N is the number of items in the Priority Queue <br> 
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			itemExists() 
		</ul> */
	public void deleteItem() throws NoCurrentItemUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot return an item from an empty queue.");
		deleteMax();
	}

	/**	Remove all items from the priority queue. <br>  		
		Analysis: Time = O(1)  */
	public void wipeOut()
	{
		((HtBalBasicDictUos)rep).wipeOut();
		count = 0;
	}

	/**	String representation of the contents of the priority queue. <br> 
		Analysis: Time = O(1) */
	public String toString()
	{
		return "PQ contents starting with the minumum item: " + rep;
	}	
}