arrayedbasicdictuos.java

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

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

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

/**	A bounded unordered arrayed implementation of BasicDictUos.  
	Capabilities include obtain, insert, delete, search, and has. */
public class ArrayedBasicDictUos implements BasicDictUos, BoundedUos
{
	/**	Internal representation of the dictionary structure is based on this array. */
	protected Object[] rep;

	/**	Keeps track of the number of items in the dictionary. */
	protected int count;
 
	/**	Default constructor, which takes in the size of the new dictionary that is a bag. <br>
		Analysis: Time: O(size) 
		@param size capacity of the dictionary */
	public ArrayedBasicDictUos(int size)
	{
		rep = new Object[size];
		count = 0;
	}
  
	/**	As a default, objects will be compared by their contents. */
	protected boolean objectReferenceComparison = false;

	/**	Set comparison to compare object references. <br> 
		Analysis: Time= O(1) */
	public void compareObjectReferences()
	{
		objectReferenceComparison = true;
	}        
  
	/**	Set comparison mode to compare objects by their contents. <br> 
		Analysis: Time = O(1) */  
	public void compareContents()
	{
		objectReferenceComparison = false;
	}  
 
	/**	Are x and y equal when compared using desired comparison mode?. <br> 
		Analysis: Time = O(1) 
		@param x item to be compared to y
		@param y item to be compared to x */
	public boolean membershipEquals(Object x, Object y)
	{
		if (objectReferenceComparison)
			return (x==y);
		else if ((x instanceof Comparable) && (y instanceof Comparable))     
			return  0==((Comparable)x).compareTo((Comparable)y);
		else if (x.equals(y))
			return true;
		else 
			return false;
	}
  
	/**	Maximum number of elements allowed to be stored in this data structure. <br> 
		Analysis: Time = O(1) */
	public int capacity()
	{
		return rep.length;
	}
	
	/**	Current number of elements in the dictionary. <br> 
		Analysis: Time = O(1) */
	public int count()
	{
		return count;
	}

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

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

	/**	Finds the location of the item x and returns count if the item is not found. <br> 
		Analysis: Time = O(count) 
		@param x item being sought */ 
	protected int location(Object x)  
	{ 
		int index = 0;
		while ((index<count) && !(membershipEquals(x, rep[index])))
		{
			index++;
		}
		return index;   
	}  
  
	/**	Does the data structure contain element y?. <br> 
		Analysis: Time = O (count) 
		@param y item whose presence is to be determined */
	public boolean has(Object y)
	{
		if (location(y)==count)  
			return false;
		else
			return true;
	}

	/**	Return the version of object x from the data structure. <br> 
		Analysis: Time =  O(count) <br>
		PRECONDITION: <br>
		<ul>
			has(x) 
		</ul> 
		@param x item to obtain from the dictionary */
	public Object obtain(Object x) throws ItemNotFoundUosException
	{
		if (!has(x))
			throw new ItemNotFoundUosException("Cannot obtain an item that does not exist.");
		
		return rep[location(x)];
	}
  
	/**	Delete the object x from the dictionary. <br> 
		Analysis : Time: O(count) <br> 
		PRECONDITION:  <br>
		<ul>
			has(x) 
		</ul> 
		@param x item to delete from the dictionary */
	public void delete(Object x) throws ItemNotFoundUosException
	{
		if (!has(x))
			throw new ItemNotFoundUosException("Cannot delete an item that does not exist.");
	
		int index = location(x);
		while (!(index==(count-1)))   
		{  
			rep[index] = rep[index+1];
			index++;
		}
		count--;
	}
	
	/**	Insert object x into the data structure. <br> 
		Analysis: Time = O(1) <br>
		PRECONDITION:  <br>
		<ul>
			!isFull()
		</ul> 
		@param x item to be inserted into the dictionary */
	public void insert(Object x) throws ContainerFullUosException
	{
		if (isFull())
			throw new ContainerFullUosException("Cannot insert into a full array container.");
		
		rep[count] = x;
		count++;
	}

	/**	String representation of this data structure. <br> 
		Analysis: Time = O(count) */
	public String toString()
	{
		String result = new String();
		for (int i = 0; i < count; i++)
			result += rep[i].toString() + " ";
	 
		return result;
	}
  
	/**	Clear the data structure of all elements presently stored in it. <br> 
		Analysis: Time = O(1) */
	public void wipeOut()
	{
		count = 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;
		}
	}
}