hashtableuos.java

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

/* HashTableUos.java
 * ---------------------------------------------
 * Copyright (c) 2001 University of Saskatchewan
 * All Rights Reserved
 * --------------------------------------------- */

package dslib.hashtable;

import dslib.exception.*;
import dslib.dictionary.DictUos;
import dslib.base.*;
import java.math.BigInteger;

/**	A HashTable version of a Dictionary used to store items by their hash value. 
	It has functions to insert, delete, obtain, and  search for items, and
	has a frequency function and a current item that can be deleted.  A linear
	iterator is included to move the current item through the hash table. */
public abstract class HashTableUos implements DictUos
{
	/**	Number of entries in the hash table. */
	protected int count;

	/**	Size of the hash table. */
	public abstract int capacity();

	/**	Number of entries in the hash table. <br>
		Analysis: Time = O(1) */
	public int count()
	{
		return count;
	}

	/**	Ratio of the number of items to the table capacity. <br>
		Analysis: Time = O(1) */
	public double loadFactor()
	{
		return ((double)count) / capacity();
	}

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

	/**	Default hash position is obtained by the simple division method, which is
		calculated by using the object's default hash code. <br>
		Analysis: Time = O(1)
		@param y item to calculate its hash position */
	public int hashPos(Object y)
	{
		return Math.abs(y.hashCode()) % capacity();
	}

	/**	Insert y into the hash table and make it current item. <br>
		PRECONDITION:
		<ul>
			!isFull() 
		</ul>
		@param y item to be inserted into the hash table */
	public abstract void insert(Object y) throws ContainerFullUosException;

	/**	Remove item y from the hash table. <br> 
		PRECONDITION: <br>
		<ul>
			has(y) 
		</ul>
		@param y item to be deleted from the hash table */
	public abstract void delete(Object y) throws ItemNotFoundUosException;

	/**	Find the first prime higher than value. <br> 
		Analysis: Time = O(n^2), n = 2 * value 
		@param value number to find the next highest prime of */
	protected int higherPrime(int value)
	{
		int[] table = new int[2 * value]; // there is a prime between value and 2*value
		/*	Mark locations not prime with a 1. */
		int i = 2;
		while (!((i >= value) && (table[i] == 0)))
		{
			if (table[i] == 0) // if prime, mark multiples of it 
				for (int x = i+i; x < table.length; x += i)
					table[x] = 1;
			i++;
		}
		return i;
	}

	/**	Should search continue from current item or start at the beginning?. */
	protected boolean searchesContinue = false;

	/**	Following searches start from the first position. <br> 
		Analysis: Time = O(1) */
	public void restartSearches()
	{
		searchesContinue = false;
	}

	/**	Following searches continue from the current position. <br>
		Analysis: Time = O(1) */
	public void resumeSearches()
	{
		searchesContinue = true;
	}

	/**	The number of times key i occurs within the hash table. <br> 
		Analysis: Time = O(n), where n = number of items in the data structure 
		@param i item to check how often it occurs in the hash table */
	public int frequency(Object i)
	{
		boolean saveSearchMode;
		
		int result = 0;
		saveSearchMode = searchesContinue;
		CursorUos savePos = currentPosition();
		restartSearches();
		search(i);
		resumeSearches();
		while (itemExists())
		{
			result++;
			search(i);
		}
		searchesContinue = saveSearchMode;
		goPosition(savePos);
		return result;
	}

	/**	Test whether x equals y using the current comparison mode.  
		Analysis: Time = O(1)
		@param x item to compare to y
		@param y item to compare to x */
	public boolean membershipEquals(Object x, Object y)
	{
		if (objectReferenceComparison & x == y)
			return true;
		else if ((x instanceof Comparable) && (y instanceof Comparable))
			return  0 == ((Comparable)x).compareTo(y);
		else if (x.equals(y))
			return true;
		else 
			return false;
	}

	/**	Compare object references or object contents; default to contents. */
	protected boolean objectReferenceComparison = false;  

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

	/**	Set comparison operations to use compareTo or equals; this is the default. <br>
		Analysis: Time = O(1) */
	public void compareContents()
	{
		objectReferenceComparison = false;
	}

	/**	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;
		}
	}
}