twothreepinterioruos.java

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

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

package dslib.dictionary.twothreetree;

import dslib.base.PairUos;
import dslib.exception.*;


/**	A TwoThreeNodeUos which contains two keys and references to two or three subtrees.
	The firstKey  is larger than any key of the first subtree, and less than or
	equal to any key of the second subtree.  If the third subtree exists, the secondKey is
	larger than any key of the second subtree, and less than or equal to any key of
	the third subtree.  The node has methods to set a child or a key, and to search,
	insert, and delete. */
public class TwoThreePInteriorUos extends TwoThreePNodeUos
{
	/**	The three children of the node. */
	protected TwoThreePNodeUos firstItem, secondItem, thirdItem;

	/**	A lower bound for keys of secondItem and thirdItem. */
	protected Comparable firstKey, secondKey;

	/**	Create a node with 2 children. <br>  
		Analysis: Time = O(1) 
		@param c1 The new first child
		@param k1 The new first key
		@param c2 The new second child */
	public TwoThreePInteriorUos(TwoThreePNodeUos c1, Comparable k1, TwoThreePNodeUos c2) 
	{
		firstItem = c1;
		firstKey = k1;
		secondItem = c2;
	}

	/**	Access function for the first subtree. <br>
		Analysis: Time = O(1) */
	public TwoThreePNodeUos firstItem()
	{
		return firstItem;
	}

	/**	Access function for the second subtree. <br>
		Analysis: Time = O(1) */
	public TwoThreePNodeUos secondItem()
	{
		return secondItem;
	}
	
	/**	Access function for the third subtree. <br>
		Analysis: Time = O(1) */
	public TwoThreePNodeUos thirdItem()
	{
		return thirdItem;
	}

	/**	Return the first key for this node. <br> 
		Analysis: Time = O(1) */
	public Comparable firstKey()
	{
		return firstKey;
	}

	/**	Return the secondKey. <br>
		Analysis: Time = O(1) */
	public Comparable secondKey()
	{
		return secondKey;
	}

	/**	Set y to be the ith item. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			(i >= 1) && (i <= 3)
		</ul>
		@param y The new node 
		@param i The index of the item that will be set */
	public void setItem(TwoThreePNodeUos y, int i) throws InvalidArgumentUosException
	{
		if (!(i >= 1 && i <= 3))
			throw new InvalidArgumentUosException("Can only set items with indices between 1 and 3 (inclusive)");

		if (i == 1)
			firstItem = y;
		else if (i == 2)
			secondItem = y;
		else
			thirdItem = y;
		if (y != null)
			y.setParent(this);
	}

	/**	Set y to be the ith key. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			(i >= 1) && (i <= 2)
		</ul>
		@param y The new key
		@param i The index of the key that will be set */
	public void setKey(Comparable y, int i) throws InvalidArgumentUosException
	{
		if (!(i >= 1 && i <= 2))
			throw new InvalidArgumentUosException("Can only set keys with indices between 1 and 2 (inclusive)");

		if (i == 1)
			firstKey = y;
		else
			secondKey = y;
	}

	/**	Search for the item with key i. <br> 
		Analysis: Time = O(log s), s = size of the subtree 
		@param i The key of the item being sought
		@param treeHeader The tree to which this node belongs to */
	public void search(Comparable i, TwoThreePKeyedDictUos treeHeader) 
	{
		obtainChild(i).search(i, treeHeader);
	}

	/**	Return the child that should be searched given key i. <br>  
		Analysis: Time = O(1)
		@param i The key used to select the child that is returned */
	public TwoThreePNodeUos obtainChild(Comparable i) 
	{
		if (i.compareTo(firstKey()) < 0)
			return firstItem;
		else if ((thirdItem == null) || (i.compareTo(secondKey) < 0))
			return secondItem;
		else
			return thirdItem;
	}

