orderedlinkedlistuos.java

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

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

import dslib.exception.*;

/**	A LinkedListUos of ordered items. It has the features of a
	linked list including those of an iterated dictionary such as
	has, obtain, search, goFirst, goForth, etc. It also has the
	added procedures insertGoPosition. */
public class OrderedLinkedListUos extends LinkedListUos 
{
	/**	Construct an empty list that allows duplicates. <br>  
		Analysis: Time = O(1) */	
	public OrderedLinkedListUos()
	{
		super();
	}
	
	/**	Insert x into the list. If current item equals x and searchesContinue, 
		then insert prior to the current item, else in front of any duplicate items. <br> 
		Analysis: Time = O(n), where n = number of nodes in list <br> 
		PRECONDITION: <br>
		<ul>
			x instanceof Comparable 
		</ul> 
		@param x item to be inserted */
	public void insert(Object x) throws ItemNotComparableUosException
	{
		if (!(x instanceof Comparable))
			throw new ItemNotComparableUosException("An insertion item must be Comparable");
			
		LinkedIteratorUos savedPos = (LinkedIteratorUos) currentPosition();

		orderedPositionSearch((Comparable)x);
		if (currentPosition().equals(savedPos))
		{
			insertPriorGo(x);
			goForth();
		}
		else
		{
			insertPriorGo(x);
			goPosition(savedPos);
		}
	}
	
	/**	Insert x and go to it. <br> 
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			x instanceof Comparable 
		</ul> 
		@param x item to be inserted */
	public void insertGo(Object x) throws ItemNotComparableUosException
	{
		if (!(x instanceof Comparable))
			throw new ItemNotComparableUosException("An insertion item must be Comparable");
					
		orderedPositionSearch((Comparable)x);
		insertPriorGo(x);
	}

	/**	Insert x before the current position and make it current item. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			x instanceof Comparable <br>
			!(itemExists() && (((Comparable)item()).compareTo(x)<0)) <br>
			!((prev!=null) && (((Comparable)prev.item()).compareTo(x)>0))
		</ul>
		@param x item to be inserted prior to the current position */
	public void insertPriorGo(Object x) throws ItemNotComparableUosException, InvalidArgumentUosException 
	{
		if (!(x instanceof Comparable))
			throw new ItemNotComparableUosException("An insertion item must be Comparable");
		if (itemExists() && (((Comparable)item()).compareTo(x)<0))
			throw new InvalidArgumentUosException("This insertion will destroy the list's ordering.");	
		if ((prev!=null) && (((Comparable)prev.item()).compareTo(x)>0))
			throw new InvalidArgumentUosException("This insertion will destroy the list's ordering.");	
		
		super.insertPriorGo(x);
	}
	
