//******************************************************************************
// interpolate.java:     Applet
//
//******************************************************************************
import java.applet.*;
import java.awt.*;

//==============================================================================
// Main Class for applet interpolate
//
//==============================================================================
public class interpolate extends Applet
{
	Label loc;              //A label to show the current location
	GraphCanvas c;          //The graph canvas (subclassed from canvas)
	Label pointcount;       //A label to display number of points
	Button newgraph;        //Button to reset the graph
	Scrollbar vs;           //Vertical scrollbar
	Scrollbar hs;           //Horizontal scrollbar
	Label polystring;       //A string representation of the polynomial
	Button drawcurve;		//Button to draw the curve
	Checkbox c1;			//A checkbox for constant update mode

	// interpolate Class Constructor
	//--------------------------------------------------------------------------
	public interpolate()
	{

	}

	// APPLET INFO SUPPORT:
	//              The getAppletInfo() method returns a string describing the applet's
	// author, copyright date, or miscellaneous information.
    //--------------------------------------------------------------------------
	public String getAppletInfo()
	{
		return "Name: Interpolate\r\n" +
		       "Author: Jason Plumb\r\n" +
		       "Created with Microsoft Visual J++ Version 1.0";
	}


	// The init() method is called by the AWT when an applet is first loaded or
	// reloaded.  Override this method to perform whatever initialization your
	// applet needs, such as initializing data structures, loading images or
	// fonts, creating frame windows, setting the layout manager, or adding UI
	// components.
    //--------------------------------------------------------------------------
	public void init()
	{
	// If you use a ResourceWizard-generated "control creator" class to
	// arrange controls in your applet, you may want to call its
	// CreateControls() method from within this method. Remove the following
	// call to resize() before adding the call to CreateControls();
	// CreateControls() does its own resizing.
	//----------------------------------------------------------------------
	
		Label L1 = new Label("Location:");
		loc = new Label("0,0          ");
		Label L2 = new Label("Point count:");
		pointcount = new Label("0     ");
		newgraph = new Button("Restart");
		drawcurve = new Button("Draw Curve");
		c = new GraphCanvas(600,200);
		c.setBackground(Color.white);
		vs = new Scrollbar(Scrollbar.VERTICAL, c.size().height/2, 20, 0, c.size().height);
		hs = new Scrollbar(Scrollbar.HORIZONTAL, c.size().width/2, 20, 0, c.size().width);
		polystring = new Label("                   ---empty---");
		c1 = new Checkbox("Auto Draw");
		c1.setState(true);

		GridBagLayout gridbag = new GridBagLayout();
		setLayout(gridbag);

		{//constraints for "Location" label
		GridBagConstraints gbc = new GridBagConstraints();
		gbc.fill = GridBagConstraints.BOTH;
		gbc.gridx = 0; gbc.gridy = 0;
		gridbag.setConstraints(L1, gbc);
		add(L1);}

		{//constraints for coordinate location label
		GridBagConstraints gbc = new GridBagConstraints();
		gbc.fill = GridBagConstraints.BOTH;
		gbc.gridx = GridBagConstraints.RELATIVE; gbc.gridy = 0;
		gridbag.setConstraints(loc, gbc);
		add(loc);}
		
		{//constraints for "Point count" label
		GridBagConstraints gbc = new GridBagConstraints();
		gbc.fill = GridBagConstraints.BOTH;
		gbc.gridx = GridBagConstraints.RELATIVE; gbc.gridy = 0;
		gridbag.setConstraints(L2, gbc);
		add(L2);}

		{//constraints for label containing number of points
		GridBagConstraints gbc = new GridBagConstraints();
		gbc.fill = GridBagConstraints.BOTH;
		gbc.gridx = GridBagConstraints.RELATIVE; gbc.gridy = 0;
		gridbag.setConstraints(pointcount, gbc);
		add(pointcount);}

		{//constraints for "Restart" button
		GridBagConstraints gbc = new GridBagConstraints();
		gbc.fill = GridBagConstraints.NONE;
		gbc.gridx = GridBagConstraints.RELATIVE; gbc.gridy = 0;
		gbc.anchor = GridBagConstraints.WEST;
		gridbag.setConstraints(newgraph, gbc);
		add(newgraph);}

		{//constraints for "Draw Curve" button
		GridBagConstraints gbc = new GridBagConstraints();
		gbc.fill = GridBagConstraints.NONE;
		gbc.gridx = GridBagConstraints.RELATIVE; gbc.gridy = 0;
		gbc.anchor = GridBagConstraints.WEST;
		gbc.insets = new Insets(0,10,0,0);
		gridbag.setConstraints(drawcurve, gbc);
		add(drawcurve);}

		{//constraints for "Auto Draw" checkbox
		GridBagConstraints gbc = new GridBagConstraints();
		gbc.fill = GridBagConstraints.NONE;
		gbc.gridx = GridBagConstraints.RELATIVE; gbc.gridy = 0;
		gbc.anchor = GridBagConstraints.WEST;
		gbc.insets = new Insets(0,10,0,0);
		gridbag.setConstraints(c1, gbc);
		add(c1);}

		{//constraints for the GraphCanvas object
		GridBagConstraints gbc = new GridBagConstraints();
		gbc.fill = GridBagConstraints.BOTH;
		gbc.gridx = 0; gbc.gridy = 1;
		gbc.gridwidth = 7;
		gbc.insets = new Insets(10,0,0,0);
		gridbag.setConstraints(c, gbc);
		add(c);}

		{//constraints for the vertical scrollbar
		GridBagConstraints gbc = new GridBagConstraints();
		gbc.fill = GridBagConstraints.BOTH;
		gbc.gridx = 7; gbc.gridy = 1;
		gbc.gridwidth = 1;
		gbc.insets = new Insets(10,0,0,0);
		gridbag.setConstraints(vs, gbc);
		add(vs);}

		{//constraints for the horizontal scrollbar
		GridBagConstraints gbc = new GridBagConstraints();
		gbc.fill = GridBagConstraints.BOTH;
		gbc.gridx = 0; gbc.gridy = 2;
		gbc.gridwidth = 7;
		gridbag.setConstraints(hs, gbc);
		add(hs);}

		{//constraints for the poly string label
		GridBagConstraints gbc = new GridBagConstraints();
		gbc.fill = GridBagConstraints.BOTH;
		gbc.gridx = 0; gbc.gridy = 3;
		gbc.gridwidth = 7;
		gridbag.setConstraints(polystring, gbc);
		add(polystring);}

		resize(640, 300);
	}

