linkedlistuos.java

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

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

import dslib.exception.*;
import dslib.dictionary.DictUos;
import dslib.base.*;

/**	This LinkedList class incorporates the functions of an 
	iterated dictionary such as has, obtain, search, goFirst, 
	goForth, etc.  In accordance with a list, items can be inserted 
	at the beginning and the end of the list, and also at the 
	current position. */
public class LinkedListUos extends LinkedLastListUos implements DictUos
{ 
	/**	Should next search continue from current item or start at the beginning?. */
	protected boolean searchesContinue = false;
  
	/**	Compare object references or object contents; default contents. */
	protected boolean objectReferenceComparison = false;
  
	/**	The current node. */
	protected LinkedNodeUos cur;

	/**	The node previous to the current node. */
	protected LinkedNodeUos prev;

	/**	Construct an empty list that allows duplicates. 
		Analysis: Time = O(1) */
	public LinkedListUos()
	{
		super();
		goBefore();
		searchesContinue = false;
	}

	/**	The current item. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION:  <br>
		<ul>
			itemExists() 
		</ul> */
	public Object item() throws NoCurrentItemUosException
	{
	   	if (!itemExists())
		  	throw new NoCurrentItemUosException("A current item must exist.");  
		
		return cur.item();
	}

	/**	Is there a current item?. <br>
		Analysis: Time = O(1) */
	public boolean itemExists()
	{
		return (!before()) && (!after());
	}
 
	/**	Set searches to always start over. <br> 
		Analysis: Time = O(1) */
	public void restartSearches()
	{
		searchesContinue = false;
	}

	/**	Set searches to continue from current item. <br> 
		Analysis: Time = O(1) */
	public void resumeSearches()
	{
		searchesContinue = true;
	}

	/**	Move to item x (in the remainder if searchesContinue). <br>
		Analysis: Time = O(n), n = number of items in the list 
		@param x item to search the list for */
	public void search(Object x)
	{
		if (!searchesContinue)
			goFirst();
		else if (!after())
			goForth();

		while (!after() && !membershipEquals(x, item()))
			goForth();
	}

	/**	Is x an item in the list (remaining part if searchesContinue)?. <br>
		Analysis: Time = O(n), n = number of items in the list 
		@param x item whose presents is to be determined */
	public boolean has(Object x)
	{
		CursorUos savePos = currentPosition();
		search(x);
		boolean result = itemExists();
		goPosition(savePos);
		return result;
	}

	/**	The first instance of x (next one if searchesContinue). <br>
		Analysis: Time = O(n), where n = number of items in the list <br>
		PRECONDITION:  <br>
		<ul>
			has(x) 
		</ul>
		@param x item to be obtained from the list */
	public Object obtain(Object x) throws ItemNotFoundUosException
	{
		if (!has(x))
			throw new ItemNotFoundUosException("Cannot obtain an item that does not exist.");
		
		CursorUos savePos = currentPosition();
		search(x);
		Object result = item();
		goPosition(savePos);
		return result;
	}

	/**	The list formed by excluding the first item. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION:  <br>
		<ul>
			!isEmpty() 
		</ul> */
	public BasicListUos firstRemainder() throws ContainerEmptyUosException
	{
		LinkedListUos result = (LinkedListUos)super.firstRemainder();
		result.goBefore();
		return result;
	}

	/**	The list formed by excluding the items up to and including the current item. <br> 
		Analysis: Time = O(1) <br>
		PRECONDITION:  <br>
		<ul>
			itemExists() 
		</ul> */
	public LinkedListUos remainder() throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("A current item must exist to return its remainder.");     
		
