/* Binary Search Tree Applet
 *
 * By James Stewart
 *    Dept of Computer Science
 *    University of Toronto
 *    jstewart@cs.toronto.edu
 *
 * Feel free to copy and modify this applet, but please give credit
 * to the original author where appropriate.
 *
 * Draws a BST and allows the user to perform searches and rotations.  The
 * applet parameters define the functionality, as follows:
 *
 * General parameters:
 *
 *   keys      list of keys to be inserted into the bst, in order of insertion
 *
 *   action    list of permissible actions, which include "rotate" and "search"
 *              (If no action is supplied, the user cannot interact with the bst.)
 *
 * Parameters for rotations:
 * 
 *   only_root_children  if present, only the children of the root may be rotated
 *  
 *   alternate_nodes     a list of two keys, indicating that only two nodes may be
 *                       rotated, and they must be rotated alternately
 *
 *   rotatable_node      a list of keys, indicating that only these nodes may be
 *                       rotated.
 *
 * For examples of using this applet, see the *.html files in the
 * directory above this one.
 */


import java.util.*;
import java.awt.*;
import java.applet.Applet;


/** A BST node */


class node { 

  int  key;			// element key
  node left;			// left child
  node right;			// right child
  node parent;			// parent
  float x, y;			// (x,y) location in window
  float incx, incy;		// increment in (x,y) with each move
  boolean highlight_node;	// true if node is to be highlighted
  Color highlight_colour;
  boolean hide_edge;		// true if parent edge is to be hidden (i.e. not drawn)
}


/** A Binary Search Tree */


public class bst extends java.applet.Applet {

  node root;			// root of tree

  node rotation_node;		// node to rotate about

  int num_edges;		// edges to draw
  float edges[][] = new float[100][4];

  rotate rotate_thread;		// thread to handle rotations
  search search_thread;		// thread to handle searches

  boolean only_root_children;	// true if only the root's children may be rotated

  boolean alternate_nodes;	// true if we alternately rotate two nodes only

  boolean allow_rotation;	// true if we can do rotations
  boolean allow_search;		// true if we can do searches

  final int MAX_ROTATABLE_NODES = 100;
  int rotatable_nodes[] = new int[MAX_ROTATABLE_NODES]; // nodes that we may rotate
  int num_rotatable_nodes = 0;	// (num_rotable_nodes = 0 means all nodes may be rotated)

  TextField search_field;	// UI component to capture user's search request
  int search_key;		// the key to search for

  // Things having to do with appearance:

  Font f = new Font( "TimesRoman", Font.PLAIN, 14 );
  FontMetrics fm = getFontMetrics( f );

  final Color LineColor      = Color.black;
  final Color HighlightColor = Color.orange;
  final Color NodeColor      = Color.cyan;

  final int NODE_WIDTH = 40;	// width of a node
  final int NODE_HEIGHT = 30;	// height of a node

  /** 
   * Init the applet.  Just insert elements into the tree and
   * compute the tree's initial position.
   */

  public void init() {

    // Get the applet parameters

    parse_parameters();

    // Determine initial tree position

    position_tree( root, 0, 0 );

    // Set up UI components

    if (allow_search) {
      setLayout( new FlowLayout(FlowLayout.LEFT) );
      search_field = new TextField( 4 );
      search_field.setEditable( true );
      add( new Label( "Enter search key:", Label.RIGHT ) );
      add( search_field );
    }
  }

  /**
   * Upon starting, start any threads that were previously stopped
   */

  public void start() {

    if (rotate_thread != null && rotate_thread.isAlive())
      rotate_thread.resume();

    if (search_thread != null && search_thread.isAlive())
      search_thread.resume();
  }

  /**
   * Upon stopping, stop all active threads
   */

  public void stop() {

    if (rotate_thread != null && rotate_thread.isAlive())
      rotate_thread.suspend();

    if (search_thread != null && search_thread.isAlive())
      search_thread.suspend();
  }

  /**
   * Upon a `paint', just redraw the tree.
   */

