linkediteratoruos.java

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

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

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

/**	A LinearIteratorUos for linked lists.  It utilizes a cursor to 
	keep track of the current item, and has functions to move 
	forward and to the front of the list.  It also has functions to 
	determine if it is before the start or after the end of the 
	structure. */
public class LinkedIteratorUos implements LinearIteratorUos
{
	/**	List being iterated. */  
	protected LinkedBasicListUos list;
  
	/**	The node with the current item. */
	protected LinkedNodeUos cur;
  
	/**	The node previous to the current node. */
	protected LinkedNodeUos prev;
  
	/**	Create a new iterator for the newList. <br>
		Analysis : Time = O(1) 
		@param newList list to be iterated */
	public LinkedIteratorUos(LinkedBasicListUos newList)
	{
		list = newList;
		goFirst();
	}
  
	/**	Create a new iterator at a specific position in the newList. <br>
		Analysis : Time = O(1)
		@param newList list to be iterated
		@param initialPrev the previous node for the initial position
		@param initialCur the current node for the initial position */
	public LinkedIteratorUos(LinkedBasicListUos newList, LinkedNodeUos initialPrev, LinkedNodeUos initialCur)
	{
		list = newList;
		prev = initialPrev;
		cur = initialCur;
	}
    
	/**	Is the current position before the first item in the structure?. <br>
		Analysis : Time = O(1) */
	public boolean before()
	{
		return (prev==null) && (cur==null);
	}
  
	/**	Is the current position after the last item in  the structure?. <br>
		Analysis : Time = O(1) */
	public boolean after()
	{
		return (cur==null) && (prev!=null || list.isEmpty());
	}
  
	/**	Is there a current item?. <br>
		Analysis : Time = O(1) */
	public boolean itemExists()
	{
		return !before() && !after();
	}

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

		return cur.item();
	}
  
	/**	Go to the first item in the data structure. <br>
		Analysis : Time = O(1) */
	public void goFirst()
	{
		prev = null;
		cur = list.firstNode();
	}
  
	/**	Move prior to the first item. <br>
		Analysis : Time = O(1) */
	public void goBefore()
	{
		cur = null;
		prev = null;
	}
  
	/**	Advance one item forth in the data structure. <br>
		Analysis : Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			!after() 
		</ul> */
	public void goForth() throws AfterTheEndUosException
	{
		if (after())
			throw new AfterTheEndUosException("Cannot advance to next item when already after.");

		if (before())
			goFirst();
		else
		{
			prev = cur;
			cur = cur.nextNode();
		}
	}
  
	/**	Go after the last item in the data sturcture. <br>
		Analysis : Time = O(n), where n = length of the list */
	public void goAfter()
	{
		if (list instanceof LinkedLastListUos)
		{
			/* list is a LinkedLastList or one of its children */
			cur = null;
			prev = ((LinkedLastListUos)list).lastNode();
		}
		else
			/* loop until we reach the end of the list */
			while (!after())
				goForth();
	}

	/**	String listing of the items in the tree. <br> 
		Analysis: Time = O(n), where n = length of the list */
	public String toString()
	{
		return list.toString();
	}

	/**	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 CursorUos, which implements Cloneable 
			e.printStackTrace();
 			return null;
		}
	}

	/**	Is this cursor pointing to the same location as other?. <br>
		Analysis: Time = O(1)
		@param other The object to compare to */
	public boolean equals(Object other)
	{
		LinkedIteratorUos otherIter = (LinkedIteratorUos) other;
		return (otherIter.cur == cur) && (otherIter.prev == prev) && (otherIter.list == list);
	}
}