orderedsimpletreeuos.java

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

package dslib.tree;

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

public class OrderedSimpleTreeUos extends LinkedSimpleTreeUos implements DispenserUos, SearchableUos
{
	/**	The curent node as set by search. */
	protected BinaryNodeUos cur;

	/**	The parent node of the current node as set by search. */
	protected BinaryNodeUos parent;

	/**	Do searches continue? */
	protected boolean searchesContinue = false;

	/**	Are equality comparisons done using object reference comparisons? */
	protected boolean objectReferenceComparison = false;

	/**	Create a new OrderedSimpleTree.
		Analysis: Time = O(1) */
	public OrderedSimpleTreeUos()
	{
		super();
	}

	/**	Create a new OrderedSimpleTree.
		Analysis: Time = O(1) */
	public OrderedSimpleTreeUos(OrderedSimpleTreeUos lt, Object r, OrderedSimpleTreeUos rt)
	{
		super(lt, r, rt);
	}
	
	/**	Is there a current node?
		Analysis : Time = O(1) */
	public boolean itemExists()
	{
		return cur != null;
	}

	/**	Contents of the current node.
		Analysis : Time = O(1) 
		PRECONDITION:
			itemExists() */
	public Object item() throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("Cannot access item when it does not exist");

		return cur.item();
	}

	/**	Set contents of the root to x.
		Analysis: Time = O(1)
		PRECONDITION:
			!isEmpty()
			value of x is between those in left subtree and right subtree
			(The second condition of the precondition isn't checked as it is too time consuming.
			Don't use this operation on this class unless the condition is known to hold.) */
	public void setRootItem(Object x) throws ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot set the root of an empty tree.");

		rootNode.setItem(x);
	}

	/**	Go to item x, if it is in the tree.  If searchesContinue, continue in the right subtree.
		Analysis : Time = O(h) worst case, where h = height of the tree
		PRECONDITION: 
			x instanceof Comparable */
	public void search(Object x) throws ItemNotComparableUosException
	{
		if (!(x instanceof Comparable))
			throw new ItemNotComparableUosException("Can only search for Comparable items");

		boolean found = false;
		if (!searchesContinue || above())
		{
			parent = null;
			cur = rootNode;
		}
		else if (!below())
		{
			parent = cur;
			cur = cur.rightNode();
		}
		while (!found && itemExists())
		{
			if (((Comparable)x).compareTo(item()) < 0)
			{
				parent = cur;
				cur = parent.leftNode();
			}
			else if (((Comparable)x).compareTo(item()) > 0)
			{
				parent = cur;
				cur = parent.rightNode();
			}
			else
				found = true;
		}
	}

	/**	Does the tree contain x?
		Analysis : Time = O(h) worst case, where h = height of the tree
		PRECONDITION:
			x instanceof Comparable */
	public boolean has(Object x) throws ItemNotComparableUosException
	{
		if (!(x instanceof Comparable))
			throw new ItemNotComparableUosException("Can only use has for Comparable items");

		BinaryNodeUos saveParent, saveCur;
		saveParent = parent;
		saveCur = cur;
		search(x);
		boolean result = itemExists();
		parent = saveParent;
		cur = saveCur;
		return result;
	}

	/**	Insert x into the tree.
		Analysis : Time = O(h) worst case, where h = height of the tree */
	public void insert(Object x)
	{
		if (isEmpty())
			rootNode = createNewNode(x);
		else if (((Comparable)x).compareTo(rootItem()) < 0)
		{
			OrderedSimpleTreeUos leftTree = (OrderedSimpleTreeUos) rootLeftSubtree();
			leftTree.insert(x);
			setRootLeftSubtree(leftTree);
		}
		else
		{
			OrderedSimpleTreeUos rightTree = (OrderedSimpleTreeUos) rootRightSubtree();
			rightTree.insert(x);
			setRootRightSubtree(rightTree);
		}
	}

	/**	Delete all items from the data structure.
		Analysis : Time = O(1) */
	public void wipeOut()
	{
		super.wipeOut();
		parent = null;
		cur = null;
	}

	/**	Delete the current item, making its replacement the current item.
		Analysis : Time = O(h) worst case, where h = height of the structure
		PRECONDITION:
			itemExists() */
	public void deleteItem() throws NoCurrentItemUosException
	{
		if(!itemExists())
			throw new NoCurrentItemUosException("No current item to delete");

		boolean foundReplacement = false;
		BinaryNodeUos replaceNode = null;

		/*	Test if there is only one child so it can replace the root. */
		if (cur.rightNode() == null)
		{
			replaceNode = cur.leftNode();
			foundReplacement = true;
		}
		else if (cur.leftNode() == null)
		{
			replaceNode = cur.rightNode();
			foundReplacement = true;
		}
		else
			foundReplacement = false;

		if (foundReplacement)
		{
			/*	Set parent node to refer to the replacement node. */
			if (parent == null)
				setRootNode(replaceNode);
			else if (parent.leftNode() == cur)
				parent.setLeftNode(replaceNode);
			else
				parent.setRightNode(replaceNode);
			cur = replaceNode;
		}
		else
		{
			/*	Replace the current item by its inorder successor and
				then delete the inorder successor from its original place. */

			/*	Find the position (replaceParent and replaceCur) of the inorder successor. */
			BinaryNodeUos replaceCur, replaceParent, saveParent, saveCur;
			replaceParent = cur;
			replaceCur = replaceParent.rightNode();
			while (replaceCur.leftNode() != null)
			{
				replaceParent = replaceCur;
				replaceCur = replaceParent.leftNode();
			}

			/*	Replace the current item (to be deleted) by the inorder successor. */
			cur.setItem(replaceCur.item());
			/*	Delete the inorder successor from its original place. */
			saveParent = parent;
			saveCur = cur;
			parent = replaceParent;
			cur = replaceCur;
			deleteItem();
			parent = saveParent;
			cur = saveCur;
		}
	}

	/**	String representation via inorder traversal.
		Analysis : Time = O(n), where n = number of items */
	public String toString()
	{
		if (isEmpty())
			return new String();
		else
			return rootNode.toString();
	}

	/**	Restart searches each time search is called.
		Analysis: Time = O(1) */
	public void restartSearches()
	{
		searchesContinue = false;
	}

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

	/**	Test whether x equals y using the current comparison mode.
		Analysis: Time = O(1) */
	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;
	}

	/**	Set comparison operations to use ==.
		Analysis: Time = O(1) */
	public void compareObjectReferences()
	{
		objectReferenceComparison = true;
	}

	/**	Set comparison operations to use equal() or compareTo(). 
		Analysis: Time = O(1) */
	public void compareContents()
	{
		objectReferenceComparison = false;
	}

	/**	Set the left subtree to t (set isEmpty if t == null). 
		Analysis: Time = O(1) 
		PRECONDITION: 
			!isEmpty()
			values in the new left subtree are less than rootItem()

			(The second condition of the precondition isn't checked as it is too time consuming.
			Don't use this operation on this class unless the condition is known to hold.) */
	public void setRootLeftSubtree(LinkedSimpleTreeUos t) throws ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot set subtree of an empty tree.");

		if (t != null)
			rootNode.setLeftNode(t.rootNode());
		else
			rootNode.setLeftNode(null);
	}

	/**	Set the right subtree to t (set isEmpty if t == null). 
		Analysis: Time = O(1) 
		PRECONDITION: 
			!isEmpty()
			values in the new right subtree are greater than rootItem()

			(The second condition of the precondition isn't checked as it is too time consuming.
			Don't use this operation on this class unless the condition is known to hold.) */
	public void setRootRightSubtree(LinkedSimpleTreeUos t) throws ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot set subtree of an empty tree.");

		if (t != null)
			rootNode.setRightNode(t.rootNode());
		else
			rootNode.setRightNode(null);
	}
	
	/**	Is the current position below the bottom of the tree?
		Analysis: Time = O(1) */
	public boolean below()
	{
		return (cur == null) && (parent != null || isEmpty());
	}
	
	/**	Is the current position above the root of the tree?
		Analysis: Time = O(1) */
	public boolean above()
	{
		return (parent == null) && (cur == null);
	}
}