import javax.swing.*;
import java.awt.*;
import java.awt.event.*;

public class Interpolation{
     static int i=0;    //孤立點指針
     public static int  n=100;           //n指點的個數，在監聽過程中可隨實際情況進行修改。
     static int[] a=new int[n];
     static int[] b=new int[n];
     public static void main(String args[]){             //構造交互界面
     	Frame f=new Frame("數值算法：插值算法（張軼雯 軟件0402 040950211）");       
     	Panel p=new Panel(); 
     	JTextField t=new JTextField();                             	
     	Button button1=new Button("拉格朗日插值算法");
     	Button button2=new Button("  牛頓插值算法  ");
     	Button button3=new Button("三次自然樣條算法");
     	Button button4=new Button("Clear！"); 
     	JTextArea display = new JTextArea(3,3);    
     	WindowClosed w=new WindowClosed(f);
     	MouseClick m=new MouseClick(f);
     	Lagrange l=new Lagrange(f);
        Newton n=new Newton(f);
        Scyt s=new Scyt(f);
        Picture ph=new Picture(f);
        display.append("請首先用鼠標在繪圖區點擊，生成點！！！"+'\n'+"然后再進行插值。");
        display.setEditable(false);

        f.addWindowListener(w);                     //加上關窗口的監聽器
        f.addMouseListener(m);                      //鼠標點擊生成孤立點
        
        button1.addActionListener(l);                   //拉格朗日
        button2.addActionListener(n);                   //牛頓
        button3.addActionListener(s);                   //三次樣條
        button4.addActionListener(ph);                 //清空畫圖區

        p.add(button1);             
        p.add(button2);
        p.add(button3);
        p.add(button4);
        p.add(display);
        p.setBackground(Color.darkGray);
                           
        f.add(p,"South");
        f.setBackground(Color.gray);                
        f.setSize(800,700);                   
        f.setLocation(10,10);           
        f.setVisible(true);                                
     }
}

class WindowClosed extends WindowAdapter{                  //關窗子
	WindowClosed(Frame f){
		this.f=f;
		}
    private Frame f;
    public void windowClosing(WindowEvent e){
    	System.exit(0);
    	}
}

class MouseClick extends MouseAdapter{                  //鼠標點擊
	MouseClick(Frame f){
		this.f=f;	
		}
  	private Frame f;
    private int[] a=Interpolation.a;
    private int[] b=Interpolation.b;
    boolean clicked=false;    
    public void mouseClicked(MouseEvent e){    	
    	clicked=true;
    	if(clicked)
    	{
    		a[Interpolation.i]=e.getX();
            b[Interpolation.i]=e.getY();
            Graphics g=f.getGraphics();
            g.setColor(Color.black);
            g.drawLine(e.getX(),e.getY(),e.getX(),e.getY());         
            g.drawString(Integer.toString(Interpolation.i+1),a[Interpolation.i],b[Interpolation.i]);
            Interpolation.i++;
        }
   }
}

class Lagrange implements ActionListener{     //拉格朗日算法         
	Lagrange(Frame f){
		this.f=f;		
	}
	private Frame f;
	private JTextArea display;
	private int[] X=Interpolation.a;
	private int[] Y=Interpolation.b;
	private int i;	
	public void actionPerformed(ActionEvent e){
		for(i=0,Interpolation.n=0;X[i]!=0;i++,Interpolation.n++);
		int n=Interpolation.n;	
	    double b,p,xm,xn,s;
	    int k,u,v;		
	    for(b=X[0];b<X[n-1];b++)
		{
			s=0;
		    for(k=0;k<n;k++)
		    {
			 	p=(double)Y[k];
			 	
				for(i=0;i<n;i++)
				{
					xm=(double)X[i];
					xn=(double)X[k];
					if(i!=k) p=p*(b-xm)/(xn-xm);					
				}
				s=s+p;	
		    }
			u=(int)s;
			v=(int)b;	   
	        Graphics g=f.getGraphics();
	        g.setColor(Color.yellow);
            for(int w=0;w<1000000;w++);//延時
	        g.drawLine(v,u,v,u);	
        }
    }
}

