basicmarytreeuos.java

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

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

package dslib.tree;

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

/**	M-ary tree class with operations on root node. */
public class BasicMAryTreeUos implements ContainerUos
{
	/**	The root of the tree. */
	protected MAryNodeUos rootNode;
  
	/**	Number of children allowed for future nodes. */
	protected int futureArity;

	/**	Create an empty tree with specified future arities. <br> 
		Analysis: Time = O(1)
		@param cap number of children allowed for future nodes */
	public BasicMAryTreeUos(int cap)
	{
		setRootNode(null);
		setFutureArity(cap);
	}
	
	/**	Create tree with the specified root node and specified future arities. <br> 
		Analysis: Time = O(1) 
		@param x item to set as the root node
		@param cap number of children allowed for future nodes */
	public BasicMAryTreeUos(Object x, int cap)
	{
		MAryNodeUos root = new MAryNodeUos(x, cap);
		setRootNode(root);
		setFutureArity(cap);
	}

	/**	Contents of the root node. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			!isEmpty()
		</ul> */
	public Object rootItem() throws ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot obtain root of an empty tree");
		
		return rootNode.item();
	}

	/**	Is the tree empty?. <br>
		Analysis: Time = O(1) */
	public boolean isEmpty()
	{
		return rootNode==null;
	}

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

	/**	Number of children possible for the root. <br>
		Analysis: Time = O(1) 
		PRECONDITION: <br>
		<ul>
			!isEmpty() 
		</ul> */
	public int rootArity() throws ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot call count() on an empty tree");
		
		return rootNode.count();
	}

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

	/**	Number of children allowed for future nodes. <br>
		Analysis: Time = O(1) */
	public int futureArity()
	{
		return futureArity;
	}

	/**	Set number of children allowed for future nodes. <br>
		Analysis: Time = O(1) 
		@param newArity new number of children allowed for future nodes */
	public void setFutureArity(int newArity)
	{
		futureArity = newArity;
	}

	/**	i'th subtree of the root. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			!isEmpty() <br>
			!((i<=0) || (i>rootArity())) 
		</ul> 
		@param i position of the subtree to be returned */
	public BasicMAryTreeUos rootSubtree(int i) throws ContainerEmptyUosException, InvalidArgumentUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot perform a search for the i'th subtree on an empty tree");
		if ((i<=0) || (i>rootArity()))
			throw new InvalidArgumentUosException("Cannot access i'th subtree since i is an invalid location.");
		
		BasicMAryTreeUos result = (BasicMAryTreeUos)this.clone();
		result.setRootNode(rootNode.subnode(i));
		return result;
	}

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

	/**	Set contents of the root to x. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			!isEmpty() 
		</ul> 
		@param x item to be set as the root item */
	public void setRootItem(Object x) throws ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot set root of an empty tree.");
		
		rootNode.setItem(x);
	}
	
	/**	Set rootNode to newRoot. <br>
		Analysis: Time = O(1) */
	protected void setRootNode(MAryNodeUos newRoot)
	{
		rootNode = newRoot;
	}

	/**	Insert x as new root item with old tree as i'th subtree. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			!((i<=0) || (i>rootArity())) 
		</ul> 
		@param x item to be set as the new root
		@param i old tree is set to this subtree of the new root */
	public void insertRoot(Object x, int i) throws InvalidArgumentUosException
	{
		if(rootNode != null)
		{
			if ((i<=0) || (i>rootArity()))
				throw new InvalidArgumentUosException("Cannot set i'th subtree since i is an invalid location.");
		}
		else
			if ((i<=0) || (i>futureArity()))
				throw new InvalidArgumentUosException("Cannot set i'th subtree since i is an invalid location.");
		
		MAryNodeUos temp = new MAryNodeUos(x, futureArity);
		temp.setSubnode(i, rootNode);
		if (temp.subnode(i)!=null)
			temp.setLastNonEmptyChild(i);
		rootNode = temp;
	}

	/**	Delete the root of the tree keeping the non-empty subtree. <br>
		If > 1 non-empty, replace the root item by the item
		specified by findReplacementItemPosition. <br>
		Analysis: Time = O(1) when tree has size 1, otherwise <br>
				 O(n) n = length of path to a leaf <br>
		PRECONDITION: <br>
		<ul>
			!isEmpty() 
		</ul> */
	public void deleteRoot() throws ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot delete from an empty tree.");
		
		MAryIteratorUos curPos = new MAryIteratorUos(this, null, 0, rootNode);
		deleteItemInPosition(curPos);
	}

	/**	Set the i'th subtree to t. <br>
		Analysis: Time = O(rootArity()) worst case (inserting empty tree) <br>
		PRECONDITION: <br>
		<ul>
			!isEmpty() <br>
			!((i<=0) || (i>rootArity)) 
		</ul> 
		@param t tree to be set as the new i'th subtree of the root 
		@param i position of the subtree to set t to */
	public void setRootSubtree(BasicMAryTreeUos t, int i) throws ContainerEmptyUosException, InvalidArgumentUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot set subtree of an empty tree.");
		if ((i<=0) || (i>rootArity()))
			throw new InvalidArgumentUosException("Cannot set t to i'th subtree since i is an invalid location.");
		
		rootNode.setSubnode(i, t.rootNode);
		if (!t.isEmpty() && i>rootNode.lastNonEmptyChild())
			rootNode.setLastNonEmptyChild(i);
		else if (t.isEmpty() && i==rootNode.lastNonEmptyChild())
		{
			int j=i-1;
			while (j>0 && rootNode.subnode(j)!=null)
				j--;
			rootNode.setLastNonEmptyChild(j);
		}
	}

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

	/**	String representation of the tree. <br>
		Analysis: Time = O(n), n = number of items in the tree */
	public String toString()
	{
		if (isEmpty())
			return "";
		else
			return rootNode.toString();
	}

	/**	String representation of the tree, level by level. <br>
		Analysis: Time = O(n), where n = number of items in the tree */
	public String toStringByLevel()
	{
		return toStringByLevel(1);
	}


	/**	Form a string representation that includes level number. <br>
		Analysis: Time = O(n), where n = number of items and empty subtrees */
	protected String toStringByLevel(int i)
	{
		int j, lastNonEmpty;
		String result = new String();
		result = result.concat("\n");
		for (j=1; j<i; j++)
			result = result.concat("	 ");
		result = result.concat(String.valueOf(i));
		result = result.concat(": ");
		if (isEmpty())
			result = result.concat("-");
		else
		{
			result = result.concat(rootItem().toString());
			if (rootLastNonEmptyChild()>0)
			{
				for (j=1; j<=rootNode.subnode.length; j++)
					result = result.concat(rootSubtree(j).toStringByLevel(i+1));
			}
		}
		return result;
	}

	/**	Delete the item in position specified by pos. <br>
		Analysis: Time = O(1) when it is a leaf. <br>
					  O(n) n = length of path to a leaf <br> 
		PRECONDITION: <br>
		<ul>
			!isEmpty()
		</ul> 
		@param pos iterator position of item to be deleted */
	protected void deleteItemInPosition(MAryIteratorUos pos) throws ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot set subtree of an empty tree.");
	
		if (pos.cur.lastNonEmptyChild()==0)
		{
			if (pos.parent==null)
				wipeOut();
			else
			{
				pos.parent.setSubnode(pos.index(), null);
				if (pos.parent.lastNonEmptyChild()==pos.index())
				{
					int j = pos.index()-1;
					while (j!=0 && pos.parent.subnode(j)==null)
						j--;
					pos.parent.setLastNonEmptyChild(j);
				}
			}
		}
		else
		{
			MAryIteratorUos replacePos = findReplacementItemPosition(pos.cur);
			pos.cur.setItem(replacePos.cur.item());
			deleteItemInPosition(replacePos);
		}
	}

	/**	Find the position of the rightmost leaf of the currentPosition. <br>
		Analysis: Time = O(n), where n = length of the path to the leaf 
		@param currentLocation node to find the replacement node for */
	protected MAryIteratorUos findReplacementItemPosition(MAryNodeUos currentLocation) throws ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot find rightmost leaf of an empty tree.");
		
		MAryNodeUos prev, cur;
		prev = currentLocation;
		cur = prev.subnode(prev.lastNonEmptyChild());
		while (cur.lastNonEmptyChild()!=0)
		{
			prev=cur;
			cur=prev.subnode(prev.lastNonEmptyChild());
		}
		return new MAryIteratorUos(this, prev, prev.lastNonEmptyChild(), cur);
	}

}