bilinkedlistuos.java

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

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

import dslib.base.*;
import dslib.exception.*;

/**	This list class incorporates the functions of an iterated 
	dictionary such as has, obtain, search, goFirst, goForth, 
	deleteItem, etc.  It also has the capabilities to iterate backwards 
	in the list, goLast and goBack. */
public class BilinkedListUos extends LinkedListUos implements BilinearIteratorUos
{
	/* 	Note that because firstRemainder() and remainder() should not cut links of the original list,
		the previous node reference of firstNode is not always correct.
		Also, the instance variable prev is generally kept up to date, but may not always be correct.  
		Use previousNode() instead! */

	/**	Construct an empty list. <br>
		Analysis: Time = O(1) */
	public BilinkedListUos()
	{
		super();
	}

	/**	Create a BilinkedNodeUos this Bilinked list.  This routine should be
		overridden for classes that extend this class that need a specialized node. <br>
		Analysis: Time = O(1) */
	public LinkedNodeUos createNewNode(Object item)
	{
		return new BilinkedNodeUos(item);
	}

	/**	Insert x as the first item of the list. <br>
		Analysis: Time = O(1) 
		@param x item to be inserted at the front of the list */
	public void insertFirst(Object x) 
	{
		super.insertFirst(x);
		if (firstNode.nextNode() != null)
		{
			BilinkedNodeUos oldFirst = (BilinkedNodeUos) firstNode.nextNode();
			oldFirst.setPreviousNode((BilinkedNodeUos)firstNode);
		}
	}

	/**	Insert x as the first item in the list. <br>
		Analysis: Time = O(1)
		@param x item to be inserted in the list */
	public void insert(Object x) 
	{
		insertFirst(x);
	}

	/**	Insert x before the current position and make it current item. <br>
		Analysis: Time = O(1)
		@param x item to be inserted before the current position */
	public void insertPriorGo(Object x) 
	{
		if (isEmpty() || before() || (cur==firstNode))
		{
			insertFirst(x);
			goFirst();
		}
		else
		{	 
			BilinkedNodeUos  temp = (BilinkedNodeUos)createNewNode(x);
			prev.setNextNode(temp); // set the pointer to the new node
			temp.setNextNode(cur);
			temp.setPreviousNode((BilinkedNodeUos)prev);
			if (cur!=null)
				((BilinkedNodeUos)cur).setPreviousNode(temp);
			cur = temp;
			if (prev==lastNode)
				lastNode = cur;
		}
	}

	/**	Insert x after the current item. <br>
		Analysis: Time = O(1) 
		@param x item to be inserted after the current position */
	public void insertNext(Object x) 
	{
		if (isEmpty() || before())
			insertFirst(x); 
		else if (cur==lastNode())
			insertLast(x); 
		else if (after()) // if after then have to deal with previous node  
		{
			insertLast(x); 
			cur = prev.nextNode();
		}
		else // in the list, so creat a node and set the pointers to the new node 
		{
			BilinkedNodeUos temp = (BilinkedNodeUos)createNewNode(x);
			temp.setNextNode(cur.nextNode());
			temp.setPreviousNode((BilinkedNodeUos)cur);
			((BilinkedNodeUos) cur.nextNode()).setPreviousNode(temp);	  
			cur.setNextNode(temp);
		}
	}

	/**	Insert x at the end of the list. <br>
		Analysis: Time = O(1)
		@param x item to be inserted at the end of the list */
	public void insertLast(Object x) 
	{
		if (isEmpty())
			insertFirst(x); 
		else	// make a new node and insert it at after the last node
		{
			BilinkedNodeUos temp = (BilinkedNodeUos) createNewNode(x);
			lastNode.setNextNode(temp); 
			temp.setPreviousNode((BilinkedNodeUos)lastNode);
			if (after()) 
				prev = lastNode;
			lastNode = temp;
		}      	
	}

	/**	Delete the current item. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			itemExists() 
		</ul> */
	public void deleteItem() throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("Cannot delete an item that does not exist.");            
		
