import java.awt.*;
import java.util.*;

public class LagrangePanel
  extends Panel
{
  public Hashtable htDr;
  private int W;
  private int H;
  private Dot grabbedDot;
  private int nPts;
  private int yBase = 350;
  private int xBase = 250;
  private double lagpoly[][];
  private double intpoly[];
  private double slopes[];

  private boolean showContrib = true;
  private boolean doSpline = false;
  private boolean doLagrange = true;

  private Color gold = new Color( 255, 215, 0 );
  private Color steelBlue = new Color( 70, 130, 180 );
  private Color curveColor[] = {
                             Color.cyan, Color.magenta, Color.yellow,
                             Color.red, Color.green, Color.blue,
                             Color.orange, Color.pink
                           };

  public LagrangePanel( int w, int h )
  {
    W = w;
    H = h;
    htDr = new Hashtable();
    setBackground( Color.black );
  }

  public Dimension minimumSize()
  {
    return new Dimension( W, H );
  }
  public Dimension preferredSize()
  {
    return minimumSize();
  }

  public void showLagrange( boolean b )
  {
    doLagrange = b;
    repaint();
  }
  public void showContributions( boolean b )
  {
    showContrib = b;
    repaint();
  }

  public void showSplines( boolean b )
  {
    doSpline = b;
    repaint();
  }

  public void lagrange( double x[], double y[] )
  {
    int i, j, jj, k;
    for( j = 0; j < nPts; j++ )
      intpoly[j] = 0.0;
    for( i = 0; i < nPts; i++ ) {
      lagpoly[i][0] = 1.0;
      double fac = y[i];
      j = 0;
      for( k = 0; k < nPts; k++ ) {
        if( k == i )
          continue;
        lagpoly[i][j+1] = lagpoly[i][j];
        for( jj = j; jj > 0; jj-- )
          lagpoly[i][jj] = lagpoly[i][jj-1] - lagpoly[i][jj]*x[k];
        lagpoly[i][0] *= -x[k];
        j++;
        fac /= ( x[i] - x[k] );
      }
      for( j = 0; j < nPts; j++ )
        lagpoly[i][j] *= fac;
      for( j = 0; j < nPts; j++ )
        intpoly[j] += lagpoly[i][j];
    }
  }

  private double polyEval( double x, double a[], int n )
  {
    int j;
    double val = a[n];
    for( j = n-1; j >= 0; j-- )
      val = val * x + a[j];
    return val;
  }
  private double polyEval( double x, double a[][], int i, int n )
  {
    int j;
    double val = a[i][n];
    for( j = n-1; j >= 0; j-- )
      val = val * x + a[i][j];
    return val;
  }

  private double A0( double x )
  {
    return (x-1.0)*(x-1.0)*(2*x+1);
  }
  private double B0( double x )
  {
    return (x-1.0)*(x-1.0)*(2*x+1);
  }

  public static double splineEval( double x,
                                    double x0, double x1,
                                      double y0, double y1,
                                        double s0, double s1 )
  {
    double h = x1 - x0;
    double t = (x-x0)/h;
    double u = 1 - t;

    return u * u * ( y0 * ( 2 * t + 1 ) + s0 * h * t )
           + t * t * ( y1 * ( 3 - 2 * t ) - s1 * h * u );
  }

  public static void computeSplineSlopes( int n,
                                        double x[],
                                          double y[],
                                            double s[] )
  {
    int i, j;
    double h[] = new double[n];
    double hinv[] = new double[n];
    double g[] = new double[n];
    double a[] = new double[n+1];
    double b[] = new double[n+1];
    double fac;

    for( i = 0; i < n; i++ ) {
      h[i] = x[i+1] - x[i];
      hinv[i] = 1.0 / h[i];
      g[i] = 3 * ( y[i+1]-y[i] ) * hinv[i] * hinv[i];
    }
    a[0] = 2 * hinv[0];
    b[0] = g[0];
    for( i = 1; i <= n; i++ ) {
      fac = hinv[i-1]/a[i-1];
      a[i] = (2-fac) * hinv[i-1];
      b[i] = g[i-1] - fac * b[i-1];
      if( i < n ) {
        a[i] += 2 * hinv[i];
        b[i] += g[i];
      }
    }
    s[n] = b[n] / a[n];
    for( i = n-1; i >= 0; i-- )
      s[i] = ( b[i] - hinv[i] * s[i+1] ) / a[i];
  }

  private String doubleFormat( double val, int dec )
  {
    StringBuffer txt  = new StringBuffer();
    if( val < 0.0 ) {
      txt.append( "-" );
      val = - val;
    }
    int i, k;
    k = (int) val;
    txt.append( "" + k );
    val -= k;
    if( dec > 0 ) {
      txt.append( '.' );
    }
    for( i = 0; i < dec; i++ ) {
      val *= 10;
      k = (int)(val + 0.001);
      txt.append( "" + k );
      val -= k;
    }
    return txt.toString();
  }

  private void paintCurves( Graphics g )
  {
    int i, j;
    String xName, yName, lName;
    String xvs, yvs;
    double x[] = new double[nPts];
    double y[] = new double[nPts];
    double xSorted[] = new double[nPts];
    double ySorted[] = new double[nPts];
    FontMetrics fm = g.getFontMetrics();

    for( i = 0; i < nPts; i++ ) {
      xName = "x" + i;
      yName = "y" + i;
      lName = "l" + i;
      Drawable xi = getDrawable( xName );
      Drawable yi = getDrawable( yName );
      Drawable li = getDrawable( lName );
      xSorted[i] = x[i] = 0.02 * ( xi.getX() - xBase );
      ySorted[i] = y[i] = 0.02 * ( xi.getY() - yi.getY() );
      g.setColor( curveColor[i%curveColor.length] );
      xvs = doubleFormat( x[i], 2 );
      yvs = doubleFormat( y[i], 2 );
      int wx = fm.stringWidth( xvs );
      int wy = fm.stringWidth( yvs );
      int h = fm.getHeight();
      g.drawString( xvs, xi.getX() - wx / 2, xi.getY() + h );
      g.drawString( yvs, 2 + li.getX(), li.getY() + h / 2 );
    }

    int ix, iy, ixLast, iyLast;
    double rx, ry, rxstep;

    if( doLagrange ) {
      lagrange( x, y );
      if( showContrib ) {
        for( i = 0; i < nPts; i++ ) {
          g.setColor( curveColor[i%curveColor.length] );
          ixLast = -1;
          iyLast = -1;
          for( ix = 0; ix <= 500; ix += 5 ) {
            rx = 0.02 * ( ix - xBase );
            ry = polyEval( rx, lagpoly, i, nPts - 1 );
            iy = yBase - (int)( ry * 50.0 );
            if( iy > 10000 ) iy = 10000;
            if( iy < -10000 ) iy = -10000;
            if( ixLast >= 0 ) {
              g.drawLine( ixLast, iyLast, ix, iy );
            }
            ixLast = ix;
            iyLast = iy;
          }
        }
      }
      g.setColor( Color.white );
      ixLast = -1;
      iyLast = -1;
      for( ix = 0; ix <= 500; ix += 5 ) {
        rx = 0.02 * ( ix - xBase );
        ry = polyEval( rx, intpoly, nPts - 1 );
        iy = yBase - (int)( ry * 50.0 + 0.5 );
        if( iy > 2000 ) iy = 2000;
        if( iy < -2000 ) iy = -2000;
        if( ixLast >= 0 ) {
          g.drawLine( ixLast, iyLast, ix, iy );
        }
        ixLast = ix;
        iyLast = iy;
        // System.out.println( ix + "," + iy );
      }
    }
    if( doSpline ) {
      double tmp;
      g.setColor( steelBlue );
      for( i = 0; i < nPts; i++ ) {
        boolean noExch = true;
        for( j = 0; j < nPts - 1; j++ ) {
          if( xSorted[j] > xSorted[j+1] ) {
            tmp = xSorted[j+1];
            xSorted[j+1] = xSorted[j];
            xSorted[j] = tmp;
            tmp = ySorted[j+1];
            ySorted[j+1] = ySorted[j];
            ySorted[j] = tmp;
            noExch = false;
          }
        }
        if( noExch )
          break;
      }
      computeSplineSlopes( nPts - 1, xSorted, ySorted, slopes );
      int seg;
      ixLast = -1;
      iyLast = -1;
      int nDivs = 50;
      for( seg = 0; seg < nPts - 1; seg++ ) {
        rxstep = ( xSorted[seg+1] - xSorted[seg] ) / nDivs;
        for( i = 0; i < nDivs; i++ ) {
          rx = xSorted[seg] + i * rxstep;
          ry = splineEval( rx,
                            xSorted[seg], xSorted[seg+1],
                            ySorted[seg], ySorted[seg+1],
                            slopes[seg], slopes[seg+1] );
          iy = yBase - (int)( ry * 50.0 + 0.5 );
          ix = xBase + (int)( rx * 50.0 + 0.5 );
          if( iy > 2000 ) iy = 2000;
          if( iy < -2000 ) iy = -2000;
          if( ixLast >= 0 ) {
            g.drawLine( ixLast, iyLast, ix, iy );
          }
          ixLast = ix;
          iyLast = iy;
        }
      }
    }
  }

  public void paint( Graphics g )
  {
    paintCurves( g );

    Enumeration e = htDr.elements();

    while( e.hasMoreElements() ) {
      Drawable dr = (Drawable)( e.nextElement() );
      dr.paint( g );
    }
  }

  public void addDrawable( String name, Drawable dr )
  {
    htDr.put( name, dr );
  }

  public Drawable getDrawable( String name )
  {
    return (Drawable)( htDr.get( name ) );
  }

  public Dot closestDot( int x, int y )
  {
    Dot d = null;
    Enumeration e = htDr.elements();

    int minSep = 7;

    while( e.hasMoreElements() ) {
      Drawable dr = (Drawable)( e.nextElement() );
      if( dr instanceof Dot ) {
        Dot a = (Dot)dr;
        int sep =  a.separation( x, y );
        if( ( sep < 6 ) && ( minSep > sep ) ) {
          minSep = sep;
          d = a;
        }
      }
    }
    return d;
  }

  public boolean handleEvent( Event evt )
  {
    if( evt.id == Event.MOUSE_DOWN ) {
      grabbedDot = closestDot( evt.x, evt.y );
    }
    if( evt.id == Event.MOUSE_DRAG ) {
      if( grabbedDot != null ) {
        grabbedDot.requestMove( evt.x, evt.y );
        repaint();
      }
    }
    if( evt.id == Event.MOUSE_UP ) {
      if( grabbedDot != null ) {
        grabbedDot.requestMove( evt.x, evt.y );
        repaint();
      }
    }
    return super.handleEvent( evt );
  }

  public void init( int nPts )
  {
    init( nPts, false );
  }
  public void init( int nPts, boolean doRandomHeights )
  {
    htDr.clear();
    this.nPts = nPts;
    Dot xa = new Dot( "xa", 0, 350, false, false, null );
    Dot xb = new Dot( "xb", 500, 350, false, false, null );
    Line xAxis = new Line( "xAxis", xa, xb, Color.gray );
    addDrawable( "xAxis", xAxis );
    int i, x, y, xStep;
    x = 50;
    xStep = 400 / (nPts - 1);
    for( i = 0; i < nPts; i++ ) {
      y = 50;
      if( doRandomHeights )
        y += (int)( 50 * Math.random() );
      Color color = curveColor[i%curveColor.length];
      Dot xi = new Dot( "x"+i, x, 350, true, false, color );
      addDrawable( "x"+i, xi );
      Dot yi = new Dot( "y"+i, x, 350 - y, false, true, color );
      yi.xSrc = xi;
      addDrawable( "y"+i, yi );
      Line li = new Line( "l"+i, xi, yi, color );
      addDrawable( "l"+i, li );
      x += xStep; 
    }
    lagpoly = new double[nPts][nPts];
    intpoly = new double[nPts];
    slopes = new double[nPts];
    repaint();
  }

  public static void main( String[] args )
  {
    LagrangePanel p = new LagrangePanel( 500, 500 );
    p.init( 5 );
    KFrame fr = new KFrame( "Lagrange's Interpolation Formula" );
    fr.add( "Center", p );
    fr.pack();
    fr.show();
  }
}