/*****************************************************************************/
/*                                                                           */
/*                 Binary Search Tree: Graphical Version                     */
/*                                                                           */
/*                     February 1998, Toshimi Minoura                        */
/*                     November 1999, Jacob Lundberg                         */
/*                                                                           */
/*****************************************************************************/

// Each node in the binary search tree can store a key and a value.

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

class SearchTreeG extends StepTestCanvas
  {

  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 );
 
  private Node root;                 // root node
  static final int RootXLoc = 400;
  static final int RootYLoc =  40;
  static final int YGap = 50;

  Node currentNode = null;         // node currently being visited

  class FindRemoveResult
    {
    Node subtree;                  // modified subtree
    Node nodeFound;                // node found
    FindRemoveResult( Node subtree, Node nodeFound )
      {
      this.subtree = subtree;
      this.nodeFound = nodeFound;
      }
    }

  class Node
    {
    public char key;                     // key for this node
    public Object value;                 // value associated with this node
    Node leftChild;                      // left subtree
    Node rightChild;                     // right subtree
    boolean focus;
  
    // constructor
    Node( char key, Object val )
      {
      this.key = key;                    // copy argument
      value = val;                       // copy argument
      leftChild = null;                  // no left subtree
      rightChild = null;                 // no right subtree
      focus = true;
      System.out.println( "node with key " + key + " created" );
      }
  
    // Add node into subtree under this node.
    // Each time new node is visited, the whole tree is repainted.
    public void addNode( SearchTreeG tree, Node node )
      {
      System.out.println( "addNode() called for node " + key + " with node " + node.key );
      currentNode = this;
      tree.repaintStep( "New node with key = " + node.key + " being added, node with key = " + key + " visited." );
      if( node.key == key )
        {
        System.out.println( "Node with same key already exists, key = " + key );
        return;
        }
      if( node.key < key )
        {
        // new node should be added to left subtree
        if( leftChild == null )
          {
          // no left subtree
          leftChild = node;         // make new node left child
          tree.repaintStep("New node with key = " + node.key + " added. ");
          currentNode = null;
          node.focus = false;       // added node no longer new
          }
        else
          leftChild.addNode( tree, node );  // add to subtree
        }
      else
        {
        if( rightChild == null )
          {
          rightChild = node;
          tree.repaintStep( "New node with key = " + node.key + " added. " );
          currentNode = null;
          node.focus = false;
          }
        else
          rightChild.addNode( tree, node );
        }
      }

    // Find a node with key == char key.
    private Node find( char findkey )
      {
      focus = true;
      repaintStep( "Node.find( key ) entered node '" + key + "'." );
      focus = false;
      if( key == findkey )
        return this;
      else if( leftChild != null && key > findkey )
        return leftChild.find( findkey );
      else if( rightChild != null && key < findkey )
        return rightChild.find( findkey );
      else
        return null;
      }

    // Find node with minimum key value in subtree under this node,
    // this node excluded, and delete and return it.
    public FindRemoveResult findRemoveMin( SearchTreeG tree )
      {
      System.out.println( "findRemoveMin() called for node with key = " + key + "." );
      FindRemoveResult result;
      if( leftChild == null )
        {
        focus = true;
        tree.repaintStep( "Leftmost node with key = " + key + " will be moved." );
        result = new FindRemoveResult( rightChild, this );  // right subtree
        }
      else
        {
        result = leftChild.findRemoveMin( tree );
        leftChild = result.subtree;                 // update left subtree
        result = new FindRemoveResult( this, result.nodeFound );
        }
      System.out.println( "Subtree = " + result.subtree +
                          "\nnodeFound: key = " + result.nodeFound.key +
                          ", value = " + result.nodeFound.value );
      return result;
      }

    // Find node with maximum key value in subtree under this node,
    // this node excluded, and delete and return it.
    public FindRemoveResult findRemoveMax( SearchTreeG tree )
      {
      System.out.println( "findRemoveMax() called for node with key = " + key + "." );
      FindRemoveResult result;
      if( rightChild == null )
        {
        focus = true;
        tree.repaintStep( "Rightmost node with key = " + key + " will be moved." );
        result = new FindRemoveResult( leftChild, this );  // left subtree
        }
      else
        {
        result = rightChild.findRemoveMax( tree );
        rightChild = result.subtree;                 // update left subtree
        result = new FindRemoveResult( this, result.nodeFound );
        }
      System.out.println( "Subtree = " + result.subtree +
                          "\nnodeFound: key = " + result.nodeFound.key +
                          ", value = " + result.nodeFound.value );
      return result;
      }

    // Remove node with given key from subtree of this node.
    public Node removeNode( SearchTreeG tree, char key )
      {
      System.out.println( "removeNode() called for node with key = " + this.key + " with argument key = " + key + "." );
      currentNode = this;
      tree.repaintStep( "Node with key = " + key + " to be deleted, node with key = " + this.key + " visited." );
     
      if( key < this.key && leftChild == null ||
          key > this.key && rightChild == null )
        {
        // no node with given key
        System.out.println( "Node to be deleted not found for key = " + key + "." );
        tree.repaintStep( "Node with key = " + key + " does not exist." );
        return this;                               // no change
        }
      if( key < this.key )
        {
        leftChild = leftChild.removeNode( tree, key );   // update left subtree
        return this;                         // return updated subtree
        }
      else if( key > this.key )
        {
        rightChild = rightChild.removeNode( tree, key ); // update right subtree
        return this;                        // return updated subtree
        }
      else
        {
        // key matches
        if( rightChild == null )
          { 
          focus = true;                     // this node will be deleted
          tree.repaintStep( "Node with key = " + key + " will be removed." );
          return leftChild;                 // skip this node
          }
        else
          {
          FindRemoveResult result = rightChild.findRemoveMin( tree );
          rightChild = result.subtree;  // remove moved node in right subtree
          this.key = result.nodeFound.key;  // copy key from moved node
          this.value = result.nodeFound.value;    // and value
          return this;
          }
        }
      }

    public void draw( 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 there a left subtree?
      if( leftChild != null )
        g.drawLine( xLoc, yLoc, xLoc - xGap, yLoc + yGap ); 
      // is there a right subtree?
      if( rightChild != null )
        g.drawLine( xLoc, yLoc, xLoc + xGap, yLoc + yGap ); 

      if( focus )
        g.setColor( NewNodeColor );        // set color for new Node
      else if( currentNode == this )
        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( currentNode == this || focus )
        g.setColor( Color.blue );          // set color for node label
      else
        g.setColor( Color.white );         // for other node
      g.drawString( key + ", " + value , xLoc - nodeWidth / 4, yLoc + 6 ); 
  
      // draw left subtree
      if( leftChild != null )
        leftChild.draw( g, xLoc - xGap, yLoc + yGap, xGap / 2, yGap );
      // draw right subtree
      if( rightChild != null )
        rightChild.draw( g, xLoc + xGap, yLoc + yGap, xGap / 2, yGap );
      }

    // create String representation of subtree
    public String toString()
      {
      String exp = ( leftChild == null ) ? "" : "( " + leftChild + " ) ";
      exp += key;                  // convert key to string
      if( rightChild != null )
        exp += " ( " + rightChild + " ) ";
      return exp;
      } 
    }

  // find() calls root.find().
  public Object find( char findkey )
    {
    return root.find( findkey ).value;
    }

  public void insert( char key, Object data )
    {
    Node newNode = new Node( key, data );
    currentNode = null;        // disable previous highlighting
    repaintStep( "New node with key = " + key + " will be added." );
    if( root == null )
      {
      root = newNode;               // add root node 
      repaintStep( "Root node with key = " + newNode.key + " added. " );
      newNode.focus = false;        // added node no longer new
      }
    else
      root.addNode( this, newNode );  // add new node under root node
  }

  public void remove( char key )
    {
    currentNode = null;        // disbale previous highlighting
    repaintStep( "Node with key = " + key + " will be removed." );
    if( root == null )
      repaintStep( "ERROR: Tree is empty." );
    else
      root = root.removeNode( this, key );   // set updated tree
    }

  public Node removeMax()
    {
    if( root == null )
      return null;
    FindRemoveResult result = root.findRemoveMax( this );
    root = result.subtree;    // replace tree with one without max node
    return result.nodeFound;  // return the max node removed
    }

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

  public synchronized void paint( Graphics g )
    {
    g.setFont( f );                   // set font for letters
    if( root == null )
      {
      // no user node, initial condition
      g.drawString( "Tree is Empty", 300, 150 );
      return;
      }
    // draw tree starting with root node
    root.draw( g, RootXLoc, RootYLoc, RootXLoc / 2, YGap );
    }

  public String toString()
    {
    // create String representation of expression
    return root == null ? "empty" : root.toString();
    } 

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

    root = null;
    repaintStep();

    int i = 24;
    int p = 1;
    int j;

    // Create a balanced tree of (most of) the alphabet (b to x).
    while( ( i / p ) > 1 )
      {
      p *= 2;
      for( j = ( i / p ) ; j < i ; j += ( i / p ) )
        if( ( ( i / ( p / 2 ) ) != 0 ) && ( ( j % ( i / ( p / 2 ) ) ) != 0 ) )
          insert( (char)( j + 97 ), new Integer( j ) );
      }

    System.out.println( "String representation of tree: " + toString() + "." );
    repaintStep( "Tree: " + toString() );

    System.out.println( "Found node 'q': " + find( 'q' ) + "." );

//    for( i = (int)'x' ; i >= (int)'b' ; i-- )
//      remove( (char)i );

    for( ; ; )
      {
      Node maxNode = removeMax();  // get node of max key value
      if( maxNode == null )
        break;
      System.out.println( "Max node removed, key = " + maxNode.key + "." );
      repaintStep( "Max node removed, key = " + maxNode.key + "." );
      }

    System.out.println( "String representation of tree: " + toString() + "." );
    repaintStep( "Tree: " + toString() );
    }

  public static void main( String argv[] )
    {
    new StepTestFrame( "Binary Search Tree", new SearchTreeG(), 800, 450 ).show();
    }
  }