/*
 *
 * Operations sur les polynomes
 *
 */
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include "polynom.h"
#include "scalaires.h"
#include "exceptions.h"
#include "main.h"
#ifdef HAVE_CONFIG_H
#include "config.h"
#else
#define _(x) x
#endif

int smartprint = 1;

/* Les fonctions de base pour la construction et la destruction de polynomes */
polynome ply_constr(rationnel coef, int degre)
{				/* constructeur monome */
	polynome temp;

	if (!coef.num)
		return NULL;

	temp = (monome *) Emalloc(sizeof(monome));

	temp->coef = coef;
	temp->degre = degre;
	temp->suiv = NULL;

	return temp;
}

polynome ply_vide(void)
{				/* cree un polynome */

	return NULL;
}

void ply_destruct(polynome poly)
{				/* destructeur */
	if (poly) {
		ply_destruct(poly->suiv);
		free(poly);
	}
}


polynome ply_copy(polynome poly)
{				/* recopie */
	polynome result = NULL, temp = NULL, t;

	while (poly) {
		t = ply_constr(poly->coef, poly->degre);
		if (result) {
			temp->suiv = t;
			temp = t;
		} else {
			result = t;
			temp = t;
		}
		poly = poly->suiv;
	}
	return result;
}


/* Voici toutes les fonctions de manipulation de polynôme. La fonction d'addition est la plus importante
puisqu'elle nous sert à construire un polynome entier à partir de monomes. Sa structure est comparable à celle
de l'opération 'fusion' dans le cas du tri fusion */

polynome ply_addition(polynome poly1, polynome poly2)
{				/* addition de deux polynomes */
	polynome resultat = NULL, temp = NULL, t;
	rationnel newrat;
	int degre;

	while (poly1 && poly2) {
		if (poly1->degre > poly2->degre) {
			t = ply_constr(poly1->coef, poly1->degre);
			poly1 = poly1->suiv;
		} else if (poly1->degre < poly2->degre) {
			t = ply_constr(poly2->coef, poly2->degre);
			poly2 = poly2->suiv;
		} else {
			newrat = rat_addition(poly1->coef, poly2->coef);
			degre = poly1->degre;
			t = ply_constr(newrat, degre);
			poly1 = poly1->suiv;
			poly2 = poly2->suiv;
		}
		if (t) {
			if (resultat) {
				temp->suiv = t;
				temp = t;
			} else {
				resultat = t;
				temp = t;
			}
		}
	}

	while (poly1) {
		t = ply_constr(poly1->coef, poly1->degre);
		if (resultat) {
			temp->suiv = t;
			temp = t;
		} else {
			resultat = t;
			temp = t;
		}
		poly1 = poly1->suiv;
	}

	while (poly2) {
		t = ply_constr(poly2->coef, poly2->degre);
		if (resultat) {
			temp->suiv = t;
			temp = t;
		} else {
			resultat = t;
			temp = t;
		}
		poly2 = poly2->suiv;
	}

	return resultat;
}

/* Nous avons choisi de réécrire cette fonction entièrement, plutôt que de bricoler à partir de la fonction addition */
polynome ply_soustraction(polynome poly1, polynome poly2)
{				/* soustraction de deux polynomes */

	polynome resultat = NULL, temp = NULL, t;
	rationnel newrat;
	int degre;

	while (poly1 && poly2) {
		if (poly1->degre > poly2->degre) {
			t = ply_constr(poly1->coef, poly1->degre);
			poly1 = poly1->suiv;
		} else if (poly1->degre < poly2->degre) {
			t = ply_constr(rat_moinsunaire(poly2->coef), poly2->degre);
			poly2 = poly2->suiv;
		} else {
			newrat = rat_soustraction(poly1->coef, poly2->coef);
			degre = poly1->degre;
			t = ply_constr(newrat, degre);
			poly1 = poly1->suiv;
			poly2 = poly2->suiv;
		}
		if (t) {
			if (resultat) {
				temp->suiv = t;
				temp = t;
			} else {
				resultat = t;
				temp = t;
			}
		}
	}

	while (poly1) {
		t = ply_constr(poly1->coef, poly1->degre);
		if (resultat) {
			temp->suiv = t;
			temp = t;
		} else {
			resultat = t;
			temp = t;
		}
		poly1 = poly1->suiv;
	}

	while (poly2) {
		t = ply_constr(rat_moinsunaire(poly2->coef), poly2->degre);
		if (resultat) {
			temp->suiv = t;
			temp = t;
		} else {
			resultat = t;
			temp = t;
		}
		poly2 = poly2->suiv;
	}

	return resultat;
}

/* La fonction multiplication se base sur la fonction addition, suivant les mathématiques classiques */
polynome ply_multiplication(polynome poly1, polynome poly2)
{				/* multiplication de deux  polynomes */
	polynome temp = NULL, t, resultat = NULL, r, tempresult = NULL, poly2init;

	poly2init = poly2;
	while (poly1) {
		poly2 = poly2init;
		while (poly2) {
			t = ply_constr(rat_multiplication(poly1->coef, poly2->coef), poly1->degre + poly2->degre);
			if (t) {
				if (tempresult) {
					temp->suiv = t;
					temp = t;
				} else {
					tempresult = t;
					temp = t;
				}
			}
			poly2 = poly2->suiv;
		}
		poly1 = poly1->suiv;
		r = ply_addition(tempresult, resultat);
		ply_destruct(resultat);
		resultat = r;
		ply_destruct(tempresult);
		tempresult = NULL;
	}

	return resultat;
}


/* L'algorithme pour la division et le modulo est le même. Seul le return change. En effet, pour faire le calcul, nous
utilisons la méthode simple vue en cours de mathématiques, qui consiste à poser la division sur une feuille et à effectuer
une série de multiplications élémentaires et de soustractions. Nous obtenons donc le quotient ET le reste. */

