arrayedbasicdictionary.java

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

/**	A basic dictionary that stores the items in an unordered array.
	Its capabilities include isEmpty, isFull, insert, has, delete, and obtain. */
public class ArrayedBasicDictionary
{
	/**	The number of items in the data structure. */
	int count;

	/**	Is the dictionary empty?
		Analysis: Time = O(1) */
	public boolean isEmpty()
	{
		return (count == 0);
	}

	/**	Is the dictionary full? 
		Analysis: Time = O(1) */
	public boolean isFull()
	{
		return count == capacity();
	}
	
	/**	Current number of items in the dictionary.
		Analysis: Time = O(1) */
	public int count()
	{
		return count;
	}

	/**	The storage for the items in the dictionary. */
	Object[ ] rep;

	/**	Create a dictionary with capacity size.
		Analysis: Time = O(size) */
	public ArrayedBasicDictionary(int size)
	{
		rep = new Object[size];
		count = 0;
	}

	/**	The maximum number of items allowed.
		Analysis: Time = O(1) */
	public int capacity()
	{
		return rep.length;
	}

	/**	Insert x into the dictionary.
		Analysis: Time = O(1) */
	public void insert(Object x)
	{
		/*	Insert at the right-hand end of the array, i.e., location = count. */
		rep[count] = x;
		count++;
	}

	/**	Does the dictionary contain 'y'?
		Analysis: Time = O(count) */
	public boolean has(Object y)
	{
		if (location(y) == count)  
			return false;
		else
			return true;
	}

	/**	An instance of x from the dictionary. 
		Analysis: Time = O(count) */
	public Object obtain(Object x)
	{
		return rep[location(x)];
	}

	/**	Delete the item x.
		Analysis: Time = O(count) */
	public void delete(Object x)
	{
		/*	Starting at the location to the right of the deleted item,
			shift all items to the left one location. */
		for (int i = location(x) + 1; i < count; i++)
			rep[i-1] = rep[i];
		count--;
	}

	/**	Return the location of the first occurrence of x, or count if not found.
		Analysis: Time = O(count) */
	public int location(Object x)
	{
		int index = 0;
		while ((index < count) && !(membershipEquals(x, rep[index])))
			index++;
		return index;   
	}

	/**	Comparison operations use == rather than 'equals'.
		Default: use 'equals' */
	boolean objectReferenceComparison = false;

	/**	Test whether x equals y using the current comparison mode. 
		Analysis: Time = O(1) */
	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(y);
		else if (x.equals(y))
			return true;
		else 
			return false;
	}
	
	/**	Set comparison operations to use 'equals'.
		Analysis: Time = O(1) */
	public void compareContents()
	{
		objectReferenceComparison = false;
	}

	/**	Set comparison operations to use ==. 
		Analysis: Time = O(1) */
	public void compareObjectReferences()
	{ 
		objectReferenceComparison = true;
	}

	/**	Remove all items from the data structure.
		Analysis: Time = O(1) */
	public void wipeOut()
	{
		count = 0;
	}

	/**	String representation of the dictionary.
		Analysis: Time = O(count) */
	public String toString()
	{
		String result = new String();
		for (int i = 0; i < count; i++)
			result += rep[i].toString() + " ";
		return result;
	}
}