	/**	Insert item y with key i into this subtree. <br> 
		Analysis: Time = O(log s), s = size of the subtree 
		@param i The key of the new item 
		@param y The new item that is to be inserted */
	public PairUos insert(Comparable i, Object y) 
	{
		/*	Call insert on the appropriate part of the tree. */
		TwoThreePNodeUos insertionChild = obtainChild(i); 
		PairUos extraChildPair = insertionChild.insert(i, y); 

		if (extraChildPair != null) 
		{
			/*	An extra child was returned.  If there is room for it in the current
				node, place it here.  Otherwise, create an extra child pair to return. */
			TwoThreePNodeUos extraChild = (TwoThreePNodeUos)extraChildPair.firstItem(); 
			Comparable extraChildMinKey = (Comparable)extraChildPair.secondItem(); 
			if (thirdItem == null)  // room for a third child
			{
				if (insertionChild == secondItem)
				{
					/*	Add the extra child as the third child. */
					thirdItem = extraChild;
					secondKey = extraChildMinKey;
				}
				else
				{
					/*	Add the extra child as the second child, after shifting
						the current second child to third. */
					thirdItem = secondItem;
					secondKey = firstKey(); 
					secondItem = extraChild;
					firstKey = extraChildMinKey; 
				}
				extraChild.setParent(this);
				return null;
			}
			else
				return createSiblingPair(insertionChild, extraChildMinKey, extraChild); 
		}
		return null; 
	}

	/**	Make a sibling node and give it the two children with largest keys;
		return the extra sibling, and its key lower bound. <br> 
		Analysis: Time = O(1) 
		@param inChild The child that spawned the extra child
		@param minKey The minimum key of the extra child
		@param extraChild The extra child spawned */
	public PairUos createSiblingPair(TwoThreePNodeUos inChild, Comparable minKey, 
								TwoThreePNodeUos extraChild) 
	{
		TwoThreePInteriorUos sibling;
		PairUos newPair;

		if (inChild == thirdItem)
		{
			sibling = new TwoThreePInteriorUos(thirdItem, minKey, extraChild); 
			thirdItem.setParent(sibling); 
			extraChild.setParent(sibling); 
			newPair = new PairUos(sibling, secondKey); 
		}
		else if (inChild == secondItem)
		{
			sibling = new TwoThreePInteriorUos(extraChild, secondKey, thirdItem); 
			extraChild.setParent(sibling);
			thirdItem.setParent(sibling);
			newPair = new PairUos(sibling, minKey);
		}
		else
		{
			sibling = new TwoThreePInteriorUos(secondItem, secondKey, thirdItem);
			secondItem.setParent(sibling);
			thirdItem.setParent(sibling);
			newPair = new PairUos(sibling, firstKey());
			secondItem = extraChild;
			extraChild.setParent(this);
			firstKey = minKey;
		}
		thirdItem = null;
		return newPair;
	}

	/**	Delete the item with key i, and return true if the current
		node needs to be deleted. <br> 
		Analysis: Time = O(log s), s = size of the subtree 
		@param i The key of the item to be deleted */
	public boolean delete(Comparable i) 
	{
		boolean result = false;
		TwoThreePNodeUos  deletionChild = obtainChild(i);

		if (deletionChild.delete(i))
		{
			if (thirdItem != null)
			{
				if (deletionChild == secondItem)
				{
					secondItem = thirdItem;
					firstKey = secondKey;
				}
				else if (deletionChild == firstItem)
				{
					firstItem = secondItem;
					secondItem = thirdItem;
					firstKey = secondKey;
				}
				thirdItem = null;
				result = false;
			}
			else // no third child so seek a replacement from a sibling
			{
				TwoThreePInteriorUos sibling = adjacentSibling(); 
				if (sibling == null)
				{
					/*	This node is the root so place the remaining child in firstItem. */
					if (deletionChild == firstItem)
						firstItem = secondItem;
					firstItem.setParent(null); 
					secondItem = null;
					result = true; 
				}
				else if (sibling.thirdItem() != null)
				{
					/*	Obtain another child from the sibling. */
					replaceDelChildFromSibling(sibling, deletionChild); 
					result = false;
				}
				else
				{
					/*	Give the remaining child to the sibling, and delete this node. */
					giveRemChildToSibling(sibling, deletionChild); 
					result = true; 
				}
			}
		}
		return result;
	}
	

	/**	Return an adjacent other child of the parent. <br> 
		Analysis: Time = O(1)  */ 
	public TwoThreePInteriorUos adjacentSibling() 
	{
		if (parent() == null)
			return null;
		else
		{
			if (parent().firstItem == this) 
				return (TwoThreePInteriorUos) parent().secondItem; 
			else if (parent().secondItem == this) 
				return (TwoThreePInteriorUos) parent().firstItem; 
			else 
				return (TwoThreePInteriorUos)parent().secondItem; 
		}
	}


