// Introduction to Algorithms
// Main program for testing Hash_Table
// Paul Taylor <pt@dcs.qmw.ac.uk> 11 March 1999

// convert login names to human names and vice versa
// TWO hash tables are used,
// to illustrate how a hash table is an "object" of class Hash_Table
// referenced by login_to_human and human_to_login -
// note how these are used with the put, get and containsKey methods 

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

public class Hash_Main  {
  public static void main (String[] args) throws IOException {

    //====================================================================
    //    INITIALISING THE HASH TABLE

    // the two hash tables in which to store the translations
    // Hash_Table (int initial_size, double initial_load_factor)
    Hash_Table login_to_human = new Hash_Table ();
    Hash_Table human_to_login = new Hash_Table ();

    // things you can control about the behaviour of the hashes
    // these methods set a new value, returning the old one
    // or, with no argument [eg int capacity()], just return the current one

    // parameters that control the size and growth of the table
    // if (used/capacity > load_factor) rebuild with
    // new_capacity = (old_capacity + increment) * inflation
    // int capacity (int new_capacity) - default 11
    // double load_factor (double new_load_factor) - default 0.5
    // double inflation (double new_inflation) - default 2.0
    // int increment (int new_increment) - default 0

    // variations on the algorithm, and debugging
    // try code+0,1,3,6,10,15,21,... instead of code+0,1,2,3,4,5,6,...
    // boolean use_quadratic_rehash (boolean new_use_quadratic_rehash)
    // print a message each time we rebuild the table
    // boolean report_rebuild (boolean new_report_rebuild)
    // two hacks for re-using deleted entries without rebuilding
    // boolean swap_deletes (boolean new_swap_deletes)
    // boolean tidy_deletes (boolean new_tidy_deletes) // linear rehash only

    // make our tables rather ineffecient to demonstrate the algorithm
    // warning: use_quadratic_rehash (true) with load_factor (0.9) crashes!
    // problem for maths students: why?
    login_to_human.load_factor (0.95);
    login_to_human.report_rebuild (true);
    login_to_human.use_quadratic_rehash (false);
    human_to_login.load_factor (0.8);
    human_to_login.report_rebuild (true);
    human_to_login.use_quadratic_rehash (true);

    //====================================================================
    //    FILLING THE HASH TABLE

    String login_names_file =
      new String ("/import/teaching/BSc/1st/I2A/1998-9/Hash/dcs-login");
    DataInputStream login_names_stream =
      new DataInputStream (new FileInputStream (login_names_file));

    // Note: The method java.lang.String readLine()
    // in class java.io.DataInputStream has been deprecated.

    while (true) { // read the database
      String line = login_names_stream.readLine();
      if (line == null) break;
      StringTokenizer toks = new StringTokenizer (line, ":");
      String login_name = toks.nextToken ();
      String human_name = toks.nextToken ();

      // add this entry to the translation tables
      login_to_human.put (login_name, human_name);
      human_to_login.put (human_name, login_name);
    }

    //====================================================================
    //    MANIPULATING THE FILLED HASH TABLE AS A WHOLE

    // the current usage
    // String stats() - a one-line message
    // int contents() - number of real entries
    // int used () - number of readl or deleted entries
    // double conflict () { return ((double)nconflicts)/((double)nsearches);}
    // double loading () { return ((double)used)/((double)capacity); }
    // double real_loading () {return ((double)contents)/((double)capacity);}

    // void clear ()
    // Hash_Table clone () - not yet implemented

    // the entire hash as a string or array
    // String toString ()
    // Object[] element_array ()
    // Object[] key_array ()

    // see the Enumeration interface in the Java library documentation
    // "quick" throws an exception if you subsequently change anything
    // "thorough" = not quick makes its own array first
    // Enumeration enum = elements (boolean quick)
    // Enumeration enum = keys (boolean quick)
    // while (enum.hasMoreElements()) {
    //    Object next = enum.nextElement() throws NoSuchElementException
    // }

    //====================================================================
    //    SEARCHING THE HASH TABLE TO ANSWER QUERIES

    // methods to access individual entries
    // Object get(Object key)  throws NoSuchElementException
    // Object put(Object key, Object data)
    // Object remove(Object skey)
    // boolean containsKey(Object skey) - hash search for key
    // boolean contains(Object sdata) - linear search for data (stupid!)
    // String show(Object skey) - debug search

    while (true) { // answer the queries
      DataInputStream query_stream = new DataInputStream (System.in);
      System.out.print("Login or human name (q to quit)? ");
      String query = query_stream.readLine();
      if (query == null) break;
      if (query.length() == 1 && query.charAt(0) == 'q') break;
      boolean found=false;

      // look for this entry in the translation tables
      if (login_to_human.containsKey(query)) {
	String human = (String) login_to_human.get(query);
	System.out.println ("Login \"" + query + "\" belongs to " + human);
	found = true;
      }

      // this is a debugging method for Hash_Table:
      // it shows the entries that were considered in the search,
      // starting from its proper hash position.
      System.out.println (login_to_human.show (query));

      if (human_to_login.containsKey(query)) {
	String login = (String) human_to_login.get(query);
	System.out.println ("The login name of " + query + " is " + login);
	found = true;
      }
      System.out.println (human_to_login.show (query));

      if (!found) System.out.println
		    ("Your query \"" + query + "\" was not found");
    }
  }
}