/*****************************************************************************/
/*                                                                           */
/*                   Heap Test Program: Graphical Version                    */
/*                                                                           */
/*                      February 1998, Toshimi Minoura                       */
/*                      November 1999, Jacob Lundberg                        */
/*                                                                           */
/*****************************************************************************/

// Each node in the heap can store a key and a value.
// This program places the nodes with larger key values towards the top of the heap.

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

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

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

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

class HeapG extends StepTestCanvas
  {
  private Node nodes[];        // storage for heap data
  private int last;            // index of last element in heap
  int currentIdx = -1;         // index for node currently being visited

  // constructor
  public HeapG()
    {
    nodes = new Node[100];
    last = -1;                 // initially, heap is empty
    }

  public void insert( char key, Object data )
    {
    currentIdx = -1;
    repaintStep( "New node with key = " + key + " will be added." );
    nodes[++last] = new Node( key, data );
    nodes[last].focus = true;
    System.out.println( "New node with key = " + key + " added at " + last );
    repaintStep( "New node with key = " + key + " added." );
    nodes[last].focus = false;
    percolateUp( last );
    }

  public Node removeMax()
    {
    if( last == -1 )
      return null;   // no node left
    currentIdx = -1;
    nodes[0].focus = true;
    repaintStep( "Node at top of heap will be removed." );
    Node max = nodes[0];           // remove element at top of heap
    System.out.println( "" + max + " removed from location 0." );
    if( last == 0 )
      {
      last = -1;
      currentIdx = -1;
      return max;
      }
    currentIdx = last;
    repaintStep( "Node at end of heap will be moved to top of heap." );
    nodes[0] = nodes[last];       // move last element to emptified slot
    System.out.println( "" + nodes[0] + " moved from location " + last + " to location 0." );
    last--;                       // reduce heap size
    currentIdx = 0;
    repaintStep( "Node at end of heap was moved to top of heap." );
    percolateDown( 0 );           // let moved element settle
    currentIdx = -1;              // no currently highlighted node
    return max;
    }

  // swap elements at idx1 and idx2
  public void swap( int idx1, int idx2 )
    {
    nodes[idx1].focus = true;
    currentIdx = idx2;
    repaintStep( "Node with key = " + nodes[idx1].key +
                 " and node with key = " + nodes[idx2].key + 
                 " will be exchanged." );
    Node temp = nodes[idx1];
    nodes[idx1] = nodes[idx2];
    nodes[idx2] = temp;
    currentIdx = idx1;
    repaintStep( "Node with key = " + nodes[idx1].key +
                 " and node with key = " + nodes[idx2].key + 
                 " were exchanged." );
    nodes[idx2].focus = false;
    currentIdx = -1;;
    System.out.println( "" + nodes[idx2] + " at location " + idx1 +
                        " and " + nodes[idx1] + " at location " + idx2 +
                        " were exchanged" );
    }

  // let element move up and settle
  public void percolateUp( int idx )
    {
    System.out.println( "percolate up " + nodes[idx] + " at location " + idx + "." );
    if( idx == 0 )
      return;
    int parentIdx = ( idx - 1 ) / 2;
    if( nodes[parentIdx].key < nodes[idx].key )
      {
      swap( idx, parentIdx );               // move larger parent down
      percolateUp( parentIdx );
      }
    }

  public void percolateDown( int idx )
    {
    System.out.println( "percolate down " + nodes[idx] + " at location " + idx + "." );
    int childIdx = idx * 2 + 1;
    if( childIdx > last )
      return;
    if( childIdx + 1 <= last && nodes[childIdx+1].key > nodes[childIdx].key )
      childIdx = childIdx + 1;
    if( nodes[idx].key < nodes[childIdx].key )
      {
      swap( idx, childIdx );
      percolateDown( childIdx );
      }
    }

  // convert an array into a heap
  public void makeHeap()
    {
    for( int i = ( last - 1 ) / 2; i >= 0; i-- )
      {
      nodes[i].focus = true;
      repaintStep( "Subtree rooted at location " + i + " will be made into a heap." );
      percolateDown( i );
      nodes[i].focus = false;
      }
    }

  // string representation of heap
  public String toString()
    {
    String str = "Heap: last = " + last + ", nodes = ";
    for( int i = 0; i <= last; i++ )
      {
      str += nodes[i].key;                   // print every value in nodes[]
      if( i < last )
        str += ", ";
      }
    return str;
    }

  static final int RootXLoc = 400;
  static final int RootYLoc =  50;
  static final int YGap = 50;

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

  public void paint( Graphics g )
    {
    System.out.println( "HeapG.paint() entered" );
    g.setFont( f );                   // set font for letters
    if( last == -1 )
      {
      // no user node, initial condition
      g.drawString( "Heap is Empty.", 300, 150 );
      return;
      }
    // draw heap starting with root node
    draw( 0, g, RootXLoc, RootYLoc, RootXLoc / 2, YGap );
    }

  static Color LineColor = new Color( 0, 0, 0 );
  static final Color OutlineColor = new Color( 100, 0, 0 );   // for node outline
  static Color NodeColor = new Color( 0, 100, 0 );
  static Color VisitedNodeColor = new Color( 150, 255, 0 );
  static Color NewNodeColor = new Color( 255, 255, 0 );

  public void draw( int nodeIdx, Graphics g, int xLoc, int yLoc, int xGap, int yGap )
    {
    int nodeWidth = 60;
    int nodeHeight = 30;

    g.setColor( LineColor );           // draw lines to children nodes
    // is this non-leaf node?
    if( nodeIdx * 2 + 1 <= last )
      g.drawLine( xLoc, yLoc, xLoc - xGap, yLoc + yGap ); 
    // is this non-leaf node?
    if( nodeIdx * 2 + 2 <= last )
      g.drawLine( xLoc, yLoc, xLoc + xGap, yLoc + yGap ); 

    if( nodes[nodeIdx].focus )
      g.setColor( NewNodeColor );        // set color for new Node
    else if( currentIdx == nodeIdx )
      g.setColor( VisitedNodeColor );    // set color for Node visited
    else
      g.setColor( NodeColor );           // color for other Nodes
    g.fillOval( xLoc - nodeWidth / 2, yLoc - nodeHeight / 2, nodeWidth, nodeHeight );
    g.setColor( OutlineColor );
    g.drawOval( xLoc - nodeWidth / 2, yLoc - nodeHeight / 2, nodeWidth, nodeHeight );

    if( currentIdx == nodeIdx || nodes[nodeIdx].focus )
      g.setColor( Color.blue );          // set color for node label
    else
      g.setColor( Color.white );         // for other node
    g.drawString( nodes[nodeIdx].key + ", " + nodes[nodeIdx].value, xLoc - nodeWidth / 4 + 2, yLoc + 5 ); 

    // draw left subtree
    if( nodeIdx * 2 + 1 <= last )
      draw( nodeIdx * 2 + 1, g, xLoc - xGap, yLoc + yGap, xGap / 2, yGap );
    // draw right subtree
    if( nodeIdx * 2 + 2 <= last )
      draw( nodeIdx * 2 + 2, g, xLoc + xGap, yLoc + yGap, xGap / 2, yGap );
    g.setColor( OutlineColor );
    g.drawString( String.valueOf(nodeIdx), xLoc - 4, yLoc - nodeHeight / 2 - 4 );
    }
 
  public static void main( String argv[] )
    {
    new StepTestFrame( "Heap Manipulation", new HeapG(), 800, 450 ).show();
    }

  static Node initData[] = null;     // no initial nodes in heap

  // called from run() of StepTestCanvas
  public void runMain()
    {
    int i;
    System.out.println( "HeapG.runMain() entered." );
    last = -1;
    repaintStep( "You may provide key values to be ued in the input area as \"e h g s o r a ! d k w c t\"" );

    StringTokenizer inputTokens = getInputTokens();  // read from input area
    int inputSize = inputTokens.countTokens();
    if( inputSize == 0 )
      {
      // no key values are provided
      inputTokens = new StringTokenizer( "m f j i c q p a ! b t h k u s" );
      inputSize = inputTokens.countTokens();
      }
    for( i = 0; i < inputSize; i++ )
      {
      String token = inputTokens.nextToken();  // get next token
      if( token.charAt( 0 ) == '!' )
        break;
      nodes[i] = new Node( token.charAt( 0 ), new Integer( i ) );
      System.out.println( "nodes[" + i + "] = " + nodes[i] + "." );
      }
    last = i - 1;

    repaintStep( "The nodes in the array will be made into a heap." );
    makeHeap();                        // make array into a heap
    repaintStep( "Heap completed" );

    // remaining nodes are inserted
    for( ; i < inputSize - 1; i++ )
      {
      String token = inputTokens.nextToken();  // get next token
      insert( token.charAt( 0 ), new Integer( i ) ); 
      }

    for ( ; ; )
      {
      Node minNode = removeMax();      // get node of min key value
      if( minNode == null )
        break;      // tree is empty
      System.out.println( "Min node removed = " + minNode + "." );
      repaintStep( "Node with key = " + minNode.key + " removed." );
      }
    System.out.println( "runMain() completed." );
    }
  }