	/**	Remove a child from adjacentSibling to replace the child to be deleted. <br> 
		Analysis: Time = O(1) 
		@param adjacentSibling The adjacent sibling
		@param deletionChild The node being removed from this node*/ 
	public void replaceDelChildFromSibling(TwoThreePInteriorUos adjacentSibling, 
											TwoThreePNodeUos deletionChild)
	{
		if (adjacentSibling.firstKey().compareTo(firstKey()) < 0) 
		{
			/* sibling to the left, so move sibling's thirdItem to firstItem */
			if (parent.secondItem == this)
			{
				if (deletionChild == secondItem)
				{	
					secondItem = firstItem;
					firstKey = parent.firstKey();
				}
				parent.setKey(adjacentSibling.secondKey(), 1);
			}
			else // (parent().thirdItem == this)
			{
				if (deletionChild == secondItem)
				{
					secondItem = firstItem;
					firstKey = parent.secondKey();
				}
				parent.setKey(adjacentSibling.secondKey(), 2);
			}
			setItem(adjacentSibling.thirdItem, 1);
			firstItem.setParent(this);
			adjacentSibling.setItem(null, 3);
		}
		else // (parent.firstItem == this)
		{
			/* sibling to the right, so move firstItem of sibling to secondItem */
			if (deletionChild == firstItem)
				firstItem = secondItem;
	
			secondItem = adjacentSibling.firstItem(); 
			secondItem.setParent(this);
			firstKey = parent.firstKey();
			adjacentSibling.setItem(adjacentSibling.secondItem,1);
			parent.setKey(adjacentSibling.firstKey,1);
			adjacentSibling.setItem(adjacentSibling.thirdItem(), 2);
			adjacentSibling.setKey(adjacentSibling.secondKey(), 1);
			adjacentSibling.setItem(null, 3);	
		}
	}


	/**	Give child not deleted to the sibling. <br> 
		Analysis: Time = O(1) 
		@param adjacentSibling The adjacent sibling
		@param deletionChild The node being removed from this node */
	private void giveRemChildToSibling(TwoThreePInteriorUos adjacentSibling, TwoThreePNodeUos deletionChild) 
	{ 
		if (adjacentSibling.firstKey().compareTo(firstKey()) < 0) 
		{
			/* adjacentSibing is to the left, so remaining item becomes sibling's thirdItem */
			if (deletionChild == firstItem) 
			{
				adjacentSibling.setItem(secondItem, 3); 
				secondItem.setParent(adjacentSibling); 
			}
			else
			{
				adjacentSibling.setItem(firstItem, 3); 
				firstItem.setParent(adjacentSibling); 
			}

			if (parent.secondItem == this)
				adjacentSibling.setKey(parent.firstKey(), 2); 
			else 
				adjacentSibling.setKey(parent.secondKey(), 2); 
		}
		else
		{
			/* adjacentSibing is to the right, so remaining item becomes sibling's firstItem */
			adjacentSibling.setItem(adjacentSibling.secondItem, 3); 
			adjacentSibling.setKey(adjacentSibling.firstKey(), 2); 
			adjacentSibling.setItem(adjacentSibling.firstItem, 2); 
			adjacentSibling.setKey(parent.firstKey(), 1);

			if (deletionChild == firstItem)
			{
				adjacentSibling.setItem(secondItem, 1); 
				secondItem.setParent(adjacentSibling);
			}
			else
			{
				adjacentSibling.setItem(firstItem, 1); 
				firstItem.setParent(adjacentSibling); 
			}
		}
		setItem(null, 1); 
		setItem(null, 2); 
	}

	/**	String representation of the contents of the node.  
		Analysis: Time = O(n), n = size of the subtree.  */ 
	public String toString() 
	{
		String result = firstItem.toString() + secondItem.toString(); 
		if (thirdItem != null) 
			result += thirdItem.toString(); 
		return result; 
	}

	/**	String representation of the detailed contents of the node.  
		Analysis: Time = O(n), n = size of the subtree 
		@param indentation The current indentation; a string of spaces */
	public String formatToString(String indentation) 
	{
		String result, nextIndentation;
		nextIndentation = indentation + "         ";
		
		result = "\n" + indentation + "1: " + firstItem.formatToString(nextIndentation) 
			+"\n" + indentation + firstKey + "\n" + indentation + "2: "
			+ secondItem.formatToString(nextIndentation);
		if (thirdItem != null)
			result += "\n" + indentation + secondKey + "\n" + indentation + "3: "
				+ thirdItem.formatToString(nextIndentation);

		return result;
	}
}