setdictuos.java

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

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

package dslib.util;

import dslib.exception.*;
import dslib.list.*;
import dslib.base.*;
import dslib.dictionary.*;
import dslib.dictionary.arrayed.*;
import dslib.dictionary.twothreetree.*;
import dslib.dictionary.bintree.*;
import dslib.tree.BinaryTreeUos;
import dslib.hashtable.DblOpenAdrHashTableUos;

/**	A class that maintains an arbritrary DictUos as a set.  It has
	several static methods that can be used to create an instance 
	of a SetDictUos with a specific descendant of DictUos for  
	representation of the set. This is the only descendant of DictUos 
	that is a set.  In order to ensure that the dictionary is actually 
	maintained as a set, it is recommended that one of the static 
	methods is used to create an instance of a SetDictUos.  When using  
	the constructor, the dictionary that is passed in as an argument 
	should be created when the constructor is called, for example: <br>
	<pre>
		SetDictUos set = new SetDictUos(new LinkedListUos());
	</pre> */
public class SetDictUos implements DictUos
{
	/**	The DictUos representation used for the set */
	protected DictUos rep;

	/**	Creates a new SetDictUos from a specified DictUos. <br>
		Analysis: Time = O(1) 
		PRECONDITION <br>
		<ul>
			newRep != null
		</ul>
		@param newRep The dictionary that will be maintained as a set  */
	public SetDictUos(DictUos newRep)
	{
		if (newRep == null)
			throw new InvalidArgumentUosException("Argument cannot be null.");
			
		rep = newRep;
	}

	/**	Return a new SetDictUos initialized with a ArrayedDictUos as the
		underlying DictUos. <br>
		Analysis: Time = O(1) 
		@param size The size of the new arrayed dictionary */
	public static SetDictUos newArrayedSet(int size)
	{
		return new SetDictUos(new ArrayedDictUos(size));
	}

	/**	Return a new SetDictUos initialized with a LinkedListUos as the
		underlying DictUos. <br>
		Analysis: Time = O(1) */
	public static SetDictUos newLinkedListSet()
	{
		return new SetDictUos(new LinkedListUos());
	}

	/**	Return a new SetDictUos initialized with a BinaryTreeUos as the
		underlying DictUos. <br>
		Analysis: Time = O(1) */
	public static SetDictUos newBinaryTreeSet()
	{
		return new SetDictUos(new BinaryTreeUos());
	}

	/**	Return a new SetDictUos initialized with a DblOpenAdrHashTableUos as the
		underlying DictUos. <br>
		Analysis: Time = O(1) 
		@param size The size of dictionary
		@param dummyItem An item that should never be inserted into the hash table */
	public static SetDictUos newHashTableSet(int size, Object dummyItem)
	{
		return new SetDictUos(new DblOpenAdrHashTableUos(size, dummyItem));
	}

	/**	Return a new SetDictUos initialized with a StdOrderedDictUos as the
		underlying DictUos. <br>
		Analysis: Time = O(1) */
	public static SetDictUos newOrderedSet()
	{
		return new SetDictUos(new StdOrderedDictUos());
	}


	/**	Is the dictionary empty?. <br>
		Analysis: Time = O(1) */
	public boolean isEmpty()
	{
		return rep.isEmpty();
	}

	/**	Is the dictionary full?. <br>
		Analysis: Time = O(1) */
	public boolean isFull()
	{
		return rep.isFull();
	}

	/**	Clear the contents of the dictionary. <br>
		Analysis: Time = O(1) */
	public void wipeOut()
	{
		rep.wipeOut();
	}

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

	/**	Return the current item. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			itemExists()
		</ul> */
	public Object item() throws NoIteratorItemUosException
	{
		if (!itemExists())
			throw new NoIteratorItemUosException("Item must exist to obtain it.");
			
		return rep.item();
	}

	/**	Search for the specified item. <br>
		Analysis: for  n = number of items in the dictionary <br>
		rep instanceof ArrayedDictUos implies Time = O(n) <br>
		rep instanceof LinkedListUos implies Time = O(n) <br>
		rep instanceof BinaryTreeUos implies Time = O(m) for  m = length of the path in the tree  <br>
		rep instanceof StdOrderedDictUos implies Time = O(log n) <br>
		rep instanceof DblOpenAdrHashTableUos implies Time = O(1) (expected), O(m) m = table size (worst case)
		@param x The item sought in the search */
	public void search(Object x)
	{
		rep.search(x);
	}