polynome ply_division(polynome dividende, polynome diviseur)
{				/* division de deux  polynomes */
	polynome interdividende = ply_copy(dividende), interdiviseur = NULL, inter = NULL, reste = dividende, resultat = NULL, r = NULL;
	int b = 0;

#ifdef DEBUG
	printf("On divise %s", ply_affichage(dividende));
	printf("par %s\n", ply_affichage(diviseur));
	printf("interdividende degre = %u\n", interdividende->degre);
	printf("diviseur degre = %u\n", diviseur->degre);
#endif
	while ((interdividende) && (interdividende->degre >= diviseur->degre)) {
		b = 1;
		inter = ply_constr(rat_division(interdividende->coef, diviseur->coef), interdividende->degre - diviseur->degre);
#ifdef DEBUG
		printf("On trouve qu'il nous faut soustraire %s fois\n", ply_affichage(inter));
#endif
		r = ply_addition(resultat, inter);
#ifdef DEBUG
		printf("Resultat intermédiaire %s\n", ply_affichage(r));
#endif
		interdiviseur = ply_multiplication(diviseur, inter);
#ifdef DEBUG
		printf("On soustrait donc %s\n", ply_affichage(interdiviseur));
#endif
		reste = ply_soustraction(interdividende, interdiviseur);
#ifdef DEBUG
		printf("Reste intermédiaire %s\n", ply_affichage(reste));
#endif
		ply_destruct(resultat);
		ply_destruct(inter);
		ply_destruct(interdividende);
		ply_destruct(interdiviseur);
		resultat = r;
		interdividende = reste;
	}

	if (!b) ply_destruct(interdividende);
	
	return resultat;
}

polynome ply_modulo(polynome dividende, polynome diviseur)
{				/* reste de la division de deux  polynomes */
	polynome interdividende = ply_copy(dividende), interdiviseur = NULL, inter = NULL, reste = dividende, resultat = NULL, r = NULL;
	int b = 0;

#ifdef DEBUG
	printf("On divise %s", ply_affichage(dividende));
	printf("par %s\n", ply_affichage(diviseur));
	printf("interdividende degre = %u\n", interdividende->degre);
	printf("diviseur degre = %u\n", diviseur->degre);
#endif
	while ((interdividende) && (interdividende->degre >= diviseur->degre)) {
		b = 1;
		inter = ply_constr(rat_division(interdividende->coef, diviseur->coef), interdividende->degre - diviseur->degre);
#ifdef DEBUG
		printf("On trouve qu'il nous faut soustraire %s fois\n", ply_affichage(inter));
#endif
		r = ply_addition(resultat, inter);
#ifdef DEBUG
		printf("Resultat intermédiaire %s\n", ply_affichage(r));
#endif
		interdiviseur = ply_multiplication(diviseur, inter);
#ifdef DEBUG
		printf("On soustrait donc %s\n", ply_affichage(interdiviseur));
#endif
		reste = ply_soustraction(interdividende, interdiviseur);
#ifdef DEBUG
		printf("Reste intermédiaire %s\n", ply_affichage(reste));
#endif
		ply_destruct(resultat);
		ply_destruct(inter);
		ply_destruct(interdividende);
		ply_destruct(interdiviseur);
		resultat = r;
		interdividende = reste;
	}

	if (!b) ply_destruct(interdividende);

	return b ? reste : ply_copy(reste);
}

polynome ply_exposant(polynome poly, unsigned int exp)
{				/* exponentiation d'un polynome */
	int i;
	polynome result, temp;

	if (poly) {
		result = ply_constr(rat_constr(1, 1), 0);
		for (i = 0; i < exp; i++) {
			temp = ply_multiplication(result, poly);
			ply_destruct(result);
			result = temp;
		}
	} else {
		result = NULL;
	}
	return result;

}

rationnel ply_valuation(polynome poly, rationnel point)
{				/* évaluation d'un polynome en un point */
	rationnel result = rat_constr_zero();

	while (poly) {
		result = rat_addition(result, rat_multiplication(poly->coef, rat_pow(point, poly->degre)));
		poly = poly->suiv;
	}
	return result;
}

char *ply_affichage(polynome poly)
{				/* routine d'affichage d'un polynome */
	static char buf[BUFSIZ];
	char temp[BUFSIZ];
	char * rat;
	int count = 0;
	int first = 1;

	buf[0] = '\0';
	if (!poly) {
		sprintf(buf, "%s ", rat_to_string(rat_constr(0,1), 1));
	} else {
		while (poly) {
			if (poly->degre != 0) {
				if (smartprint) {
					rat = (rat_to_double(poly->coef) == 1) ? (first ? "" : "+ ") : rat_to_double(poly->coef) == -1 ? (first ? "-" : "- ") : rat_to_string(poly->coef, first);
					switch(poly->degre) {
					case 1:
						sprintf(temp, "%s%s ", rat, mute);
						break;
					case 2:
						sprintf(temp, "%s%s%c ", rat, mute, 178);
						break;
					case 3:
						sprintf(temp, "%s%s%c ", rat, mute, 179);
						break;
					default:
						sprintf(temp, "%s%s^%u ", rat, mute, poly->degre);
						break;
					}
				} else {
					sprintf(temp, "%s*%s^%u ", rat_to_string(poly->coef, first), mute, poly->degre);
				}
			} else {
				sprintf(temp, "%s ", rat_to_string(poly->coef, first));
			}
			count += strlen(temp);
			if (count < BUFSIZ)
				strcat(buf, temp);
			else
				exception(2, _("ply_affichage: strcat error, not enough space in buffer"));
			poly = poly->suiv;
			first = 0;
		}
	}	
	return buf;
}