htbaldictuos.java

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

/* HtBalDictUos.java
 * ---------------------------------------------
 * Copyright (c) 2001 University of Saskatchewan
 * All Rights Reserved
 * -------------------------------------------- */
package dslib.dictionary.bintree;

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

/**	A complete dictionary implemented by means of a height balanced
	binary tree. */
public class HtBalDictUos extends HtBalBasicDictUos implements DictUos
{

	/**	The current node for searching and iteration */
	protected HtBalNodeUos cur;

	/**	The parent of the current node */
	protected HtBalNodeUos parent;
	
	/**	Stack to store a pair of interior nodes during iteration */
	protected LinkedStackUos theStack;
	
	/**	Do searches continue? Default: false */
	public boolean searchesContinue = false;

	/**	Create a new HtBalDictUos that is a bag. <br>
		Analysis: Time = O(1) */
	public HtBalDictUos()
	{
		super();
	}
	
		/**	The current item. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			itemExists()
		</ul> */
	public Object item() throws  ContainerEmptyUosException
	{
		if (!itemExists())
			throw new ContainerEmptyUosException("No Current Item.");

		return cur.item();
	}

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

	/**	Is the current position before the start of the structure?. <br>
		Analysis: Time = O(1) */
	public boolean before()
	{
		return (cur == null) && (parent == null);
	}

	/**	Is the current position after the end of the structure?. <br>
		Analysis: Time = O(1) */
	public boolean after()
	{
		return (cur == null) && (parent != null || isEmpty());
	}

	/**	Move to the next instance of x; first instance if not searchesContinue. <br> 
		Analysis: Time = O(log n), n = the number of items in the dictionary 
		@param x The item to search for */ 
	public void search(Object x)
	{
		if (!searchesContinue || before())
		{
			if (isEmpty())
				goAfter();
			else
			{
				/* move to the occurance of x closest to the root */
				goRoot();
				Comparable compX = (Comparable) x;
				while (!after() && !membershipEquals(item(), x)) 
				{
					if (compX.compareTo(item()) < 0)	
						goLeft();
					else
						goRight();
				}

				/* if an x occurs in left subtree, it is earlier */ 
				if (!after())
				{
					/* subtreeNode moves ahead looking for another occurance
					 of x, and the cursosr catcges up when one is found. */ 
					HtBalNodeUos subtreeNode = (HtBalNodeUos) cur.leftNode();
					while (subtreeNode != null)
					{
						if (compX.compareTo(subtreeNode.item()) == 0)
						{
							goLeft();
							while (cur != subtreeNode)
								goRight();
							subtreeNode = (HtBalNodeUos) cur.leftNode();				
						}
						else
						{
							subtreeNode =  (HtBalNodeUos) subtreeNode.rightNode();
						}
					}
				}
			}
		} 
		else
		{
			if (!after())
				goForth();

			while (!after() && !(((Comparable)item()).compareTo(x) >= 0))
				goForth();

			if (!after() && (((Comparable)item()).compareTo(x)>0))
				goAfter();
		}
		
	}	


	
	/**	Delete the item x from the dictionary. <br> 
		Analysis: Time = O(log n), n = the number of items in the dictionary 
		@param x The item to delete */
	public void delete(Object x)
	{
		if (! itemExists())
			super.delete(x);
		else if (((Comparable)x).compareTo(item())!=0)
		{
			super.delete(x);
			search(item());
		}
		else
			deleteItem();
	}

	/**	Delete the current item and move to it's successor. <br>
		Analysis: Time = O(log n), n = the number of items in the dictionary */
	public void deleteItem()
	{
		HtBalNodeUos delNode = cur, nextNode;
		
		if ((cur.leftNode() != null) && (cur.rightNode() != null))
			/*The sucessor item will be moved to this node. */
			nextNode = cur;
		else
		{
			goForth();
			nextNode = cur;
		}
		boolean done = deleteNodeWithParentUpdate(delNode, null);
		if (nextNode != null)
			searchForNode(nextNode);
		else
			goAfter();
	}

	/**	Remove all the items from the dictionary. <br>
		Analysis: Time = O(1) */
	public void wipeOut()
	{
		cur = null;
		parent = null;
		theStack = null;
		super.wipeOut();
	}

	/**	Move to the first item in the dictionary. <br>
		Analysis: Time = O(log n), n = the number of items in the dictionary */
	public void goFirst()
	{
		if (isEmpty())
			goAfter();
		else
		{
			goRoot();
			while (cur.leftNode() != null)
				goLeft();
		}
	}

