/* Roots.java
 *
 * Graphs a function and demonstrates root-finding.
 *
 * This is based upon code taken from
 *
 *    http://www.mcluhan.toronto.edu/~zoli/java/Graph.html
 *
 * Really should have a graphing class that takes
 * a function to draw, provides add_point, add_line,
 * del_point, del_line, and reset methods, and a 
 * function to call upon a click.
 */


import java.applet.*;
import java.awt.*;
import java.lang.Math;


class Coordinate {
  double x, y;
}

class Segment {
  double x0, y0, x1, y1;
  Color colour;
}

class ColouredPoint {
  double x, y;
  Color colour;
}

public class Roots extends Applet

{
  int MAX_NUM_SEGS = 100;
  int MAX_NUM_POINTS = 100;
  int POINT_RADIUS = 3;
  double SCALE_FACTOR = 0.4;
  double INITIAL_SCALE = 50;

  /* Some colours:
   *
   * 34, 139, 34  forrest green
   * 205, 92, 92  indian red
   * 210, 105, 30 chocolate
   * 143, 188, 143 dark sea green
   * 192, 96, 119  "unselected window" in X
   */

  Color not_found_colour = Color.red;
  Color found_colour = Color.green;

  Color prev_colour = Color.red;
  Color curr_colour = Color.orange;
  Color next_colour = Color.yellow;

  double mid_x, mid_y, pix_per_unit;

  Scrollbar zoom_bar;

  Coordinate dragFrom = new Coordinate();
  Coordinate dragTo = new Coordinate();
  Coordinate origin = new Coordinate();

  Segment segs[];
  ColouredPoint pts[];
  int num_segs = 0;
  int num_pts = 0;

  Graphics slate;
  Image HiddenIm;

  double Scale = INITIAL_SCALE * SCALE_FACTOR;
  int MouseUp = 1;

  // ---------------------------------------------------------------- Roots 
  // ---------------------------------------------------------------- Roots 
  // ---------------------------------------------------------------- Roots 

  Choice method_choice;
  Choice function_choice;
  Button reset_button;

  Panel graph;

  String functions[] = { "3 sin(x)", "x^2/10", "1/x", "5 sin(x) / x", "sin(1/x)", "" };
  String methods[] = { "Bisection method", "Newton method", "Secant method", "" };

  int num_functions, num_methods;

  int ROOT_DIST = 4;		// dist (in pixels) to extend vertical line at root
  int TANGENT_DIST = 20;	// dist to extend tangent line beyond endpoints
  int mode = 0;			// 0 = stop, 1 = run
  int alg = 1;			// 0 = bisect, 1 = newton, 2 = secant
  int step = 0;			// current step within algorithm
  double prev_x, prev_y;		// current & previous positions
  double curr_x, curr_y;
  double next_x, next_y;

/* The Function itself
 */


private double f( double x )

  {
    switch (function_choice.getSelectedIndex()) {

    case 0:
      return 3 * Math.sin(x);

    case 1:
      return x * x / 10.0;

    case 2:
      if (x != 0)
	return 1.0 / x;
      else
	return 0;

    case 3:
      if (x != 0)
	return 5 * Math.sin(x) / x;
      else
	return 5;

    case 4:
      if (x == 0)
	return 0;
      else
	return Math.sin(1/x);

    default:
      System.out.println( "Unknown function type" );
      return 0;
    }
  }


private double f_deriv( double x )

  {
    switch (function_choice.getSelectedIndex()) {

    case 0:
      return 3 * Math.cos(x);
    case 1:
      return 2 * x / 10.0;
    case 2:
      if (x != 0)
	return -1.0 / (x * x);
      else
	return 0.0;
    case 3:
      if (x != 0)
	return 5 * (Math.cos(x) / x - Math.sin(x) / (x * x));
      else
	return 99999;
    default:
      System.out.println( "Unknown function type" );
      return 0;
    }
  }


/* What to do on a mouse click
 */


private void mouse_click( int x, int y )

  {
    switch (alg) {
    case 0:
      bisect_click( x, y );
      break;
    case 1:
      newton_click( x, y );
      break;
    case 2:
      secant_click( x, y );
      break;
    }
  }


private void bisect_click( int scr_x, int scr_y )

