twothreeleafuos.java

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

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

package dslib.dictionary.twothreetree;

import dslib.base.*;

/**	A TwoThreeNodeUos with no children containing an item.
	It has routines search, insert, delete, and toString. */
public class TwoThreeLeafUos extends TwoThreeNodeUos
{
	/**	The item of this leaf */
	protected KeyedUos item;

	/**	The key for the item. */
	protected Comparable key;

	/**	Create node with value y and key i. <br>
		Analysis: Time = O(1)
		@param i The key for this node
		@param y The item in this node */
	public TwoThreeLeafUos(KeyedUos y)
	{
		key = y.key();
		item = y;                
	}

	/**	The item in this leaf. <br>
		Analysis: Time = O(1) */
	public KeyedUos item()
	{
		return item;
	}

	/**	Set the item in this leaf to be x. <br> 
		Analysis: Time = O(1) 
		@param x The new item */
	public void setItem(KeyedUos x)
	{
		item = x;
	}


	/**	The key of the item in this leaf. <br>
		Analysis: Time = O(1) */
	public Comparable key()
	{
		return key;
	}

	/**	If the key is i, set currentNode to this, else to null. <br> 
		Analysis: Time = O(1)
		@param i The key of the item to being sought0
		@param treeHeader The tree to which this node belongs*/
	public void search(Comparable i, TwoThreeKeyedDictUos treeHeader)
	{
		if (key.compareTo(i)==0)
			treeHeader.setCurrentNode(this);
		else
			treeHeader.setCurrentNode(null);
	}
	
	/**	Put the smaller key here and larger in extraChild. <br>
		Analysis: Time = O(1)
		@param y The new item */
	public PairUos insert(KeyedUos y)
	{
		TwoThreeLeafUos newLeaf;
		PairUos result;

		if (key.compareTo(y.key()) < 0)
		{
			newLeaf = new TwoThreeLeafUos(y);
			return new PairUos(newLeaf, y.key());
		}
		else
		{
			newLeaf = new TwoThreeLeafUos(item);
			result = new PairUos(newLeaf, key);
			key = y.key();
			item = y;
			return result;
		}
	}

	/**	Delete the item with key i, and return true if the node
		needs to be deleted. <br> 
		Analysis: Time = O(1) 
		@param i The key of the item to be deleted */
	public boolean delete(Comparable i)
	{

		if (i.compareTo(key)==0)
			return true;
		else
			return false;     
	}

	/**	String representation of the item of the leaf. <br>
		Analysis: Time = O(1) */
	public String toString()
	{
		return item.toString() + " ";
	}

	/**	String representation of the detailed contents of the node. <br> 
		Analysis: Time = O(n), n = size of the subtree 
		@param indent The current amount of indentation; a string of blanks */
	public String formatToString (String indent)
	{
		return "(" + key.toString() + ": " + item.toString() + ")";
	}
}