package finiteAutomata;
import java.util.Vector;
/**
 * Data structure which allows for insertions, deletions, and finds in 
 * constant average time.  
 * 
 * <BR><BR>This Hashtable class uses separate chaining to store Associations 
 * (key-value pairs).  Any non-null object can be used as the key (which 
 * is used as input to the hashing function). To successfully store and 
 * retrieve values from a hashtable, the objects used as keys must 
 * implement the hashCode method and the equals method. To store an 
 * Association, apply the hash function to its key and store the 
 * Association in the resulting list (first check that an equivalent
 * Association is not already present).  To retrieve an Association, 
 * apply the hash function to its key and search for it in the resulting 
 * list. If the hashtable is appropriately long and if the hash function 
 * does a good job of distributing the keys evenly among the hashing
 * locations, then all the lists should be short and it will be very 
 * quick to find, insert, and delete based on keys.
 * 
 * <BR><BR>Data Fields:
 * A Hashtable is based on an array "table" of Vectors.  The integer field
 * "tableSize" gives the length of the array, and should be a prime number
 * (to help insure even distribution for the hashing function).
 * The integer field "size" tells how many Associations are currently 
 * stored; load factor can thus be calculated by size / tableSize. (Load 
 * factor around 1.0 is ideal for efficient use of time and space in open 
 * chaining.)
 * 
 * @author Barbara Wahl
 * @version Fall 2007
 */
public class Hashtable {

	// ** DATA FIELDS **
	/**
	 * Vector lists for storing Assocations
	 */
	protected Vector[] table;
	/**
	 * length of the "table" array
	 */
	protected int tableSize;  
	/**
	 * number of Associations currently stored
	 */
	protected int size; 
	
	// ** CONSTRUCTORS **
	
	/**
	 * 1-parameter constructor.
	 * @param n table size
	 * @pre n > 0
	 * @post creates an empty Hashtable with tableSize = n
	 */
	public Hashtable(int n)
	{
		Assert.pre(n > 0,"n is positive");
		table = new Vector[n];
		for(int i=0; i<n; i++)
			table[i] = new Vector();
		tableSize = n;
		size = 0;
	}
	/**
	 * 0-parameter constructor.
	 *@post creates an empty Hashtable with tableSize = 101
	 */
	public Hashtable()
	{
		this(101);
	}
	
	/**
	 * Returns tableSize.
	 * @return tableSize
	 */
	public int tableSize()
	{
		return tableSize;
	}
	/**
	 * Returns number of Associations currently stored.
	 * @return size
	 */
	public int size()
	{
		return size;
	}
	/**
	 * Returns the current load factor, size divided by tableSize.
	 * @return size / tableSize
	 */
	public double loadFactor()
	{
		double loadF = ((double)size)/((double)tableSize);
		return loadF;
	}
	
