twothreepkeyeddictuos.java

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

/* TwoThreePKeyedDictUos.java
 * ---------------------------------------------
 * Copyright (c) 2001 University of Saskatchewan
 * All Rights Reserved
 * -------------------------------------------- */
 
package dslib.dictionary.twothreetree;

import dslib.base.*;
import dslib.dictionary.*;
import dslib.dispenser.LinkedStackUos;
import dslib.exception.*;

/**	A PKeyedDictUos implemented by means of a two-three tree. It has all the
	dictionary methods: insert, delete, set, obtain, search, and frequency.
	It also has the LinearIteratorUos capabilities to move the current item:
	goFirst, goForth, goBefore, and goAfter.  There are functions to determine if
	the current item is before or after the structure. */
public class TwoThreePKeyedDictUos implements PKeyedDictUos
{
	/**	Root node of the tree. */
	protected TwoThreePNodeUos rootNode;

	/**	The node which stores the current item; used for both iteration and searching. */
	protected TwoThreePLeafUos currentNode;
	
	/**	Create an empty tree. <br>
		Analysis: Time = O(1) */
	public TwoThreePKeyedDictUos()
	{
		rootNode = null;
		currentNode = null;
	}

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

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

	/**	Set the current node equal to y. <br>
	 	Analysis: Time = O(1)
		@param y The new current node */
	protected void setCurrentNode(TwoThreePLeafUos y)
	{
		currentNode = y;
		if (y == null)
			after = true;
		else
			after = false;
	}

	/**	Is there a current item?. <br>
		Analysis: Time = O(1) */
	public boolean itemExists()
	{
		return currentNode != null;
	}

	/**	The current item. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			itemExists()
		</ul> */
	public Object item() throws NoCurrentItemUosException 
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("There is no current node");

