/*********************************************************************
 * Author: B. Alex Bridges                                           *
 * Login ID: brid0129                                                *
 * Class: CPSC-221, Winter 1999                                      *
 * Project: Programming Assignment 2                                 *
 * Description: This program generates a cross reference for a Java  *
 *              program file.  It uses a closed hash table with      *
 *              double hashing.                                      *
 * Contents: Methods for dealing with References as hash table.      *
 *********************************************************************/

/* IMPORTS */
import java.io.*;


class Hash
{
  /* CONSTANTS */
  final static boolean b_debug = false; // CONTROLS EXTRA DEBUG OUTPUT
  final static int int_table = 211;     // SIZE OF HASH TABLE
                                        // (POWER OF 2 -or- PRIME NUMBER)


  /* OBJECT VARIABLES */
  private Reference[] refA_table;

  public Hash()
  {
    refA_table = new Reference[int_table];
    for(int i = 0; i < int_table; i++)
      refA_table[i] = new Reference();
  } // constructor Hash

  /*************************************************************************
   * Method: key                                                           *
   * Purpose: Creates a Natural number key for Reference's value.          *
   * Input: --PARAMATERS--                                                 *
   *        => 'str_value' = Reference's value.                            *
   * Output: --RETURNS--                                                   *
   *         => 'int_key' = Reference's resultant key.                     *
   *************************************************************************/
  private int key(String str_value)
  {
    /* LOCAL VARIABLES */
    int int_key = 0;          // REFERENCE'S RESULTANT KEY
    int int_len;              // LENGTH OF REFERENCE'S VALUE
    int i;                    // LOOP COUNTER
    Character Char_current;   // CURRENT CHARACTER FOR LOOP

    /* KEY CREATION */
    int_len = str_value.length();

    for(i = 1; i <= int_len; i++)
    {
      Char_current = new Character ( str_value.charAt(int_len - i) );
      int_key += ( Char_current.charValue() );
    } // for

    if(b_debug)
      System.out.println("Keyed '"+str_value+"' as "+int_key+".");

    return int_key;
  } // method key


  /*************************************************************************
   * Method: insert                                                        *
   * Purpose: Inserts a Reference into the hash table.                     *
   * Input: --PARAMATERS--                                                 *
   *        => 'str_value' = Reference's value.                            *
   *        => 'int_line'  = Reference's line number.                      *
   * Output: --RETURNS--                                                   *
   *         => NONE                                                       *
   *************************************************************************/
  public void insert(String str_value, int int_line)
  {
    /* LOCAL VARIABLES */
    int int_key = -1;             // REFERENCE'S RESULTING KEY
    int int_hash = -1;            // REFERENCE'S RESULTING HASH VALUE
    boolean b_collision = false;  // COLLISION STATUS



    /* DETERMINE APPROPRIATE KEY */
    int_key = key(str_value);

    /* HASHING FUNCTION #1 : h1(k) = k mod m */
    int_hash = int_key % int_table;

    if(b_debug)
    {
      System.out.println(" Hashing '"+str_value+"' as "+int_hash+".\n");

      System.out.println(" Index "+int_hash+"'s contents:\n"+
                         " Value      = '"+refA_table[int_hash].str_value+"'\n"+
                         " Line       = '"+refA_table[int_hash].int_line+"'\n"+
                         " Occurences = '"+refA_table[int_hash].int_occurs+"'\n");
    } // if

    /* EMPTY SLOT */
    if(refA_table[int_hash].int_occurs == 0)
    {
      if(b_debug)
        System.out.println(" CASE 1: EMPTY SLOT ");

      refA_table[int_hash].str_value = str_value;
      refA_table[int_hash].int_line = int_line;
      refA_table[int_hash].int_occurs++;
    } // if
    /* FILLED SLOT, SAME VALUE AND SAME LINE */
    //
    else if( refA_table[int_hash].str_value.equals(str_value) && refA_table[int_hash].int_line == int_line )
    {
      if(b_debug)
        System.out.println(" CASE 2: FILLED SLOT, SAME VALUE AND SAME LINE ");

      refA_table[int_hash].int_occurs++;
    } // if
    /* FILLED SLOT, DIFFERENT VALUE OR DIFFERENT LINE */
    else
    {
    if(b_debug)
      System.out.println(" CASE 3: FILLED SLOT, DIFFERENT VALUE OR DIFFERENT LINE ");

      b_collision = true;

      while(b_collision)
      {
        /* HASHING FUNCTION #2 : h2(k) = 1 + (k mod m') where m' = m-1 | m-2 */
        int_hash = 1 + ( int_hash % (int_table - 1) );

        if(b_debug)
          System.out.println(" Hashing '"+str_value+"' as "+int_hash+".");

        /* EMPTY SLOT */
        if(refA_table[int_hash].int_occurs == 0)
        {
          refA_table[int_hash].str_value = str_value;
          refA_table[int_hash].int_line = int_line;
          refA_table[int_hash].int_occurs++;

          b_collision = false;
        } // if
      } // while
    } // else

    if(b_debug)
      System.out.println("Hashed '"+str_value+"' as "+int_hash+".");
  } // method insert
} // class Hash