  {
    double x, y, signum;

    switch (step) {

    case 0:  // get prev_x & prev_y

      x = world_x( scr_x );
      y = f(x);

      if (y < 0)
	signum = -1;
      else
	signum = +1;

      reset_graph();
      add_pt( x, y, prev_colour );
      add_extended_seg( ROOT_DIST, x, 0, x, y, prev_colour );

      prev_x = x;
      prev_y = y;

      step++;
      break;

    case 1: // get curr_x and curr_y

      x = world_x( scr_x );
      y = f(x);

      if (y < 0)
	signum = -1;
      else
	signum = +1;

      add_pt( x, y, prev_colour );
      add_extended_seg( ROOT_DIST, x, 0, x, y, prev_colour );

      curr_x = x;
      curr_y = y;

      step++;
      break;

    case 2: // Got prev & curr (already drawn); now draw midpoint

      x = (prev_x + curr_x) / 2.0;
      y = f(x);
      
      add_extended_seg( ROOT_DIST, x, 0, x, y, next_colour );

      next_x = x;
      next_y = y;
      
      step++;
      break;
      
    case 3: // now choose which endpoint to replace

      reset_graph();

      if (Math.abs(next_x - curr_x) < .04) {
	
	add_pt( next_x, next_y, found_colour );
	add_extended_seg( ROOT_DIST, next_x, 0, next_x, next_y, found_colour );
	step++;
	
      } else {
	
	if (prev_y * next_y > 0) {
	  prev_x = next_x;
	  prev_y = next_y;
	} else if (curr_y * next_y > 0) {
	  curr_x = next_x;
	  curr_y = next_y;
	} else {
	  prev_x = next_x; curr_x = next_x; prev_y = next_y; curr_y = next_y;
	}

	add_pt( prev_x, prev_y, prev_colour );
	add_extended_seg( ROOT_DIST, prev_x, 0, prev_x, prev_y, prev_colour );

	add_pt( curr_x, curr_y, prev_colour );
	add_extended_seg( ROOT_DIST, curr_x, 0, curr_x, curr_y, prev_colour );
	
	step = 2;
      }
      break;
      
    case 4:

      step = 0;
      reset_graph();
      break;
    }
  }


private void newton_click( int scr_x, int scr_y )

  {
    double x, y, signum;

    switch (step) {

    case 0:  // stopped

      // Set the initial approximation at this position

      x = world_x( scr_x );
      y = f(x);

      if (y < 0)
	signum = -1;
      else
	signum = +1;

      reset_graph();
      add_pt( x, y, not_found_colour );
      add_extended_seg( ROOT_DIST, x, 0, x, y, not_found_colour );

      curr_x = x;
      curr_y = y;

      step++;
      break;

    case 1: // At a function value (i.e. an approx root), next find tangent

      x = curr_x - f(curr_x) / f_deriv(curr_x);
      y = 0;
      
      reset_graph();
      add_extended_seg( ROOT_DIST, curr_x, 0, curr_x, curr_y, not_found_colour );
      add_pt( curr_x, curr_y, not_found_colour );
      add_extended_seg( TANGENT_DIST, x, y, curr_x, curr_y, next_colour );
      
      prev_x = curr_x;
      prev_y = curr_y;
      curr_x = x;
      curr_y = y;
      
      step++;
      break;
      
    case 2: // At a tangent, next find function value

      y = f(curr_x);
      
      reset_graph();
      
      if (Math.abs(y) < .01) {
	
	step++;
	add_pt( curr_x, y, found_colour );
	add_extended_seg( ROOT_DIST, curr_x, 0, curr_x, y, found_colour );
	
      } else {
	
	add_extended_seg( TANGENT_DIST, curr_x, curr_y, prev_x, prev_y, next_colour );
	add_pt( curr_x, y, not_found_colour );
	add_extended_seg( ROOT_DIST, curr_x, 0, curr_x, y, not_found_colour );
	step = 1;
      }
      
      curr_y = y;
      break;
      
    case 3:
      
      step = 0;
      reset_graph();
      break;
    }
  }


private void secant_click( int scr_x, int scr_y )