	/**	Insert x as the first item of the list. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			x instanceof Comparable <br>
			!(!isEmpty() && ((Comparable)firstItem()).compareTo(x)<0) 		   
		</ul>
		@param x item to be inserted at the front of the list */
	public void insertFirst(Object x) throws ItemNotComparableUosException, InvalidArgumentUosException 
	{
		if (!(x instanceof Comparable))
			throw new ItemNotComparableUosException("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);
	}

	/**	Insert x after the current item. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			x instanceof Comparable <br>
			!(itemExists() && ((Comparable)item()).compareTo(x)>0) <br>
			!(itemExists() && (cur.nextNode()!=null) && ((Comparable)cur.nextNode().item()).compareTo(x)<0)
		</ul>
		@param x item to be inserted in the next position in the list */
	public void insertNext(Object x) throws ItemNotComparableUosException, InvalidArgumentUosException 
	{
		if (!(x instanceof Comparable))
			throw new ItemNotComparableUosException("An insertion item must be Comparable");
		if (itemExists() && ((Comparable)item()).compareTo(x)>0)
			throw new InvalidArgumentUosException("This insertion will destroy the list's ordering."); 	
		if (itemExists() && (cur.nextNode()!=null) && ((Comparable)cur.nextNode().item()).compareTo(x)<0)
			throw new InvalidArgumentUosException("This insertion will destroy the list's ordering."); 	
		
		super.insertNext(x);
	}
	
	/**	Insert x as the last item of the list. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			x instanceof Comparable <br>
			!(!isEmpty() && ((Comparable)lastItem()).compareTo(x)>0)
		</ul>
		@param x item to be inserted at the end of the list */
	public void insertLast(Object x) throws ItemNotComparableUosException, InvalidArgumentUosException  
	{
		if (!(x instanceof Comparable))
			throw new ItemNotComparableUosException("An insertion item must be Comparable");
		if (!isEmpty() && ((Comparable)lastItem()).compareTo(x)>0)
			throw new InvalidArgumentUosException("Inserting a smaller item at the rear will destroy the list's ordering."); 	
		
		super.insertLast(x);
	}
	  
	/**	Move to the position of first x or move to the next x if searchesContinue.
		Move after list if not found. <br>  
		Analysis: Time = O(n), where n = number of items in the list <br>
		PRECONDITION: <br>
		<ul>
			x instanceof Comparable 
		</ul> 
		@param x item to search for */
	public void search(Object x) throws ItemNotComparableUosException
	{
		if (!(x instanceof Comparable))
			throw new ItemNotComparableUosException("Can only search for items of type Comparable");
		
		if (objectReferenceComparison)
		{
			if (!searchesContinue)
				goFirst();
			else if (!after())
				goForth();

			while((!after()) && (!membershipEquals(item(), x)))
				goForth();
		}
		else
		{
			orderedPositionSearch((Comparable)x);
			if ((itemExists()) && !membershipEquals(x, item()))
				goAfter();
		}
	}
	
	/**	Move to the position of first x (next x if searchesContinue)
		or if not found, stop at the position of the first larger item. <br> 
		Analysis: Time = O(n), where n = number of nodes in list
		@param x item to search for */
	public void orderedPositionSearch(Comparable x)
	{
		if (!itemExists())
		{
			if (prev!=null && (searchesContinue || (x.compareTo(prev.item())>0)))	
				; // already at the position
			else
				goFirst();
		}
		else if (((Comparable)item()).compareTo(x)<0)
			/* continue searches from here */ 
			;
		else if (x.compareTo(item())<0)
		{
			if (searchesContinue)
				/* any occurrences are earlier but not restarting searches */ 
				;
			else if (prev==null || (x.compareTo(prev.item())>0))	
				/* already at the position after where it would be */ 
				;
			else
				goFirst();
		}
		else // x.compareTo(item()) == 0
		{
			if (searchesContinue)
				goForth();
			else if (prev!=null && (x.compareTo(prev.item())==0) )
				/* need to start over to find first occurrence */
				goFirst(); 
			else
				/* already at the first occurence */
				; 
		}

		while (itemExists() && (x.compareTo(item())>0))
			goForth();
	}
	
	/**	Set the list to be newList preceded by firstItem. <br> 
		Analysis: Time = O(1) <br>
		PRECONDITION:  <br>
		<ul>
			!isEmpty() <br>
			!(((Comparable)firstItem()).compareTo(((LinkedListUos)newList).firstItem())>0) <br>
		</ul>
		@param newList The list to replace firstRemainder() */
	public void setFirstRemainder(BasicListUos newList) throws InvalidArgumentUosException, ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot set the first remainder of an empty list");
		if (((Comparable)firstItem()).compareTo(((LinkedListUos)newList).firstItem())>0)
			throw new InvalidArgumentUosException("Inserting a larger item at the front will destroy the list's ordering."); 	
		
		super.setFirstRemainder(newList);
	}
	
	/**	Set the list following the current position to newList. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION:  <br>
		<ul>
			itemExists() <br>
			!(itemExists() && ((Comparable)item()).compareTo(((LinkedListUos)newList).firstIitem())>0) 
		</ul>
		@param newList list that is set to the remainder of the current list */
	public void setRemainder(BasicListUos newList) throws InvalidArgumentUosException, NoCurrentItemUosException 
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("There is no current item to set the remainer for");
		if (itemExists() && ((Comparable)item()).compareTo(((LinkedListUos)newList).firstItem())>0)
			throw new InvalidArgumentUosException("Setting remainder to newList will destroy the list's ordering."); 	
		
		super.setRemainder(newList);
	}
}