	/**	Move to the next item in the dictionary. <br>
		Analysis: Time = O(log n), n = the number of items in the dictionary */
	public void goForth()
	{
		if (before())
			goFirst();
		else if (cur.rightNode() != null)
		{
			goRight();
			while (cur.leftNode() != null)
				goLeft();
		}
		else if (theStack.isEmpty())
			goRight();
		else
		{
			PairUos pair = (PairUos) theStack.item();
			theStack.deleteItem();
			parent = (HtBalNodeUos) pair.firstItem();
			cur = (HtBalNodeUos) pair.secondItem();
		}
	}

	/**	Move before the first item in the dictionary. <br>
		Analysis: Time = O(1) */
	public void goBefore()
	{
		cur = null;
		parent = null;
	}

	/**	Move to the last item in the dictionary. <br>
		Analysis: Time = O(log n) n = number of items in the dictionary <br>
		PRECONDITION: <br>
		<ul>
			!isEmpty()
		</ul> */
	public void goLast() throws ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot go last in an empty dictionary");

		goRoot();
		while (cur.rightNode() != null)
			goRight();
	}

	/**	Move after the last item in the dictionary. <br> 
		Analysis: Time = O(log n) n = the the number of items in the dictionary */
	public void goAfter()
	{
		if (isEmpty())
			goBefore();
		else
		{
			goLast();
			goForth();
		}
	}

	/**	Move to the root of the tree. <br>
		Analysis: Time = O(1) */
	public void goRoot()
	{
		theStack = new LinkedStackUos();
		parent = null;
		cur = rootNode;
	}

	/**	Move to the left in the tree, saving current to be reached later in order. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			itemExists()
		</ul> */
	public void goLeft() throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("Cannot go left when there is no current item");

		PairUos newPair = new PairUos(parent, cur);
		theStack.insert(newPair);
		parent = cur;
		cur = (HtBalNodeUos) cur.leftNode();
	}

	/**	Move to the right in the tree, finished with current item. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			itemExists()
		</ul> */
	public void goRight() throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("Cannot go right when there is no current item");

		parent = cur;
		cur = (HtBalNodeUos) cur.rightNode();
	}

	/**	Search for searchNode in the rep tree. <br>
		Analysis: Time = O(log(n) + d) n = number of elements in the dictionary
		d = number of items equal to searchNode.item() */
	public void searchForNode(HtBalNodeUos searchNode)
	{
		goBefore();
		search(searchNode.item());
		while (searchNode != cur)
			goForth();
	}

	/**	The current position. <br>
		Analysis: Time = O(1) */
	public CursorUos currentPosition()
	{
		if(theStack != null)
			return new OrderedDictCursorUos(cur, parent, ((LinkedStackUos)theStack.clone()));
		else 
			return new OrderedDictCursorUos(cur, parent, null);
	}

	/**	Move to the specified position. <br>
		Analysis: Time = O(1) 
		@param pos The position to move to */
	public void goPosition(CursorUos pos)
	{
		OrderedDictCursorUos oPos = (OrderedDictCursorUos) pos;
		cur = oPos.cur;	
		parent = oPos.parent;
		theStack = oPos.theStack;
	}

	/**	Restart searches after each call to search. <br>
		Analysis: Time = O(1) */
	public void restartSearches()
	{
		searchesContinue = false;	
	}

	/**	Resume searches after each call to search. <br>
		Analysis: Time = O(1) */
	public void resumeSearches()
	{
		searchesContinue = true;
	}

	/**	Is the dictionary full? Answer is always no. <br>
		Analysis: Time = O(1) */
	public boolean isFull()
	{
		return false;
	}

	/**	Are the two objects equal?. <br>
		Analysis: Time = O(1) */
	public boolean membershipEquals(Object x, Object y)
	{
		return ((Comparable)x).compareTo(y)==0;
	}

	/**	How times does x appear in the dictionary?. <br>
		Analysis: Time = O(log(n) + d) n = the number of items in the dictionary
		d = the number of occurences of x */
	public int frequency(Object x)
	{
		CursorUos savedPos = currentPosition();
		boolean searchMethod = searchesContinue;
		int result = 0;

		restartSearches();
		search(x);
		resumeSearches();
		while (itemExists())
		{
			result++;		
			search(x);
		}
		
		searchesContinue = searchMethod;
		goPosition(savedPos);
		return result;
	}

	protected boolean objectReferenceComparison = false;
	
	public void compareObjectReferences()
	{
		objectReferenceComparison = true;
	}

	public void compareContents()
	{
		objectReferenceComparison = false;
	}
		

}