/****************************************************
*  This program calculates R(x) = P(Q(x)),          *
*  P(x), Q(x) and R(x) being polynomials.           *
* ------------------------------------------------- *
* Ref.: "Mathématiques en Turbo-Pascal By M. Ducamp *
* and A. Reverchon (vol 2), Eyrolles, Paris, 1988"  *
* [BIBLI 05].                                       *
* ------------------------------------------------- *
* SAMPLE RUN:                                       *
*                                                   *
* SUBSTITUTION OF TWO POLYNOMIALS:                  *
*                                                   *
* P(x) = -5x2 +3                                    *
* Q(x) = 2x3 -x +5                                  *
*                                                   *
*                                                   *
* -20 X6 +20 X4 -100 X3 -5 X2 +50 X - 122           *
*                                                   *
*                                                   *
* SUBSTITUTION OF TWO POLYNOMIALS:                  *
*                                                   *
* P(x) = x4                                         *
* Q(x) = 2x2 -3                                     *
*                                                   *
*                                                   *
* +16 X8 -96 X6 +216 X4 -216 X2 + 81                *
*                                                   *
* ------------------------------------------------- *
* Functions used (of unit Polynoms):                *
*                                                   *
*  AddNumber(), EnterPolynom(), DisplayPolynom(),   *
*  MultNumber() and SetNumber().                    *
*                                                   *
*                      C++ version by J-P Moreau.   *
*                  (To be linked with polynoms.cpp).*
*                          (www.jpmoreau.fr)        *
****************************************************/
#include <stdio.h>
#include <malloc.h>
#include <math.h>

#include "polynoms.h"


ar_polynom  *P, *Q, *R;


// P(X) * Q(X) = R(X)
bool MultPolynom(ar_polynom *P, ar_polynom *Q, ar_polynom *R) {
  int i,j, n;
  ar_number u;
  ar_polynom *nr;
  nr = (ar_polynom *) calloc(1,sizeof(ar_polynom));
  //verify that P and Q are not void
  if (P->degree==0 && P->coeff[0].value==0) return FALSE;
  if (Q->degree==0 && Q->coeff[0].value==0) return FALSE;
  nr->degree=P->degree+Q->degree;
  if (nr->degree>AR_MAXPOL) return FALSE;  // R degree is too big
  for (n=0; n<=nr->degree; n++)  {
    if (!SetNumber(&nr->coeff[n],"0")) return FALSE;
    for (i=0; i<=P->degree; i++) {
      j=n-i;
      if (j>=0 && j<=Q->degree) {
        if (!MultNumber(P->coeff[i],Q->coeff[j],&u)) return FALSE;
        if (!AddNumber(nr->coeff[n],u,&nr->coeff[n])) return FALSE;
      }
    }
  }
  //copy nr in R
  R->degree=nr->degree;
  for (i=0; i<=nr->degree; i++)  R->coeff[i]=nr->coeff[i];
  free(nr);
  return TRUE;
}

// a P(X) + b Q(X) = R(X)
bool CombiPolynom(ar_polynom *P, ar_polynom *Q, ar_number a, ar_number b, ar_polynom *R) {
  int i; ar_number u,v;
  if (Q->degree > P->degree)  R->degree=Q->degree;
  else R->degree=P->degree;
  if (R->degree > AR_MAXPOL) return FALSE;   // degree of R is too big
  for (i=0; i<=R->degree; i++) {
    if (!SetNumber(&u,"0")) return FALSE;
    if (!SetNumber(&v,"0")) return FALSE;
    if (i<=P->degree)
      if (!MultNumber(a,P->coeff[i], &u)) return FALSE;
    if (i<=Q->degree)
      if (!MultNumber(b,Q->coeff[i], &v)) return FALSE;
	  if (!AddNumber(u,v,&R->coeff[i])) return FALSE;
  }
  while (R->degree>0 && fabs(R->coeff[R->degree].value)<AR_SMALL)
    R->degree--;
  return TRUE;
}

// R(X) = P(Q(X))
bool SubstPolynom(ar_polynom *P, ar_polynom *Q, ar_polynom *R) {
  int i;
  ar_number  a;
  ar_polynom *v;
  v = (ar_polynom *) calloc(1,sizeof(ar_polynom));
  R->degree=P->degree * Q->degree;
  if (R->degree>AR_MAXPOL) return FALSE;     //R degree is too big
  R->coeff[0]=P->coeff[0]; v->degree=0;
  if (!SetNumber(&v->coeff[0],"1")) return FALSE;;
  if (!SetNumber(&a,"1")) return FALSE;
  for (i=1; i<=P->degree; i++) {
    if (!MultPolynom(Q,v,v)) return FALSE;
    if (!CombiPolynom(R,v,a,P->coeff[i],R)) return FALSE;
  }
  free(v);
  return TRUE;
}


void main() {
  //dynamic memory allocation of polynomials
  P = (ar_polynom *) calloc(1,sizeof(ar_polynom));
  Q = (ar_polynom *) calloc(1,sizeof(ar_polynom));
  R = (ar_polynom *) calloc(1,sizeof(ar_polynom));
  printf("\n SUBSTITUTION OF TWO POLYNOMIALS:\n\n");
  if (!EnterPolynom(" P(X) = ", P)) return;
  if (!EnterPolynom(" Q(X) = ", Q)) return;
  printf("\n");
  if (SubstPolynom(P,Q,R))
    DisplayPolynom(R);
  else
    printf(" Error in polynomial substitution.");
  printf("\n\n");
  free(P); free(Q); free(R);
}

//end of file substpol.cpp