  public void paint( Graphics g ) {

    // Draw any stored edges

    if (num_edges > 0) {
      g.setColor( LineColor );
      for (int i=0; i<num_edges; i++)
	g.drawLine( (int) edges[i][0], (int) edges[i][1],
                    (int) edges[i][2], (int) edges[i][3] );
    }

    // Draw the rest of the tree

    draw_tree( root, g );
  }

  /**
   * Use update() to do double buffering.
   */

  Image     buffer_image;
  Graphics  buffer_graphics;
  Dimension buffer_size;

  public synchronized void update( Graphics g ) {

    if (buffer_image == null) {
      buffer_size     = size();
      buffer_image    = createImage( buffer_size.width, buffer_size.height );
      buffer_graphics = buffer_image.getGraphics();
      buffer_graphics.setFont( getFont() );
    }

    buffer_graphics.setColor( Color.white );
    buffer_graphics.fillRect( 0, 0, buffer_size.width, buffer_size.height );

    paint( buffer_graphics );

    g.drawImage( buffer_image, 0, 0, null );
  }

  /**
   * Upon a mouseDown, colour the two nodes involved, but
   * don't rotate.
   */

  public boolean mouseDown( Event evt, int x, int y ) {

    // Ignore mouse if rotations are not allowed

    if (! allow_rotation)
      return false;

    // Ignore mouse if still rotating

    if (rotate_thread != null && rotate_thread.isAlive())
      return false;

    // Find node closest to mouse

    rotation_node = find_closest_node( root, x, y );

    if (rotation_node == root)
      rotation_node = null;	// Ignore root, since it can't be rotated

    else if (only_root_children && rotation_node.parent != root)
      rotation_node = null;	// Restrict to children of root if flag is set

    else if (alternate_nodes && rotatable_nodes[0] != rotation_node.key)
      rotation_node = null;	// Restrict rotations to two nodes alternately

    else if (num_rotatable_nodes != 0) { // Restrict to `rotatable nodes' if supplied
      int i;
      for (i=0; i<num_rotatable_nodes; i++)
	if (rotatable_nodes[i] == rotation_node.key)
	  break;
      if (i == num_rotatable_nodes)
	rotation_node = null;
    }

    if (alternate_nodes && rotation_node != null) {
      int temp = rotatable_nodes[0];
      rotatable_nodes[0] = rotatable_nodes[1];
      rotatable_nodes[1] = temp;
    }      
      
    // Highlight rotation node and its parent

    if (rotation_node != null) {
      rotation_node.highlight_node = true;
      rotation_node.parent.highlight_node = true;
      repaint();
    }

    return true;
  }

  /**
   * Upon a mouseUp, rotate the two nodes.  This involves spawning
   * a thread that will slowly move the nodes.
   */

  public boolean mouseUp( Event evt, int x, int y ) {

    // Ignore mouse if still rotating

    if (rotate_thread != null && rotate_thread.isAlive())
      return false;

    // Ignore mouse no node selected for rotation

    if (rotation_node == null)
      return true;

    // Start rotating

    rotation_node.highlight_node = false;
    rotation_node.parent.highlight_node = false;

    rotate_thread = new rotate(this);
    rotate_thread.start();

    return true;
  }

  /**
   * Handle an action from one of the UI components.
   */

  public boolean action( Event evt, Object arg ) {

    // Ignore if searches not allowed

    if (! allow_search)
      return false;

    // Ignore if still performing the search

    if (search_thread != null && search_thread.isAlive())
      return false;

    // Handle the event

    if (evt.target instanceof TextField) {
      try
	search_key = Integer.parseInt( search_field.getText() );
      catch (NumberFormatException e) {
	System.out.println( "ERROR in BST applet: `" + search_field.getText() + "' is not an integer" );
	return true;
      }
      search_thread = new search(this);
      search_thread.start();

    } else
      System.out.println( "ERROR in BST applet: Unrecognized UI event" );

    return true;
  }

  /**
   * Parse the parameters supplied with the applet.  These are listed at the
   * top of this file.
   */

