import java.util.*;
import java.io.*;

/**
 *
 * @author Sriram Pemmaraju
 * @date Nov 13th, 2008, modified on Nov 15th
 */

public class wordList{

	private wordPair[] hashTable; // an array of wordPair objects used as a hash table
	private int M;		      // the size of the hash table
	private int numWords; 	      // number of words in the has table

	private int numProbes;	      // keeps track of the total number of probes performed
				      // the only purpose of this is to generate statistics on
				      // average number of probes performed per insertion

	private int maxProbes; 	      // keeps track of the maximum number of probes
				      // made for any insertion
	
	/**
        * The default constructor assumes, somewhat arbitrarly that the user is interested
	* in inserting 20 words into the table. I want to define a table 5 times that size,
	* so I use the prime 101 as the table size.
        */
        public wordList() {
		M = 101; // M is assigned a prime number about 5 times 20
		hashTable = new wordPair[M]; // the default values of all slots is null 
		numWords = 0;
		numProbes = 0;
		maxProbes = 0;
	}

	/**
        * This constructor is given the number of words t the user expects to insert into the
	* table. We want to pick a prime, just more than 5*t, as the hash table size
	*
	* @param: an int t that is the number of words that the user expects to place
	*         in the hash table
        */
        public wordList(int t) {
		M = getPrime(5*t); // this returns the smallest prime number >= 5*t 
		hashTable = new wordPair[M]; // the default values of all slots is null 
		numWords = 0;
		numProbes = 0;
		maxProbes = 0;
	}

	/**
        * This returns the smallest prime at least as large as the given parameter x
	*
	* @param: an int x that is a lower bound on the prime number returned
        */
        private int getPrime(int x) {
		// Currently this is dummy code
		return x;	
	}


	/**
	 * A private method that computes the hash value of a given string. 
 	* Assumes that the string consists of lower case letters, upper case letters, and 
 	* digits. Views the string as a base-32 number and returns equivalent
 	* decimal value modulo 32. Uses bit shifting for multiplying
 	* by 32 and Horner's rule for reducing number of multiplications
 	* 
 	* @param s is the String whose hash value needs to be computed
 	* @return an int value in the range 0..M-1 that is the hash value
 	*         of the given string s
 	*/
 	private int hash(String s) {

   		int hashValue = 0;
	
        	for(int i = 0; i < s.length(); i++) {
        		// Also note that we are now bit-shifting by 2 to the 6th or 64.
                	// Consider digits and map these to values in the range 1 - 10
			if((s.charAt(i) >= '0') && (s.charAt(i) <= '9'))
                		hashValue = ((hashValue << 6) + (s.charAt(i) - '0') + 1) % M;
                	// Consider upper case characters and map these to values in the range 11 - 36 
                	else if((s.charAt(i) >= 'A') && (s.charAt(i) <= 'Z'))
                		hashValue = ((hashValue << 6) + (s.charAt(i) - 'A') + 11) % M;
                	// Consider lower case characters and map these to values in the range 37 - 62 
                	else if((s.charAt(i) >= 'a') && (s.charAt(i) <= 'z'))
                		hashValue = ((hashValue << 6) + (s.charAt(i) - 'a') + 37) % M;
        	} // end of for-loop

         	return hashValue;
 	}

	
	/**
        * A private method that computes the index at which the ith quadratic probe into 
	* a hashtable of size M needs to be performed. The method returns the computed index.
        *
        * @param: s, the string for whom a slot is being probed
        * @return: the slot index at which the ith probe should be performed
        */
        private int hash(String s, int i) {

		// I use a long variable to avoid possible overflow
		long square = i*i;
		
		// Use the quadratic probing formula (h(s) + i^2)%M
		int slotIndex = (int)((hash(s) + square) % (long) M);

                return slotIndex;
        }

	

