maryiteratoruos.java

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

/* MAryIteratorUos.java
 * ---------------------------------------------
 * Copyright (c) 2001 University of Saskatchewan
 * All Rights Reserved
 * --------------------------------------------- */
 
package dslib.tree;


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

/**	An Iterator for an m-ary tree.  It includes functions to test for 
	above and below, and to move to a subtree. */
public class MAryIteratorUos implements CursorUos
{
	/**	Internal representation of the structure. */
	protected BasicMAryTreeUos tree;
  
	/**	The current node. */
	protected MAryNodeUos cur;

	/**	Access to the node with the current item. <br>
		Analysis: Time = O(1) */
  
	/**	The parent node. */
	protected MAryNodeUos parent;
  
	/**	The index of cur in parent node. */
	protected int index;

	/**	Access to the index of cur in parent node. */
	public int index()
	{
		return index;
	}
  
	/**	Construct a new cursor with corresponding values. <br>
		Analysis: Time = O(1) 
		@param newTree tree to be iterated
		@param newParent parent of the node to create the iterator at
		@param newIndex position to set index to
		@param newCur current node to create the iterator at */
	public MAryIteratorUos(BasicMAryTreeUos newTree, MAryNodeUos newParent, int newIndex, MAryNodeUos newCur)
	{
		tree = newTree;
		parent = newParent;
		cur = newCur;
		index = newIndex;
	}

	/**	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 (cur==null) && (parent==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 root item of the data strucuture (if it exists). <br>
		Analysis: Time = O(1) */
	public void goRoot()
	{
		cur = tree.rootNode;
		parent = null;
	}

	/**	Advance to the root of the ith subtree. <br>
		Analysis: Time = O(1)
		@param i subtree to advance to */
	public void goSubtree(int i)
	{
		parent = cur;
		index = i;
		cur = cur.subnode(i);
	}

	/**	Output the current item. <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;
		}
	}
}