  void parse_parameters() {

    String keys;

    // Read keys

    keys = getParameter( "keys" );
    if (keys != null) {
      StringTokenizer t = new StringTokenizer( keys );
      while (t.hasMoreTokens())
	insert( Integer.parseInt(t.nextToken()) );
    }

    // Read allowable actions

    keys = getParameter( "action" );
    if (keys != null) {
      StringTokenizer t = new StringTokenizer( keys );
      while (t.hasMoreTokens()) {
	String s = t.nextToken();
	if (s.equals("rotate"))
	  allow_rotation = true;
	else if (s.equals("search"))
	  allow_search = true;
	else
	  System.out.println( "Error in BST applet: unrecognized action `" + s + "' in param list." );
      }
    }

    // Read rotatable nodes

    only_root_children = (getParameter( "only_root_children" ) != null);

    keys = getParameter( "alternate_nodes" );
    if (keys != null) {
      alternate_nodes = true;
      StringTokenizer t = new StringTokenizer( keys );
      while (t.hasMoreTokens()) {
	int i = Integer.parseInt(t.nextToken());
	if (num_rotatable_nodes < MAX_ROTATABLE_NODES)
	  rotatable_nodes[ num_rotatable_nodes++ ] = i;
      }
      if (num_rotatable_nodes != 2)
	System.out.println( "Error in BST applet: expected 2 keys for `alternate_nodes' param, but got " + num_rotatable_nodes );
    }

    keys = getParameter( "rotatable_nodes" );
    if (keys != null) {
      StringTokenizer t = new StringTokenizer( keys );
      while (t.hasMoreTokens()) {
	int i = Integer.parseInt(t.nextToken());
	if (num_rotatable_nodes < MAX_ROTATABLE_NODES)
	  rotatable_nodes[ num_rotatable_nodes++ ] = i;
      }
    }
  }

  /**
   * Find the closest tree node to a mouse click.
   */

  node find_closest_node( node root, int x, int y ) {

    node l_closest, r_closest;
    int  l_dist, r_dist, root_dist;

    if (root == null)
      return null;

    l_closest = find_closest_node( root.left, x, y );
    r_closest = find_closest_node( root.right, x, y );

    l_dist = dist_to_node( l_closest, x, y );
    r_dist = dist_to_node( r_closest, x, y );
    root_dist = dist_to_node( root, x, y );
    
    if (l_dist <= r_dist && l_dist <= root_dist)
      return l_closest;

    if (r_dist <= l_dist && r_dist <= root_dist)
      return r_closest;
    
    return root;
  }

  /**
   * Return the L1 distance from (x,y) to node n.
   */

  int dist_to_node( node n, int x, int y ) {

    if (n == null)
      return Integer.MAX_VALUE;

    return Math.abs( x - (int) n.x ) + Math.abs( y - (int) n.y );
  }

  /**
   * Determine the (x,y) locations of each node of the tree.  This
   * positions the subtree at `root' in a box whose upper-left corner
   * is defined by `upper' and `left' pixel locations.  This returns
   * the width of the box, in pixels.
   */

  int position_tree( node root, int upper, int left ) {

    int l_width, r_width;

    if (root == null)
      return 0;

    l_width = position_tree( root.left, upper + NODE_HEIGHT, left );

    root.x = left + l_width + NODE_WIDTH/2;
    root.y = upper + NODE_HEIGHT/2;

    r_width = position_tree( root.right, upper + NODE_HEIGHT,
			     left + l_width + NODE_WIDTH ); 

    return l_width + NODE_WIDTH + r_width;
  }

  /**
   * Draw the tree: For each node, draw its subtrees, then
   * draw its parent link (if any), then draw the node itself.
   */

  void draw_tree( node root, Graphics g ) {

    if (root == null)
      return;

    draw_tree( root.left, g );
    draw_tree( root.right, g );

    if (root.parent != null)
      draw_parent_edge( root, g );

    draw_node( root, g );
  }

  /**
   * Draw the parent edge of this node.
   */

  void draw_parent_edge( node n, Graphics g ) {

    if (! n.hide_edge) {
      g.setColor( LineColor );
      g.drawLine( (int) n.x, (int) n.y, (int) n.parent.x, (int) n.parent.y );
    }
  }

