/*
 * poli.c
 */

#include <stdlib.h>
#include <stdio.h>
#include <malloc.h>
#include "poli.h"

/* Função auxiliar */
ap_poli cria_no(float coef, int expo, ap_poli prox) {
  if (coef != 0) {
    ap_poli n = (ap_poli) malloc (sizeof (struct termo));
    n->coef = coef;
    n->expo = expo;
    n->prox = prox;
    return n;
  } else
    return prox;
}

/* 3x^2 - x + 5 

ap_no q = cria_no(3,2,cria_no(-1,1,cria_no(5,0,NULL)));

*/

/* Cria um polinomio formado por um único termo de coeficiente coef
   e expoente expo. */
ap_poli cria_termo(float coef, int expo) {
  return cria_no(coef, expo, NULL);
}


/* Soma os polinômios apontados por p e q, sem destruí-los e retorna
   o resultado. */
ap_poli soma(ap_poli p, ap_poli q) {
  if (p == NULL)
    return copia(q);
  if (q == NULL)
    return copia(p);
  if (p->expo > q->expo)
    return cria_no(p->coef, p->expo, soma(p->prox, q));
  if (p->expo == q->expo)  /* cria_no tem um teste != 0 */
    return cria_no(p->coef+q->coef, p->expo, soma(p->prox, q->prox));
  return cria_no(q->coef, q->expo, soma(p, q->prox));
}

/* Multiplica o polinômio p por um escalar, sem destruí-lo, e retorna o
   polinômio resultante. */
ap_poli mult_escalar(ap_poli p, float escalar) {
  if (p == NULL || escalar == 0)
    return NULL;
  return cria_no(p->coef * escalar, 
		 p->expo,
		 mult_escalar(p->prox, escalar));
}

/* Subtrai q de p e retorna o polinômio resultante. As funções 
   multEscalar e soma podem ser utilizadas para fazer a subtração. */
ap_poli subtrai(ap_poli p, ap_poli q) {
  ap_poli nq = mult_escalar(q, -1);
  ap_poli r = soma(p,nq);
  libera(nq);
  return r;
}

ap_poli mult_termo(ap_poli p, float coef, int expo) {
  if (p == NULL)
    return NULL;
  return cria_no(p->coef * coef, 
		 p->expo + expo,
		 mult_termo(p->prox, coef, expo));
}

/* Multiplica os polinômios apontados por p e q, sem destruí-los, e 
   retorna o resultado. Os nós intermediários, criados durante o
   processo, devem ser destruídos. */
ap_poli multiplica(ap_poli p, ap_poli q) {
  if (p == NULL || q == NULL)
    return NULL;
  ap_poli m1 = mult_termo(p, q->coef, q->expo);
  ap_poli m2 = multiplica(p, q->prox);
  ap_poli r = soma (m1, m2);
  libera(m1);
  libera(m2);
  return r;

}
 
/* Retorna uma cópia do polinômio p. A função multEscalar pode
   ser utilizada para fazer a cópia. */
ap_poli copia(ap_poli p) {
  if (p == NULL)
    return NULL;
  return cria_no(p->coef, p->expo, copia(p->prox));
}

/* Desaloca a memória correspondente ao polinômio p. */
void libera(ap_poli p) {
  if (p != NULL) {
    libera(p->prox);
    free(p);
  }
}

/* Escreve o polinômio apontado por p */
void escreve(ap_poli p) {

  if (p == NULL)
    printf("0");
  else { 
    /* Escreve o primeiro termo */
    printf ("%.1f", p->coef);
    if (p->expo > 1)
      printf ("x^%d", p->expo);
    else if (p->expo == 1)
      printf ("x");
    p = p->prox;
    /* Escreve os outros termos */
    while (p != NULL) {
      if (p->coef >= 0) 
	printf (" + %.1f", p->coef);
      else
	printf (" - %.1f", - p->coef);
      if (p->expo > 1)
	printf ("x^%d", p->expo);
      else if (p->expo == 1)
	printf ("x");
      p = p->prox;
    }
  }
  printf ("\n");
}


void teste() {
  /* Cria 3x^2 + 5x - 1 */
  ap_poli p = cria_no (3, 2, cria_no(5, 1, cria_no(-1, 0, NULL)));
  escreve(p);
  /* Cria 4x^3 - 5x */
  ap_poli q = cria_no (4, 3, cria_no(-5, 1, NULL));
  escreve(q); 

 ap_poli r = multiplica(p, q);
 escreve(r); 

  libera(p);
  libera(q);
  libera(r);
}

int main() {
 struct mallinfo info;
 int mall_minblks;
  
  /* Utiliza o sistema de memória dinâmica uma vez, alocando e
     desalocando um nó, e verifica o número mínimo de blocos na
     memória. */
  ap_poli p = (ap_poli) malloc (sizeof (struct termo));
  free(p);
  info = mallinfo();
  mall_minblks = info.uordblks;

  teste();

  /* Verifica a utilização de memória dinâmica */
  {
    struct mallinfo info;
    info = mallinfo();
    if (info.uordblks > mall_minblks)
      printf("Memória sobrando...\n");
  }
  return 0;

}