package Current.popups.Polynomial;

import Current.*;
import Current.basic.*;

import java.applet.Applet;
import java.awt.event.*;
import java.awt.*;


/*This class does some basic manipulations with
polynomials with Complex coefficients.  I set the
maximum degree at 100*/


public class Polynomial {
    Complex[] z=new Complex[100];   //the coefficients
    int D;  //the degree


    /**basic constructors*/
    public Polynomial() {
	D=0;
	for(int i=0;i<100;++i) z[i]=new Complex(0,0);
    }


    public Polynomial(Complex[] w,int d) {
	D=d;
	for(int i=0;i<100;++i) z[i]=new Complex(0,0);
	for(int i=0;i<=d;++i) z[i]=new Complex(w[i].x,w[i].y);
    }

    public void print() {
	System.out.println("Polynomial:");
	for(int i=0;i<=D;++i) {
            Integer I=new Integer(i);
	    System.out.print("k^"+I.toString()+" ");
	    z[i].print();}
    }

    /**vector space operations*/

    public Polynomial scale(Complex w) {
	Polynomial P=new Polynomial();
	P.D=D;
	for(int i=0;i<=D;++i) {
	    P.z[i]=w.times(this.z[i]);
	}
	return(P);
    }

    public Polynomial plus(Polynomial P) {
	int d;
	d=this.D;
	if(d<P.D) d=P.D;
	Polynomial Q=new Polynomial();
	Q.D=d;
	for(int i=0;i<99;++i)
	    Q.z[i]=Complex.plus(z[i],P.z[i]);
	return(Q);
    }


    public Polynomial minus(Polynomial P) {
	int d;
	d=this.D;
	if(d<P.D) d=P.D;
	Polynomial Q=new Polynomial();
	Q.D=d;
	for(int i=0;i<99;++i)
	    Q.z[i]=Complex.minus(z[i],P.z[i]);
	return(Q);
    }



    /**the derivative of a polynomial*/
    public Polynomial derivative() {
	Polynomial P=new Polynomial();
	P.D=D-1;
	for(int i=1;i<=D;++i) {
	  P.z[i-1]=this.z[i].times(new Complex(i,0));
	}
	return(P);
    }

    /**In this routine we encode a finite sequence as
       the coefficients of a polynomial.  Then we take the
       difference sequence.*/

    public Polynomial difference() {
	Polynomial P=new Polynomial();
	P.D=D-1;
	for(int i=0;i<D;++i) {
	    P.z[i]=Complex.minus(z[i+1],z[i]);
	}
	return(P);
    }

    /**this routine recognizes when some of the coefficients of a
       polynomial are nearly integers*/

    public Polynomial recognizeInteger(int tolerance) {
	Polynomial P=new Polynomial();
	P.D=D;
	for(int i=0;i<=D;++i) {
	    P.z[i]=Complex.recognizeInteger(z[i],tolerance);
	}
	return(P);
    }




    /**recognizes the zero polynomial.  0 means yes*/

    public int recognizeZero() {
	for(int i=0;i<=D;++i) {
	    if(z[i].norm()>.0001) return(1);
	}
	return(0);
    }





    /**This routine is applied to a sequence (encoded as a
       polynomial) f(0),f(1),f(2),f(3),...  Assuming that these
       numbers are the output of a polynomial f, this routine
       takes successive differences and tried to find the
       degree.   If the degree is higher than the number of
       terms, meaning that taking successive differences does
       not reveal a pattern, then -1 is returned*/

    public int effectiveDegree() {
	int test=0;
	Polynomial P=new Polynomial(this.z,this.D);
	for(int i=0;i<D;++i) {
	    P=P.difference();
	    test=P.recognizeZero();
	    if(test==0) return(i);
	}
	return(-1);
    }



    /**This routine assumes that the effective degree of a
       sequence f(0),f(1),...,f(d) is d.  Then it computes
       the highest term (coeff of x^d) of the degree d
       polynomial which generates the sequence.  We only use
       the routine after computing the effective degree of
       the sequence*/

    public Polynomial termFromGrowth(int d) {
	int test=0;
	Polynomial P=new Polynomial(this.z,this.D);
	for(int i=0;i<d;++i) {
	    P=P.difference();
	}
	Complex Z=P.z[0];
	Polynomial Q=new Polynomial();
	Q.z[0]=new Complex(0,0);
	Q.D=d;
	for(int i=1;i<=d;++i) {
            Z=new Complex(Z.x*1.0/i,Z.y*1.0/i);
	    Q.z[i]=new Complex(0,0);
	}
	Q.z[d]=Z;
	return(Q);
    }



    /*Given a mononial of the form f(x)=Cx^D, this
      routine computes f(0),...,f(d), and returns these
      values encoded as a polynomial.*/

    public Polynomial createValues(int d) {
	Polynomial P=new Polynomial();
	if(d==0) {
	    P.D=0;
	    return(P);
	}
	P.D=d;
	Complex Z=z[D];
	for(int i=0;i<=d;++i) {
	    Complex X=new Complex(Math.pow(1.0*i,D),0);
	    P.z[i]=Complex.times(Z,X);
	}
	return(P);
    }

    /*Here is the main routine.  In this routine we have a
      sequence f(0),f(1),f(2),... and we compute the 
      polynomial which generates the sequence.  If the
      effective degree computation gives a -1 we return
      the 0 polynomial (with degree -1) to indicate that
      there are not enough numbers in the sequence to
      determine the polynomial*/


    public Polynomial fitPolynomial() {
	Polynomial A1=new Polynomial(this.z,this.D);
	Polynomial A2=new Polynomial();
	Polynomial B1=new Polynomial();
	Polynomial B2=new Polynomial();
	int d=this.effectiveDegree();
	if(d==-1) {A2.D=-1;return(A2);}
	A2.z[0]=new Complex(A1.z[0].x,A1.z[0].y);
	for(int i=d;i>0;--i) {
	    B1=A1.termFromGrowth(i);
	    B2=B1.createValues(this.D);
	    A1=A1.minus(B2);
	    A2=A2.plus(B1);
	}
	return(A2);
    }

}