htbaltreeiteratoruos.java

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

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

package dslib.dictionary.bintree;

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

/**	Class used for traversing binary trees */
public class  HtBalTreeIteratorUos implements BinaryIteratorUos
{
	/**	Internal representation of the structure. */
	protected HtBalBasicDictUos tree;

 	/**	Initialize the iterator at the root. <br> 
		Analysis: Time = O(1) 
		@param newTree tree to be iterated */
	public HtBalTreeIteratorUos(HtBalBasicDictUos newTree)
	{
		tree = newTree;
		goRoot();
	}
  
	/**	Create a new iterator at a specific position in the newTree. <br>
		Analysis : Time = O(1) 
		@param newTree tree to be iterated
		@param newParent parent of the node to become the current node
		@param newCur node to be made the current node */
	public HtBalTreeIteratorUos(HtBalBasicDictUos newTree, BinaryNodeUos newParent, BinaryNodeUos newCur)
	{
		tree = newTree;
		parent = newParent;
		cur = newCur;
	}
  
	/**	The node with the current item. */
	protected BinaryNodeUos cur;
  
	/**	The node with the current item. <br> 
		Analysis: Time = O(1) */
	protected BinaryNodeUos cur()
	{
		return cur;
	}
  
	/**	The node which is the parent of the current node. */
	protected BinaryNodeUos parent;
  
	/**	The node which is the parent of the current node. <br> 
		Analysis: Time = O(1) */
	public BinaryNodeUos parent()
	{
		return parent;
	}
  
	/**	Is there a current item?. <br> 
		Analysis: Time = O(1) */
	public boolean itemExists()
	{
		return !above() && !below();
	}

	/**	Contents of the current node. <br> 
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			itemExists() 
		</ul> */
	public Object item() throws NoIteratorItemUosException
	{
		if (!itemExists())
			throw new NoIteratorItemUosException("A current item must exist");  
	
		return cur.item();
	}

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

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

	/**	Move to above the root item. <br> 
		Analysis: Time = O(1) */
	public void goAbove()
	{
		parent = null;
		cur = null;
	}

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

	/**	Advance to the root of the leftSubtree. <br> 
		Analysis: Time = O(1) */
	public void goLeft()
	{
		if (above())
			goRoot();
		else
		{
			parent = cur;
			cur = cur.leftNode();
		}
	}

	/**	Advance to the root of the rightSubtree. <br>
		Analysis: Time = O(1) */
	public void goRight()
	{
		if (above())
			goRoot();
		else
		{
			parent = cur;
			cur = cur.rightNode();
		}
	}
  
	/**	Move to the position where inorder successor goes. <br> 
		Analysis: Time = O(n), where n = length of path to successor */
	public void goToSuccessorInsertPosition()
	{
		goRight();
		while (cur!=null)
			goLeft();
	}
  
	/**	Go up one level in the tree so that the parent becomes current. <br>
		This procedure can only be applied to a tree with TwoWayBinaryNodeUos nodes. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			parent instanceof TwoWayBinaryNodeUos <br>
			!cur==null 
		</ul> */
	public void goParent() throws ClassCastException, BeforeTheStartUosException
	{
		if (!(parent instanceof TwoWayBinaryNodeUos))
			throw new ClassCastException("Cannot perform goParent: requires parent to be a two-way node");
		if (cur==null)
			throw new BeforeTheStartUosException("Cannot go to parent since are already before.");
		
		cur = parent;
		if (cur==tree.rootNode)
			parent = null;
		else
			parent = ((TwoWayBinaryNodeUos)parent).parentNode();
	}
  
	/**	String listing of the items in the tree. <br> 
		Analysis: Time = O(1) */
	public String toString()
	{
		return tree.toString();
	}

	/**	A shallow clone of this object. <br> 
		Analysis: Time = O(1) */
	public Object clone()
	{
		try
		{
			return super.clone();
		} catch (CloneNotSupportedException e)
		{
			// Should not occur: this is a CursorUos, which implements Cloneable 
			e.printStackTrace();
 			return null;
		}
	}
}