/*****************************************************************************/
/*                                                                           */
/*                Hashing Test program: Graphical Version                    */
/*                                                                           */
/*                     February 1998, Toshimi Minoura                        */
/*                     November 1999, Jacob Lundberg                         */
/*                                                                           */
/*****************************************************************************/

// Each node in the hash table can store a key and a value.
// Linear probing is implemented for collision resolution.

import java.awt.*;
import java.awt.event.*;
import java.util.*;

// The primality test below is taken from Mark Weiss'
// "Data Structures and Problem Solving Using Java"
class Primality
  {
  private static boolean isPrime( long n )
    {
    for( long i = 3 ; i * i <= n ; i += 2 )
      if( n % i == 0 )
        return false;
    return true;
    }

  public final static int nextPrime( int n )
    {
    if( n % 2 == 0 )
      ++n;
    for( ; !isPrime( n ) ; n += 2 );
    return n;
    }
  }

class Node
  {
  public String key;                   // key for this node
  public Object value;                 // value associated with key
  boolean focus;
  boolean extant;

  // constructor
  Node( String key, Object val )
    {
    this.key = key;                    // copy argument
    value = val;                       // copy argument
    focus = true;
    extant = true;
    System.out.println( "node with key " + key + " created" );
    }

  // create String for node
  public String toString()
    {
    return "node with key = " + key + ", value = " + value;
    }
  }