		return currentNode.item();	
	}

	/**	The key of the current item. <br> 
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			itemExists()
		</ul> */
	public Comparable itemKey() throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("There is no current item and hence no current key");

		return currentNode.key();
	}

	/**	The current key-item pair. <br> 
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			itemExists()
		</ul> */
	public PairUos keyItemPair() throws NoCurrentItemUosException 
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("Cannot return an item that does not exist");

		return new PairUos(itemKey(), item());
	}

	/**	Does structure contain an item with key k?. <br> 
		Analysis: Time = O(log n), n = size of the tree 
		@param k The key of the object being sought */
	public boolean has(Comparable k)
	{
		TwoThreePLeafUos saveCurrentNode = currentNode;
		search(k);
		boolean result = itemExists();
		currentNode = saveCurrentNode;
		return result;
	}

	/**	An instance of an item with key k from the container. <br>
		Analysis: Time = O(log n), n = size of the tree <br>
		PRECONDITION: <br>
		<ul>
			has(k)
		</ul>
		@param k The key of the item that will be returned */
	public Object obtain(Comparable k) throws ItemNotFoundUosException
	{
		if (!has(k))
			throw new ItemNotFoundUosException("Can not obtain an item that is not in the dictionary");

		TwoThreePLeafUos saveCurrentNode = currentNode;
		search(k);
		Object result = item();
		currentNode = saveCurrentNode;
		return result;
	}
	
	/**	Is the current position before the start of the structure?. <br>
		Analysis: Time = O(1) */
	public boolean before()
	{
		return isEmpty() || ( (!itemExists()) && !after);
	}

	/**	Is the current position after the end of the structure?. */
	protected boolean after = false;

	/**	Is the current position after the end of the structure?. <br>
		Analysis: Time = O(1) */
	public boolean after()
	{
		return after || isEmpty();
	}

	/**	Go to the first item in the data structure. <br>
		Analysis: Time = O(log n), n = number of items in the structure */
	public void goFirst()
	{
		if (rootNode != null)
		{
			after = false;
			TwoThreePNodeUos cur = rootNode;
			while (cur instanceof TwoThreePInteriorUos)
			{
				cur = ((TwoThreePInteriorUos) cur).firstItem();
			}
			currentNode = (TwoThreePLeafUos) cur;
		}
		else
		{
			after = true;
			currentNode = null;
		}
	}

	/**	Advance one item in the data structure. <br>
		Analysis: Time = O(log n), n = the number of items n the structure 
		PRECONDITION: <br>
		<ul>
			!after()
		</ul> */
	public void goForth() throws AfterTheEndUosException
	{
		if (after())
			throw new AfterTheEndUosException("Can't goForth() when after.");
		if (before())
			goFirst();
		else 
		{	
			TwoThreePInteriorUos parentNode = currentNode.parent;
			TwoThreePNodeUos childNode = currentNode;
			TwoThreePNodeUos nextChild = nextChild(parentNode, childNode);
			while ((parentNode != null) && (nextChild == null))
			{
				childNode = parentNode;
				parentNode = childNode.parent;
				nextChild = nextChild( ( (TwoThreePInteriorUos) parentNode), childNode);
			}
			if (nextChild != null)
			{
				while (nextChild instanceof TwoThreePInteriorUos)
					nextChild  = ((TwoThreePInteriorUos) nextChild).firstItem;
				currentNode = (TwoThreePLeafUos) nextChild;
			}
			else
			{
				after = true;
				currentNode = null;
			}
		}
	}

	/**	For node n, find the next sibling with respect to parent p. <br>
		Analysis: Time = O(1)
		@param p The parent of node n.
		@param n The n for which the next sibling is being sought.
	 */		
	protected TwoThreePNodeUos nextChild(TwoThreePInteriorUos p, TwoThreePNodeUos n)
	{
		TwoThreePInteriorUos parentNode = p;
		TwoThreePNodeUos node = n;
		if(parentNode == null)
			node = null;
		else if (node == parentNode.firstItem)
			node = parentNode.secondItem;
		else if (node == parentNode.secondItem)
		{
			if (parentNode.thirdItem() != null)
				node = parentNode.thirdItem();
			else
				node = null;
		}
		else
			node = null;
		return node;			
	}

	/**	Move prior to the first item. <br>
		Analysis: Time = O(1) */
	public void goBefore()
	{
		currentNode = null;
		after = false;
	}

	/**	Move after the last item. <br>
		Analysis: Time = O(1) */
	public void goAfter()
	{
		currentNode = null;
		after = true;
	}
		
	/**	Set y to be the item associated with key k. <br>
		Analysis: Time = O(log n), n = the number of items in the structure <br>
		PRECONDITION: <br>
		<ul>
			has(k)
		</ul>
		@param k The key of the item to be set
		@param y The new value for the item with key k */
	public void set(Comparable k, Object y) throws ItemNotFoundUosException
	{
		if (!has(k))
			throw new ItemNotFoundUosException("Cannot set since key does not appear in the tree");

		if (itemExists() && (k.compareTo(itemKey())==0))
			setItem(y);
		else
		{
			TwoThreePLeafUos saveCurrentNode = currentNode;
			setItem(y);
			currentNode = saveCurrentNode;
		}
	}

	/**	Set the current item to x. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			itemExists()
		</ul>
		@param x The new value of the current item */
	public void setItem(Object x) throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("There is no current item to set");

		currentNode.setItem(x);
	}
	
	/**	Insert y with key k into the dictionary. <br> 
		Analysis: Time = O(log n), n = size of the tree
		PRECONDITION: <br>
		<ul>
			!has(k)
		</ul>
		@param k The key of the new item
		@param y The new item to be inserted into the tree */
	public void insert(Comparable k, Object y) throws DuplicateItemsUosException
	{
		if (has(k))
			throw new DuplicateItemsUosException("Cannot insert a duplicate item into a set");

		if (isEmpty())
		{
			TwoThreePLeafUos leaf = new TwoThreePLeafUos(k, y);
			rootNode = leaf;
		}
		else
		{
			PairUos extraChildPair = rootNode.insert(k, y);
			/*	If an extra child is returned, it consists of (subtree, key) 
				where the key is larger than any key in the root node subtree, 
				and less than or equal to keys in the returned subtree. */
			if (extraChildPair != null)
			{
				TwoThreePInteriorUos interior = new TwoThreePInteriorUos(rootNode, 
						(Comparable) extraChildPair.secondItem(), 
						(TwoThreePNodeUos) extraChildPair.firstItem());
				rootNode.setParent(interior);
				((TwoThreePNodeUos) extraChildPair.firstItem()).setParent(interior);
				rootNode = interior;
			}
		}
	}

	/**	Search for the node with key k saving the search path. <br>
		Analysis: Time = O(log(n)), n = the number of items in the tree 
		@param k The key of the item being sought */
	public void search(Comparable k)
	{
		if (isEmpty())
			goAfter();
		else
			rootNode.search(k, this);
	}

	/**	Delete the item with key k. <br> 
		Analysis: Time(n) = O(log n), n= size of the tree <br>
		PRECONDITION: <br>
		<ul>
			has(k)
		</ul> 
		@param k The key of the item to be deleted */
	public void delete(Comparable k) throws ItemNotFoundUosException
	{
		if (!has(k))
			throw new ItemNotFoundUosException("Cannot delete an item that does not exist.");

		if (itemExists() && (k.compareTo(itemKey())==0))
			goForth();  //after deletion the iterator should refer to the next item

		if (rootNode.delete(k))
		{
			if (rootNode instanceof TwoThreePInteriorUos)
				rootNode = ((TwoThreePInteriorUos)rootNode).firstItem();	
			else
				wipeOut();
		}
	}

	/**	Delete the current item. <br>
		Analysis: Time = O(log n), n = number of items in the structure <br>
		PRECONDITION: <br>
		<ul>
			itemExists()
		</ul> */ 
	public void deleteItem() throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("No current item to delete.");
	
		Comparable curKey = itemKey();
		goForth(); // After deletion the iterator should refer to the next item
		delete(curKey);	
	}

	/**	Make the tree empty. <br>
		Analysis: Time = O(1) */
	public void wipeOut()
	{
		rootNode = null;
		currentNode = null;
		after = false;
	}

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

	/**	String representation of the contents of the tree that is formatted 
		according to how the data is arranged in the tree. <br>
		Analysis: Time = O(n), n = number of items in the tree */
	public String formatToString()
	{
		if (isEmpty())
			return new String();
		else
			return rootNode.formatToString("");
	}

	/**	Return the current position within the tree. <br>
		Analysis: Time = O(1) */
	public CursorUos currentPosition()
	{
		if (itemExists())
			return new TwoThreePCursorUos(currentNode, after);
		else
			return new TwoThreePCursorUos(currentNode, after);
	}

	/**	Move to cursor to the specified position. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			pos instanceof TwoThreePCursorUos 
		</ul> 
		@param pos The position to become the current position */
	public void goPosition(CursorUos pos) throws InvalidArgumentUosException
	{
		if (!(pos instanceof TwoThreePCursorUos))
			throw new InvalidArgumentUosException("Position in a 2-3 tree must be a TwoThreePCursorUos");
			 
		currentNode = ((TwoThreePCursorUos)pos).node;
		after = ((TwoThreePCursorUos)pos).after;

	}

	/**	The number of times key k occurs within the dictionary.  This tree
		is a set so it will only ever return 0 or 1. 
		@param k key to check how often it occurs */
	public int frequency(Comparable k)
	{
		if (has(k))
			return 1;
		else
			return 0;
	} 

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