twothreepleafuos.java

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

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

package dslib.dictionary.twothreetree;

import dslib.base.PairUos;

/**	A TwoThreePNodeUos with no children containing an item and a key.
	It has methods search, insert, delete, and toString. */
public class TwoThreePLeafUos extends TwoThreePNodeUos
{
	/**	The item of this leaf. */
	protected Object 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 TwoThreePLeafUos(Comparable i, Object y)
	{
		key = i;
		item = y;
	}

	/**	The item in this leaf. <br>
		Analysis: Time = O(1) */
	public Object 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(Object 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 being sought
		@param treeHeader The tree to which this node belongs */
	public void search(Comparable i, TwoThreePKeyedDictUos treeHeader)
	{
		if (key.compareTo(i) == 0)
			treeHeader.setCurrentNode(this);
		else
			treeHeader.setCurrentNode(null);
	}
	
	/**	Put the smaller key here and the larger one in extraChild. <br>
		Analysis: Time = O(1)
		@param i The key of the new item
		@param y The new item */
	public PairUos insert(Comparable i, Object y)
	{
		TwoThreePLeafUos newLeaf;
		PairUos result;

		if (key.compareTo(i) < 0)
		{
			newLeaf = new TwoThreePLeafUos(i, y);
			return new PairUos(newLeaf, i);
		}
		else
		{
			newLeaf = new TwoThreePLeafUos(key, item);
			result = new PairUos(newLeaf, key);
			key = i;
			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() + ")";
	}
}