/* Solution proposee par Ning Hu, legerement modifiee */

#include <stdio.h>
#include "polynome.h"

//structs
//-----------------------------
//un structure pour un point
//-----------------------------
struct point
{
  float  x;
  float  y;
};
typedef struct point point;


//functions
//----------
//prototypes
//----------
poly*  aitken(node*,int,int);               //algorithm de aitken
poly*  aitken_formula(poly*,poly*,int,int); //appliquer l'algorithm d'aitken sur polynomes

//global variables
//-----------------------------
//Un tableau des points
//-----------------------------
point *ptr_points;

main()
{
  poly* ptr_reponse_poly;
  node* ptr_list_initial_polys;
  poly* ptr_tmp_poly;
  int   i_nombre_des_points;
  int   i_loop;

  //action
  //initialization
  ptr_list_initial_polys = NULL;

  //1. saisir les points
  printf("Combien des points a t il? ");
  scanf("%i",&i_nombre_des_points);

  //cree le tableau
  ptr_points = (point*)malloc(sizeof(point)*i_nombre_des_points);

  for(i_loop = 0; i_loop < i_nombre_des_points; i_loop++)
  {
    printf("pour la point %i, si vous plait,\n",i_loop);

    printf("entre un valeur de X:");
    scanf("%f",&(ptr_points[i_loop].x));

    printf("entre un valeur de Y:");
    scanf("%f",&(ptr_points[i_loop].y));
  }

  //2. cree les polynomes initiaux
  for(i_loop = 0; i_loop < i_nombre_des_points; i_loop++)
  {
    ptr_tmp_poly = (poly*)malloc(sizeof(poly));
    ptr_tmp_poly->degree = 0;
    ptr_tmp_poly->coefficient = (float*)malloc(sizeof(float));
    ptr_tmp_poly->coefficient[0] = ptr_points[i_loop].y;

    //ajouter polynome a liste
    ptr_list_initial_polys = ajouter_a_list(ptr_list_initial_polys,ptr_tmp_poly);
  }

  //3. calculer le polynome
  ptr_reponse_poly = aitken(ptr_list_initial_polys,
			     i_nombre_des_points,
			     0);                       //degree commence a zero

  //4. afficher la reponse
  montre(ptr_reponse_poly);
}

//---------------------------------------------------
//desc   = this method takes a list of polynomials (of degree 0
//         initially)
//         and outputs one polynomial curve of degree-1
//input  = list of polynomials,size of list,degree of polynomials
//output = polynomial representing the fitted curve
//---------------------------------------------------
poly*  aitken(node* ptr_polys,int i_size,int i_degree)
{
  //variables
  node* ptr_nouveau_polys;
  node  *ptr_tmp_poly,*ptr_tmp2_poly;
  int   i_loop_points;
  poly* ptr_poly1;
  poly* ptr_poly2;
  poly* ptr_poly3;

  //action
  //0.initialization
  ptr_nouveau_polys = NULL;


  //1.base case return if size of list = 1
  if(i_size == 1)
  {
    return ptr_polys->poly;
  }
  
  //2.calculate new list of polynomials
  for(ptr_tmp_poly=ptr_polys, i_loop_points = 0;
      ptr_tmp_poly != NULL;
      ptr_tmp_poly=ptr_tmp_poly->next, i_loop_points++)
  {
    ptr_tmp2_poly = ptr_tmp_poly->next;

    //si on arrive a la fin de la list original
    if(ptr_tmp2_poly == NULL)
    {
      break;
    } 

    //saisir les deux polynomes
    ptr_poly1 = ptr_tmp_poly->poly;
    ptr_poly2 = ptr_tmp2_poly->poly;

    ptr_poly3 = aitken_formula(ptr_poly1, 
			       ptr_poly2,
			       i_loop_points,  //# polynomes
			       i_degree+1);    //degree of new polynome

    //ajouter le nouveau polynome
    ptr_nouveau_polys = ajouter_a_list(ptr_nouveau_polys,ptr_poly3);
  }

  //3.free obsolete old list of polynomials
  for(ptr_tmp_poly=ptr_polys; 
      ptr_tmp_poly != NULL;
      ptr_tmp2_poly = ptr_tmp_poly,
      ptr_tmp_poly = ptr_tmp_poly->next,
      free(ptr_tmp2_poly->poly),
      free(ptr_tmp2_poly));

  //recursive call to itself to do next iteration
  return aitken(ptr_nouveau_polys, i_size-1 , i_degree+1 );
}

   
//---------------------------------------------------
//desc   = this method takes in two polynomials, and
//         two ints( used in aitkens algorithm) to 
//         access the initial points and calculate
//         the final polynomial from those two.  This
//         is in fact a helper function and the engine
//         behind the recursive aitken algorithm
//input  = two polynomials and two ints to access the
//         points global table
//output = poly structure representing the result
//---------------------------------------------------        
poly*  aitken_formula(poly* ptr_poly1,poly* ptr_poly2,int i_pt,int i_degree)
{
  //variables
  float T_i_r,T_i;
  poly  *ptr_result_poly,*ptr_temp_poly;
  poly  *ptr_final_result1,*ptr_final_result2;

  //1. chercher la valeur de T_i_r et T_i
  T_i_r = (ptr_points[i_pt+i_degree].x);
  T_i   = (ptr_points[i_pt].x);

  //2. commencer a calculer le resultat.
  ptr_result_poly = copy(ptr_poly1);

  ptr_temp_poly   = (poly*)malloc(sizeof(poly));
  ptr_temp_poly->coefficient = (float*)malloc(sizeof(float)*2);
  ptr_temp_poly->coefficient[0] = T_i_r;
  ptr_temp_poly->coefficient[1] = -1;   
  ptr_temp_poly->degree = 1;

  ptr_final_result1 = multiplier(ptr_temp_poly,ptr_result_poly);
  
  //2b calculate second part of polynomial
  destroy(ptr_temp_poly);
  destroy(ptr_result_poly);
  
  ptr_result_poly = copy(ptr_poly2);

  ptr_temp_poly   = (poly*)malloc(sizeof(poly));
  ptr_temp_poly->coefficient = (float*)malloc(sizeof(float)*2);
  ptr_temp_poly->coefficient[0] = -1*T_i;
  ptr_temp_poly->coefficient[1] = 1;    
  ptr_temp_poly->degree = 1;

  ptr_final_result2 = multiplier(ptr_temp_poly,ptr_result_poly);

  //2c last calculation add two polynomials together and multiply by a const
  destroy(ptr_result_poly);
  destroy(ptr_temp_poly);

  ptr_result_poly = ajouter(ptr_final_result1,ptr_final_result2);

  ptr_result_poly = multiplier_const(ptr_result_poly,1/(T_i_r - T_i));

  //2.f clean up
  destroy(ptr_final_result1);
  destroy(ptr_final_result2);

  //3. return result
  return ptr_result_poly;
}