binarytreeuos.java

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

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

package dslib.tree;

import dslib.exception.*;
import dslib.dictionary.DictUos;
import dslib.base.*;
import dslib.dispenser.LinkedStackUos;

/**	A BasicBinaryTreeUos with additional Dictinary functions, 
	including both linear and binary iterator capabilities.  The 
	new features include insertLeafLeftGo, insertLeafRightGo, 
	and with respect to the current position, leftSubtree and 
	rightSubtree.  It inherits the dictionary functions has, 
	delete, insert, obtain, and frequency, as well as the iterator 
	functions goFirst, goRoot, goForth, goLeft, goRight, 
	before, above, below, and after.  Once a linear iterator is 
	initiated, changes to the tree should not be made until the iteration 
	is complete.  Doing so would mess up the stack used for linear 
	iteration and undesirable results would be obtained. */
public class BinaryTreeUos extends BasicBinaryTreeUos implements DictUos, BinaryIteratorUos
{
	/**	The current for tree iteration. */
	protected BinaryNodeUos cur;

	/**	The parent of the current node for iteration */
	protected BinaryNodeUos parent;

	/**	Nodes that keep current position for linear traversal. */
	protected BinaryNodeUos linCur;

	/**	Should searching be continued from the current item?. */
	protected boolean searchesContinue = false;

	/**	Compare object references or object contents; default contents. */
	protected boolean objectReferenceComparison = false;

	/**	Constructor:  make lt, r, and rt the left subtree, root item and right subtree,
		respectively (lt and/or rt can be null for an empty subtree). <br>
		Analysis: Time = O(1) <br>
		@param lt tree to initialize as the left subtree
		@param r item to initialize as the root
		@param rt tree to initialize as the right subtree */
	public BinaryTreeUos(LinkedSimpleTreeUos lt, Object r, LinkedSimpleTreeUos rt) 
	{
		super(lt, r, rt);
	}

	/**	Make an empty tree. <br> 
		Analysis: Time = O(1)  */
	public BinaryTreeUos()
	{
		super();
	}

	/**	Is there a current item?. <br> 
		Analysis: Time = O(1) */  
	public boolean itemExists()
	{
		return (!above() && !below());
	}
	
	/**	The current item. <br> 
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			itemExists() 
		</ul> */
	public Object item() throws NoCurrentItemUosException
	{
		if (!itemExists())
		   throw new NoCurrentItemUosException("A current item must exist.");  
	
		return cur.item();
	}
	
	/**	Is there a current linear item?. <br> 
		Analysis: Time = O(1) */
	public boolean linearItemExists()
	{
		return linCur!=null;
	}
	  
	/**	The current item for linear iteration. <br> 
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			linearItemExists() 
		</ul> */
	public Object linearItem() throws NoCurrentItemUosException
	{
	   	if (!linearItemExists())
		  	throw new NoCurrentItemUosException("A current item must exist.");  
		
		return linCur.item();
	}

	/**	Set contents of current node to x. <br> 
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			itemExists() 
		</ul> 
		@param x item to become the current item */
	public void setItem(Object x) throws NoCurrentItemUosException
	{
		if (!itemExists())
		  	throw new NoCurrentItemUosException("A current item must exist.");  
		
		cur.setItem(x);
	}

	/**	Test whether x equals y using the current comparison mode. <br> 
		Analysis: Time = O(1) 
		@param x item to be compared to y
		@param y item to be compared to x */
	public boolean membershipEquals(Object x, Object y)
	{
		if (objectReferenceComparison)
			return x==y;
		else if ((x instanceof Comparable) && (y instanceof Comparable))	    	      
			return  0==((Comparable)x).compareTo((Comparable)y);
		else if (x.equals(y))
			return true;
		else 
			return false;
	}

	/**	Set comparison operations to use compareTo or equals. 
		This is the default. <br>
		Analysis: Time = O(1) */
	public void compareContents()
	{
		objectReferenceComparison = false;
	}
  
	/**	Set comparison operations to use '=='.  <br>
		Analysis: Time = O(1) */
	public void compareObjectReferences()
	{
		objectReferenceComparison = true;
	}

	/**	Set searches to continue from current item. <br> 
		Analysis: Time = O(1) */
	public void resumeSearches() 
	{
		searchesContinue = true; 
	}

	/**	Set searches to always start over. <br>
		Analysis: Time = O(1) */
	public void restartSearches() 
	{
		searchesContinue = false; 
	}

	/**	Return the current position. <br>
		Analysis: Time = O(1) */
	public CursorUos currentPosition() 
	{
		return new LinkedBinaryIteratorUos(this, parent, cur);
	}

	/**	Go to position c. <br> 
		Analysis: Time = O(1) 
		@param c position to become the current position */
	public void goPosition(CursorUos c)
	{
		LinkedBinaryIteratorUos lbi = (LinkedBinaryIteratorUos)c;      
		parent = lbi.parent;
		cur = lbi.cur;
	}

	/**	Preorder search for x from curNode updating prev. <br> 
		Analysis: Time = O(n), where n = number of items in (sub)tree 
		@paracurrentPositionm x item being sought
		@param pos iterator position from which to search */
	protected void searchFromPosition(Object x, LinkedBinaryIteratorUos pos) 
	{
		if (pos.above())
			pos.goRoot();
		if (pos.below() || membershipEquals(x, pos.item()))
			goPosition(pos);
		else
		{
			LinkedBinaryIteratorUos savePos = (LinkedBinaryIteratorUos)pos.clone();
			pos.goLeft();
			searchFromPosition(x,pos);
			if (!itemExists())
			{
				savePos.goRight();
				searchFromPosition(x,savePos);
			}
		}
	}

