package username.dict;

import java.io.PrintWriter;

/**
 * A simple bucket-based hash table.
 *
 * @author Samuel A. Rebelsky
 * @version 1.0 of April 2005
 */
class HashTable<K,V>
  implements NewDict<K,V>
{
  // +------------------+----------------------------------------
  // | Design Decisions |
  // +------------------+

/*
  (1) This hash table is bucket-based.  That is, when two values
  hash to the same cell in the table, we put them in a linked
  structure within that cell.  (The alternative is to shift to
  another cell.)

  (2) This hash table never expands.  That means that after
  awhile, the hash table will take O(n) for put and get, rather
  than O(1).

  (3) Although the table officially contains objects (for ease
  of creating the table), in reality the code ensures that it
  contains only Node<K,V> objects.
*/

  // +--------+--------------------------------------------------
  // | Fields |
  // +--------+

  /**
   * The table
   */
  Object[] table;

  /**
   * The number of things in the table.
   */
  int size;


  // +--------------+--------------------------------------------
  // | Constructors |
  // +--------------+

  /**
   * Build a new hash table.
   */
  public HashTable()
  {
    this.table = new Object[16];
    this.size = 0;
  } // HashTable()


  // +---------+-------------------------------------------------
  // | Methods |
  // +---------+

  public void put(K key, V value)
  {
    // Determine which cell the key/value pair belongs in.
    int i = this.getCell(key);
    // Shove it in that bucket.
    this.table[i] = this.insert((Node<K,V>) this.table[i], key, value);
  } // put(K,V)
    
  public V get(K key)
  {
    // Determine which cell the key/value pair belongs in.
    int i = this.getCell(key);
    // Scan through the bucket, looking for it.
    return this.find((Node<K,V>) this.table[i], key);
  } // get(K)

  public void dump(PrintWriter pen)
  {
    pen.println("The structure of this dictionary is confidential.");
  } // dump(PrintWriter)


  // +---------+-------------------------------------------------
  // | Methods |
  // +---------+

  /**
   * Determine which cell the key belongs in.
   */
  int getCell(K key)
  {
    return Math.abs(key.hashCode()) % this.table.length;
  } // getCell(K)

  /**
   * Insert a key/value pair into a bucket.
   */
  Node<K,V> insert(Node<K,V> bucket, K key, V value)
  {
    // Case one: The bucket is empty, so create a new one.
    if (bucket == null) {
      return new Node<K,V>(key,value);
    } // empty bucket

    // Case two: The current node contains the same key, so
    // replace the value
    else if (key.equals(bucket.key)) {
      bucket.value = value;
      return bucket;
    } // matching key

    // Case three: As a default, insert into the remainder
    // of the bucket.
    else {
      bucket.next = this.insert(bucket.next, key, value);
      return bucket;
    } // default case
  } // insert(Node<K,V>, K, V)

  /**
   * Find a key in a bucket and return the corresponding value.
   */
  V find(Node<K,V> bucket, K key)
  {
    // Case one: The bucket is empty, so return the default
    // value (null)
    if (bucket == null) {
      return null;
    } // empty bucket

    // Case two: The current node contains the same key, so
    // use that value
    else if (key.equals(bucket.key)) {
      return bucket.value;
    } // matching key

    // Case three: As a default, insert into the remainder
    // of the bucket.
    else {
      return this.find(bucket.next, key);
    } // default case
  } // find(Node<K,V>, K, V)


} // class HashTable