class Newton implements ActionListener{
	Newton(Frame f){
		this.f=f;
	}
	private Frame f;
	private int[] a=Interpolation.a;
	private int[] b=Interpolation.b;
	private int i,k,vBound,n;
	public void actionPerformed(ActionEvent e){
    for(i=0,Interpolation.n=0;a[i]!=0;i++,Interpolation.n++);//    ji suan   n	  
	n=Interpolation.n;	                  
	double[] d=new double[n];
	for(i=0;i<n;i++)
	    d[i]=b[i];  //ba zongzuobiao gei d[i]
	for(k=1;k<n;k++)
	   for(i=n-1;i>=k;i--)
	       d[i]=(d[i]-d[i-1])/(a[i]-a[i-k]);	              
	double p;
	for(int hBound=a[0];hBound<a[n-1];hBound++){
		p=d[n-1];
        for(i=n-2;i>=0;i--)
	    	p=d[i]+p*(hBound-a[i]);
	    vBound=(int)p; 	   
	    Graphics g=f.getGraphics();	    
	    g.setColor(Color.red);
	    for(int w=0;w<(1000000);w++);//延時
	        g.drawLine(hBound,vBound,hBound,vBound);  	
	    }	
	}
}

class Scyt implements ActionListener{
	Scyt(Frame f){
		this.f=f;
	}
    private Frame f;
	private int[] X=Interpolation.a;
	private int[] Y=Interpolation.b;
	private int i,k,n,statue,uuu;//	
	public void actionPerformed(ActionEvent e){
	    for(i=0,Interpolation.n=0; X[i]!=0;i++,Interpolation.n++);
        n=Interpolation.n;	//ji suan n;
		double S, S1;
		double h[]=new double[n];
		double a[]=new double[n];
		double b[]=new double[n];
		double c[]=new double[n];
		double d[]=new double[n];
		double s[]=new double[n];
		double s1[]=new double[n];
		double s2[]=new double[n];
		for(k=0;k<n-1;k++)
		  h[k]=X[k+1]-X[k];
		a[1]=2*(h[0]+h[1]);
		for(k=2;k<n-1;k++)
		  a[k]=2*(h[k-1]+h[k])-h[k-1]*h[k-1]/a[k-1];
		for(k=1;k<n;k++)
		  c[k]=(Y[k]-Y[k-1])/h[k-1];
		for(k=1;k<n-1;k++)
		   d[k]=6*(c[k+1]-c[k]);
		    b[1]=d[1];
		for(k=2;k<n-1;k++)
		   b[k]=d[k]-b[k-1]*h[k-1]/a[k-1];
		s2[n-2]=b[n-2]/a[n-2];
		for(k=n-3;k>0;k--)
		  s2[k]=(b[k]-h[k]*s2[k+1])/a[k];
		s2[0]=0;
		s2[n-1]=0;        
        for(int t=X[0];t<X[n-1];t++)//key process of the sanciyangtiaosuanfa 
                {          
	         	  for(statue=0,uuu=0;statue<n-1&&uuu==0;statue++)
	         	   if(t<=X[statue+1]) {	         	   	
	         	   	k=statue;         	       
	         	    uuu=1;	         	   	                      
                    S1=c[k+1]-s2[k+1]*h[k]/6-s2[k]*h[k]/3;                  
                    S=Y[k]+S1*(t-X[k])+s2[k]*(t-X[k])*(t-X[k])/2;
                    S=S+(s2[k+1]-s2[k])*(t-X[k])*(t-X[k])*(t-X[k])/(6*h[k]);                  
                    int zong=(int)S;	         
		            Graphics g=f.getGraphics();    
	                g.setColor(Color.green);
	                for(int w=0;w<1000000;w++);//延時!
	                g.drawLine(t,zong,t,zong);          
		            		         
		          }
		        }
		         
    }
}

class Picture implements ActionListener{
	Picture(Frame f){
		this.f=f;
	}
	private Frame f;
	public void actionPerformed(ActionEvent e){
		f.repaint();
		for(int i=0;i<Interpolation.n;i++)
		{
			Interpolation.a[i]=0;
		    Interpolation.b[i]=0;}
		    Interpolation.n=100;
		    Interpolation.i=0; 
	     }
}