arrayedbasiclistuos.java

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

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

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

/**	An arrayed implementation of a BasicListUos, with a bounded 
	capacity, a function to return the number of items, and 
	operations to add and delete items at the front of the list. */
public class ArrayedBasicListUos extends ArrayedSimpleListUos implements BasicListUos
{
	/**	Construct a new empty list with capacity cap <br>
		Analysis: Time = O(cap) 
		@param cap capacity of the new list */
	public ArrayedBasicListUos(int cap)
	{
		super(cap);
	}

	/**	Set the first item to x. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			!isEmpty()
		</ul>
		@param x item to replace the first item */
	public void setFirstItem(Object x) throws ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot set first item since no items exist in the list.");
		
		// first item in location count-1 and last in location 0 
		rep[count - 1] = x;
	}

	/**	Set the list to be rem list preceded by firstItem. <br>
		Analysis: Time = O(r), r = length of rem <br>
		PRECONDITION: <br>
		<ul>
			!isEmpty() <br>
			!(1+((ArrayedBasicListUos)rem).count > capacity())		
		</ul>
		@param rem the replacement list for firstRemainder() */
	public void setFirstRemainder(BasicListUos rem) throws ContainerEmptyUosException, ContainerFullUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot setFirstRemainder of an empty list.");
		if (1+((ArrayedBasicListUos)rem).count > capacity())
			throw new ContainerFullUosException("The array does not have room for the firstItem() and the rem list.");

		Object saveFirstItem = firstItem();     
		System.arraycopy(((ArrayedBasicListUos)rem).rep, 0, rep, 0, ((ArrayedBasicListUos)rem).count); 
		count = ((ArrayedBasicListUos)rem).count;
		insertFirst(saveFirstItem);
	}

	/**	The list formed by excluding the first item. <br>
		Analysis: Time = O(capacity) <br>
		PRECONDITION: <br>
		<ul>
			!isEmpty() 
		</ul> */
	public BasicListUos firstRemainder() throws ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot return first remainder of an empty list.");

		ArrayedBasicListUos rem = (ArrayedBasicListUos) listClone();  // clone the list including the array
		rem.deleteFirst();
		return rem;
	}

	/**	Iterator for list initialized to first item. <br>
		Analysis: Time = O(1)  */
	public LinearIteratorUos iterator()
	{
		return new ArrayedListIteratorUos(this.rep, count);
	}
}