twothreeinterioruos.java

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

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

package dslib.dictionary.twothreetree;

import dslib.base.*;
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 routines to set
	a child or a key, and to search, insert, and delete. */
public class TwoThreeInteriorUos extends TwoThreeNodeUos
{
	/**	The three children of the node. */
	protected TwoThreeNodeUos firstItem, secondItem, thirdItem;

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

	/**	Create a node with two 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 TwoThreeInteriorUos(TwoThreeNodeUos c1, Comparable k1, TwoThreeNodeUos c2) 
	{ 
		firstItem = c1;
		firstKey = k1;
		secondItem = c2;
	} 

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

	/**	Access function for the second subtree. <br>
		Analysis: Time = O(1) */
	public TwoThreeNodeUos secondItem()
	{
		return secondItem;
	}
	
	/**	Access function for the third subtree. <br>
		Analysis: Time = O(1) */
	public TwoThreeNodeUos 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;
	}

	/**	Search for the item with key i. <br> 
		Analysis: Time = O(log s), s = size of the subtree 
		@param i The key of the being sought
		@param treeHeader The tree to which this node belongs to */
	public void search(Comparable i, TwoThreeKeyedDictUos 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 TwoThreeNodeUos obtainChild(Comparable i) 
	{ 
		if (i.compareTo(firstKey()) < 0)
			return firstItem;
		else if ((thirdItem == null) || (i.compareTo(secondKey) < 0))
			return secondItem;
		else
			return thirdItem;
	} 
 
	/**	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(TwoThreeNodeUos 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;
	}

	/**	Insert item y into this subtree. <br> 
		Analysis: Time = O(log s), s = size of the subtree 
		@param y The new item that is to be inserted */
	public PairUos insert(KeyedUos y) 
	{ 
		/* call insert on the appropriate part of the tree */
		TwoThreeNodeUos insertionChild = obtainChild(y.key()); 
		PairUos extraChildPair = insertionChild.insert(y); 
		   
		if (extraChildPair != null) 
		{ 
			TwoThreeNodeUos extraChild = (TwoThreeNodeUos)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 that extra child 
		@param extraChild The extra child spawned*/
	public PairUos createSiblingPair(TwoThreeNodeUos inChild, Comparable minKey, TwoThreeNodeUos extraChild) 
	{ 
		TwoThreeInteriorUos sibling; 
		PairUos newPair;    
 
		if (inChild==thirdItem)  
		{ 
			sibling = new TwoThreeInteriorUos(thirdItem, minKey, extraChild); 
			thirdItem.setParent(sibling); 
			extraChild.setParent(sibling); 
			newPair = new PairUos(sibling, secondKey); 
		} 
		else if (inChild==secondItem)
		{ 
			sibling = new TwoThreeInteriorUos(extraChild, secondKey, thirdItem); 
			extraChild.setParent(sibling); 
			thirdItem.setParent(sibling); 
			newPair = new PairUos(sibling, minKey); 
		}  
		else 
		{ 
			sibling = new TwoThreeInteriorUos(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;
		TwoThreeNodeUos 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
			{  
				TwoThreeInteriorUos 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 TwoThreeInteriorUos adjacentSibling() 
	{ 
		if (parent()==null) 
			return null; 
		else 
		{ 
			if (parent().firstItem == this) 
				return (TwoThreeInteriorUos) parent().secondItem; 
			else if (parent().secondItem == this) 
				return (TwoThreeInteriorUos) parent().firstItem; 
			else 
				return (TwoThreeInteriorUos)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(TwoThreeInteriorUos adjacentSibling, TwoThreeNodeUos deletionChild)
	{
		if (adjacentSibling.firstKey().compareTo(firstKey())<0) 
		{
		        /* sibling to the left, so move silbing'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(TwoThreeInteriorUos adjacentSibling, TwoThreeNodeUos deletionChild) 
	{ 
	        /* adjacentSibing is to the left, so remaining item becomes sibling's thirdItem */
		if (adjacentSibling.firstKey().compareTo(firstKey())<0) 
		{  
			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 left, so remaining item becomes sibling's thirdItem */
			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;
	} 
}