linkediterator.java

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

package simple;


/**	An iterator class for a LinkedSimpleListUos.  It keeps track of the current item
	in the sequence, and has methods to move to the front of the sequence and to move
	forward in it.  It also has tests for before the start and after the end of the list. */
public class LinkedIterator implements LinearIterator 
{
	/**	The current node storing the current item. */ 
	protected LinkedNode cur;
   
	/**	The node previous to the current node. */
	protected LinkedNode prev;

	/**	The list being iterated. */
	protected LinkedSimpleList list; 

	/**	Initialize the iterator at the first node.
		Analysis: Time = O(1) */
	public LinkedIterator(LinkedSimpleList newList)
	{
		list = newList;
		goFirst();
	}

	/**	Initialize the iterator at the position passed in.
		Analysis: Time = O(1) */
	public LinkedIterator(LinkedSimpleList newList, LinkedNode initialPrev, LinkedNode initialCur)
	{
		list = newList;
		prev = initialPrev;
		cur = initialCur;
	}

	/**	Is there a current item? 
		Analysis: Time = O(1) */
	public boolean itemExists()
	{
		return !before() && !after();
	}

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

		return cur.item();
	}

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

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

	/**	Go to first item of the list (if it exists).
		Analysis: Time = O(1) */
	public void goFirst()
	{
		prev = null;
		cur = list.firstNode; // first node is set as current node
	}

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

		if (before())
			goFirst();
		else
		{
			prev = cur;  // current node becomes new previous node
			cur = cur.nextNode();   // next node becomes current node
		}
	}

	/**	Move to before the first item.
		Analysis: Time = O(1) */
	public void goBefore()
	{
		prev = null;
		cur = null;
	}

	/**	Move to after the last item.
		Analysis: Time = O(n), n = length of the list */
	public void goAfter()
	{
		if (before())
			goFirst();
		while (!after())
			goForth();
	}
}