arrayedsimplelistuos.java

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

/* ArrayedSimpleListUos.java
 * ---------------------------------------------
 * Copyright (c) 2001 University of Saskatchewan
 * All Rights Reserved
 * --------------------------------------------- */
 
package dslib.list;

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

/**	An arrayed implementation of a SimpleListUos.  It has methods to 
	manipulate the item at the front of the list and to test for empty or 
	full.  It also includes an instance variable to store
	the number of items in the list. */
public class ArrayedSimpleListUos implements SimpleListUos, BoundedUos
{
	/**	Internal representation for this list, where the first 
		item is stored in location count-1, and last in location 0. */
	protected Object[] rep;
  
	/**	The number of items in the list. */
	protected int count;

	/**	Construct a new empty list with capacity cap <br>
		Analysis: Time = O(cap) <br>
		@param cap capacity of the new list*/
	public ArrayedSimpleListUos(int cap)
	{
		rep = new Object[cap];
		count = 0;
	}

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

	/**	The maximum number of items that can be in the list. <br> 
		Analysis: Time = O(1) */
	public int capacity()
	{
		return rep.length;
	}
  
	/**	Is the list empty?. <br>
		Analysis: Time = O(1) */
	public boolean isEmpty()
	{
		return (count==0);
	}

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

	/**	Insert x as the first item of the list. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			 !isFull() 
		</ul>
		@param x item to be inserted at the front of the list */
	public void insertFirst(Object x) throws ContainerFullUosException
	{
		if (isFull())
			throw new ContainerFullUosException("Cannot insert into a full list");
		
		rep[count] = x;
		count++;
	}

	/**	The first item in the list. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			!isEmpty() 
		</ul> */
	public Object firstItem() throws ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot obtain an item from an empty list");
		
		return rep[count-1];
	}
  
	/**	Delete the first item from the list. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			 !isEmpty() 
		</ul> */
	public void deleteFirst() throws ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot delete an item from an empty list");
		
		count--;
	}

	/**	Return a list clone of this list. <br>
		Analysis: Time = O(capacity) */
	public SimpleListUos listClone()
	{
		ArrayedSimpleListUos tempClone = (ArrayedSimpleListUos) clone();
		tempClone.rep = (Object[]) rep.clone();  // creates a duplicate array
		return tempClone;
	}

	/**	String representation of the list. <br>  
		Analysis: Time = O(count) */
	public String toString()
	{
		String result = new String();
		for (int i=count-1; i>=0; i--)
			result = result+rep[i]+"  ";      
		return result;
	}

	/**	Remove all items from the list. <br>  
		Analysis: Time = O(1) */
	public void wipeOut()
	{
		count = 0;
	}
  
	/**	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, which implements Cloneable 
			e.printStackTrace();
 			return null;
		}
	}
}