//Hermit Interpolation
import java.io.*;

class NA123
{ 
  public static double [] Hermite(double xi[],double fi[],double dfi[])
  {
  //m degree of polynomial	  
  int i,j;
  int m=xi.length; 
  int n=m-1;
  double Q[][]=new double[2*n+2][2*n+2];
  double QQ[]=new double[2*n+2];
  double z[]=new double[2*n+2];
  for(i=0;i<=n;i++)
    {
	z[2*i]=xi[i];
	z[2*i+1]=xi[i];
	Q[2*i][0]=fi[i];
	Q[2*i+1][0]=fi[i];
	Q[2*i+1][1]=dfi[i];
	if(i!=0) { Q[2*i][1]=(Q[2*i][0]-Q[2*i-1][0])/(z[2*i]-z[2*i-1]);}
	}
	for(i=2;i<=(2*n+1);i++)
	   {for(j=2;j<=i;j++){Q[i][j]=(Q[i][j-1]-Q[i-1][j-1])/(z[i]-z[i-j]);}
	   }
	for(i=0;i<=(2*n+1);i++)
	  {QQ[i]=Q[i][i];}   
	//System.out.println(QQ.length+"\n"+Matrix.toStringT(QQ));
	return QQ;	
  }
  
  public static double funcHermite(double QQ[],double xi[],double x)
  {
	  //Hermit polynomial
  int i,j;
  int m=QQ.length-1;
  double xx=1;
  double toplam=QQ[0];
  for(i=1;i<m;i+=2)
    {   j=(i-1)/2;
	    xx*=(x-xi[j]);
	    toplam+=QQ[i]*xx;
	    xx*=(x-xi[j]);
	    toplam+=QQ[i+1]*xx;
    }
  return toplam;  	  
  }
    
 public static double[][]  funcHermite(double xi[],double yi[],double dyi[],int aradegersayisi)
 {
	//number of midpoints:  x--o--o--x--o--o--x  x data points midpoints are 2
	int n=xi.length;
	int nn=(n-1)*(aradegersayisi+1)+1;
	double z[][]=new double[2][nn];
    double Q[]=Hermite(xi,yi,dyi);	
    double dx=0;
    int k=0;
    int i;
    for(i=0;i<(n-1);i++)
       {  z[0][k]=xi[i];z[1][k]=funcHermite(Q,xi,z[0][k]);k++;
          for(int j=0;j<aradegersayisi;j++) 
             {dx=(xi[i+1]-xi[i])/((double)aradegersayisi+1.0);
              z[0][k]=z[0][k-1]+dx;z[1][k]=funcHermite(Q,xi,z[0][k]);k++;
             }
       }
       z[0][k]=xi[i];z[1][k]=funcHermite(Q,xi,z[0][k]);
    return z;
 } 
     
  public static void main(String args[]) throws IOException
  {
  double x[]={1.3,1.6,1.9};
  double y[]={0.620086,0.4554022,0.281818186};
  double dy[]={-0.5220232,-0.5698959,-0.5811571};
  double z1[][]=funcHermite(x,y,dy,8);
  Text.print(Text.T(z1),"Interpolation by using Hermite polynomials");
  System.out.println("Hermite polynomial interpolation\n"+Matrix.toStringT(z1));  
  Plot pp=new Plot(x,y);
  pp.setPlabel("Interpolation by using Hermite polynomials");
  pp.setPlotType(0,20); 
  pp.addData(z1[0],z1[1]);
  pp.plot();
   
  }
}