  /**
   * Draw this node.
   */

  void draw_node( node n, Graphics g ) {

    String key = Integer.toString( n.key );
    int width  = fm.stringWidth( key );
    int height = fm.getAscent(); // just numbers, so Descent = 0

    // Fill in node's circle

    if (n.highlight_node)
      if (n.highlight_colour == null)
	g.setColor( HighlightColor );
      else
	g.setColor( n.highlight_colour );
    else
      g.setColor( NodeColor );

    g.fillOval( (int) n.x - NODE_WIDTH/2, (int) n.y - NODE_HEIGHT/2,
		NODE_WIDTH, NODE_HEIGHT );

    // Outline the circle and draw the key

    g.setColor( LineColor );

    g.drawOval( (int) n.x - NODE_WIDTH/2, (int) n.y - NODE_HEIGHT/2,
		NODE_WIDTH, NODE_HEIGHT );
    g.drawString( key, (int) n.x - width/2, (int) n.y - height/2 + fm.getAscent() - 1 );
  }

  /**
   * Insert a node into the BST
   */

  void insert( int k ) {

    node x, y, new_node;

    y = null;
    x = root;
  
    // y follows x down the tree until x is null

    while (x != null) {
      y = x;
      if (k == x.key)
	return;
      else if (k < x.key) 
	x = x.left;
      else
	x = x.right;
    }

    // allocate a new node

    new_node = new node();

    new_node.key    = k;
    new_node.parent = y;
    new_node.left   = null;
    new_node.right  = null;

    // point tree node to new node

    if (y == null)
      root = new_node;
    else 
      if (k < y.key)
	y.left = new_node;
      else
	y.right = new_node;
  }

  /**
   * Perform a rotation
   */

  void rotate( node c ) {

    node p = c.parent;		// parent of c
    node gp = p.parent;		// grandparent of c (might be null)

    // Update the lower edge which switches sides

    if (c == p.left) {
      p.left = c.right;
      if (p.left != null)
	p.left.parent = p;
      c.right = p;
      p.parent = c;
    } else {
      p.right = c.left;
      if (p.right != null)
	p.right.parent = p;
      c.left = p;
      p.parent = c;
    }

    // Update the upper edge which switches sides

    if (gp == null)
      root = c;
    else if (p == gp.left)
      gp.left = c;
    else
      gp.right = c;
    
    c.parent = gp;
  }
}


/* A Thread to animate rotating nodes */


class rotate extends Thread implements Runnable {

  final int ROTATE_TIME = 1000;	// total rotate time, in milliseconds

  bst tree;			// tree in which rotation occurs

  rotate( bst t ) {
    tree = t;
  }
  
