/*****************************************************************************/
/*                                                                           */
/*              Hash Table with Linked List: Graphical Version               */
/*                                                                           */
/*                     February 1998, Toshimi Minoura                        */
/*                     November 1999, Jacob Lundberg                         */
/*                                                                           */
/*****************************************************************************/

// Each slot in the hash table is a singly-linked list.
// Colliding items are put in the linked list provided for each table slot.

import java.awt.*;
import java.awt.event.*;
import java.util.*;
 
class HashLG extends StepTestCanvas
  {
  static final int TableSize = 17;   // hash table size
  private SListHash table[];         // storage for hash table data
  int currentIdx = -1;               // index for node currently being visited

  // constructor
  public HashLG()
    {
    table = new SListHash[TableSize];
    for( int i = 0; i < TableSize; i++ )
      table[i] = new SListHash();
    }

  // hashing function
  static int hash( String key )
    {
    return Math.abs( key.hashCode() % TableSize );
    }

  // add node to hash table
  public void insert( String key, Object data )
    {
    int idx = hash( key );
    currentIdx = idx;                              // set arrow location
    repaintStep( "New node with key = " + key + " will be added at " + idx + "." );
    currentIdx = -1;                               // hide arrow
    table[idx].insertTail( this, key, data );
//    System.out.println( "New node with key = " + key + " added at " + idx + "." );
//    repaintStep( "New node with key = " + key + " added." );
    }

  public Object find( String key )
    {
    System.out.println( "HashLG.find() entered with key = " + key + "." );
    int idx = hash( key );
    System.out.println( "HashLG.find(): idx = " + idx + "." );
    currentIdx = idx;                              // show arrow
    repaintStep( "Node with key = " + key + " should be located at " + idx + "." );
    currentIdx = -1;
    Object value = table[idx].find( this, key );   // return value found
    if( value == null )
      {
      repaintStep( "Node with key = " + key + " does not exist." );
      System.out.println( "Node with key = " + key + " does not exist." );
      }
    return value;
    }

  // remove a node with a given key if it exists
  public void remove( String key )
    {
    table[hash( key )].remove( this, key );
    }

  static final int TableXLoc = 120;
  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 OccupiedNodeColor = new Color( 150, 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( "HashLG.paint() entered." );
    g.setFont( f );                      // set font for letters
  
    if( currentIdx >= 0 )
      {
      int y = TableYLoc + currentIdx * NodeHeight;    // y position of arrow
      drawRightArrow( g, TableXLoc - NodeWidth * 4 / 5, y + NodeHeight / 2, TableXLoc - 30 );
      }
    for( int i = 0; i < TableSize; i++ )
      {
      int y = TableYLoc + i * NodeHeight;  // y position of node

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

      if( table[i].head == null )
        g.setColor( EmptyNodeColor );      // set color for empty node
      else
        g.setColor( OccupiedNodeColor );   // color for other occupied nodes

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

      if( table[i].head == null )
        {
        g.setColor( Color.white );
        g.drawString( "null", TableXLoc + NodeWidth / 3, y + NodeHeight / 2 + 6 );
        continue;
        }
      g.setColor( RightArrowColor );   // set right arrow color
      drawRightArrow( g, TableXLoc + NodeWidth  * 3 / 4, y + NodeHeight / 2, TableXLoc + NodeWidth * 3 / 2 );
      table[i].draw( g, TableXLoc + NodeWidth * 3 / 2, y + 2, NodeWidth * 3 / 4, NodeHeight - 4 );
      }
    }

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

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

    for( int i = 0; i < TableSize; i++ )
      table[i].initialize();
    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++ )
      {
      Object valueFound = find( keys[j] );    // locate value for a given key
      if( valueFound != null )
        {
        System.out.println( "Value for key = " + keys[j] + " is " + valueFound + "." );
        repaintStep( "Value for key = " + keys[j] + " found: " + valueFound + "." );
        }
      else
        repaintStep( "Value for key = " + keys[j] + " not found." );
      }

    // sample invalid removals
    remove( "P" );  // removal from an extant list
    remove( "i" );  // removal from an empty list

    // removal of valid nodes, as long as the user hasn't changed the input
    inputTokens = getInputTokens();  // read from input area
    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++ )
      remove( inputTokens.nextToken() );

    repaintStep( "Node removal complete." );

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