	// Place additional applet clean up code here.  destroy() is called when
	// when you applet is terminating and being unloaded.
	//-------------------------------------------------------------------------
	public void destroy()
	{
	}

	// interpolate Paint Handler
	//--------------------------------------------------------------------------
	public void paint(Graphics g)
	{
		if((c1.getState()==true)&&(c.ptcount>0))
			c.udc = true;			//If in auto-draw mode, draw curve
		//c.repaint();
	}

	//              The start() method is called when the page containing the applet
	// first appears on the screen. The AppletWizard's initial implementation
	// of this method starts execution of the applet's thread.
	//--------------------------------------------------------------------------
	public void start()
	{
	}
	
	//              The stop() method is called when the page containing the applet is
	// no longer on the screen. The AppletWizard's initial implementation of
	// this method stops execution of the applet's thread.
	//--------------------------------------------------------------------------
	public void stop()
	{
	}

	//mouseMove event handler
	public boolean mouseMove(Event evt, int x, int y){
		Rectangle r;
		r = c.bounds();

		if((x < r.x) || (x > r.x + r.width) || (y<r.y) || (y>r.y+r.height)) 
			return false;   //Exit out if outside of canvas 

		loc.setText(String.valueOf(x-c.yzero-r.x) + "," + String.valueOf(c.xzero-y+r.y));
		return true;
	}//mouseMove
	
	//Mouse click hander
	public boolean mouseUp(Event e, int x, int y){
		Rectangle r;
		r = c.bounds();

		if((x < r.x) || (x > r.x + r.width) || (y<r.y) || (y>r.y+r.height)) 
			return false;   //Exit out if outside of the GraphCanvas 
		//If we're here, they clicked inside the GraphCanvas
		x = x - c.yzero-r.x;                              //Adjust for origin
		y = c.xzero+r.y-y;	                              //Adjust for origin		
		c.userpts[c.ptcount] = new Point(x,y);
		c.ptcount++;
		pointcount.setText(String.valueOf(c.ptcount));

		c.p = c.Interpolate(c.userpts, c.ptcount);        //Interpolate new polynomial
		polystring.setText(c.p.ToString());
		if(c1.getState()==true)
			c.udc = true;
		c.repaint();
		return true;
	}//mouseUp

	//This is the action event handler
	public boolean action(Event e, Object o){       
		if(e.target==newgraph){//If they clicked the Restart button
			c.ptcount = 0;	//Set number of points to zero
			c.repaint();    //Repaint the GraphCanvas
			pointcount.setText("0");
			polystring.setText("                   ---empty---                    ");
			c.p=new Polynomial(0);
			return true;
		}//if
		if(e.target==drawcurve){//If they clicked the Draw Curve button
			c.udc = true;
			c.repaint();
			return true;
		}//if
		if(e.target==c1){		//If they clicked the check box
			if(c1.getState()==true){
				c.udc = true;
			}//if
			c.repaint();
			return true;
		}//if
		return false;
	}//action