	/**	Does the dictionary contain x?. <br>
		Analysis: for  n = number of items in the dictionary <br>
		rep instanceof ArrayedDictUos implies Time = O(n) <br>
		rep instanceof LinkedListUos implies Time = O(n) <br>
		rep instanceof BinaryTreeUos implies Time = O(m) for  m = length of the path in the tree  <br>
		rep instanceof StdOrderedDictUos implies Time = O(log n) <br>
		rep instanceof DblOpenAdrHashTableUos implies Time = O(1) (expected), O(m) m = table size (worst case)
		@param x The item sought in the search */
	public boolean has(Object x)
	{
		return rep.has(x);
	}

	/**	Obtain an instance of x from the dictionary. <br>
		Analysis: for  n = number of items in the dictionary <br>
		rep instanceof ArrayedDictUos implies Time = O(n) <br>
		rep instanceof LinkedListUos implies Time = O(n) <br>
		rep instanceof BinaryTreeUos implies Time = O(m) for  m = length of the path in the tree  <br>
		rep instanceof StdOrderedDictUos implies Time = O(log n) <br>
		rep instanceof DblOpenAdrHashTableUos implies Time = O(1) (expected), O(m) m = table size (worst case)
		@param x The item to obtain */
	public Object obtain(Object x)
	{
		return rep.obtain(x);
	}

	/**	Return the number of times that an object exists in the dictionary. <br>
		Analysis: for  n = number of items in the dictionary <br>
		rep instanceof ArrayedDictUos implies Time = O(n) <br>
		rep instanceof LinkedListUos implies Time = O(n) <br>
		rep instanceof BinaryTreeUos implies Time = O(m) for  m = length of the path in the tree  <br>
		rep instanceof StdOrderedDictUos implies Time = O(log n) <br>
		rep instanceof DblOpenAdrHashTableUos implies Time = O(1) (expected), O(m) m = table size (worst case)
		@param x The item to count */
	public int frequency(Object x)
	{
		if (rep.has(x))
			return 1;
		else
			return 0;
	}

	/**	Insert a new item into the dictionary.<br>
		Recall that this is a set, so a check for duplicates must be made. <br>
		Analysis: (time for precondition check) for n = number of items inthe dictionary <br>
		rep instanceof ArrayedDictUos implies Time = O(n) <br>
		rep instanceof LinkedListUos implies Time = O(n) <br>
		rep instanceof BinaryTreeUos implies Time = O(m) for  m = length of the path in the tree  <br>
		rep instanceof StdOrderedDictUos implies Time = O(log n) <br>
		rep instanceof DblOpenAdrHashTableUos implies Time = O(1) (expected), O(m) m = table size (worst case)
		Analysis: (time for insert operation) <br>
		rep instanceof ArrayedDictUos implies Time = O(1) <br>
		rep instanceof LinkedListUos implies Time = O(1) <br>
		rep instanceof BinaryTreeUos implies Time = O(1) <br>
		rep instanceof StdOrderedDictUos implies Time = O(log n) <br>
		rep instanceof DblOpenAdrHashTableUos implies Time = O(1) (expected), O(m) m = table size (worst case)
		PRECONDITION: <br>
		<ul>
			!isFull()
			!has(x)
		</ul>
		@param x The item to be inserted into the dictionary */
	public void insert(Object x) throws ContainerFullUosException, DuplicateItemsUosException
	{
		if (isFull())
			throw new ContainerFullUosException("Cannot insert into a full set");
		if (has(x))
			throw new DuplicateItemsUosException("Cannot insert a duplicate item into a set");

		rep.insert(x);
	}

	/**	Delete an item from the dictionary. <br>
		Analysis: for n = number of items inthe dictionary <br>
		rep instanceof ArrayedDictUos implies Time = O(n) <br>
		rep instanceof LinkedListUos implies Time = O(n) <br>
		rep instanceof BinaryTreeUos implies Time = O(m) for  m = length of the path in the tree  <br>
		rep instanceof StdOrderedDictUos implies Time = O(log n) <br>
		rep instanceof DblOpenAdrHashTableUos implies Time = O(1) (expected), O(m) m = table size (worst case)
		@param x The item to be deleted */
	public void delete(Object x)
	{
		rep.delete(x);
	}