  {
    double x, y, signum;

    switch (step) {

    case 0:  // get prev_x & prev_y

      x = world_x( scr_x );
      y = f(x);

      if (y < 0)
	signum = -1;
      else
	signum = +1;

      reset_graph();
      add_pt( x, y, prev_colour );
      add_extended_seg( ROOT_DIST, x, 0, x, y, prev_colour );

      prev_x = x;
      prev_y = y;

      step++;
      break;

    case 1: // get curr_x and curr_y

      x = world_x( scr_x );
      y = f(x);

      if (y < 0)
	signum = -1;
      else
	signum = +1;

      add_pt( x, y, curr_colour );
      add_extended_seg( ROOT_DIST, x, 0, x, y, curr_colour );

      curr_x = x;
      curr_y = y;

      step++;
      break;

    case 2: // Got prev & curr (already drawn); now draw secant

      x = (prev_x * f(curr_x) - curr_x * f(prev_x)) / (f(curr_x) - f(prev_x));
      y = f(x);
      
      add_extended_seg( TANGENT_DIST, x, 0, curr_x, curr_y, next_colour );
      add_extended_seg( TANGENT_DIST, x, 0, prev_x, prev_y, next_colour );

      next_x = x;
      next_y = y;
      
      step++;
      break;
      
    case 3: // prev, curr, & secant drawn; now draw line up to f()

      if (Math.abs(next_y) < .01) {
	
	reset_graph();
	add_pt( next_x, next_y, found_colour );
	add_extended_seg( ROOT_DIST, next_x, 0, next_x, next_y, found_colour );
	step++;
	
      } else {
	
	//add_pt( prev_x, prev_y, prev_colour );
	//add_extended_seg( ROOT_DIST, prev_x, 0, prev_x, prev_y, prev_colour );

	//add_pt( curr_x, curr_y, curr_colour );
	//add_extended_seg( ROOT_DIST, curr_x, 0, curr_x, curr_y, curr_colour );

	add_pt( next_x, next_y, next_colour );
	add_extended_seg( ROOT_DIST, next_x, next_y, next_x, 0, next_colour );
      }

      step++;
      break;
      
    case 4:

      prev_x = curr_x; prev_y = curr_y; curr_x = next_x; curr_y = next_y;

      reset_graph();
      add_pt( prev_x, prev_y, prev_colour );
      add_extended_seg( ROOT_DIST, prev_x, 0, prev_x, prev_y, prev_colour );
      add_pt( curr_x, curr_y, curr_colour );
      add_extended_seg( ROOT_DIST, curr_x, 0, curr_x, curr_y, curr_colour );

      step = 2;
      break;

    case 5:
      
      step = 0;
      reset_graph();
      break;
    }
  }



  // ---------------------------------------------------------------- end Roots
  // ---------------------------------------------------------------- end Roots
  // ---------------------------------------------------------------- end Roots


public void init()

  {
    int i;

    setup_panels();

    setForeground (Color.black);
    origin.x = 0;
    origin.y = 0;
    HiddenIm = createImage( size().width, size().height );
    slate = HiddenIm.getGraphics();

    pts = new ColouredPoint[MAX_NUM_POINTS];
    for (i=0; i<MAX_NUM_POINTS; i++)
      pts[i] = new ColouredPoint();

    segs = new Segment[MAX_NUM_SEGS];
    for (i=0; i<MAX_NUM_SEGS; i++)
      segs[i] = new Segment();

    reset_graph();
  }


public void reset_graph()

  {
    num_pts = 0;
    num_segs = 0;
  }


public void del_pt()

  {
    num_pts--;
    if (num_pts < 0)
      num_pts = 0;
  }


public void add_pt( double x, double y, Color colour )

  {
    if (num_pts >= MAX_NUM_POINTS)
      System.out.println( "Too many points added to graph" );
    else {
      pts[num_pts].x = x;
      pts[num_pts].y = y;
      pts[num_pts].colour = colour;
      num_pts++;
    }
  }


public void add_seg( double x0, double y0, double x1, double y1, Color colour )

