arrayedpkeyedbasicdictuos.java

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

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

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

/**	A PKeyedBasicDictUos implemented via an ordered sequence of (key, item)
	pairs in an array.  Capabilities include insert for key-item pairs, and 
	obtain, has, and delete by key. */
public class ArrayedPKeyedBasicDictUos implements PKeyedBasicDictUos, BoundedUos
{
	/**	Internal representation of the dictionary structure is based on this array. */
	protected PairUos[] rep;

	/**	The number of items in the dictionary. */
	protected int count;

	/**	Default constructor which makes a set with duplicates disallowed. <br>
		Analysis: Time = O(size)
		@param size capacity of the dictionary */
	public ArrayedPKeyedBasicDictUos(int size)
	{
		rep = new PairUos[size];
		count = 0;
	}

	/**	Current number of elements in the dictionary. <br> 
		Analysis: Time = O(1) */
	public int count()
	{
		return count;
	}

	/**	Maximum number of elements allowed to be stored in this data structure. <br> 
		Analysis: Time = O(1) */
	public int capacity()
	{
		return rep.length;
	}

	/**	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 == capacity(); 
	}

	/**	Finds the first location of the item with key k and 
		returns count if the item is not found. <br> 
		Analysis: Time = O(log(count)) 
		@param k key of the item to find the location of */
	protected int location(Comparable k) 
	{
		/*	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 (k.compareTo(rep[middle].firstItem()) < 0)
				high = middle - 1;
			else if (k.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;
	}

	/**	Does the data structure contain an item with key k?.<br>
		Analysis: Time = O (log(count))
		@param k item to check the dictionary for */
	public boolean has(Comparable k) 
	{
		int pos = location(k);
		if (pos == count())
			return false;
		else
			return true;
	}

	/**	Return the item with key k from the data structure. <br> 
		Analysis: Time = O(log(count)) <br>
		PRECONDITION:  <br>
		<ul>
			has(k) 
		</ul>
		@param i key of the item to obtain from the dictionary */
	public Object obtain(Comparable k) throws ItemNotFoundUosException
	{
		if (!has(k))
			throw new ItemNotFoundUosException("Cannot obtain items that do not exist.");

		return rep[location(k)].secondItem();
	}

	/**	Insert a key and item pair into the data structure. <br>
		Analysis: Time = O(count) <br>
		PRECONDITION:  <br>
		<ul>
			!isFull() <br>
			!(has(key))
		</ul>
		@param key key of the new item
		@param item item to be inserted */
	public void insert(Comparable key, Object item) throws ContainerFullUosException, DuplicateItemsUosException
	{
		if (isFull())
			throw new ContainerFullUosException("Cannot insert into a full array container");
		if (has(key))
			throw new DuplicateItemsUosException("Cannot insert an item that already exists into a set.");
		
		int index = count - 1; 
		while ((index >= 0) && (key.compareTo(rep[index].firstItem()) < 0))
		{
			rep[index + 1] = rep[index];
			index--;
		}
		PairUos insertionPair = new PairUos(key, item);
		rep[index+1] = insertionPair;
		count++;
	}

	/**	Set the item associated with key k to be x. <br>
		Analysis: Time = O(log(count)) <br>
		PRECONDITION:<br>
		<ul>
			has(k)
		</ul>
		@param k key of the new item and the item to be replaced
		@param x replacement item for an item with the same key value */
	public void set(Comparable k, Object x) throws ItemNotFoundUosException
	{
		if (!has(k))
			throw new ItemNotFoundUosException("Cannot set item since it does not exist.");

		rep[location(k)].setSecondItem(x);
	}

	/**	Delete an object from the dictionary with key k. <br>
		Analysis: Time = O(count) <br>
		PRECONDITION: <br>
		<ul>
			has(k)
		</ul>
		@param k key of item to be deleted */
	public void delete(Comparable k) throws ItemNotFoundUosException
	{
		if (!has(k))
			throw new ItemNotFoundUosException("Cannot delele an item that does not exist.");

		int index = location(k);
		/*	Starting at the location to the right of the deleted item,
			shift all items to the left one location */
		for (int i = index + 1; i < count; i++)
			rep[i-1] = rep[i];
		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] + " ";
		return result;
	}

	/**	Clear the data structure of all present elements 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;
		}
	}
}