openadrhashtableuos.java

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

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

package dslib.hashtable;

import dslib.exception.*;
import dslib.dictionary.arrayed.*;
import dslib.base.*;
import dslib.list.*;
import dslib.hashtable.HashTableUos;

/** An abstract class for an open address HashTable that forms a DictUos. */
public abstract class OpenAdrHashTableUos extends HashTableUos implements BoundedUos
{    
	/** Array to store the hashable items. */
	protected Object[] hashArray;

	/**	The location of the current item. */
	protected int itemLocation;
	
	/**	Is the hash table fixed in size so that it might overflow? Default is false. */
	protected boolean capacityFixed = false;

	/**	Create hash table structure with at least size locations. <br>
		(dummyItem is an artificial impossible item.) 
		Analysis: Time = O(size*size) to find a prime number large enough
		@param size size of the hash table is at least this large 
		@param dummyItem object used to mark deletions; should not be possible to
		insert it as a normal item */
	public OpenAdrHashTableUos(int size, Object dummyItem)
	{
		hashArray = new Object[higherPrime(size)];
		count = 0;
		deleted = dummyItem;
		itemLocation = -1;  // Before the start of the table
	}
	
	/**	Special item to indicate that an item has been deleted from this location.  */
	protected Object deleted;
	
	/**	The step size for the probe sequence. <br>
		Analysis: Time = O(1) 
		@param y item for which the hashing displacement is to be found */
	public abstract int hashCodeDisplacement(Object y);
	
	/**	Return a new instance of the actual class of `this'. <br>
		Analysis: Time = O(1) */
	public abstract OpenAdrHashTableUos newInstance(int newSize, Object dummyItem);

	/**	Is there a current item?. <br>  
		Analysis: Time = O(1)  */
	public boolean itemExists()
	{
		return  ((itemLocation >= 0) && (itemLocation <= capacity() - 1)) 
			&& ((hashArray[itemLocation] != null) && (hashArray[itemLocation] != deleted));
	}

	/**	The current item. <br>
		Analysis : Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			itemExists()
		</ul> */
	public Object item() throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("Cannot return an item that does not exist.");
		