  {
    if (num_segs >= MAX_NUM_SEGS)
      System.out.println( "Too many segments added to graph" );
    else {
      segs[num_segs].x0 = x0;
      segs[num_segs].y0 = y0;
      segs[num_segs].x1 = x1;
      segs[num_segs].y1 = y1;
      segs[num_segs].colour = colour;
      num_segs++;
    }
  }


public void add_extended_seg( int dist, double x0, double y0, double x1, double y1, Color colour )

  {
    double incx, incy, len;

    len = Math.sqrt( (y1-y0)*(y1-y0) + (x1-x0)*(x1-x0) );

    incx = (x1-x0) / len * POINT_RADIUS * dist / pix_per_unit;
    incy = (y1-y0) / len * POINT_RADIUS * dist / pix_per_unit;

    add_seg( x0-incx, y0-incy, x1+incx, y1+incy, colour );
  }



public void start()

  {
  }


private void setup_panels()

  {
    Panel panel = new Panel();

    // method choice

    method_choice = new Choice();
    for (num_methods = 0; methods[ num_methods ].length() != 0; num_methods++)
      method_choice.addItem( methods[ num_methods ] );
    method_choice.select( "Newton method" );

    // function choice

    function_choice = new Choice();
    for (num_functions = 0; functions[ num_functions ].length() != 0; num_functions++)
      function_choice.addItem( functions[ num_functions ] );
    function_choice.select( "x^2/10" );

    // scrollbar

    zoom_bar = new Scrollbar( Scrollbar.VERTICAL );
    zoom_bar.setValues( (int)INITIAL_SCALE, 5, 1, 2 * (int) INITIAL_SCALE );

    // reset

    reset_button = new Button( "Reset" );

    // Set up the South subpanel

    panel.setLayout( new FlowLayout( FlowLayout.LEFT, 25, 0 ) );
    panel.add( method_choice );
    panel.add( function_choice );
    panel.add( reset_button );

    // Add to main panel

    setLayout( new BorderLayout() );
    add( "North", panel );
    add( "East", zoom_bar );

    // Add a restart button ??
  }


  /////////////////////////////////////////////////////////
  // Event handling
  /////////////////////////////////////////////////////////

public boolean handleEvent( Event e )
	
  {
    double newScale;

    if (e.target == zoom_bar) {

      newScale = zoom_bar.getValue() * SCALE_FACTOR;

      origin.x = (double) origin.x * Scale / newScale; // keep the same position centred 
      origin.y = (double) origin.y * Scale / newScale; // in the window

      Scale = newScale;

      repaint();
      return true;

    } else if (e.target == function_choice) {

      repaint();
      return true;

    } else if (e.target == method_choice) {
      
      reset_graph();
      step = 0;
      alg = method_choice.getSelectedIndex();
      repaint();
      return true;

    } else if (e.target == reset_button) {

      origin.x = 0;
      origin.y = 0;
      Scale = INITIAL_SCALE * SCALE_FACTOR;
      zoom_bar.setValue( (int) INITIAL_SCALE );
      step = 0;
      repaint();
      return true;

    } else

      return super.handleEvent(e);
  }

  // This enables the user to see the graph by pressing enter only

public boolean keyUp (Event evt, int Key)
  {
    return false;
  }

  // This enables the user to drag the coordinate system with the mouse

public boolean mouseDown (Event evt, int x, int y)
  {
    dragFrom.x = x;
    dragFrom.y = y;
    MouseUp = 0;
    return false;
  }

public boolean mouseDrag (Event evt, int x, int y)
  {
    dragTo.x = x;
    dragTo.y = y;
    repaint();
    return false;
  }

public boolean mouseUp (Event evt, int x, int y)
  {
    if (x == dragFrom.x && y == dragFrom.y) { // no motion between mouse down and up

      mouse_click( x, y );

    } else {			// mouse was dragged

      origin.x += dragTo.x - dragFrom.x;
      origin.y += dragTo.y - dragFrom.y;
    }

    dragFrom.x = dragTo.x;
    dragFrom.y = dragTo.y;

    MouseUp = 1;

    repaint();
    return false;
  }


