marynodeuos.java

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

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

package dslib.tree;

import java.io.Serializable;

/**	A linked node with arbitrary arity for an m-ary tree.  It has 
	contents of generic type, an array to store the subnodes, and a 
	feature to refer to the last non-empty subnode.  There is a 
	function to check the equality of two m-ary nodes, and the out
	function gives a pre-order string representation of the m-ary
	tree with the current node as the root. */
public class MAryNodeUos implements Cloneable, Serializable
{
	/**	Contents of the node. */
	protected Object item;

	/**	References to children. */
	protected MAryNodeUos subnode[];

	/**	Index of the last non-empty child of the node. */
	protected int lastNonEmptyChild;

	/**	Construct a node with initItem as the item and nodeArity possible children. <br>
		Analysis: Time = O(nodeArity)
		@param initItem item new node is constructed with
		@param nodeArity number of children possible for the new node */
	public MAryNodeUos(Object initItem, int nodeArity)
	{
		setItem(initItem);
		subnode = new MAryNodeUos[nodeArity];
	}

	/**	Contents of the node. <br>
		Analysis: Time = O(1) */
	public Object item()
	{
		return item;
	}

	/**	Number of children for this node. <br>
		Analysis: Time = O(1) */
	public int count()
	{
		return subnode.length;
	}

	/**	i'th subnode for this node. <br>
		Analysis: Time = O(1) 
		@param i i'th subnode to be returned */
	public MAryNodeUos subnode(int i)
	{
		return subnode[i-1];
	}

	/**	Index of the last non-empty child of the node. <br>
		Analysis: Time = O(1) */
	public int lastNonEmptyChild()
	{
		return lastNonEmptyChild;
	}

	/**	Set item equal to x. <br>
		Analysis: Time = O(1) 
		@param x  item to set as the current node's item */
	public void setItem(Object x)
	{
		item = x;
	}

	/**	Set subnode i equal to newNode. <br>
		Analysis: Time = O(1) 
		@param i i'th subnode to set the new node at
		@param newNode new node to be set as the i'th child */
	public void setSubnode(int i, MAryNodeUos newNode)
	{
		subnode[i-1] = newNode;
	}

	/**	Set lastNonEmptyChild to newValue. <br>
		Analysis: Time = O(1) 
		@param newValue position of the last non-empty child */
	public void setLastNonEmptyChild(int newValue)
	{
		lastNonEmptyChild = newValue;
	}

	/**	Pre-order string representation suitable for output. <br>
		Analysis: Time = O(count) */
	public String toString()
	{
		String result = item.toString() + " ";
		for (int i=0; i<subnode.length; i++)
		{
			if (subnode[i]!=null)
				result += subnode[i].toString();
			else
				result += "-";
		}
		return result;
	}

	/**	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 class implements Cloneable 
			e.printStackTrace();
 			return null;
		}
	}
}