		return hashArray[itemLocation];
	}
	
	/**	Set capacityFixed to newValue. <br> 
		Analysis: Time = O(1)  */
	public void setCapacityFixed(boolean newValue)
	{
		capacityFixed = newValue;
	}
	
	/**	Size of the hash table. <br> 
		Analysis: Time = O(1) */
	public int capacity()
	{
		return hashArray.length;	
	}
	
	/**	Does the hashtable contain 'y'?. <br> 
		Analysis: Successful Expected time =  O(-ln(1-loadFactor)/loadFactor) <br>
			       Unsuccessful Expected time =  O(1/(1-loadFactor))
		@param y item being sought */
	public boolean has(Object y)
	{
		int saveLocation;
		saveLocation = itemLocation;
		search(y);
		boolean result= itemExists();
		itemLocation = saveLocation;
		return result;
	}   
	
	/**	Is the table full?  If the capacity is not fixed then the  hash table is never full. <br> 
		Analysis: Time = O(1) */
	public boolean isFull()
	{
		return capacityFixed && (count==capacity());
	}
	
	/**	Is the current position before the start of the structure?. <br> 
		Analysis: Time = O(1) */
	public boolean before()
	{
		return itemLocation<0;
	}
	
	/**	Is the current position after the end of the structure?. <br> 
		Analysis: Time = O(1) */
	public boolean after()
	{
		return itemLocation==capacity();
	}
	
	/**	Insert y. <br>
		Analysis: Expected time = O(1/(1-loadFactor)) <br> 
		PRECONDITION: <br>
		<ul>
			!isFull() 
		</ul>
		@param y item to be inserted in the hash table */
	public void insert(Object y) throws ContainerFullUosException
	{
		if (isFull())
			throw new ContainerFullUosException("Hashtable is full so cannot do another insert"
			       + " since capacity is fixed.");
		
		itemLocation = hashPos(y);
		int hashShift = hashCodeDisplacement(y);
		while ((hashArray[itemLocation] != null) && (hashArray[itemLocation] != deleted))
			itemLocation = (itemLocation + hashShift) % capacity();	
		hashArray[itemLocation] = y;
		count++;
		if (!capacityFixed && (count > 0.8*capacity()))
			rebuild(3 * capacity() / 2 + 1);
	}
	
	/**	Remove all items from the hash table. <br> 
		Analysis: Time = O(capacity()) */
	public void wipeOut()
	{
		for (int i=0; i<capacity(); i++)
			hashArray[i] = null;      
		count = 0;
		itemLocation = -1;
	}
	
	/**	Rebuild the hash table. <br> 
		Analysis: Time = O(newSize^2) (to find new prime size)
		@param newSize new size of the hash table is at least this large */
	public void rebuild(int newSize)
	{
		OpenAdrHashTableUos newTable = newInstance(newSize, deleted);
		newTable.setCapacityFixed(capacityFixed);
		for (int i=0; i<capacity(); i++)
			if ((hashArray[i]!=null) && (hashArray[i]!=deleted))
				newTable.insert(hashArray[i]);
				
		Object saveItem = null;
		boolean itemExists;
		if (itemExists())
		{ 
			saveItem = item();
			itemExists = true;
		}
		else
			itemExists = false;	
		/* Copy newTable to this */
		hashArray = newTable.hashArray;
		if (itemExists)
			search(saveItem);
		else
			goAfter();
	}
	
	/**	Remove the entry y from the table. <br> 
		Analysis: Expected Time = O(-ln(1-loadFactor)/loadFactor) <br> 	
		PRECONDITION: <br>
		<ul>
			has(y)
		</ul>
		@param y item to be deleted from the hash table */
	public void delete(Object y) throws ItemNotFoundUosException
	{
		if (!has(y))
			throw new ItemNotFoundUosException("Cannot delete an item that does not exist.");
		
		int saveLocation = itemLocation;
		search(y);
				
		if (itemLocation!=saveLocation)
		{
			/* Deleting an item other than current item  */
			deleteItem();
			itemLocation = saveLocation;
		}
		else
			deleteItem(); 
	}
	
	/**	Delete the current item. <br> 
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			itemExists()
		</ul>*/
	public void deleteItem() throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("Cannot delete an item that does not exist.");
		
		hashArray[itemLocation] = deleted;
		count--;
		goForth();
	}
	
	/**	Advance one item in the data structure. <br> 
		Analysis: Time = O(capacity()) - worst case <br>
		PRECONDITION: <br>
		<ul>
			!after()
		</ul>*/
	public void goForth() throws AfterTheEndUosException
	{
		if (after())
			throw new AfterTheEndUosException("Cannot advance since already after.");
			
		itemLocation++;
		while (!after() && (!itemExists()))
			itemLocation++;
	}
	
	/**	Go to first item of the data structure (if it exists). <br> 
		Analysis: Time = O(capacity()) - worst case */
	public void goFirst()
	{
		goBefore();
		goForth();
	} 
	
	/**	Move to prior to the first item. <br> 
		Analysis: Time = O(1) */
	public void goBefore()
	{
		itemLocation = -1;
	}
	
	/**	Move to after the last item. <br> 
		Analysis: Time = O(1) */
	public void goAfter()
	{
		itemLocation = capacity();
	}
	
	/**	If y exists in the table, then make it the current item.
		Make the next occurrence current if searchesContinue. <br> 
		Analysis: Successful Expected time =  O(-ln(1-loadFactor)/loadFactor) <br>
				<ul><ul>Unsuccessful Expected time =  O(1/(1-loadFactor)) </ul></ul><br>
		PRECONDITION: <br>
		<ul>
			!(searchesContinue && after())
		</ul>
		@param y item being sought */
	public void search(Object y) throws AfterTheEndUosException
	{
		if (searchesContinue && after())
			throw new AfterTheEndUosException("Cannot continue to search for an item since already after.");
			
		int saveHashPos = hashPos(y);
		int hashShift = hashCodeDisplacement(y);
		if (searchesContinue && !before())
			itemLocation = (itemLocation + hashShift) % capacity();
		else
			itemLocation = saveHashPos;
		
		boolean wrappedAround = false;
		while ((hashArray[itemLocation] != null) && !(wrappedAround) 
			&& !(itemExists() && membershipEquals(y,item())))
		{
			itemLocation = (itemLocation + hashShift) % capacity();
			if (itemLocation == saveHashPos)
				wrappedAround = true;
		}
		
		if (hashArray[itemLocation] == null || (wrappedAround))
			goAfter();
	}
	
	/**	Return item y from the hash table. <br> 
		Analysis: Successful Expected time = O(-ln(1-loadFactor)/loadFactor) <br>
			       Unsuccessful Expected time = O(1/(1-loadFactor)) <br>
		PRECONDITION: <br>
		<ul>
			has(y)
		</ul>
		@param y item to obtain from the hash table */
	public Object obtain(Object y) throws ItemNotFoundUosException
	{
		if(!has(y))
			throw new ItemNotFoundUosException("Cannot obtain an itme that does not exist.");
		
		int saveLocation = itemLocation;
		boolean saveSearchMode = searchesContinue;
		restartSearches();
		search(y);
		Object result = item();
		itemLocation = saveLocation;
		searchesContinue = saveSearchMode;
		return result;
	}   
	
	/**	String representation of the hash table. <br> 
		Analysis: Time = O(capacity()) */
	public String toString()
	{
		String result = new String();
		for (int i = 0; i<capacity(); i++)
		{
			if ((hashArray[i]!=null) && (hashArray[i]!=deleted))
				result += hashArray[i].toString() + " ";
			else
			{
				if (hashArray[i]==deleted)
					result += " * ";
				if (hashArray[i]==null)
					result += " - ";
			}
		}
		return result;
	}
	
	/**	An iterator at the current position. <br> 
		Analysis: Time = O(count) */
	public CursorUos currentPosition()
	{
		 ArrayedIteratorUos result = new ArrayedIteratorUos(hashArray, count);
		 result.setPos(itemLocation);
		 return result;
	}

	/**	Go the the position in the hash table specified by position. <br> 
		Analysis: Time = O(1)
		@param position position of to which to move */
	public void goPosition(CursorUos position) 
	{
		 itemLocation = ((ArrayedIteratorUos)position).pos();
	}
}