	/**	Move to item x (in a subtree if searchesContinue) <br>
		Analysis: Time = O(n), where n = number of items in (sub)tree 
		@param x item being sought */
	public void search(Object x)
	{
		if (!searchesContinue || above())
		{
			searchFromPosition(x, newIterator());
		}
		else if (below())
			;
		else
		{
			LinkedBinaryIteratorUos c = (LinkedBinaryIteratorUos)currentPosition();
			goLeft();
			searchFromPosition(x, (LinkedBinaryIteratorUos)currentPosition());
			if (!itemExists())
			{
				goPosition(c);
				c.goRight();
				searchFromPosition(x, c);
			}
		}
	}

	/**	Does the tree contain x?. <br> 
		Analysis: Time = O(n), where n = number of nodes in tree
		@param x item to be determined whether it is in the tree */
	public boolean has(Object x)
	{
		LinkedBinaryIteratorUos savePos = (LinkedBinaryIteratorUos)currentPosition();
		search(x);
		boolean result = itemExists();
		goPosition(savePos);
		return result;
	}

	/**	Return first instance of x (next one if searches continue). <br> 
		Analysis: Time = O(n), where n = number of items in the tree 
		PRECONDITION: <br>
		<ul>
			has(x) 
		</ul> 
		@param item to be obtained from the tree */
	public Object obtain(Object x) throws ItemNotFoundUosException
	{
		if (!has(x))
			throw new ItemNotFoundUosException("Cannot return an item that does not exist.");
			
		LinkedBinaryIteratorUos savePos = (LinkedBinaryIteratorUos)currentPosition();
		search(x);
		Object result = item();
		goPosition(savePos);
		return result;
	}

	/**	The tree formed by the left subtree. The cursor for the subtree that
		is returned is positioned above the structure. <br> 
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			!isEmpty()
		</ul> */
	public SimpleTreeUos rootLeftSubtree() throws ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot return a subtree of an empty tree.");
			
		BinaryTreeUos result = (BinaryTreeUos)super.rootLeftSubtree();
		result.goAbove();
		return result;
	}

	/**	The tree formed by the right subtree. The cursor for the subtree that
		is returned is positioned above the structure. <br> 
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			!isEmpty()
		</ul> */ 
	public SimpleTreeUos rootRightSubtree() throws ContainerEmptyUosException
	{	
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot return a subtree of an empty tree.");
			
		BinaryTreeUos result = (BinaryTreeUos)super.rootRightSubtree();
		result.goAbove();
		return result;
	}

	/**	Left subtree of the current item. <br> 
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			itemExists() 
		</ul> */
	public BinaryTreeUos leftSubtree() throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("A current item must exist.");     
		
		BinaryTreeUos result = (BinaryTreeUos)this.clone();
		result.setRootNode(cur.leftNode());
		result.goAbove();
		return result;
	}

	/**	Right subtree of the current item. <br> 
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			itemExists() 
		</ul> */
	public BinaryTreeUos rightSubtree() throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("A current item must exist.");     
		
		BinaryTreeUos result = (BinaryTreeUos)this.clone();
		result.setRootNode(cur.rightNode());
		result.goAbove();
		return result;
	}

	/**	Insert x as new root item up to the left of old root. <br> 
		Analysis: Time = O(1) 
		@param x item to be inserted as the new root */
	public void insertRootLeft(Object x) 
	{
		super.insertRootLeft(x);
		if (cur!=null && cur==rootNode.rightNode())
			parent = rootNode;
	}

	/**	Insert x as new root item up to the right of old root. <br> 
		Analysis: Time = O(1) 
		@param x item to be inserted as the new root */
	public void insertRootRight (Object x) 
	{
		super.insertRootRight(x);
		if (cur!=null && cur==rootNode.leftNode())
			parent = rootNode;
	}

	/**	Insert x as new root item up the right of old root. <br> 
		Analysis: Time = O(1) 
		@param x item to be inserted as the new root */
	public void insertRoot(Object x) 
	{
		insertRootRight(x);
	}
  
	/**	Insert x as new root item up the right of old root. <br> 
		Analysis: Time = O(1)
		@param x item to be inserted as the new root */
	public void insert(Object x) 
	{
		insertRootRight(x);
	}

	/**	Insert x as a new leaf item below and left, and make it current. <br> 
		Analyis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			(below() || leftSubtree().isEmpty()) 
		</ul> 
		@param x item to be inserted as the new left leaf */
	public void insertLeafLeftGo(Object x) throws InvalidArgumentUosException
	{
		if (!(below() || leftSubtree().isEmpty()))
			throw new InvalidArgumentUosException("Cannot do leaf insertion because not at valid insertion point.");
						
		if (isEmpty())
		{
			insert(x);
			goRoot();
		}
		else
		{
			if (!below())
				goLeft();
			cur = createNewNode(x);
			parent.setLeftNode(cur);
		}
	}

	/**	Insert x as a new leaf item below and right, and make it current. <br> 
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			(below() || rightSubtree().isEmpty()) 
		</ul> 
		@param x item to be inserted as the new right leaf */
	public void insertLeafRightGo(Object x) throws InvalidArgumentUosException
	{
		if (!(below() || rightSubtree().isEmpty()))
			throw new InvalidArgumentUosException("Cannot do leaf insertion because not at valid insertion point.");
					
		if (isEmpty())
		{
			insert(x);
			goRoot();
		}
		else
		{
			if (!below())
				goRight();
			cur = createNewNode(x);
			parent.setRightNode(cur);
		}
	}

	/**	Insert x above and left of current item and make x current item. <br> 
		Analysis: Time = O(1) <br>