linkedpquos.java

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

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

package dslib.dispenser;

import dslib.exception.*;
import dslib.list.OrderedBilinkedListUos;

/**	An implementation of PqUos that uses an OrderedBilinkedListUos to
	store the items.  The items are ordered, with the largest item at the 
	front of the queue.  minItem and maxItem are the smallest and 
	largest items, respectively.  There are functions to delete 
	minItem and maxItem, to insert and to check for empty. */
public class LinkedPqUos extends PqUos
{
	/**	Construct an empty priority queue. <br>
		Analysis: Time = O(1) */
	public LinkedPqUos()
	{
		rep = new OrderedBilinkedListUos();
	}
  
	/**	The minimum priority item. <br>
		Analysis: Time = O(1) 
		PRECONDITION: <br>
		<ul>
			!isEmpty() 
		</ul> */
	public Object minItem() throws ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot return an item from an empty queue.");
		
		return ((OrderedBilinkedListUos)rep).firstItem();
	}
  
	/**	The maximum priority item. <br> 
		Analysis: Time = O(1) 
		PRECONDITION: <br>
		<ul>
			!isEmpty() 
		</ul> */
	public Object maxItem() throws ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot return an item from an empty queue.");
		
		return ((OrderedBilinkedListUos)rep).lastItem();
	}
  
	/**	The maximum priority item. <br>
		Analysis: Time = O(1)
		PRECONDITION: <br>
		<ul>
			itemExists() 
		</ul> */
	public Object item() throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("Cannot return an item that does not exist.");
		
		return ((OrderedBilinkedListUos)rep).lastItem();
	}
  
	/**	Inserts an object into the queue. <br> 
		Analysis: Time = O(1) <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.");
		
		((OrderedBilinkedListUos)rep).insert(x);
	}
  
	/**	Deletes the minimum priority item. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			!isEmpty() 
		</ul> */
	public void deleteMin() throws ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot delete an item from an empty queue.");
		
		((OrderedBilinkedListUos)rep).deleteFirst();
	}
  
	/**	Deletes the maximum priority item. <br> 
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			!isEmpty() 
		</ul> */
	public void deleteMax() throws ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot delete an item from an empty queue.");
		
		((OrderedBilinkedListUos)rep).deleteLast();
	}
  
	/**	Deletes the maximum priority item. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			itemExists() 
		</ul> */
	public void deleteItem() throws NoCurrentItemUosException
	{
		if (isEmpty())
			throw new NoCurrentItemUosException("Cannot delete an item that does not exist.");
		
		((OrderedBilinkedListUos)rep).deleteLast();
	}
  
	/**	Is the queue full?. <br>
		Analysis: Time = O(1) */
	public boolean isFull()
	{
		return false;
	}
}