stdunordereddictuos.java

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

/* StdUnorderedDictUos.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.bintree.*;

/**	A standard dictionary to store items of type Object that are
	not necessarily Comparable. */
public class StdUnorderedDictUos implements DictUos, SavableCursorUos
{
	/**	The internal representation */
	private LinkedListUos rep;

	/**	Create a new unordered dictionary that is a bag. <br> 
		Analysis: Time = O(1) */
	public StdUnorderedDictUos()
	{
		rep = new LinkedListUos();
	}

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

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

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

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

	/**	Does the structure contain y. <br>
		Analysis: Time = O(n), n = the length of the list 
		@param y The item that is to be searched for */
	public boolean has(Object y)
	{
		return rep.has(y);
	}

	/**	An instance of y from the container. <br>
		Analysis: Time = O(n), n = the length of the list <br>
		PRECONDITION: <br>
		<ul>
			has(y)
		</ul>
		@param y The item to obtain */
	public Object obtain(Object y) throws ItemNotFoundUosException
	{
		if (!has(y))
			throw new ItemNotFoundUosException("Cannot obtain an item that is not in the dictionary");

		return rep.obtain(y);
	}

	/**	A string representation of the contents of this dictionary. <br>
		Analysis: Time = O(n), n = the length of the list */
	public String toString()
	{
		return rep.toString();
	}

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

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

	/**	Insert x into the dictionary. <br>
		Analysis: Time = O(1)
		@param x The item to be inserted into the dictionary */
	public void insert(Object x) 
	{
		rep.insert(x);
	}

	/**	Move to an instance of x if one exists. <br>
		Analysis: Time = O(n), n = the length of the list
		@param x The item to be searched for */
	public void search(Object x)
	{
		rep.search(x);
	}

	/**	Delete the item x from the dictionary. <br>
		Analysis: Time = O(n), n = the length of the list <br>
		PRECONDITION: <br>
		<ul>
			has(x)
		</ul>
		@param x The item to be deleted */
	public void delete(Object x) throws ItemNotFoundUosException
	{
		if (!has(x))
			throw new ItemNotFoundUosException("Cannot delete an item that does not exist.");
		
		rep.delete(x);
	}

	/**	Delete the current item from the dictionary. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			itemExists()
		</ul> */
	public void deleteItem() throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("Cannot delete an item that does not exist.");
		rep.deleteItem();
	}

	/**	Remove all the items from the dictionary. <br>
		Analysis: Time = O(1) */
	public void wipeOut()
	{
		rep.wipeOut();
	}

	/**	Move to the next item in the dictionary. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			!after()
		</ul> */
	public void goForth() throws AfterTheEndUosException
	{
		if (after())
			throw new AfterTheEndUosException("Cannot advance to next item since already after.");
		rep.goForth();
	}

	/**	Move to the first item in the dictionary. <br>
		Analysis: Time = O(1) */
	public void goFirst()
	{
		rep.goFirst();
	}

	/**	Move before the first item in the dictionary. <br>
		Analysis: Time = O(1) */
	public void goBefore()
	{
		rep.goBefore();
	}

	/**	Move after the last item in the dictionary. <br>
		Analysis: Time = O(1) */
	public void goAfter()
	{
		rep.goAfter();
	}

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

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

	/**	An iterator for lists intialized to the first item. <br>
		Analysis: Time = O(1) */
	public LinearIteratorUos iterator()
	{
		return rep.iterator();
	}

	/**	Restart searches. <br>
		Analysis: Time = O(1) */
	public void restartSearches()
	{
		rep.restartSearches();
	}

	/**	Resume searches. <br>
		Analysis: Time = O(1) */
	public void resumeSearches()
	{
		rep.resumeSearches();
	}

	/**	Are the two objects equal using the current comparison mode. <br>
		Analysis: Time = O(1) 
		@param x One of the items to be compared
		@param y The other item to be compared */
	public boolean membershipEquals(Object x, Object y)
	{
		return rep.membershipEquals(x, y);
	}

	/**	Set comparison to be based upon object references. <br>
		Analysis: Time = O(1) */
	public void compareObjectReferences()
	{
		rep.compareObjectReferences();
	}
	
	/**	Set comparision to be based upon object contents. <br>
		Analysis: Time = O(1) */
	public void compareContents()
	{
		rep.compareContents();
	}

	/**	Returns the number of times that x appears in the dictionary. <br>
		Anslysis: Time = O(n), n = the number of items in the dictionary
		@param x The item to count */
	public int frequency(Object x)
	{
		return rep.frequency(x);
	}

	/**	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;
		}
	}
}