	/**
	 * Returns the hash location for the provided key.
	 * @param key the key to be hashed on
	 * @return key.hashCode() % tableSize, the hashing location
	 * @pre key is not null
	 */
	protected int locate(Object key)
	{
		return Math.abs(key.hashCode() % tableSize);
	}
	/**
	 * Returns the index, relative to the Vector table[hash], of
	 * the Association with the given key.
	 * @param key the key to be located
	 * @param hash indexes the Vector to be searched 
	 * @return index of the Association in table[hash] with the
	 * given key, or -1 if not found there
	 * @pre key is not null
	 * @pre 0 <= hash < tableSize
	 */
	protected int indexOf(Object key, int hash)
	{
		Vector v = table[hash]; 
		return v.indexOf(new Association(key));		
	}
	/**
	 * Returns the value associated with key, or null (if not found).
	 * @param key the key to be searched on
	 * @return value of the stored Association with matching key
	 * @pre key is not null
	 * @post this Hashtable is not modified (the matching Association 
	 * is not removed, just accessed)
	 */
	public Object get(Object key)
	{
		Association current;
		int hash = locate(key); // which vector to look in
		int index = indexOf(key,hash); // location in that vector
		if(index < 0) 
			return null;
		else 
		{
			current = (Association)table[hash].elementAt(index);
			return (current.getValue());
		}
	}
	/**
	 * Returns true if an item with this same key exists in the hashtable.
	 * @param key the key to be searched on
	 * @return true iff an Association with matching key is found
	 * @pre key is not null
	 */
	public boolean contains(Object key)
	{
		int hash = locate(key);
		Association current;
		// if key is in table, it is in vector table[hash]
		boolean found = false;
		for(int i=0; i<table[hash].size(); i++)
		{
			current = (Association)table[hash].elementAt(i);		
			if(current.getKey().equals(key))
			{
				found = true;
				break;
			}			
		}
		return found;			
	}
	/**
	 * Inserts an Association.
	 * @param key the key to be searched on
	 * @param value the associated value for key
	 * @pre key is not null
	 * @post if an equivalent Association is not found in the table, 
	 * the given key-value pair is added to the appropriate vector
	 * and size is incremented
	 */
	public void insert(Object key, Object value)
	{
		int hash = locate(key); // which vector to look in
		int index = indexOf(key,hash); // location in that vector
		if(index < 0) // if not already in table...
		{
			table[hash].add(new Association(key,value));		
			size++;
		}
	}
	/**
	 * Removes an Association.
	 * @param key the key to be searched on
	 * @return the associated value for key, or null if not found
	 * @pre key is not null
	 * @post if found, the equivalent Association is removed from the
	 * table and size is decremented
	 */
	public Object remove(Object key)
	{
		int hash = locate(key); // which vector to look in
		int index = indexOf(key,hash); // location in that vector
		if(index < 0) // if not in table...
			return null;
		size--;       // else, decrement size & return value
		return ((Association)table[hash].remove(index)).getValue();			
	}
	/**
	 * True if no Associations are stored.
	 * @return size == 0
	 */
	public boolean isEmpty()
	{
		return size == 0;
	}
	/**
	 * Pretty-prints the hash table information.
	 * @post Reports tableSize and load factor, and for each stored
	 * Association prints the hash value, the index relative to the 
	 * vector in which the Association is stored, and the key-value 
	 * pair.
	 */
	public void printTable()
	{
		System.out.println("%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%");
		System.out.println("tableSize = " + tableSize);
		System.out.println("size = " + size);
		System.out.println("load factor = " + this.loadFactor());
		System.out.println("KEY-VALUE PAIRS IN TABLE:");
		for(int i=0; i<tableSize; i++)
			for(int j=0; j<table[i].size(); j++)
				System.out.println("hash = " +i+", index = " 
						+j+", pair = " + table[i].elementAt(j));		
		System.out.println("%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%");
	}

	// ** TEST METHOD **
	public static void main(String[] args) 
	{
		// create a hashtable
		Hashtable t = new Hashtable(19);
		
		// store associations in Hashtable
		t.insert("zero",new Integer(0));
		t.insert("one",new Integer(1));
		t.insert("two",new Integer(2));
		t.insert("three",new Integer(3));
		t.insert("four",new Integer(4));
		t.insert("five",new Integer(5));
		t.insert("six",new Integer(6));
		t.insert("seven",new Integer(7));
		t.insert("eight",new Integer(8));
		t.insert("nine",new Integer(9));
		t.insert("ten",new Integer(10));
		
		// print table
		t.printTable();
		
		// remove two items & print again
		t.remove("ten");
		t.remove("nine");
		t.printTable();
		
		// test contains
		System.out.println("Does table contain \"eleven\"?  " + 
				t.contains("eleven"));
		System.out.println("Does table contain \"five\"?  " + 
				t.contains("five"));
		
		// try adding item with duplicate key
		t.insert("seven", new Integer(20));
		t.printTable();
		
		// try removing item which isn't there
		t.remove("cat");
		t.printTable();
		
		// try get method
		System.out.println("The value associated with \"two\" is: " + 
				t.get("two"));
		System.out.println("The value associated with \"cat\" is: " + 
				t.get("cat"));
	}

}