orderedbilinkedlistuos.java

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

/* OrderedBilinkedListUos.java
 * ---------------------------------------------
 * Copyright (c) 2001 University of Saskatchewan
 * All Rights Reserved
 * --------------------------------------------- */

package dslib.list;

import dslib.exception.*;

/**	An ordered bilinked list.  Items in the list must be Comparable.
	The object's position in the list is provided by the Comparable object. */
public class OrderedBilinkedListUos extends BilinkedListUos
{
	/**	Constructs a new, empty list. <br>
		Analysis: Time = O(1) */
	public OrderedBilinkedListUos()
	{
		super();
	}

	/**	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 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");

		BilinkedIteratorUos savedPos = (BilinkedIteratorUos) 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 before 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: " + prev.item() + " " + x);	
			
		super.insertPriorGo(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 after the current position */
	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 at the end 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("Cannot insert an item that is not comparable");
		if (((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
		PRECONDITION: <br>
		<ul>
			x instanceof Comparable <br>
		</ul> 
		@param x item to search for */
	public void search(Object x) throws ItemNotComparableUosException
	{
		if (!(x instanceof Comparable))
			throw new ItemNotComparableUosException("Item to search for must be Comparable");
		
		if (objectReferenceComparison)
		{
			// perform a search based upon object reference comparison
			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 position 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 (isEmpty())
			goAfter();
		else if (!itemExists())
		{
			if (!searchesContinue | before())
				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 first occurrence */
				;
		}
		while (itemExists() && (x.compareTo(item())>0))
			goForth();
	}
	
	/**	Set the list to new list preceeded by first item. <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 ContainerEmptyUosException, InvalidArgumentUosException
	{
		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 new list.  
		Analysis: Time = O(1)
		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 NoCurrentItemUosException, InvalidArgumentUosException
	{
		if (!itemExists()) 
			throw new NoCurrentItemUosException("Cannot set the remainder of item() since it does not exist");
		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);
	}
}