arrayedpkeyedbasicdictionary.java

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

/**	A keyed basic dictionary that stores an ordered sequence of (key, item)
	pairs in an array. There are procedures to insert and delete keyed items, 
	as well as the functions has and obtain. The first item of a pair is the 
	key, and the second item of a pair is the data value associated with the key. */
public class ArrayedPKeyedBasicDictionary
{
	/**	The number of items in the dictionary. */
	int count;

	/**	The array storing the items. */
	Pair[ ] rep;

	/**	Current number of items in the dictionary.
		Analysis: Time = O(1) */
	public int count()
	{
		return 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();
	}

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

	/**	Create a dictionary with capacity size.
		Analysis: Time = O(size) */
	public ArrayedPKeyedBasicDictionary(int size)
	{
		rep = new Pair[size];
		count = 0;
	}
		
	/**	Does the dictionary contain an item with the key?
		Analysis: Time = O(log(count)) */
	public boolean has(Comparable key)
	{
		if (location(key) == count)  
			return false;
		else
			return true;
	}

	/**	An instance of an item with the key from the dictionary.
		Analysis: Time = O(log(count)) */
	public Object obtain(Comparable key)
	{
		return (rep[location(key)]).secondItem;
	}

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

	/**	Insert x and its key value into the keyed dictionary.
		Analysis : Time = O(count) */
	public void insert(Comparable key, Object x)
	{
		/*	Shift all higher-keyed items back one position. */
		int index = count - 1; 
		while ((index >= 0) && (key.compareTo(rep[index].firstItem) < 0))	   
		{
			rep[index + 1] = rep[index];
			index--;
		} 
		Pair newPair = new Pair(key, x);
		rep[index + 1] = newPair;
		count++;
	}
	
	/**	The location of the first occurrence of an item with the key,
		returning count if not found.
		Analysis: Time = O(log(count)) */
	public int location(Comparable key)
	{
		/*	Perform a binary search on the sorted array of elements. */
		int low = 0, high = count - 1 , middle = 0;
		boolean found = false;
		while (!found && (low <= high))
		{ 
			middle = (low + high) / 2;
			if (key.compareTo(rep[middle].firstItem) < 0)
				high = middle - 1;
			else if (key.compareTo(rep[middle].firstItem) > 0)
				low = middle + 1;
			else  // if necessary, move high to find the first occurrence
				if (middle != low)
					high = middle;
				else
					found = true;
		}
		if (found)
			return middle;
		else
			return count;	  
	}

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

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