		LinkedListUos result = (LinkedListUos)this.clone();
		result.setFirstNode(cur.nextNode());
		if (cur==lastNode)
			result.setLastNode(null);
		result.goBefore();
		return result;
	}

	/**	Is the current position before the start of the list?. <br>
		Analysis: Time = O(1) */
	public boolean before()
	{
		return (prev==null) && (cur==null);
	}

	/**	Is the current position after the end of the list?. <br>
		Analysis: Time = O(1) */
	public boolean after()
	{
		return (cur==null) && (prev!=null || isEmpty());
	}  

	/**	Insert x as the first item of the list. <br>
		Analysis: Time = O(1) 
		@param x item to be inserted at the front of the list */
	public void insertFirst(Object x)
	{
		super.insertFirst(x);
		if (cur!=null && cur==firstNode.nextNode())
			prev = firstNode;
	}

	/**	Insert x as the first item of the list. <br>
		Analysis: Time = O(1) 
		@param x item to be inserted */
	public void insert(Object x) 
	{
		insertFirst(x);	
	}

	/**	Insert x as the first item and go to it. <br>
		Analysis: Time = O(1) 
		@param x item to be inserted at the front of the list */
	public void insertGo(Object x) 
	{
		insertFirst(x);
		goFirst();
	}

	/**	Insert x after the current item. <br>
		Analysis: Time = O(1) 
		@param x item to be inserted in the next position in the list */
	public void insertNext(Object x) 
	{
		if (isEmpty() || before()) // if the list is empty, insert first 
			insertFirst(x);
		else if (cur == lastNode) // if we are at the end, insert it last 
			insertLast(x);
		else if (after()) // if we are after, insert it last and update cur
		{
			insertLast(x);
			cur = prev.nextNode();
		}
		else // else make a new node and set up the pointers
		{
			LinkedNodeUos temp = createNewNode(x);
			temp.setNextNode(cur.nextNode());
			cur.setNextNode(temp);
		}
	}
	  
	/**	Insert x as the last item of the list. <br>
		Analysis: Time = O(1) 
		@param x item to be inserted at the end of the list */
	public void insertLast(Object x) 
	{
		super.insertLast(x);
		if (cur==null && prev!=null)
			prev = lastNode;
	}

	/**	Insert x before the current position and make it current item. <br>
		Analysis: Time = O(1) 
		@param x item to be inserted prior to the current position*/
	public void insertPriorGo(Object x) 
	{
		if (isEmpty() || before() || (cur==firstNode))
		{
			insertFirst(x);
			goFirst();
		}
		else
		{
			LinkedNodeUos temp = cur;
			cur = createNewNode(x);
			cur.setNextNode(temp);
			prev.setNextNode(cur);
			if (prev == lastNode)
				lastNode = cur;
		}
	}

	/**	Set the list to be newList preceded by firstItem, and goFirst(). <br> 
		Analysis: Time = O(1) <br>
		PRECONDITION:  <br>
		<ul>
			!isEmpty() 
		</ul>
		@param newList list the replaceent list for firstRemainder */
	public void setFirstRemainder(BasicListUos newList) throws ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot perform setFirstRemainder() on an empty list.");
		
		super.setFirstRemainder(newList);
		goFirst();
	}
  
	/**	Set the list following the current position to newList. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION:  <br>
		<ul>
			itemExists() 
		</ul>
		@param newList list that is set to the remainder of the current list */
	public void setRemainder(BasicListUos newList) throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("Cannot perform setRemainder() since there is no current item.");
		
		cur.setNextNode(((LinkedSimpleListUos)newList).firstNode);
		lastNode = ((LinkedLastListUos)newList).lastNode;
	}

	/**	Set the current item to x. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION:  <br>
		<ul>
			itemExists() 
		</ul>
		@param x item that replaces the current item */
	public void setItem(Object x) throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("A current item must exist.");
		
		cur.setItem(x);
	}

	/**	Delete the current item moving to its successor. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION:  <br>
		<ul>
			itemExists() 
		</ul> */
	public void deleteItem() throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("A current item must exist if it is to be deleted");
		
		if (cur==firstNode)
		{
			deleteFirst();
			cur = firstNode;
		}
		else
		{
			prev.setNextNode(cur.nextNode());
			if (cur==lastNode)
				lastNode = prev;
			cur = cur.nextNode();
		}
	}

	/**	Delete the first item. <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.");
		
		if (prev==firstNode)
			prev = null;
		else if (cur==firstNode)
			cur = cur.nextNode();
		super.deleteFirst(); 
	}

	/**	Delete item x (from remainder if searchesContinue). <br>
		Analysis: Time = O(n), where n = number of items in the list <br>
		PRECONDITION:  <br>
		<ul>
			has(x) 
		</ul>
		@param x item to be deleted from the list */
	public void delete(Object x) throws ItemNotFoundUosException
	{
		if (!has(x))
			throw new ItemNotFoundUosException("Cannot delete an item that does not exist.");
		
		LinkedNodeUos saveCur = cur;
		LinkedNodeUos savePrev = prev;

		search(x);
		if (itemExists() && (cur==saveCur || cur==savePrev))
			deleteItem();
		else if (itemExists())
		{
			deleteItem();
			prev = savePrev;
			cur = saveCur;
		}
	}

	/**	Move prior to the first item in the list. <br>
		Analysis: Time = O(1) */
	public void goBefore()
	{
		cur = null;
		prev = null;
	}

	/**	Move to the logical first item in the list. <br> 
		Analysis: Time = O(1) */
	public void goFirst()
	{
		prev = null;
		cur = firstNode;
	}

	/**	Advance one item in the list. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			!after() 
		</ul> */
	public void goForth() throws AfterTheEndUosException
	{
		if (after())
			throw new AfterTheEndUosException("Cannot go forth when after the end of the structure.");

		if (before())
			goFirst();
		else
		{
			prev = cur;
			cur = cur.nextNode();
		}
	}

	/**	Move past the last item in the list. <br>
		Analysis: Time = O(1) */
	public void goAfter()
	{
		cur = null;
		prev = lastNode;
	}
  
	/**	Go to the position in the list specified by c. <br>
		Analysis: Time = O(1) 
		@param c position to which to go */
	public void goPosition(CursorUos c)
	{
		LinkedIteratorUos lc = (LinkedIteratorUos) c;      
		prev = lc.prev;
		cur = lc.cur;
	}
  
	/**	The current position in this list. <br>
		Analysis: Time = O(1) */
	public CursorUos currentPosition()
	{
		return  new LinkedIteratorUos(this, prev, cur);
	}

	/**	The number of times x occurs in the list. <br> 
		Analysis: Time = O(n), where n = number of items in the list 
		@param x item to check how often it occurs in the list */
	public int frequency(Object x) 
	{
		int result = 0;
		CursorUos savePos = currentPosition();  // save the current position before iteration
		
 		// traverse the list 
		goFirst(); 
		while (!after()) 
		{
			if (membershipEquals(x, item()))
				result++; 
			goForth();
		}

		goPosition(savePos); // go to the previously saved position
		return result;
	}

	/**	Set comparison operations to use '=='. <br>
		Analysis: Time = O(1) */
	public void compareObjectReferences()
	{
		objectReferenceComparison = true;
	}
  
	/**	Set comparison operations to use compareTo or equals; this is the default. <br> 
		Analysis: Time = O(1) */
	public void compareContents()
	{
		objectReferenceComparison = false;
	}

	/**	Test whether x equals y using the current comparison mode. <br>
		Analysis: Time = O(1) 
		@param x item to be compared to y
		@param y item to be compared to x */
	public boolean membershipEquals(Object x, Object y)
	{
		if (objectReferenceComparison)
			return  x==y;
		else if ((x instanceof Comparable) && (y instanceof Comparable))
			return  0==((Comparable)x).compareTo(y);
		else if (x.equals(y))
			return true;
		else 
			return false;
	}	

	/**	Remove all items from the list. <br>
		Analysis: Time = O(1) */
	public void wipeOut()
	{
		super.wipeOut();
		cur = null;
		prev = null;
	}
}