	/**	Delete the current item from the dictionary. <br>
		Analysis: for n = number of items inthe dictionary <br>
		rep instanceof ArrayedDictUos implies Time = O(n) <br>
		rep instanceof LinkedListUos implies Time = O(1) <br>
		rep instanceof BinaryTreeUos implies Time = O(m) for  m = length of the path to the successor  <br>
		rep instanceof StdOrderedDictUos implies Time = O(log n) <br>
		rep instanceof DblOpenAdrHashTableUos implies Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			itemExists()
		</ul> */
	public void deleteItem()
	{
		if (!itemExists())
			throw new NoIteratorItemUosException("Cannot delete an item that does not exist.");

		rep.deleteItem();
	}

	/**	Move the cursor to the first item in the dictionary. <br>
		Analysis: <br>
		rep instanceof ArrayedDictUos implies Time = O(1) <br>
		rep instanceof LinkedListUos implies Time = O(1) <br>
		rep instanceof BinaryTreeUos implies Time = O(m), m = length of the leftmost path <br>
		rep instanceof StdOrderedDictUos implies Time = O(log n), n = number of items in the dictionary <br>
		rep instanceof DblOpenAdrHashTableUos implies Time = O(1) (expected) O(m) m = table size (worst case) */
	public void goFirst()
	{
		rep.goFirst();
	}

	/**	Advance the cursor to the next item in the dictionary. <br>
		Analysis: <br>
		rep instanceof ArrayedDictUos implies Time = O(1) <br>
		rep instanceof LinkedListUos implies Time = O(1) <br>
		rep instanceof BinaryTreeUos implies Time = O(m), m = length of the tree path <br>
		rep instanceof StdOrderedDictUos implies Time = O(log n), n = number of items in the dictionary <br>
		rep instanceof DblOpenAdrHashTableUos implies Time = O(1) (expected) O(m) m = table size (worst case) <br>
		PRECONDITION: <br>
		<ul>
			!after()
		</ul> */
	public void goForth() throws AfterTheEndUosException 
	{
		if (after())
			throw new AfterTheEndUosException("Cannot go forth when already after.");
			
		rep.goForth();
	}

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

	/**	Is the current position before the start of the dictionary. <br>
		Analysis: Time = O(1) */
	public boolean before()
	{
		return rep.before();
	}

	/**	Move the cursor to the after position. <br>
		Analysis: <br>
		rep instanceof ArrayedDictUos implies Time = O(1) <br>
		rep instanceof LinkedListUos implies Time = O(1) <br>
		rep instanceof BinaryTreeUos implies Time = O(m), m = length of rightmost path <br>
		rep instanceof StdOrderedDictUos implies Time = O(log n), n = number of items in the dictionary <br>
		rep instanceof DblOpenAdrHashTableUos implies Time = O(1) */
	public void goAfter()
	{
		rep.goAfter();
	}

	/**	Move the cursor to the before position. <br>
		Analysis:  Time = O(1)) */
	public void goBefore()
	{
		rep.goBefore();
	}

	/**	Returns the current position in the dictionary. <br>
		Analysis: Time = O(1) */
	public CursorUos currentPosition()
	{
		return rep.currentPosition();
	}

	/**	Go to the specified position. <br>
		Analysis: Time = O(1) */
	public void goPosition(CursorUos pos)
	{
		rep.goPosition(pos);
	}

	/**	Return a string representation of the dictionary. <br>
		Analysis: Time = O(n), n = number of items in the dictionary */
	public String toString()
	{
		return rep.toString();
	}
	
	/**	Are the two items passed in as arguments equal?. <br>
		Analysis: Time = O(1) 
		@param x The item to be compared to y
		@param y The item to be compared to  x */
	public boolean membershipEquals(Object x, Object y)
	{
		return rep.membershipEquals(x, y);
	}

	/**	Restart searching after subsequent calls to search. <br>
		Analysis: Time = O(1) */
	public void restartSearches()
	{
		rep.restartSearches();
	}
	
	/**	Resume searching from the current position after subsequent
		calls to search. <br>
		Analysis: Time = O(1) */
	public void resumeSearches()
	{
		rep.resumeSearches();
	}
	
	protected boolean objectReferenceComparison = false;
	
	public void compareObjectReferences()
	{
		objectReferenceComparison = true;
	}

	public void compareContents()
	{
		objectReferenceComparison = false;
	}
		
}