iteratedsimplelist.java

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

package simple;

/**	A LinkedSimpleList class with iterator capabilities.  It keeps track of the current
	item of the list, and has methods to move to the front of the list and to move forward
	in the list.  It also has a function to return an external iterator. */
public class IteratedSimpleList extends LinkedSimpleList implements LinearIterator
{
	/**	The current node storing the current item. */
	protected LinkedNode cur;
   
	/**	Node previous to the current node. */
	protected LinkedNode prev;

	/**	Initialize the list.
		Analysis: Time = O(1) */
	public IteratedSimpleList()
	{
		super();
		cur = null;
		prev = null;
	}

	/**	Insert x as the first item of the list. 
		Analysis: Time = O(1) */
	public void insertFirst(Object x)
	{
		super.insertFirst(x);
		if ((cur != null) && (prev == null))
			prev = firstNode;   // cur was the first node so now it has a predecessor
	}
 
	/**	Delete the first item from the list.
		Analysis: Time = O(1)
		PRECONDITION:
			!isEmpty() */
	public void deleteFirst() throws ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot delete first item from an empty list");

		/*	Correct the references cur and prev to their correct state after the deletion. */
		if (cur == firstNode)
			cur = null;
		else if (prev == firstNode)
			prev = null;
		super.deleteFirst();
	}

	/**	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) || isEmpty());
	}

	/**	Go to first item of the list (if it exists).
		Analysis: Time = O(1) */
	public void goFirst()
	{
		prev = null;
		cur = 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();
	}

	/**	Iterator for the list starting at the present position.
		Analysis: Time = O(1) */
	public LinkedIterator iterator()
	{
		return new LinkedIterator(this, prev, cur);
	}

	/**	Set the current item to x.
		Analysis: Time = O(1) 
		PRECONDITION:
			itemExists() */
	public void setItem(Object x) throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("Cannot set the current item if one does not exist.");

		cur.setItem(x);
	}

	/**	Delete the current item.
		Analysis: Time = O(1) 
		PRECONDITION:
			itemExists() */
	public void deleteItem() throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("Cannot delete the current item if one does not exist.");

		if (cur == firstNode)
		{
			deleteFirst();
			cur = firstNode;
		}
		else
		{
			prev.setNextNode(cur.nextNode());
			cur = cur.nextNode();
		}
	}

	/**	Insert x before the current position and make it current item.
		Analysis: Time = O(1) */
	public void insertPriorGo(Object x)
	{ 
		if ((cur == firstNode) || isEmpty() || before())
		{
			insertFirst(x);
			goFirst();
		}
		else
		{
			LinkedNode temp = new LinkedNode(x);
			prev.setNextNode(temp);
			temp.setNextNode(cur);
			cur = temp;
		}
	}  

	/**	Insert x after the current item.
		Analysis: Time = O(1) */
	public void insertNext(Object x)
	{ 
		if (isEmpty() || before())
			insertFirst(x);
		else if (after())
			insertPriorGo(x);
		else
		{
			LinkedNode temp = new LinkedNode(x);
			temp.setNextNode(cur.nextNode());
			cur.setNextNode(temp);
		}
	}
}