twothreekeyeddictuos.java

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

/* TwoThreeKeyedDictUos.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 KeyedDictUos 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 TwoThreeKeyedDictUos implements KeyedDictUos
{
	/**	Root node of the tree. */
	protected TwoThreeNodeUos rootNode;

	/**	The node which stores the current item; used for both
		iteration and searching. */
	protected TwoThreeLeafUos currentNode;

	/**	Construct an empty tree. <br>
		Analysis: Time = O(1) */
	public TwoThreeKeyedDictUos()
	{
	    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(TwoThreeLeafUos 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)
	{
		TwoThreeLeafUos 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 KeyedUos obtain(Comparable k) throws ItemNotFoundUosException
	{
		if (!has(k))
			throw new ItemNotFoundUosException("Can not obtain an item that is not in the dictionary");

		TwoThreeLeafUos saveCurrentNode = currentNode;
		search(k);
		Object result = item();
		currentNode = saveCurrentNode;
		return (KeyedUos) 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;
			TwoThreeNodeUos cur = rootNode;
			while (cur instanceof TwoThreeInteriorUos)
			{
				cur = ((TwoThreeInteriorUos) cur).firstItem();
			}
			currentNode = (TwoThreeLeafUos) 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 
		{	
			TwoThreeInteriorUos parentNode = currentNode.parent;
			TwoThreeNodeUos childNode = currentNode;
			TwoThreeNodeUos nextChild = nextChild(parentNode, childNode);
			while ((parentNode != null) && (nextChild == null))
			{
				nextChild = nextChild( ( (TwoThreeInteriorUos) parentNode), childNode);
				childNode = parentNode;
				parentNode = childNode.parent;
			}
			if (nextChild != null)
			{
				while (nextChild instanceof TwoThreeInteriorUos)
					nextChild  = ((TwoThreeInteriorUos) nextChild).firstItem;
				currentNode = (TwoThreeLeafUos) nextChild;
			}
			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> */		
	protected TwoThreeNodeUos nextChild(TwoThreeInteriorUos p, TwoThreeNodeUos n)
	{
		if(after())
			throw new AfterTheEndUosException("Can't goForth() when after.");
		TwoThreeInteriorUos parentNode = p;
		TwoThreeNodeUos 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 the current key. <br>
		Analysis: Time = O(log n), n = the number of items in the structure <br>
		PRECONDITION: <br>
		<ul>
			has(y.key())
		</ul>
		@param y The new value for the current key */
	public void set(KeyedUos y) throws ItemNotFoundUosException
	{
		if (!has(y.key()))
			throw new ItemNotFoundUosException("Cannot set since key does not appear in the tree");

		if (itemExists() && (y.key().compareTo(itemKey())==0))
			setItem(y);
		else
		{
			TwoThreeLeafUos 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(KeyedUos x) throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("There is no current item to set");

		currentNode.setItem(x);
	}

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

		if (isEmpty())
		{
			TwoThreeLeafUos leaf = new TwoThreeLeafUos((KeyedUos)y);
			rootNode = leaf;
		}
		else
		{
			PairUos extraChildPair = rootNode.insert(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)
			{
				TwoThreeInteriorUos interior = new TwoThreeInteriorUos(rootNode, 
						(Comparable) extraChildPair.secondItem(), 
						(TwoThreeNodeUos) extraChildPair.firstItem());
				rootNode.setParent(interior);
				((TwoThreeNodeUos) extraChildPair.firstItem()).setParent(interior);
				rootNode = interior;
			}
		}
	}

	/**	Search for the node with key k saving the search path. <br>
		Analysis: Time = O(log n), n = size of the tree <br>
		PRECONDITION: <br>
		<ul>
		     k instanceof Comparable
		</ul>
		@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 and 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 TwoThreeInteriorUos)
				rootNode = ((TwoThreeInteriorUos)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 TwoThreeCursorUos(currentNode, after);// return new TwoThreeCursorUos(itemKey(), item());
		else
		{
			return new TwoThreeCursorUos(currentNode, after);
		}
	}

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