// Introduction to Algorithms
// Template for Hash_Table
// Paul Taylor <pt@dcs.qmw.ac.uk> 1 March 1999
// <put your name, login name & student number here>

// You have to fill in: the private locate (search) method,
// the put (insertion) method and
// building a new table  (called rehash here - NOT the same as Richard
// meant by rehash!)

// My hash table consists of three parts for each entry:
// key (the thing by which you're searching), code and data.
// code is the LONG hash code, which you can get from the Java hashCode()
// method for Objects (and for Strings), or by writing it yourself.
// EMPTY and DELETED are special values that are never hash codes -
// you'll have to modify the output of hashCode() to do this, so whenever
// you get one of these values back, translate it into a third.
// Alternatively, use two boolean arrays (or, better, BitSets - see the Java
// library), one which is true to denote EMPTY and the other which is true
// to denote EMPTY or DELETED (these being the tests that the code actually
// needs).

// use toString(skey) to see the algorithm at work

// use /import/teaching/BSc/1st/I2A/1998-9/Hash/dcs-login for test data

import java.util.Enumeration;
import java.util.NoSuchElementException;

public class Hash_Table {
  //====================================================================
  // parameters controlling the size of the hash table
  private int capacity;   // number of cells available in the array altogether
  private int overflow;   // if (used>overflow) {rehash();}
  private int used;       // contents + DELETED cells
  private int contents;   // the payload
  private double load_factor; // overflow = capacity * load_factor
  private double inflation;// new_capacity = (capacity + increment) * inflation
  private int increment;

  // the payload, indexed by 0 <= i < capacity
  private Object [] key;
  private int    [] code;
  private Object [] data;

  // dummy hash code values
  private final int EMPTY   = 0xffffffff; // this cell is not used at all
  private final int DELETED = 0xfffffffe; // it's a placeholder

  public String stats() {
    return "capacity=" + capacity;
  }

  //====================================================================
  // methods for creating, cloning, clearing and rehashing

  public Hash_Table () { this (10, 0.5); }

  public Hash_Table (int initial_size) { this (initial_size, 0.5); }

  public Hash_Table (int initial_size, double initial_load_factor) {
    capacity = initial_size;
    if (capacity < 10) capacity = 10;
    load_factor = initial_load_factor;
    if (load_factor < 0.1) load_factor = 0.1;
    if (load_factor > 0.9) load_factor = 0.9;
    inflation = 2;
    increment = 0;
    newhash ();    
  }
 
  public int size () {
    return contents;
  }
  
  public void clear () {
    contents = 0;
    used = 0;
    for (int i=0; i<capacity; i++) { code[i] = EMPTY; }
  }
  
  // public Hash_Table clone () { ????? }
  
  private void newhash () {
    overflow = (int) ((double)capacity * load_factor);
    key  = new Object[capacity];
    code = new int[capacity];
    data = new Object[capacity];
    clear ();
  }
 
  int next_prime (int p) {
    if (p<3) { return 2; }
    if (p % 2 == 0) { p++; }
  candidate:
    for (;; p+=2) {
      if (p % 3 == 0) { continue candidate; }
      if (p % 5 == 0) { continue candidate; }
      if (p < 49) { return p; }
      int root = (int) Math.sqrt ((double)p);
      for (int i=0; i<=root; i+=30) {
	if (p % (i+7)  == 0) { continue candidate; }
	if (p % (i+11) == 0) { continue candidate; }
	if (p % (i+13) == 0) { continue candidate; }
	if (p % (i+17) == 0) { continue candidate; }
	if (p % (i+19) == 0) { continue candidate; }
	if (p % (i+23) == 0) { continue candidate; }
	if (p % (i+29) == 0) { continue candidate; }
	if (p % (i+31) == 0) { continue candidate; }
      }
      return p;
    }
  }

  private int rehash_size () {
    double new_size = (double) (capacity + increment) * inflation;
    return next_prime((int) new_size);
  }

  // create a bigger hash table and copy everything into it
  private void rehash (int new_size) {

    // ***** FILL IN HERE 

  }

  //====================================================================
  // two very similar methods for turning the table into a printable string

  public String toString () {
    StringBuffer output = new StringBuffer(stats ());

    for (int i=0; i<capacity; i++) {
      output.append(Integer.toHexString(code[i]));

      switch (code[i]) {
      case EMPTY:
	output.append(" EMPTY\n");
	break;

      case DELETED:
	output.append(" DELETED\n");
	break;

      default:
	String key_string = key[i].toString();
	output.append(key_string);
	// output.append(20-key_string.length spaces); how do I do this?
	output.append(data[i]);
	output.append("\n");
	break;
      }
    }
    return output.toString();
  }

  public String show(Object skey) {
    StringBuffer output = new StringBuffer(stats ());
    int i=skey.hashCode() % capacity;

    while (true) {
      output.append(Integer.toHexString(code[i]));

      switch (code[i]) {
      case EMPTY:
	output.append(" EMPTY: \"");
	output.append(skey);
	output.append("\" not found\n");
	return output.toString(); // give up

      case DELETED:
	output.append(" DELETED\n");
	break;

      default:
	String key_string = key[i].toString();
	output.append(key_string);
	// output.append(20-key_string.length spaces); how do I do this?
	output.append(data[i]);
	output.append("\n");
	if (skey.equals (key[i])) { return output.toString();} // found the key
	break;
      }
      
      i++; if (i == capacity) { i=0; } // next position, with wraparound
    }
  }


  //====================================================================
  // methods for searching, inserting and deleting

  // hash search for a key
  public boolean containsKey(Object skey) {
    int i=locate(skey, skey.hashCode());
    if (code[i] == EMPTY || code[i] == DELETED) { return false; }
    return true;
  }
  
  // linear search for data (stupid!)
  public boolean contains(Object sdata) {
    for (int i=0; i<capacity; i++) {
      if (code[i] == EMPTY || code[i] == DELETED) { continue; }
      if (sdata.equals(data[i])) { return true; }
    }
    return false;
  }

  // hash retrieval by key
  // returns null on failure - should raise an exception instead
  public Object get(Object skey) {
    int i=locate(skey, skey.hashCode());
    if (code[i] == EMPTY || code[i] == DELETED) { return null; }
    return data[i];
  }
  
  // put new data by key, return the old value or null
  public Object put(Object skey, Object sdata) {

    // ******** YOU HAVE TO FILL SOMETHING IN HERE! **********
 
    return olddata;
  }

  // delete by key, return the old value or null
  public Object remove(Object skey) {
    int i=locate(skey, skey.hashCode());
    if (code[i] == EMPTY || code[i] == DELETED) { return null; }
    
    Object olddata = data[i];
    key[i]  = null;
    data[i] = null;
    code[i] = DELETED;
    contents--; // still same number of cells used
    return olddata;
  }
  
  static int nsearches=0;
  static int nconflicts=0;
  
  // the hash workhorse;
  // it's more convenient for the caller (one of our methods)
  // to calculate the hash code
  private int locate (Object skey, int scode) {

    // ******* YOU HAVE TO FILL SOMETHING IN HERE! *******

  }
}

//====================================================================