pquos.java

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

/* PqUos.java
 * ---------------------------------------------
 * Copyright (c) 2001 University of Saskatchewan
 * All Rights Reserved
 * --------------------------------------------- */

package dslib.dispenser;

import dslib.exception.ContainerEmptyUosException;
import dslib.base.*;

/**	A dispenser which stores comparable items of generic type.  minItem
	and maxItem refer to the smallest and largest items in the structure that
	that can be deleted.  There are also methods to insert items and
	check for empty. */
public abstract class PqUos implements DispenserUos
{
	/**	The internal representation of the priority queue. */
	protected ContainerUos rep;

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

	/**	The smallest item in the priority queue. <br> 
		PRECONDITION: <br>
		<ul>
			!isEmpty() 
		</ul> */
	public abstract Object minItem() throws ContainerEmptyUosException;

	/**	The largest item in the priority queue. <br> 
		PRECONDITION: <br>
		<ul>
			!isEmpty() 
		</ul> */
	public abstract Object maxItem() throws ContainerEmptyUosException;

	/**	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;
	}

	/**	Delete the smallest item in the priority queue. <br> 
		PRECONDITION: <br>
		<ul>
			!isEmpty() 
		</ul> */
	public abstract void deleteMin() throws ContainerEmptyUosException;

	/**	Delete the largest item in the priority queue. <br> 
		PRECONDITION: <br>
		<ul>
			!isEmpty() 
		</ul> */
	public abstract void deleteMax() throws ContainerEmptyUosException;

	/**	Remove all items from the priority queue. <br>  		
		Analysis: Time = O(1)  */
	public void wipeOut()
	{
		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;
	}

	/**	A shallow clone of this object. <br> 
		Analysis: Time = O(1) */
	public Object clone()
	{
		try
		{
			return super.clone();
		} catch (CloneNotSupportedException e)
		{
			/*	Should not occur: this is a ContainerUos that implements Cloneable. */
			e.printStackTrace();
			return null;
		}
	}
}