arrayedkeyedbasicdictuos.java

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

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

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

/**	A KeyedBasicDictionaryUos implemented via an ordered sequence of 
	keyed items in an array.  Capabilities include insert for items, and 
	obtain, has, and delete by key. */
public class ArrayedKeyedBasicDictUos implements KeyedBasicDictUos, BoundedUos
{
	/**	Internal representation of the dictionary structure is based on this array. */
	protected KeyedUos[] rep;
  
	/**	The number of items in the dictionary. */
	protected int count;
  
	/**	Default constructor that makes a keyed dictionary that is a set. <br> 
		Analysis: Time: O(size) 
		@param size capacity of the dictionary */
	public ArrayedKeyedBasicDictUos(int size)
	{
		rep = new KeyedUos[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 dictionary empty?. <br> 
		Analysis: Time = O(1) */
	public boolean isEmpty()
	{
		return (count==0);
	}

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

	/**	Finds the first location of 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 being sought */
	protected int location(Comparable k) 
	{
		/* perform a binary search on the sorted array of elements */
		int low = 0;
		int high = count - 1 ;
		int middle = 0;
		boolean found = false;
		while (!found && (low<=high))
		{ 
			middle = (low + high)/2;
			if (k.compareTo(rep[middle].key())<0)
				high = middle - 1;
			else if (k.compareTo(rep[middle].key())>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 dictionary contain an item with key 'k'?.  <br> 
		Analysis: Time = O (log(count)))
		@param k key whose presence is to be determined */
	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 k key of the item to obtain from the dictionary */
	public KeyedUos obtain(Comparable k) throws ItemNotFoundUosException
	{
		if (!has(k))
				throw new ItemNotFoundUosException("Cannot return an item that does not exist.");	
	
		return rep[location(k)];
	}

	/**	Insert a key item pair into the dictionary. <br>
		Analysis: Time = O(count) <br>
		PRECONDITION:  <br>
		<ul>
			!isFull() <br>
			!has(x.key()) <br>
		</ul> 
		@param x item to insert into the dictionary*/
	public void insert(KeyedUos x) throws ContainerFullUosException, 
	                 DuplicateItemsUosException
	{
		if (isFull())
			throw new ContainerFullUosException("Cannot insert into a full array.");
		if (has(x.key()))
			throw new DuplicateItemsUosException("Cannot insert since duplicates are not allowed in a set.");
		
		int index = count - 1; 
		while ((index>=0) && (x.key().compareTo(rep[index].key())<0))       
		{
			rep[index + 1] = rep[index];
			index--;
		} 
		rep[index + 1] = x;
		count++;
	}

	/**	Set x to replace an item having the same key value as x. <br> 
		Analysis: Time = O(log(count)) <br>
		PRECONDITION:  <br>
		<ul>
			has(x.key()) 
		</ul> 
		@param x replacement item for an item with the same key value */
	public void set(KeyedUos x) throws ItemNotFoundUosException
	{
		if (!has(x.key()))
			throw new ItemNotFoundUosException("Cannot associate an item with a key that does not exist.");
	
		rep[location(x.key())] = x;
	}

	/**	Delete the item 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 from the dictionary */
	public void delete(Comparable k) throws ItemNotFoundUosException
	{
		if (!has(k))
				throw new ItemNotFoundUosException("Cannot delete an item that does not exist.");
		
		int index = location(k);	
		while (!(index==(count-1)))   
		{  
			rep[index] = rep[index + 1];
			index++;
		}
		count--;
	}

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

		return temp;
	}

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