		if (cur==firstNode)
			deleteFirst(); 
		else // have to delete the node from the list and update the pointers of prev and cur 
		{ 
			prev = ((BilinkedNodeUos)cur).previousNode();
			prev.setNextNode(cur.nextNode());
			if(cur.nextNode()!=null)
				((BilinkedNodeUos) cur.nextNode()).setPreviousNode((BilinkedNodeUos)prev);
			if (cur==lastNode)
				lastNode = prev;
			cur = cur.nextNode();
		}     
	}

	/**	Delete the first item. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION:  <br>
		<ul>
			!isEmpty() 
		</ul> */
	public void deleteFirst() throws ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot delete an item from an empty list.");
		
		super.deleteFirst(); 
		if (!isEmpty())
			((BilinkedNodeUos)firstNode).setPreviousNode(null);
	}

	/**	Delete last item. <br> 
		Analysis: Time = O(1) <br> 
		PRECONDITION: <br>
		<ul>
			!isEmpty() 
		</ul> */
	public void deleteLast() throws ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot delete last item of an empty list.");
		
		if (firstNode==lastNode)
			deleteFirst(); 
		else // delete the last node and update prev and cur if necessary
		{ 
			if (prev==lastNode())
				prev = ((BilinkedNodeUos)lastNode()).previousNode();	 
			else if (cur==lastNode)
				cur = null;
			lastNode = ((BilinkedNodeUos)lastNode).previousNode();	  
			
			if (lastNode!=null)
				lastNode.setNextNode(null);
		}
	}

	/**	Set the list to new list preceeded by first item. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			!isEmpty() 
		</ul>
		@param rem the replacement list for firstRemainder() */
	public void setFirstRemainder(BasicListUos newList) throws ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot perform setFirstRemainder() on an empty list.");
		
		super.setFirstRemainder(newList);
		if (newList!=null && !newList.isEmpty())
			((BilinkedNodeUos)firstNode.nextNode()).setPreviousNode((BilinkedNodeUos)firstNode);
	}
  
	/**	Set the list following the current position to new list.  
		Analysis: Time = O(1)
		PRECONDITION: <br>
		<ul>
			itemExists() 
		</ul>
		@param newList list that is set to the remainder of the current list */
	public void setRemainder(BasicListUos newList) throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("Cannot perform setRemainder() since there is no current item.");
		
		super.setRemainder(newList);
		if (newList!=null && !newList.isEmpty())
			((BilinkedNodeUos)cur.nextNode()).setPreviousNode((BilinkedNodeUos)cur);
	}
 
	/**	Move to the last item in the list. <br>
		Analysis: Time = O(1) */
	public void goLast()
	{
		cur = lastNode();
		if (cur==null)
			prev = null;
		else
			prev = ((BilinkedNodeUos)cur).previousNode();
	}
  
	/**	Move back one item in the list. <br> 
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			!before() 
		</ul> */
	public void goBack() throws BeforeTheStartUosException
	{
		if (before()) 
			throw new BeforeTheStartUosException("Cannot go back since already before list.");
		
		if (after()) // move to the last node 
			goLast(); 
		else
		{ 
			cur = ((BilinkedNodeUos)cur).previousNode();     
			if (cur!=null)
			{
				if (cur==firstNode)
					prev = null;
				else
					prev = ((BilinkedNodeUos)cur).previousNode();
			}
		}
	}

	/**	Iterator for list initialized to first item. <br>
		Analysis: Time = O(1) */
	public LinearIteratorUos iterator()
	{
		return new BilinkedIteratorUos(this);
	}

	/**	Go to the position in the list specified by c. <br>
		Analysis: Time = O(1) 
		@param c position to which to go */
	public void goPosition(CursorUos c)
	{
		BilinkedIteratorUos lc = (BilinkedIteratorUos)c;      
		cur = (BilinkedNodeUos)lc.cur;
		if (cur!=null)
			prev = ((BilinkedNodeUos)cur).previousNode();
		else
			prev = null;
	}
	
	/**	The current position in this list. <br>
		Analysis: Time = O(1) */
	public CursorUos currentPosition()
	{
		return  new BilinkedIteratorUos(this);
	}


}