	//This is the handleEvent handler.  Used really only for scrollbars
	public boolean handleEvent(Event e){
		if(e.target==vs){       //If they toyed with the vertical scrollbar
			if((e.id==Event.MOUSE_MOVE)||(e.id==Event.MOUSE_ENTER)||(e.id==Event.MOUSE_EXIT))
				return false;   //Don't care about these events
			c.xzero = vs.getValue();
			if(c1.getState()==true)
				c.udc = true;
			c.repaint();
			return true;
		}//if
		if(e.target==hs){       //If they toyed with the horizontal scrollbar
			if((e.id==Event.MOUSE_MOVE)||(e.id==Event.MOUSE_ENTER)||(e.id==Event.MOUSE_EXIT))
				return false;   //Don't care about these events
			c.yzero = hs.getValue();
			if(c1.getState()==true)
				c.udc = true;			//If auto draw mode, redraw curve
			c.repaint();
			return true;
		}//if
		return super.handleEvent(e);            //Return this so other events can be processed
	}//handleEvent
	

}//interpolate applet

//This is the definition of the sub-classed canvas class
class GraphCanvas extends Canvas{

	int xzero, yzero;               //Coordinates of the origin
	int xtic, ytic;                 //Tic mark spacing
	Point[] userpts;                //Array of user clicked points
	int ptcount;                    //Count of number of points
	double[] coeff;                 //Array of coefficients
	int p_degree;                   //Degree of the polynomial
	Polynomial p;
	boolean udc;					//Boolean to determine whether or not the curve needs to be drawn

	//Constructor for the GraphCanvas class
	//Takes height and width as parameters
	public GraphCanvas(int w, int h){
		xzero = h/2;                        //Set origin at middle of canvas
		yzero = w/2;
		xtic = 50;                          //Set x tic to 50
		ytic = 30;                          //Set y tics to 30
		userpts = new Point[50];			//Max # of userpts = 50
		ptcount = 0;                        //Start off with no points
		udc = false;
		this.resize(w,h);
	}//constructor

	//The paint method
	public void paint(Graphics g){
		DrawAxis(g);
		DrawPoints(g);
		//System.out.println("Inside canvas paint");
		if(udc==true){
			DrawCurve(g);
			udc = false;
		}//if
	}//paint

	//This function draws the points that the user clicked
	private void DrawPoints(Graphics g){
		int i;
		g.setColor(Color.red);
		for(i=0;i<ptcount;i++){
			g.drawOval(userpts[i].x + yzero - 1, xzero - userpts[i].y - 1, 3, 3);
		}//for
	}//DrawPoints

	//This function will draw the axis on the canvas.
	//It also draws the tic marks and the axis labels
	private void DrawAxis(Graphics g){
		Dimension d;
		int i, j;

		d = size();
		g.setColor(Color.black);
		g.drawLine(0,xzero,d.width,xzero);      //Draw x axis
		g.drawLine(yzero,0,yzero, d.height);//Draw y axis
		g.setColor(Color.blue);
		Font f = new Font("Helvetica", 0, 10);
		g.setFont(f);
		g.drawString("0",yzero+5, xzero+15);    //Draw 0 at origin
		for(i=yzero+xtic;i<d.width;i=i+xtic){   //Do right hand side of x axis
			g.drawLine(i,xzero-3, i, xzero+3);
			g.drawString(String.valueOf(i-yzero), i-5, xzero+17);
		}//for
		for(i=yzero-xtic;i>0;i=i-xtic){                 //Do left hand side of x axis
			g.drawLine(i,xzero-3, i, xzero+3);
			g.drawString(String.valueOf(i-yzero), i-5, xzero+17);
		}//for
		for(i=xzero-ytic;i>0;i=i-ytic){ //Do top of y axis
			g.drawLine(yzero-3, i,yzero+3, i);
			g.drawString(String.valueOf(xzero-i), yzero+5, i);
		}//for
		for(i=xzero+ytic;i<d.height;i=i+ytic){  //Do top of y axis
			g.drawLine(yzero-3, i,yzero+3, i);
			g.drawString(String.valueOf(xzero-i), yzero+5, i);
		}//for

	}//DrawAxis