  /////////////////////////////////////////////////////////
  // Painting and Stuff
  /////////////////////////////////////////////////////////

public void update(Graphics g)
  {
    paint( g );
  }


public void paint(Graphics g)

  {
    DrawCoordSystem ();
    Draw ();
    g.drawImage (HiddenIm, 0, 0, this);
  }

  ////////////////////////////////////////////////////////////////////
  // This function draws the initial coordinating system to the screen.
  ////////////////////////////////////////////////////////////////////

private void DrawCoordSystem ()

  {
    int i, x, y;

    mid_x = size().width  * 0.5 + origin.x + dragTo.x - dragFrom.x;
    mid_y = size().height * 0.5 + origin.y + dragTo.y - dragFrom.y;
    pix_per_unit     = size().width / Scale;

    // First clear the slate

    slate.setColor( getBackground() );
    slate.fillRect( 0, 0, size().width, size().height );

    // Draw x and y-axis

    slate.setColor( Color.black );
		
    slate.drawLine( 0, (int)mid_y, size().width, (int)mid_y );	// x-axis
    slate.drawLine( (int)mid_x, 0, (int)mid_x, size().height ); // y-axis
		
    // Draw the tick marks

    for (i=1; i<100; i++) {
      x = screen_x(i);
      if (x >= 0 && x < size().width)
	slate.drawLine( x, (int)mid_y + 2, x, (int)mid_y - 2);
      x = screen_x(-i);
      if (x >= 0 && x < size().width)
	slate.drawLine( x, (int)mid_y + 2, x, (int)mid_y - 2);
      y = screen_y(i);
      if (y >= 0 && x < size().height)
	slate.drawLine( (int)mid_x - 2, y, (int)mid_x + 2, y );
      y = screen_y(-i);
      if (y >= 0 && x < size().height)
	slate.drawLine( (int)mid_x - 2, y, (int)mid_x + 2, y );
    }
  }


/* Draw everything:
 *
 *  - the function f()
 *  - any stored points
 *  - any stored lines
 */


private void Draw ()

  {
    double y, x;
    int Y, OLD_Y;
    int i;

    mid_x = size().width  * 0.5 + origin.x + dragTo.x - dragFrom.x;
    mid_y = size().height * 0.5 + origin.y + dragTo.y - dragFrom.y;
    pix_per_unit     = size().width / Scale;

    // Draw the function

    x = world_x(0);
    y = f(x);
    Y = screen_y(y);

    slate.setColor (Color.black);

    for (i = 1; i <= size().width; i++)
      {
	x = world_x(i);
	y = f(x);

	OLD_Y = Y;
	Y = screen_y(y);

	slate.drawLine (i - 1, OLD_Y, i, Y);
      }

    // Draw the segments

    for (i=0; i<num_segs; i++) {
      slate.setColor( segs[i].colour );
      slate.drawLine( screen_x(segs[i].x0), screen_y(segs[i].y0),
			 screen_x(segs[i].x1), screen_y(segs[i].y1) );
    }

    // Draw the points

    for (i=0; i<num_pts; i++) {
      slate.setColor( pts[i].colour );
      slate.fillOval( screen_x(pts[i].x) - POINT_RADIUS,
			 screen_y(pts[i].y) - POINT_RADIUS,
			 POINT_RADIUS*2, POINT_RADIUS*2 );
      slate.setColor( Color.black );
      slate.drawOval( screen_x(pts[i].x) - POINT_RADIUS,
			 screen_y(pts[i].y) - POINT_RADIUS,
			 POINT_RADIUS*2, POINT_RADIUS*2 );
    }
  }


/* Routines to convert back and forth
 * between screen and world coordinates
 */


private double world_x( int scr_x )

  {
    return (double) (scr_x - mid_x) / pix_per_unit;
  }


private double world_y( int scr_y )

  {
    return (double) (mid_y - scr_y) / pix_per_unit;
  }


private int screen_x( double world_x )

  {
    return (int) mid_x + (int) (world_x * pix_per_unit);
  }


private int screen_y( double world_y )

  {
    return (int) mid_y - (int) (world_y * pix_per_unit);
  }
}