// ComplexPolynomial.java
//       A complex polynomial is represented by
//       an array of complex coefficients c[0], c[1], ... , c[n]
//       The value of a complex polynomial for some value 'z' is
//       P(z) = c[0] + c[1]*z + c[2]*z^2 + c[3]*z^3 + ... + c[n]*z^n
//       where z^3 represents pow(z,3) and P is an nth order polynomial

public class ComplexPolynomial
{
  Complex P[];

  public ComplexPolynomial()
  {
  }
  
  public ComplexPolynomial(ComplexPolynomial T)
  {
    int n = T.P.length;
    P = new Complex[n];
    for(int i=0; i<n; i++) P[i]= new Complex(T.P[i]);
  }
  
  public ComplexPolynomial(Complex T[])
  {
    int n = T.length;
    P = new Complex[n];
    for(int i=0; i<n; i++) P[i]= new Complex(T[i]);
  }
 
  public ComplexPolynomial(double X[])
  {
    int n = X.length;
    P = new Complex[n];
    for(int i=0; i<n; i++) P[i]=new Complex(X[i]);
  }
 
  public ComplexPolynomial(double X[], double Y[])
  {
    int n = X.length;
    P = new Complex[n];
    for(int i=0; i<n; i++) P[i]=new Complex(X[i],Y[i]);
  }

  public Complex[] toVector()
  {
    int n = P.length;
    Complex X[] = new Complex[n];
    for(int i=0; i<n; i++) X[i]=P[i];
    return X;
  }
  
  public static ComplexPolynomial fromRoots(Complex X[])
  {
    int n = X.length;
    Complex P[] = new Complex[n+1];
    P[0] = X[0].negate();
    P[1] = new Complex(1.0);
    if(n==1) return new ComplexPolynomial(P);
    for(int i=1; i<n; i++)
    {
      P[i+1] = new Complex(0.0);
      for(int j=0; j<=i; j++)
      {
        P[i+1-j] = P[i-j].subtract(P[i+1-j].multiply(X[i]));
      }
      P[0] = P[0].multiply(X[i]).negate();
    }
    return new ComplexPolynomial(P);
  }

  public void print()
  {
    int n = P.length;
    for(int i=0; i<n; i++) System.out.println("c["+i+"]="+P[i]);
  }
  
  public Complex evaluate(Complex A)
  {
    int n = P.length;
    Complex val = new Complex(0.0);
    for(int i=n-1; i>=0; i--)
    {
      val = (A.multiply(val)).add(P[i]);
    }
    return val;
  }

  public boolean equals(ComplexPolynomial Q)
  {
     int n = P.length;
     int m = Q.P.length;
     if(m!=n) return false;
     boolean val = true;
     for(int i=0; i<n; i++) 
     {
       val=val && (P[i]==Q.P[i]);
     }
     return val;
  } // end equals

  public ComplexPolynomial add(ComplexPolynomial Q)
  {
     int n = P.length;
     int m = Q.P.length;
     int k = Math.max(n,m);
     Complex T[] = new Complex[k];
     for(int i=0; i<k; i++) 
     {
       if(i<n && i<m) 
         T[i]=Q.P[i].add(P[i]);
       else if(n>=i)
         T[i]= new Complex(Q.P[i]);
       else
         T[i]= new Complex(P[i]);
     }
     return new ComplexPolynomial(T);
  } // end add
  
  public ComplexPolynomial subtract(ComplexPolynomial Q)
  {
     int n = P.length;
     int m = Q.P.length;
     int k = Math.max(n,m);
     Complex T[] = new Complex[k];
     for(int i=0; i<k; i++) 
     {
       if(i<n && i<m) 
         T[i]=Q.P[i].subtract(P[i]);
       else if(n>=i)
         T[i]= new Complex(Q.P[i].negate());
       else
         T[i]= new Complex(P[i]);
     }
     return new ComplexPolynomial(T);
  } // end subtract

  public ComplexPolynomial multiply(Complex Q)
  {
     int n = P.length;
     Complex T[] = new Complex[n];
     for(int i=0; i<n; i++) 
     {
         T[i]=Q.multiply(P[i]);
     }
     return new ComplexPolynomial(T);
  } // end multiply

