import java.io.*;

/**************************************************************************
/* Programmer: Sriram Pemmaraju
/* Date: Oct 7th, 2007
/* Depends on the StringLink and the StringLinkList classes
/**************************************************************************/

class Dictionary{

	private StringLinkList[] table; // stores the hash table as an array of 
				  // singly linked lists
	private int M;		  // size of hash table
	private int numWords;	  // number of words in hash table

	// computes the hash function of a given string. Assumes
	// that the string consists of lower case letters. 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
	private int hash(String word)
	{
		int hashValue = 0;
		for(int i = 0; i < word.length(); i++)
			hashValue = ((hashValue << 5) + (word.charAt(i)-'a')) % M;

		return hashValue;
	}

	// Constructs a Dictionary of the given size
	public Dictionary(int size)
	{
		M = size;
		table = new StringLinkList[M];
		numWords = 0;

		// Initialize all linked lists in the hash table to
		// empty
		for(int i = 0; i < M; i++)
			table[i] = new StringLinkList();
	}
		
	// Searches for the given String myWord. Returns
	// null if not found; otherwise, returns a copy of the Link
	// containing the String
	public StringLink search(String myWord)
	{
		// compute the hash value of the given word
		int index = hash(myWord);

		// need to call the search/find function in the LinkList class
		StringLink myLink = table[index].find(myWord);
		
		// Either return null or a copy of the Link that was found
		if(myLink == null)
			return null;
		else
			return new StringLink(myLink.sData, null);
	}

	// Inserts the given String. Does not search first
	public void insert(String myWord)
	{
		int index = hash(myWord);
		table[index].insertFirst(myWord);
		numWords++;
	}

	// Deletes a Record with the given word
	public void delete(String myWord)
	{
		// compute the hash value of the given word
		int index = hash(myWord);

		// need to call the delete function in the LinkList class
		StringLink myLink = table[index].delete(myWord);
		
		if(myLink != null)
			numWords--;
	}

	// Returns the number of words in the hash table
	public int numberWords()
	{
		return numWords;
	}

	// Prints the contents of the hash table by printing
	// contents of each non-empty linked list in the hash table
	public void print()
	{
		for(int i = 0; i < M; i++)
			table[i].displayList();
	}

	public void printStatistics()
	{
		System.out.println("Number of words is: "+ numWords);
		
		System.out.println("Here is how the words are distributed:");
		int max = 0;
		for(int i = 0; i < M; i++)
			if(table[i].size() > max)
				max = table[i].size();
		System.out.println("Max length is: "+ max);

		int[] distribution = new int[max+1];
		for(int i = 0; i < distribution.length; i++)
			distribution[i] = 0;

		for(int i = 0; i < M; i++)
			distribution[table[i].size()]++;

		System.out.println("Length 	Number of words");
		for(int i = 0; i < distribution.length; i++)
			System.out.println(i+"\t "+distribution[i]);
			
	}
		

// The main method tests the class by inserting into a Dictionary object the
// 5757 words from words.dat.

	public static void main(String args[])
        {
		// I wanted to make the load factor about 1/5 by choosing a 
		// hash table size about 5 times the number of words that the
		// table is supposed to hold. There are 5757 words in words.dat.
		// 5757*5 = 28785 and the next smallest prime is 28789. Prime numbers
		// are sometimes chosen as hash table sizes because they tend to reduce
		// collisions.

		Dictionary D = new Dictionary(28789);
                try
                {
                        // This is one way to read from a file. The list of all 5-letter words
                        // is in a file called words.dat
                        BufferedReader in = new BufferedReader(new FileReader("words.dat"));
                        String word;

                        // read all the words from the file
                        System.out.println( "Reading words.dat..." );

                        while( (word = in.readLine()) != null )
                                // Insert the word into the Dictionary
                                D.insert( word );

                        in.close();

			D.printStatistics();
                }
                catch (IOException e) {}
	} // end of main


} // end of class