import java.awt.*;
import java.applet.*;

public class Polynom extends Applet {
    PlotControls controls;
    TextArea co;
    public void init() {
        setLayout(new BorderLayout());
	co = new TextArea("Hallo!",7,20);
        PlotCanvas c = new PlotCanvas(co);
        add("Center", c);
	add("East",co);
        add("South", controls = new PlotControls(c));
	doLayout();
    }

    public void start() {
        controls.enable();
    }

    public void stop() {
        controls.disable();
    }

    public boolean handleEvent(Event e) {
        if (e.id == Event.WINDOW_DESTROY) {
            System.exit(0);
        }
        return false;
    }

    public static void main(String args[]) {
        Frame f = new Frame("Poynomial Interpolation");
        Polynom P = new Polynom();

        P.init();
        P.start();

        f.add("Center", P);
        f.resize(500, 500);
        f.show();
    }
}

class PlotCanvas extends Canvas{
    double      xmin=-1,xmax=1;
    double      ymin=-1,ymax=1;
    double      xtics=(double)0.5,ytics=(double)0.5;
    double      xtics1=(double)0.1,ytics1=(double)0.1;
    int         Grad;
    int         MaxGrad=100;
    double       x[];     //   Stützstellen
    double       y[];     //      -||-
    double       a[];     //   Koeffizienten
    int pointOnMouse=-1;
    Rectangle   r;
    Font        font; 
    int         mode;
    int   AddPoint=1;
    int   DelPoint=2;
    int   MovePoint=3;
    TextArea coeffs;

    public PlotCanvas(TextArea coeffs){
	this.coeffs=coeffs;
	this.Grad=3;
	x=new double[MaxGrad+1];
	y=new double[MaxGrad+1];
	a=new double[MaxGrad+1];
	x[0]=0; 	y[0]=0; 
	x[1]=-1;	y[1]=1;
	x[2]=1;	        y[2]=1;
	x[3]=.5;	y[3]=.25;
	calc_as();
	mode=MovePoint;
	font=new Font("Times",Font.PLAIN,10);
	this.coeffs.setFont(font);
	setBackground(Color.white);
    }

    public void paint(Graphics g) {
        r = getBounds();
        int hlines = r.height / 10;
        int vlines = r.width / 10;
	int xi,yi,yr;

	// Draw Ticlines
	g.setColor(Color.pink);
	for(int i=(int)(xmin/xtics1);i<=(int)(xmax/xtics1);i++){
	    xi=(int)(r.width*(i*xtics1-xmin)/(xmax-xmin));
	    g.drawLine(xi,0,xi,r.height-1);
	}

	g.setColor(Color.gray);
	g.setFont(font);
	for(int i=(int)(xmin/xtics);i<=(int)(xmax/xtics);i++){
	    xi=(int)(r.width*(i*xtics-xmin)/(xmax-xmin));
	    g.drawLine(xi,0,xi,r.height-1);
	    g.drawString(""+String.valueOf(i*xtics),xi+1,r.height/2+12*i);
	}

	int step=1;
	// Plot Graph
        g.setColor(Color.red);
	xi=0; yi=yval(xi); 
	for (int i = step; i <= r.width;i+=step) {
	    yr=yval(i);
	    g.drawLine(xi,yi,i,yr);
	    xi=i;yi=yr;
	} 
	// Write Coeffs.
	g.setFont(font);
        g.setColor(Color.black);
	for(int i=0;i<=Grad;i++) g.drawString("a"+i+"="+a[i],15,30+15*i);
	g.drawString("b0="+a[0],215,30);
	for(int i=1;i<=Grad;i++) 
	    g.drawString("b"+i+"="+a[i]/a[i-1],215,30+15*i);
	// Draw Points
	for(int i=0;i<=Grad;i++){
	    if(i==pointOnMouse) g.setColor(Color.green);
	    else g.setColor(Color.blue);
	    xi=(int)(r.width*(x[i]-xmin)/(xmax-xmin));
	    yi=(int)(r.height*(1-(y[i]-ymin)/(ymax-ymin)));
	    g.drawOval(xi-5,yi-5,10,10);
	    g.drawLine(xi-2,yi,xi+2,yi);
	    g.drawLine(xi,yi-2,xi,yi+2);
	}
    }

