// Clase para manipular polinomios
// Antonio Carrillo Ledesma


// Se define al polinomio por sus coeficientes, es decir
//    A0 + A1x^1 + ...+Anx^n
// Quedando el arreglo como
//    A0, A1, ... An

public class Poly {

   // Coeficientes del polinomio
   private double []C;
   // Guarda la dimension del arreglo de coeficientes
   private int Dim;


   // Constructor de la clase
   public Poly(int n) {
      int i;
      C = new double [n];
      for (i = 0; i < n; i++) C[i] = 0.0;
      Dim = n;
   }

   // Constructor de la clase
   public Poly(double []coef) {
      int i, n = coef.length;
      C = new double [n];
      for (i = 0; i < n; i++) C[i] = coef[i];
      Dim = n;
   }

   // Constructor de la clase
   public Poly(Poly a) {
      int i, n = a.dimension();
      C = new double [n];
      for (i = 0; i < n; i++) C[i] = a.coeficiente(i);
      Dim = n;
   }

   // Retorna los coeficientes del polinomio
   double coeficiente(int i) {
      if (i < Dim) return C[i];
      return 0.0;
   }

   // Retorna la dimension del arreglo de coeficientes
   int dimension() {
      return Dim;
   }

   // Devuelve el grado del polinomio contenido en el arreglo
   public int grado(double []a) {
      int i, g;
      g = a.length - 1 ;
      for (i = (a.length - 1); i > 0; i--) {
         if (a[i] == 0.0) g--;
         else return g;
      }
      return g;
   }

   // Devuelve el grado del polinomio
   public int grado(Poly a) {
      int i, g;
      g = a.C.length - 1;
      for (i = (a.C.length - 1); i > 0; i--) {
         if (a.coeficiente(i) == 0.0) g--;
         else return g;
      }
      return g;
   }


   // Visualiza el polinomio
   public void visualiza() {
      int i;

      for (i = 0; i < Dim; i++) {
         if (C[i] != 0.0) {
            System.out.print(" + ");
            System.out.print(C[i]);
            if (i == 0) continue;
            System.out.print("X^");
            System.out.print(i);
         }
      }
      System.out.println(" ");
   }


   // Suma el polinomio A y B
   public void Suma(Poly a, Poly b) {
      int i, n, n1 = a.Dim, n2 = b.Dim;

      if (n1 > n2) {
         for (i = 0; i < n2; i++)  C[i] = a.coeficiente(i) + b.coeficiente(i);
         for (i = n2; i < n1; i++) C[i] = a.coeficiente(i);
         Dim = n1;
      } else {
         for (i = 0; i < n1; i++)  C[i] = a.coeficiente(i) + b.coeficiente(i);
         for (i = n1; i < n2; i++) C[i] = b.coeficiente(i);
         Dim = n2;
      }
   }


   // Suma el contenido al del polinomio B
   public void Suma(Poly b) {
      int i, n, n1 = Dim, n2 = b.Dim;

      if (n1 > n2) {
         double []d = new double [n1];
         for (i = 0; i < n2; i++)  d[i] = C[i] + b.coeficiente(i);
         for (i = n2; i < n1; i++) d[i] = C[i];
         Dim = n1;
         C = new double [Dim];
         for (i = 0; i < Dim; i++) C[i] = d[i];
      } else {
         double []d = new double [n2];
         for (i = 0; i < n1; i++)  d[i] = C[i] + b.coeficiente(i);
         for (i = n1; i < n2; i++) d[i] = b.coeficiente(i);
         Dim = n2;
         C = new double [Dim];
         for (i = 0; i < Dim; i++) C[i] = d[i];
      }
   }


   // Algoritmo de Euclides para polinomios
   public void aep(double []f, double []g, double q[], double []r) {
      int i, j, gg, gr;

      // Inicializo r y q
      for (i = 0; i < f.length; i++) {
         r[i] = f[i];
         q[i] = 0.0;
      }
      // Algoritmo de Euclides para polinomios
      gg = grado(g);
      gr = grado(r);
      while (gr >= gg) {
         q[gr - gg] = r[gr] / g[gg];
         for (j = 0; j <= gg; j++) r[gr - j] -= (g[gg - j] * q[gr - gg]);
         gg = grado(g);
         gr = grado(r);
      }
   }



   // Funcion Principal ....
   public static void main(String[] args) {
      int i, j;
      double A[] = {3.0, -4.0, 1.5};
      double f[] = {1.0, 1.0, 2.0};
      double g[] = {1.0, 3.0};
      double q[] = new double [10];
      double r[] = new double [10];

      Poly a = new Poly(A);
      a.aep(f, g, q, r);
      System.out.println("Dividendo:");
      Poly F = new Poly(f);
      F.visualiza();
      System.out.println("Divisor:");
      Poly G = new Poly(g);
      G.visualiza();

      System.out.println("q:");
      Poly Q = new Poly(q);
      Q.visualiza();
      System.out.println("r:");
      Poly R = new Poly(r);
      R.visualiza();
   }
}