class HashG extends StepTestCanvas
  {
  private int TableSize = 17;        // good starting hash table size
  private Node table[];              // storage for hash table data
  int currentIdx;               // index for node currently being visited
  int currentSize;

  // constructor
  public HashG()
    {
    // nodes initialized null; this is important
    table = new Node[TableSize];
    currentIdx = -1;
    currentSize = 0;
    }

  // locating function; finds where a value is or should be
  int locate( String key )
    {
    int idx = Math.abs( key.hashCode() % TableSize );
    while( table[idx] != null && !table[idx].key.equals( key ) )
      {
      table[idx].focus = true;
      System.out.println( "Index " + idx + " already occupied placing key " + key + "." );
      if( table[idx].extant )
        repaintStep( "Node with key " + table[idx].key + " already occupies index " + idx + "." );
      else
        repaintStep( "A ghost node already occupies index " + idx + "." );
      table[idx].focus = false;
      ++idx;
// This relies on a table guaranteed to have holes.
// If you break this you must uncomment the next two lines!
//      if( idx == Math.abs( key.hashCode() % TableSize ) )
//        return -1;
      if( idx >= TableSize )
        idx -= TableSize;
      }
    return idx;
    }

  // add node to hash table
  public void insert( String key, Object data )
    {
    int idx = locate( key );
    currentIdx = idx;                              // set arrow location
    repaintStep( "New node with key = " + key + " will be added at " + idx + '.' );
    table[idx] = new Node( key, data );            // put the new node in the table
    table[idx].focus = true;                       // highlight new node
    System.out.println( "New node with key = " + key + " added at " + idx );
    repaintStep( "New node with key = " + key + " added." );
    table[idx].focus = false;
    currentIdx = -1;                               // hide arrow

    // rehashing
    // This guarantees holes and therefore is _important_ because of locate()!
    if( ++currentSize < table.length / 2 )
      return;
    Node[] oldTable = table;
    TableSize = Primality.nextPrime( 2 * oldTable.length );
    table = new Node[TableSize];
    currentSize = 0;
    repaintStep( "Table resized and rehashed." );
    for( int i = 0 ; i < oldTable.length ; i++ )
      if( oldTable[i] != null && oldTable[i].extant )
        insert( oldTable[i].key, oldTable[i].value );
    }

  // find by key
  public Node find( String key )
    {
    System.out.println( "HashG.find() entered with key = " + key + "." );
    int idx = locate( key );
    System.out.println( "HashG.find(): idx = " + idx + "." );
    currentIdx = idx;                          // show arrow
    if( table[idx] == null || !table[idx].extant )
      {
      repaintStep( "Node with key = " + key + " does not exist." );     
      currentIdx = -1;
      return null;
      }
    table[idx].focus = true;                   // highlight node located
    repaintStep( "Node with key = " + key + " located at " + idx + "." );
    table[idx].focus = false;              // unhighlight node located
    return table[idx];
    }

  // remove by key
  public Node remove( String key )
    {
    System.out.println( "HashG.remove() entered with key = " + key + "." );
    int idx = locate( key );
    System.out.println( "HashG.remove(): idx = " + idx + "." );
    currentIdx = idx;                          // show arrow
    if( table[idx] == null || !table[idx].extant )
      {
      repaintStep( "Node with key = " + key + " does not exist." );     
      currentIdx = -1;
      return null;
      }
    table[idx].extant = false;
    table[idx].focus = true;                   // highlight node located
    repaintStep( "Node with key = " + key + " has been removed from " + idx + "." );
    table[idx].focus = false;                  // unhighlight node located
    return table[idx];
    }

  static final int TableXLoc = 100;
  static final int TableYLoc =  20;

  static final int NodeWidth  = 80;
  static final int NodeHeight = 30;

  static Color LineColor = new Color( 0, 0, 0 );
  static Color EmptyNodeColor = new Color( 0, 100, 0 );
  static Color DeletedNodeColor = new Color( 25, 125, 25 );
  static Color OccupiedNodeColor = new Color( 150, 255, 0 );
  static Color NewNodeColor = new Color( 255, 255, 0 );
  static final Color RightArrowColor = new Color( 0, 100, 255 );

  public void drawRightArrow( Graphics g, int x1, int y1, int x2 )
    {
    Polygon poly = new Polygon();      // arrow from (x1, y1) to (x2, y1)
    poly.addPoint( x1, y1 - 2 );
    poly.addPoint( x1, y1 + 2 ); 
    poly.addPoint( x2 - 6, y1 + 2 );
    poly.addPoint( x2 - 6, y1 + 6 );
    poly.addPoint( x2, y1 );           // tip of right arrow
    poly.addPoint( x2 - 6, y1 - 6 );
    poly.addPoint( x2 - 6, y1 - 2 );
    g.fillPolygon( poly );             // draw arrow
   }

  Font f = new Font( "TimesRoman", Font.BOLD, 18 );

  public void paint( Graphics g )
    {
    System.out.println( "HashG.paint() entered." );
    g.setFont( f );                     // set font for letters

    if( currentIdx >= 0 )
      {
      // position arrow
      int x = TableXLoc + ( currentIdx / 17 ) * NodeWidth * 2;
      int y = TableYLoc + ( currentIdx % 17 ) * NodeHeight;

      g.setColor( RightArrowColor );    // set right arrow color
      drawRightArrow( g, x - NodeWidth * 4 / 5, y + NodeHeight / 2, x - 30 );
      }
    for( int i = 0; i < TableSize; i++ )
      {
      // position center of node
      int x = TableXLoc + ( i / 17 ) * NodeWidth * 2;
      int y = TableYLoc + ( i % 17 ) * NodeHeight;

      g.setColor( Color.black );             // color for node index
      if( i < 10 ) 
        g.drawString( "  " + i, x - 25, y + NodeHeight / 2 + 4 ); 
      else
        g.drawString( "" + i, x - 25, y + NodeHeight / 2 + 4 ); 

      if( table[i] == null )
        g.setColor( EmptyNodeColor );      // set color for empty node
      else if( !table[i].extant )
        g.setColor( DeletedNodeColor );    // set color for new or visited node
      else if( table[i].focus )
        g.setColor( NewNodeColor );        // set color for new or visited node
      else
        g.setColor( OccupiedNodeColor );   // color for other occupied nodes

      g.fillRect( x + 2, y + 2, NodeWidth - 3, NodeHeight - 3 );
  
      g.setColor( Color.black );           // color for node frame
      g.drawRect( x, y, NodeWidth, NodeHeight );  // draw node

      if( table[i] == null )
        {
        g.setColor( Color.white );
        g.drawString( "null", x + NodeWidth / 3, y + NodeHeight / 2 + 4 ); 
        continue;
        }
      g.setColor( Color.blue );       // set label color for occupied node
      g.drawString( table[i].key + ", " + table[i].value, x + NodeWidth / 3, y + NodeHeight / 2 + 5 );
      }
    }

  public static void main( String argv[] )
    {
    new StepTestFrame( "Hash Table", new HashG(), 700, 700 ).show();
    }

  // called from run() of StepTestCanvas
  public void runMain()
    {
    System.out.println( "HashG.runMain() entered" );

    for( int i = 0; i < TableSize; i++ )
      table[i] = null;              // initially no entry

    currentIdx = -1;
    currentSize = 0;
    repaintStep();  // display message "Press Step, Delay, or Continue Button."
    repaintStep( "You may provide key values to be used in the input area as \"e h g s o r a d k w c t\"" );

    int i = 0;                        // counter
    StringTokenizer inputTokens = getInputTokens();  // read from input area
    int inputSize = inputTokens.countTokens();     
    if( inputSize == 0 )
      {
      // no key values are provided
      inputTokens = new StringTokenizer( "e h g s o r a d k w c t" );
      inputSize = inputTokens.countTokens();
      }
    for( i = 0; i < inputSize; i++ )
      {
      String token = inputTokens.nextToken();  // get next token
      insert( token, new Integer( i ) ); 
      }
    repaintStep( "Node insertion complete." );

    String keys[] = { "c", "h", "w", "donkey", "j" };

    for( int j = 0; j < keys.length; j++ )
      {
      Node nodeFound = find( keys[j] );    // locate node with a given key
      if( nodeFound != null && nodeFound.key.equals( keys[j] ) )
        repaintStep( "Node found: " + nodeFound );
      else
        repaintStep( "Node with key = " + keys[j] + " not found." );
      }

    inputTokens = new StringTokenizer( "e h g s o r a d k w c t" );
    for( i = 0 ; i < inputSize ; i++ )
      remove( inputTokens.nextToken() );
    repaintStep( "Node removal complete." );

    System.out.println( "runMain() completed." );
    }
  }