htbalbasicdictuos.java

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

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

package dslib.dictionary.bintree;

import dslib.dictionary.*;
import dslib.tree.*;
import dslib.exception.*;

/**	An ordered dictionary implemented by means of a height-balanced
	binary tree. It has all the BasicDictUos methods:  has,
	obtain, insert, delete, and isEmpty. */
public class HtBalBasicDictUos implements BasicDictUos
{
	/**	Internal representation. */
	protected HtBalNodeUos rootNode; 
	
	
	/**	Set root node to newRoot. <br>
		Analysis: Time = O(1) 
		@param newRoot value assigned to rootNode */
	protected void setRootNode(HtBalNodeUos newRoot) 
	{
		rootNode = (HtBalNodeUos) newRoot;
	}

	/**	Does the current comparison method use '=='? The default is false */
	protected boolean objectReferenceComparison = false;
	        
	/**	Create a new HtBalBasicDictUos that is a bag. <br>
		Analysis: Time = O(1) */
	public HtBalBasicDictUos()
	{
	}

	/**	Return a new node that is appropriate for this tree. <br>
		Analysis: Time = O(1) 
		@param contents The contents of the node that will be returned */
	public HtBalNodeUos createNewNode(Object contents)
	{
		return new HtBalNodeUos(contents);
	}

	/**	Is the dictionary empty. <br>
		Analysis: Time = O(1) */
	public boolean isEmpty()
	{
		return rootNode == null;
	}
	
	/**	Does dictionary contain y. <br> 
		Analysis: Time = O(log(n)), n = the number of items in the dictionary<br>
		PRECONTIION: <br>
		<ul>
			y instanceof Comparable
		</ul>
		@param y The object being sought in the tree */
	public boolean has(Object y) throws ItemNotComparableUosException
	{
		if (!(y instanceof Comparable))
			throw new ItemNotComparableUosException("Cannot search for an item that is not Comparable");

		HtBalTreeIteratorUos c = location((Comparable)y, null);
		if (c.itemExists())
			return true;
		else
			return false;
	}
	
	/**	An instance of y from the dictionary. <br> 
		Analysis: Time = O(log(n)), n = the number of items in the dictionary <br>
		PRECONDITION: <br>
		<ul>
			y instanceof Comparable <br>
			has(y)
		</ul> 
		@param y The object to obtain */
	public Object obtain(Object y) throws ItemNotComparableUosException
	{
		if (!(y instanceof Comparable))
			throw new ItemNotComparableUosException("Items in tree must be Comparable.");
		if (!has(y)) 
			throw new ItemNotFoundUosException("Cannot return an item that does not exist.");
	
		return location((Comparable)y, null).item();
	}

	/**	Is the data structure full. <br>
		Analysis: Time = O(1) */
	public boolean isFull()
	{
		return false;
	}

	/**	String representation of the tree. <br> 
		Analysis: Time = O(n), n = the number of items in the tree */
	public String toString()
	{
		if (isEmpty())
			return new String();
		else
			return rootNode.toString();
	}
	
	/**	Form a string representation that includes level number. <br>
		Analysis: Time = O(n), n = number of items in the (sub)tree 
		@param i The level for the root of the tree */
	public String toStringByLevel(int i) 
	{
		StringBuffer blanks = new StringBuffer((i-1) * 5);

		for (int j = 0; j < i-1; j++)
			blanks.append("    ");
	
		String result = new String();
		if (!isEmpty() && (!rootLeftSubtree().isEmpty() || !rootRightSubtree().isEmpty()))
			result += ((HtBalBasicDictUos)rootRightSubtree()).toStringByLevel(i+1);

		result += "\n" + blanks + i + ": " ;

		if (isEmpty())
			result += "-";
		else 
		{
			result += rootNode.item().toString();
			if (!rootLeftSubtree().isEmpty() || !rootRightSubtree().isEmpty())
				result += ((HtBalBasicDictUos)rootLeftSubtree()).toStringByLevel(i+1);
		}
		return result;
	}

	/**	Insert x into the tree and adjust tree as necessary. <br>
		Analysis: Time = O(log(n)), n = the number of items in the tree <br>
		PRECONDITION: <br>
		<ul>
			x instanceof Comparable 
		</ul> 
		@param x The item to be inserted */
	public void insert(Object x) throws ItemNotComparableUosException
	{
		if (!(x instanceof Comparable))
			throw new ItemNotComparableUosException("Items to be inserted must be Comparable.");
		
		insertWithParentUpdate((Comparable)x, null);
	}

