orderedsimplelist.java

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

package simple;

/**	This class defines a simple linked list with the items kept in order.
	In addition to the list operations, it has a search operation to move to
	a specific item.  Also, the current item can be accessed or deleted.  */
public class OrderedSimpleList extends LinkedSimpleList
{
	/**	The node previous to the current node. */
	private LinkedNode prev;

	/**	The current node storing the current item. */
	private LinkedNode cur; 

	/**	Create an empty ordered list.
		Analysis : Time = O(1) */
	public OrderedSimpleList()
	{
		super();
		prev = null;
		cur = null;
	}

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

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

	/**	Move to x or else off the list.
		Analysis: Time = O(n) worst case, n = size of the list */
	public void search(Comparable x)
	{
		goToLocation(x);
		if (!itemExists() || (x.compareTo(item()) != 0))
		{
			prev = null;
			cur = null;
		}
	}

	/**	Move to x, or where x would be if it were present.
		Analysis: Time = O(n) worst case, n = size of the list */
	private void goToLocation(Comparable x)
	{
		prev = null;
		cur = firstNode;
		boolean found = false;
		while (!found & (cur != null))
		{
			if (x.compareTo(cur.item) <= 0 )
				found = true;
			else
			{
				prev = cur;
				cur = cur.nextNode;
			}
		}
	}

	/**	Insert x into the list.
		Analysis: Time = O(1) */
	public void insert(Comparable x)
	{
		LinkedNode savePrev = prev;
		LinkedNode saveCur = cur;
		goToLocation(x); // move the location where x would be

		/*	Insert the new node between prev and cur. */
		LinkedNode newNode = new LinkedNode(x);
		if (prev == null)
		{
			newNode.setNextNode(firstNode);
			firstNode = newNode;
		}
		else
		{
			newNode.setNextNode(cur);
			prev.setNextNode(newNode);
		}
		
		/*	Restore prev and cur to refer to the correct current item. */
		if (saveCur == cur)
		{
			/*	The insertion was between the saved prev and cur. */
			cur = saveCur;
			prev = newNode;
		}
		else 
		{
			/*	The correct prev and cur are not affected by the insertion. */
			cur = saveCur;
			prev = savePrev;
		}
	}

	/**	Insert x as the first item of the list. 
		Analysis: Time = O(1)
		PRECONDITION:
			x instanceof Comparable 
			!(!isEmpty() && ((Comparable)firstItem()).compareTo(x) < 0)  */
	public void insertFirst(Object x) throws ItemNotComparableUosException, InvalidArgumentUosException 
	{
		if (!(x instanceof Comparable))
			throw new ItemNotComparableUosException("For an ordered list, an insertion "
					+ "item must be Comparable");
		if (!isEmpty() && ((Comparable)firstItem()).compareTo(x) < 0) 		   
			throw new InvalidArgumentUosException("Inserting a larger item at the front "
					+ "will destroy the list's ordering.");	
		
		super.insertFirst(x);
		if (cur != null && cur == firstNode.nextNode())
			prev = firstNode;
	}

	/**	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 an item from an empty list");
		/*	Make sure that the current item reference is updated, when necessary. */
		if (cur == firstNode) // deleting the current item
			cur = null;	
		else if (prev == firstNode) // deleting the predecessor of the current node
			prev = null;
		super.deleteFirst();
	}

	/**	Delete the current item from the list.
		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 (prev != null)
			prev.setNextNode(cur.nextNode);
		else
			firstNode = cur.nextNode;
		cur = null;
		prev = null;
	}
}