	//This function will draw the curve on the screen
	private boolean DrawCurve(Graphics g){
		int i;
		double tmpy1, tmpy2;
		int ty1, ty2;
		g.setColor(Color.blue);
		for(i=-1*yzero;i<size().width-yzero;i++){
			tmpy1 = Horner(p.coeff, p.degree+1, (double)i);	 //Calculate the value of the poly at this point
			tmpy2 = Horner(p.coeff, p.degree+1, (double)i+1);	 //Calculate the value of the poly at next point
			ty1 = Math.round((float)tmpy1);
			ty2 = Math.round((float)tmpy2);
			//System.out.println("Drawing point at " + i + ", " + ty1);
			ty1 = xzero - ty1;								//Adjust for origin
			ty2 = xzero - ty2;								//Adjust for origin
			g.drawLine(i+yzero, ty1, i+1+yzero, ty2);
		}//for
		//repaint();
		return true;
	}

	//This function implements Horner's rule to evaluate a polynomial at a given point (x)
	//It takes an array of polynomial coefficients, a count of the number of items
	//in the coefficient array, and a point (x) at which to evaluate.
	double Horner(double[] pcoeff, int psize, double x){
		double result;
		int i;

		result = pcoeff[psize-1];
		for(i=psize-2;i>=0;i--){
			result = (result * x) + pcoeff[i];
		}//for
		return result;
	}//Horner

	//This funciton will do interpolation on the points in the points array passed
	//to it.  n must be passed and is the number of points in the array.
	//The function returns a Polynomial
	Polynomial Interpolate(Point[] pts, int n){
		Polynomial D, U, G, TMP;
		double num, denom;
		int i, j, k;

		D = new Polynomial(n);
		U = new Polynomial(n);                //Create new polynomials
		G = new Polynomial(n);

		G.coeff[0] = pts[0].y;                  //G begins constant
		D.coeff[0] = -1*pts[0].x;               //D begins as a linear poly
		D.coeff[1] = 1;

		for(j=1;j<n;j++){
			denom = Horner(D.coeff, n, pts[j].x);   //Evaluate D at x[j]
			num = Horner(G.coeff, n, pts[j].x);     //Evaluate G at x[j]
		
			for(i=0;i<n;i++){
				U.coeff[i] = D.coeff[i] * (pts[j].y - num) / denom;
			}//for
			for(i=0;i<n;i++){     //Loop to implement G = G + U
				G.coeff[i] = G.coeff[i] + U.coeff[i];
			}//for
			U.coeff[0] = -1*pts[j].x;
			U.coeff[1] = 1;

			TMP = new Polynomial(D.degree + U.degree - 2);
			//The following nested for loop is needed to implement D*U
		      for(i=D.degree-1;i>=0;i--){     //
				for(k=0;k<2;k++){
					TMP.coeff[i+k] = TMP.coeff[i+k] + (D.coeff[i]*U.coeff[k]);
				}//for
			}//for
			D = TMP;                        //D = D*U
		
		}//for j

		return G;
	}//interpolate

}//GraphCanvas

class Polynomial{
	double[] coeff;                 //Array of polynomial coefficients.
	int degree;                             //The degree of the poly
	String stringpoly;              //A string representation of the poly

	public Polynomial(int n){       //Create a new poly of degree n
		int i;
		coeff = new double[n+1];
		for(i=0;i<=n;i++){
			coeff[i]=0;
		}//for
		stringpoly = "--empty---";              //Polynomial starts off empty
		degree = n;
	}//Polynomial constructor

	//Creates a string representation of the polynomial
	public String ToString(){
		int i;
		String temp;
		stringpoly = "";
		for(i=degree;i>0;i--){
			if(coeff[i]!=0.0){        //Only show non-zero terms
				temp = String.valueOf(coeff[i]);
				
				if((temp.lastIndexOf('.')+3)>temp.length())
					temp = temp.substring(0, temp.lastIndexOf('.')+2);
				else
					temp = temp.substring(0, temp.lastIndexOf('.')+3);
				if((temp.compareTo("0.00")!=0) && (temp.compareTo("-0.00")!=0)){						//If it's smaller than 0.01 don't show it
					stringpoly = stringpoly + temp + "x^";
					stringpoly = stringpoly + String.valueOf(i) + " + ";
				}
			}//if
		}//for
		temp = String.valueOf(coeff[0]);
		if((temp.lastIndexOf('.')+3)>temp.length())
			temp = temp.substring(0, temp.lastIndexOf('.')+2);
		else
			temp = temp.substring(0, temp.lastIndexOf('.')+3);
		if((temp.compareTo("0.00")!=0) && (temp.compareTo("-0.00")!=0)){						//If it's smaller than 0.01 don't show it
			stringpoly = stringpoly + temp;     //Zero power term
		}//if
		return stringpoly;
	}//ToString
}//Polynomial