	/**	Delete the item x and adjust tree as necessary. <br>
		Analysis: Time = O(log(n)), n = the number of items in the tree <br> 
		PRECONDITION: <br>
		<ul>
			x instanceof Comparable <br>  
			has(x) 
		</ul> 
		@param x The item to be  deleted*/
	public void delete(Object x) throws ItemNotComparableUosException, ItemNotFoundUosException
	{
		if (!(x instanceof Comparable))
			throw new ItemNotComparableUosException("Item to be deleted must be Comparable.");
		if (!has(x))
			throw new ItemNotFoundUosException("Item to be deleted does not exist.");

		deleteWithParentUpdate((Comparable)x, null);
	}

	/**	Remove all items from the data structure. <br>
		Analysis: Time = O(1) */
	public void wipeOut()
	{
		rootNode = null;
	}       

	/**	Test whether x equals y using the current comparison mode. <br>
		Analysis: Time = O(1) 
		@param x Item to compare to y
		@param y Item to compare 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(y);
  		else if (x.equals(y))
  			return true;
  		else 
  			return false;
	}

	/**	Compare objects using `=='. <br>
		Analysis: Time = O(1) */
	public void compareObjectReferences()
	{
		objectReferenceComparison = true;
	}
	
	/**	Compare object with compareTo if they are Comparable; otherwise
		use equals. <br>
		Analysis: Time = O(1) */
	public void compareContents()
	{
		objectReferenceComparison = false;
	}

	/**	Iterator for the tree initialized to the root item. <br>
		Analysis: Time = O(1) */
	public HtBalTreeIteratorUos newIterator()
	{
		return  new HtBalTreeIteratorUos(this); 
	}

	/**	Return the location of the first occurrence of y starting at curLoc. <br>
		Analysis: Time = O(log(n) + d), n = the number of items in the tree
		d = the number of items equal to y
		@param y The item being sought
		@param curLoc The location at which the search will start */
	protected HtBalTreeIteratorUos location(Comparable y, LinkedBinaryIteratorUos curLoc)
	{
		HtBalTreeIteratorUos result;
		if (curLoc == null || curLoc.above())
			result = newIterator();
		else
			result = (HtBalTreeIteratorUos) curLoc.clone();
	
		boolean found = false;
		while (!found && result.itemExists())
		{
			if (y.compareTo(result.item())<0)
				result.goLeft();
			else if (y.compareTo(result.item())>0)
				result.goRight();
			else if (membershipEquals(y, result.item()))
				found = true;
			else // item can be in left or right subtree
			{
				LinkedBinaryIteratorUos leftIterator = ((LinkedBinaryIteratorUos) result.clone());
				leftIterator.goLeft();
				result = location(y, leftIterator);
				if (result.itemExists())
					found = true;
				else
					result.goRight();
			}
		} 
		return result;     
	}

	/**	The height of the tree. <br>
		Analysis: Time = O(1)     */
	protected int height()
	{
		if (isEmpty())
			return -1;
		else
			return rootNode.height();
	}
	
	/**	Set the height of the rootNode to y. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			!(y < -1 || (!isEmpty() && y == -1)) 
		</ul> 
		@param y The new value for the height */
	protected void setHeight(int y) throws InvalidArgumentUosException
	{
		if (y < -1 || (!isEmpty() && y == -1))
			throw new InvalidArgumentUosException("Cannot set height to an invalid height."); 
	
		if (!isEmpty())
			rootNode.setHeight(y);
	}
	
	/**	Height of the heighest subtree. <br>
		Analysis: Time = O(1) */
	protected int maxSubtreeHeight()
	{
		if (isEmpty())
			return -1;
		else
			return Math.max(rootLeftSubtree().height(), rootRightSubtree().height());
	}
	
	/**	Insert y and correct parent reference. <br>
		Analysis: Time = O(log(n)), n = the number of items in the tree 
		@param y The item to insert
		@param parent The parent of the current root node */
	protected void insertWithParentUpdate(Comparable y, HtBalNodeUos parent)
	{
		if (isEmpty())
		{
			if(parent == null)
				rootNode = createNewNode(y);  
			else
			{
				HtBalNodeUos temp = createNewNode(y);
				if (y.compareTo(parent.item()) < 0)
					parent.setLeftNode(temp);
				else
					parent.setRightNode(temp);