/*****************************************************************************/
/*                                                                           */
/*           Singly-Linked List Manipulation: Graphical Version              */
/*                                                                           */
/*                     February 1998, Toshimi Minoura                        */
/*                     November 1999, Jacob Lundberg                         */
/*                                                                           */
/*****************************************************************************/

import java.awt.*;

// A SLNode is a node in a singly-linked list.
class SLNode
  {
  SLNode next;            // next SLNode in a singly-linked list
  String key;             // key value for this node
  public Object data;     // data stored in this SLNode
  boolean focus;          // node under focus

  // constructor for a SLNode without data
  SLNode()
    {
    next = null;
    this.key = null;      // set argument key to instance variable key
    this.data = null;     // set argument data to instance variable data
    }

  // constructor for a SLNode with data
  SLNode( String key, Object data )
    {
    next = null;
    this.key = key;       // set argument key to instance variable key
    this.data = data;     // set argument data to instance variable data
    }

  // removes requested node
  // silently returns entire list if node is not found
  SLNode removeNode( StepTestCanvas canvas, String key )
    {
    SLNode current = new SLNode();
    current.next = this;
    while( current.next != null && !current.next.key.equals( key ) )
      {
      current.next.focus = true;
      canvas.repaintStep( "Node with key " + current.next.key +
                          " touched searching for key " + key + "." );
      current.next.focus = false;
      current = current.next;
      }
    if( current.next == null )
      canvas.repaintStep( "Node with key " + key +
                          " not found in list with hash " + HashLG.hash( key ) + "." );
    else
      {
      current.next.focus = true;
      canvas.repaintStep( "Removing node with key " + key +
                          " from list with hash " + HashLG.hash( key ) + "." );
      current.next.focus = false;
      if( current.next == this )
        return this.next;
      else
        current.next = current.next.next;
      }
    return this;
    }
  }

class SListHash
  {
  public SLNode head;                          // head of singly-linked list
  SLNode currentNode = null;                   // node currently being visited

  public void initialize()
    {
    System.out.println( "SListHashG.initialize() entered." );
    head = null;                               // make list empty
    }

  public void insertTail( StepTestCanvas canvas, String key, Object data )
    {
    SLNode newNode = new SLNode( key, data );  // create new data node
//    currentNode = null;
//    canvas.repaintStep("New node with key = " + key + " will be added. ");
    // is list empty?
    if( head == null )
      {
      head = newNode;                          // add single new data node
      currentNode = head;
      }
    else
      {
      SLNode current = head;
      currentNode = head;
      // find node at tail
      while( true )
        {
        canvas.repaintStep( "New node with key = " + newNode.key + 
                            " being added, node with key = " + current.key + " visited." );
        if( current.next == null )
          break;                               // tail node found
        current = current.next;                // proceed to next node
        currentNode = current;
        }
      current.next = newNode;                  // add new node at end
      }
    newNode.focus = true;
    currentNode = null;
    canvas.repaintStep( "New node with key = " + key + " added. " );
    newNode.focus = false;       // added node no longer new
    System.out.println( "Node with key = " + key + " added." );
    }

  // find value for key
  public Object find( StepTestCanvas canvas, String key )
    {
//    currentNode = null;
//    canvas.repaintStep("Node with key = " + key + " will be searched for. ");
    for( SLNode current = head ; current != null ; current = current.next )
      {
      // is key contained in current SLNode?
      if( current.key.equals( key ) )
        {
        System.out.println( "Node containing " + key + " found." );
        currentNode = null;
        current.focus = true;           // highlight node found
        canvas.repaintStep( "Node with key = " + key + " found." );
        current.focus = false;          // end highlighting
        return current.data;            // return data associated with key
        }
      else
        {
        currentNode = current;
        canvas.repaintStep( "Node with key = " + key + 
                            " being searched for, node with key = " + current.key + " visited." );
        }
      }
    currentNode = null;
    System.out.println( "Data " + key + " not found." );
    return null;
    }

  // remove is a wrapper for removeNode() in class SLNode
  void remove( StepTestCanvas canvas, String key )
    {
    if( head == null )
      canvas.repaintStep( "Node with key " + key +
                          " not found in list with hash " + HashLG.hash( key ) + "." );
    else
      head = head.removeNode( canvas, key );
    }

  // print content of list
  public void print()
    {
    // is list empty
    if( head == null )
      {
      System.out.println( "list empty" );
      return;
      }
    System.out.print( "List content: " );
    for( SLNode current = head ; current != null ; current = current.next )
      System.out.print( "  key = " + current.key + ", data = " + current.data );
    System.out.println( "" );
    }

  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
    }

  static Color LineColor = new Color( 0, 0, 0 );
  static Color NodeColor = new Color( 0, 100, 0 );
  static Color VisitedNodeColor = new Color( 150, 255, 0 );
  static Color NewNodeColor = new Color( 255, 255, 0 );
  static final Color RightArrowColor = new Color( 0, 100, 255 );

  public void draw( Graphics g, int x1, int y1, int nodeWidth, int nodeHeight )
    {
    int linkWidth = nodeWidth / 2;
    if( head == null )
      {
      // list head not created yet, initial condition
      g.drawString( "List is empty.", 200, 80 );
      return;
      }
    SLNode current = head;
    int x = 0;                                           // x position of node
    for( int i = 0 ; i == 0 || current != null ; i++ )
      {
//      System.out.println( "Drawing SLNode with data " + current.data + "." );
      x = x1 + i * ( nodeWidth + linkWidth );            // x position of node

      g.setColor( LineColor );
      g.drawRect( x, y1, nodeWidth, nodeHeight );        // draw box
      if( current.focus )
        g.setColor( NewNodeColor );      // set color for new Node
      else if( currentNode == current )
        g.setColor( VisitedNodeColor );  // set color for Node visited
      else
        g.setColor( NodeColor );         // color for other Nodes
      g.fillRect( x + 2, y1 + 2, nodeWidth - 3, nodeHeight - 3 );   // draw box

      if( currentNode == current || current.focus )
        g.setColor( Color.blue );        // set color for node label
      else
        g.setColor( Color.white );       // for other node

      // draw key and value within node
      g.drawString( current.key + ", " + current.data, x + 15, y1 + 18 );

      g.setColor( RightArrowColor );
      if( current.next != null )
        // draw link to next node
        drawRightArrow( g, x + nodeWidth - 6, y1 + nodeHeight /2, x + nodeWidth + linkWidth );
      current = current.next;                    // go to next node
      }
    }
  }