linkedbasiclistuos.java

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

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

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

/**	A BasicListUos class which has a linear iterator to move through 
	a list of items stored as a number of LinkedNodeUos.  It has the basic list 
	functions to manipulate the first item and the remainder of the 
	list. The first node can be accessed and set. */
public class LinkedBasicListUos extends LinkedSimpleListUos implements BasicListUos
{
	/**	Construct an empty list. <br>
		Analysis: Time = O(1) */
	public LinkedBasicListUos()
	{
		super();
	}

	/**	Set the first item to x. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION:  <br>
		<ul>
			!isEmpty() 
		</ul>
		@param x item to be set as the first item */
	public void setFirstItem(Object x) throws ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot set first item since list is empty.");
		
		firstNode.setItem(x);
	}

	/**	The list formed by excluding the first item. <br>
		Beware that afterwards the list this and the list returned share a sublist. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION:  <br>
		<ul>
			!isEmpty() 
		</ul> */
	public BasicListUos firstRemainder() throws ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot return first remainder of an empty list.");
	
		LinkedBasicListUos rem = (LinkedBasicListUos) clone();
		/* The shallow clone operation yields a list of the same type as this */
		rem.deleteFirst(); 
		return rem;
	}

	/**	Set the list to be list rem preceded by firstItem. <br>
		Beware that afterwards the list this and the list rem share a sublist. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION:  <br>
		<ul>
			!isEmpty() 
		</ul>
		@param rem the replacement list for firstRemainder */
	public void setFirstRemainder(BasicListUos rem) throws ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot setFirstRemainder of an empty list");

		Object saveFirstItem = firstItem();
		firstNode = ((LinkedBasicListUos) rem).firstNode;
		insertFirst(saveFirstItem);
	}

	/**	Iterator for list initialized to first item.
		Analysis: Time = O(1) */
	public LinearIteratorUos iterator()
	{
		return new LinkedIteratorUos(this);
	}
}