  public void run() {

    node c, p, gc, gp;		// rotate about edge c-p
    
    c = tree.rotation_node;	// find c (= child)
    p = c.parent;		// find p (= parent)
    gp = p.parent;		// find gp (= grandparent)
    if (c == p.right)		// find gc (= grandchild, might be null)
      gc = c.left;
    else
      gc = c.right;

    // Phase I: move the nodes

    c.highlight_node = true;
    p.highlight_node = true;

    for (int i=0; i<tree.NODE_HEIGHT; i++) {

      c.y --;
      if (c == p.left)
	shift_up( c.left );
      else
	shift_up( c.right );

      p.y ++;
      if (c == p.right)
	shift_down( p.left );
      else
	shift_down( p.right );

      tree.repaint();

      try			// delay 1/3 of ROTATE_TIME for ALL of Phase I
	Thread.sleep( ROTATE_TIME/3/tree.NODE_HEIGHT );
      catch (InterruptedException e) {}
    }

    c.highlight_node = false;
    p.highlight_node = false;

    // Phase II: swap the lower edge (= parent edge of gc) from c to p

    tree.num_edges = 0;

    if (gc != null) {

      tree.num_edges = 1;
      gc.highlight_node = true;
      gc.hide_edge = true;

      tree.edges[0][0] = gc.x;
      tree.edges[0][1] = gc.y;
      tree.edges[0][2] = c.x;
      tree.edges[0][3] = c.y + tree.NODE_HEIGHT/2;

      float dx = p.x - tree.edges[0][2];
      float dy = p.y - tree.edges[0][3];

      float loops = (Math.abs(dx) > Math.abs(dy) ? Math.abs(dx) : Math.abs(dy)) / 2;

      int sleep_time = (int) (ROTATE_TIME/3/loops);
      if (sleep_time < 5)
	sleep_time = 5;

      dx = dx/loops;
      dy = dy/loops;

      tree.repaint();

      for (int i=0; i < loops; i++) {

	tree.edges[0][2] += dx;
	tree.edges[0][3] += dy;

	tree.repaint();

	try			// delay 1/3 of ROTATE_TIME for ALL of Phase II
	  Thread.sleep( sleep_time );
	catch (InterruptedException e) {}
      }

      gc.highlight_node = false;
    }

    // Phase III: swap the upper edge

    if (gp != null) {

      tree.num_edges ++;
      gp.highlight_node = true;
      p.hide_edge = true;

      tree.edges[tree.num_edges-1][0] = gp.x;
      tree.edges[tree.num_edges-1][1] = gp.y;
      tree.edges[tree.num_edges-1][2] = p.x;
      tree.edges[tree.num_edges-1][3] = p.y - tree.NODE_HEIGHT/2;

      float dx = c.x - tree.edges[tree.num_edges-1][2];
      float dy = c.y - tree.edges[tree.num_edges-1][3];

      float loops = (Math.abs(dx) > Math.abs(dy) ? Math.abs(dx) : Math.abs(dy)) / 2;

      int sleep_time = (int) (ROTATE_TIME/3/loops);
      if (sleep_time < 5)
	sleep_time = 5;

      dx = dx/loops;
      dy = dy/loops;

      tree.repaint();

      for (int i=0; i < loops; i++) {

	tree.edges[tree.num_edges-1][2] += dx;
	tree.edges[tree.num_edges-1][3] += dy;

	tree.repaint();

	try			// delay 1/3 of ROTATE_TIME for ALL of Phase II
	  Thread.sleep( sleep_time );
	catch (InterruptedException e) {}
      }

      p.hide_edge = false;
      gp.highlight_node = false;
    }

    if (gc != null)
      gc.hide_edge = false;

    tree.num_edges = 0;

    tree.rotate( c );

    tree.repaint();
  }

  void shift_up( node n ) {
    if (n == null)
      return;
    shift_up( n.left );
    shift_up( n.right );
    n.y --;
  }

  void shift_down( node n ) {
    if (n == null)
      return;
    shift_down( n.left );
    shift_down( n.right );
    n.y ++;
  }

}


/* A Thread to animate BST search */


class search extends Thread implements Runnable {

  final int SEARCH_TIME = 800;	// search time per node, in milliseconds

  bst tree;			// tree in which search occurs

  search( bst t ) {
    tree = t;
  }
  
  public void run() {
    node n, pn;

    // Clear old highlights

    if (tree.root != null && tree.root.highlight_node) {
      clear_highlights( tree.root );
      tree.repaint();
      try
	Thread.sleep( SEARCH_TIME );
      catch (InterruptedException e) {}
    }

    // Search

    pn = null;
    n = tree.root;

    while (n != null && n.key != tree.search_key) {

      // Pause on the node

      n.highlight_node = true;
      tree.repaint();
      try
	Thread.sleep( SEARCH_TIME );
      catch (InterruptedException e) {}

      // Move downward

      pn = n;

      if (tree.search_key < n.key)
	n = n.left;
      else
	n = n.right;
    }

    if (n != null) {
      n.highlight_node = true;
      tree.repaint();
      try
	Thread.sleep( SEARCH_TIME );
      catch (InterruptedException e) {}
      n.highlight_colour = Color.green;
    } else if (pn != null) {
      pn.highlight_node = true;
      pn.highlight_colour = Color.red;
    }

    tree.repaint();
  }

  void clear_highlights( node n ) {

    if (n == null)
      return;

    clear_highlights( n.left );
    clear_highlights( n.right );

    n.highlight_node = false;
    n.highlight_colour = null;
  }
}