    public int yval(int xi){
	double x = xmin+xi*(xmax-xmin)/r.width;
	double y = a[Grad];
	double norm;
	for (int i=Grad-1;i>=0;i--){
	    y=x*y+a[i];
	}
	if(y>ymax)return -1;
	if(y<ymin)return r.height+1; 
	return (int)(r.height*(1-(y-ymin)/(ymax-ymin)));
    }
    public void calc_as(){
	// Calculate the coefficients of the polinom a[0]...a[Grad]
	double m[][];
	double norm;
	m=new double[Grad+2][Grad+1];
	for(int k=0;k<=Grad;k++){ 
	    m[0][k]=1; m[Grad+1][k]=y[k];
	}
	for(int i=1;i<=Grad;i++) for(int k=0;k<=Grad;k++){
	    m[i][k]=m[i-1][k]*x[k];
	}
	for(int n=1;n<=Grad;n++){
	    for(int i=0;i<=Grad+1;i++) for(int k=n;k<=Grad;k++){
		m[i][k]=m[i][k]-m[i][n-1];
	    }
	    for(int k=n;k<=Grad;k++){
		norm=m[n][k];
		for(int i=0;i<=Grad+1;i++)
		    m[i][k]=m[i][k]/norm;	
	    }
	}
	a[Grad]=m[Grad+1][Grad];
	for(int k=Grad-1;k>=0;k--){
	    a[k]=m[Grad+1][k];
	    for(int i=Grad;i>k;i--){
		a[k]-=a[i]*m[i][k];
	    }
	}
    }

    public void changeMode(String label){
	if(label.equals("+")) mode=AddPoint;
	if(label.equals("-")) mode=DelPoint;
	if(label.equals("move")) mode=MovePoint;
    }

    public void zoom(double p){
	double xmax1=((1+p)*xmax+(1-p)*xmin)/2;
	xmin=((1+p)*xmin+(1-p)*xmax)/2;
	xmax=xmax1;
	if(2*xtics>xmax-xmin){xtics=xtics/10;xtics1=xtics1/10;}
	if(20*xtics<xmax-xmin){xtics=xtics*10;xtics1=xtics1*10;}
	redraw();
    }

    public boolean handleEvent(Event e) {
        switch (e.id) {
	case Event.MOUSE_DOWN:
	    if(mode==AddPoint){ if(Grad<MaxGrad){
		Grad++;
		x[Grad]= xmin+e.x*(xmax-xmin)/r.width;
                y[Grad]= ymax-e.y*(ymax-ymin)/r.height;
		redraw();
	    }}
	    else{
		int xi,yi;
		for(int i=0;i<=Grad;i++){
		    xi=(int)(r.width*(x[i]-xmin)/(xmax-xmin))-e.x;
		    yi=(int)(r.height*(1-(y[i]-ymin)/(ymax-ymin)))-e.y;
		    if(Math.sqrt(xi*xi+yi*yi)<=5){
			if(mode==MovePoint) pointOnMouse=i;
			if(mode==DelPoint && Grad > 1){
			    for(int k=i;k<Grad;k++) {x[k]=x[k+1];y[k]=y[k+1];}
			    Grad--;
			}
			redraw(); break;
		    }
		}
	    }
	    return true;
	case Event.MOUSE_UP:
	    pointOnMouse=-1;
	    writeCoeffs();
	    redraw();
	    return true;
	case Event.MOUSE_DRAG:
	    if(pointOnMouse>=0){
		x[pointOnMouse]= xmin+e.x*(xmax-xmin)/r.width;
		y[pointOnMouse]= ymax-e.y*(ymax-ymin)/r.height;
		redraw();
	    }
	    return true;
	case Event.WINDOW_DESTROY:
            System.exit(0);
            return true;
	default: return false;
	}
    }

    public void redraw() {
	calc_as();
        repaint();
    }

    void writeCoeffs(){
	coeffs.append("\na_i=");
	for(int i=0;i<=Grad;i++) coeffs.append(" "+a[i]);
	coeffs.append("0 \nb_i= "+a[0]);
	for(int i=1;i<=Grad;i++) coeffs.append(" "+a[i]/a[i-1]);
	coeffs.append("0 \n  ");
	coeffs.setCaretPosition((coeffs.getText()).length()); 
    }

}

class PlotControls extends Panel {
    TextField s;
    TextField e;
    PlotCanvas canvas;

    public PlotControls(PlotCanvas canvas) {
        this.canvas = canvas;
	add(new Button("><"));
	add(new Button("<>"));
        add(new Button("+"));
        add(new Button("-"));
        add(new Button("move"));
    }

    public boolean action(Event ev, Object arg) {
        if (ev.target instanceof Button) {
            String label = (String)arg;
	    if(label.equals("><")) canvas.zoom(5./4);
	    if(label.equals("<>")) canvas.zoom(4./5);
	    if(label.equals("+")) canvas.mode=canvas.AddPoint;
	    if(label.equals("-")) canvas.mode=canvas.DelPoint;
	    if(label.equals("move")) canvas.mode=canvas.MovePoint;
            return true;
        }
        return false;
    }
}