  public ComplexPolynomial multiply(ComplexPolynomial Q)
  {
     int n = P.length;
     int m = Q.P.length;
     int k=m+n-1;
     Complex X[] = new Complex[k];
     ComplexMatrix.zero(X);
     for(int i=0; i<n; i++) 
     {
       for(int j=0; j<m; j++)
       {
         X[i+j]=X[i+j].add(P[i].multiply(P[j]));
       }
     }
     return new ComplexPolynomial(X);
  } // end multiply

  public ComplexPolynomial divide(Complex Q)
  {
     int n = P.length;
     Complex T[] = new Complex[n];
     for(int i=0; i<n; i++) 
     {
         T[i]=P[i].divide(Q);
     }
     return new ComplexPolynomial(T);
  } // end divide


  public ComplexPolynomial divide(ComplexPolynomial Q) // P dividend, Q divisor
  {
     int n = P.length;
     int m = Q.P.length;
     while(m<0 && !(Q.P[m-1].equals(new Complex(0.0)))) m--; // highest coefficient of divisor non zero
     // if(Q.P[m-1]==0.0) throw divisionByZeroException; 
     // if(m<n) return new Polynomial(null); // no terms, only remainder
     Complex pquo[] = new Complex[n-m+1];
     Complex prem[] = new Complex[n];
     Complex trial;
     ComplexMatrix.copy(P, prem);  
     for(int i=n-m; i>=0; i--) 
     {
       trial=prem[i+m-1].divide(Q.P[m-1]);
       pquo[i]=trial;
       for(int j=0; j<m; j++)
       {
         prem[i+m-1-j] = prem[i+m-1-j].subtract(trial.multiply(Q.P[m-1-j]));
       }
     }
     return new ComplexPolynomial(pquo);
  } // end divide

  public ComplexPolynomial remainder(ComplexPolynomial Q) // P dividend, Q divisor
  {
     int n = P.length;
     int m = Q.P.length;
     while(m<0 && !Q.P[m-1].equals(new Complex(0.0))) m--; // highest coefficient of divisor non zero
     // if(Q.P[m-1]==0.0) throw divisionByZeroException; 
     // if(m<n) return new Polynomial(null); // no terms, only remainder
     Complex pquo[] = new Complex[n-m+1];
     Complex prem[] = new Complex[n+m-1];
     Complex rem[]  = new Complex[m];
     Complex trial;
     for(int i=0; i<n; i++) prem[i]=P[i]; // partial remainder 
     for(int i=n-m; i>=0; i--) 
     {
       trial=prem[i+m-1].divide(Q.P[m-1]);
       pquo[i]=trial;
       for(int j=0; j<m; j++)
       {
         prem[i+m-1-j] = prem[i+m-1-j].subtract(trial.multiply(Q.P[m-1-j]));
       }
     }
     for(int i=0; i<m; i++)
     {
       rem[i]=prem[i];
     }
     return new ComplexPolynomial(rem);
  } // end remainder

  public ComplexPolynomial derivitive()
  {
     int n = P.length;
     Complex X[] = new Complex[n-1];
     for(int i=0; i<n-1; i++)
     {
       X[i] = P[i+1].multiply(new Complex((double)(i+1)));
     }
     return new ComplexPolynomial(X);
  } // end derivitive

  public ComplexPolynomial integral(Complex Q) // the new c[0] value
  {
     int n = P.length;
     Complex X[] = new Complex[n+1];
     X[0] = Q;
     for(int i=1; i<n+1; i++)
     {
       X[i] = P[i-1].divide(new Complex((double)(i)));
     }
     return new ComplexPolynomial(X);
  } // end integral

  public Complex integral(Complex A, Complex B) // integral from A to B
  {
    Complex valA, valB;
    ComplexPolynomial Q = this.integral(new Complex(0.0));
    valA = Q.evaluate(A);
    valB = Q.evaluate(B);
    return valB.subtract(valA);
  } // end integral

} // end class ComplexPolynomial