	/**
	 * This function inserts the given myWord into the hash table.
         * @param a given word called myWord that needs to be inserted into the hash table
         */
	public void insert(String myWord)
	{
		int probe = 0; // this is the probe number
		int slotIndex; // this is the index of the slot being probed

		// This is just for error-checking and should be commented
		// out in the typical running mode
		//System.out.println("word being inserted: " + myWord);

		// This is the loop that repeatedly probes the hash table
		// until an empty slot has been found. We are always guaranteed
		// to find an empty slot; so it is ok to do this with a while-true
		// and break out when successful
		while(true){
			// Find the index of the slot being probed
			slotIndex = hash(myWord, probe);

			// This is just for error-checking and should be commented
			// out in the typical running mode
			//System.out.println("slot index: " + slotIndex);
			
			// check if slot is empty
			if(hashTable[slotIndex] == null)
			{
				hashTable[slotIndex] = new wordPair(myWord);
				numWords++;

				// maxProbes is being updated just for reporting statistics
				if(probe > maxProbes)
					maxProbes = probe;

				// This is just for error-checking and should be commented
				// out in the typical running mode
				//System.out.println("Inserted word.");

				return;
			}
			// check is slot contains the word we are trying to insert
			// In this case we are done and we exit after updating maxProbes
			else if(myWord.equals(hashTable[slotIndex].getWord()))
			{
				// maxProbes is being updated just for reporting statistics
				if(probe > maxProbes)
					maxProbes = probe;

				// This is just for error-checking and should be commented
				// out in the typical running mode
				//System.out.println("Word already in table.");

				return;
			}

			probe++;
			numProbes++; // this is being updated just for reporting
				     // statistics
		}
			
		
		// Currently this is missing code for resizing the hash table.
		// Will be inserted in the next version
	}

	/**
         * @param a given word called myWord that needs to be searched for in the hash table
	 * @return true if myWord is found in the hash table, false otherwise
         */
	public boolean search(String myWord)
	{
                int slotIndex; // this is the index of the slot being probed

                // This is the loop that repeatedly probes the hash table
                // until the word we are looking for has been found or we	
		// know for sure that there is no hope of finding the word

		// The fact that it is enough to use probe values from 0 through
		// (M-1)/2 is because it is known that for the probing function we are
		// using, the slot indices for these probe values will be distinct.
		// Since our table is at least half empty, every insertion succeeds
		// with probe values between 0..(M-1)/2 and therefore if myWord exists
		// in the table, it will found using just this many probe values.
		for(int probe = 0; probe <= (M-1)/2; probe++)
		{
                        // Find the index of the slot being probed
                        slotIndex = hash(myWord, probe);

                        // check if slot is empty; in this case myWord cannot be in 
			// the hashTable
			if(hashTable[slotIndex] == null)
				return false;

                        if(myWord.equals(hashTable[slotIndex].getWord()))
                                return true;
                }

		return false;
	}

	/**
	 * @return: the number of words in the hash table. Runs in constant time
         */
	public int numberWords()
	{
		return numWords;	
	}

	/**
	 * @return: the size of the hash table. Runs in constant time
         */
	public int size()
	{
		return hashTable.length;	
	}

	/**
	 * @return: the average number of probes performed per insertion or
	 *          per word in the hash table
         */
	public double averageNumberOfProbes()
	{
		return (numProbes*1.0)/(numWords*1.0);
	}

	/**
	 * @return: the maximum number of probes performed over all insertions
         */
	public double maxNumberOfProbes()
	{
		return maxProbes;
	}

	/**
	 * Copies the strings in the hash table into an array of strings
         * in which the strings appear in contiguous slots and the size
         * of the array is exactly the number of strings in the hash table
         *
         * @return: the array of String objects
         */
	String[] copyIntoArray()
	{
		// Make a new String[] to copy the words into
		String[] wordArray = new String[numWords];
		
		// Counter for the wordArray
		int count = 0;

		// Scan the hash table and pick out words
		for(int i = 0; i < hashTable.length; i++)
			if(hashTable[i] != null)
				wordArray[count++] = hashTable[i].getWord();

		return wordArray;
	} 


	/**
	 * Prints the words in the hash table in alphabetical order
         */
	public void sortedPrint()
	{
		// Copy the strings in the hash table into an array of strings
		// in which the strings appear in contiguous slots and the size
		// of the array is exactly the number of strings in the hash table
		String[] wordArray = copyIntoArray();
		
		// Just call the sort method in the Arrays class
		Arrays.sort(wordArray);
		
		for(int i = 0; i < wordArray.length; i++)
			System.out.println(wordArray[i]);
	}


	/**
	 * Prints the words in the hash table into a file with name fileName in 
         * alphabetical order
         */
	public void sortedPrint(String fileName)
	{
		// Currently a dummy function; does nothing
		System.out.println("Inside sortedPrint(fileName)");
	}

}