#include <stdlib.h>
#include "poly.h"

typedef struct term {
  int coef;
  int exp;
} PolyTerm;

/* 
 * Functions which operate on PolyTerms.  
 */

static PolyTerm *
term_create(int c, int e)
{
  PolyTerm *result = (PolyTerm *) malloc(sizeof(PolyTerm));
  result->coef = c;
  result->exp = e;

  return result;
}


/*
 * Written to be a list action.
 */
static void
term_destroy(void *term, void *dummy)
{
  free((PolyTerm *) term);
}


/* Relies on the caller to print the sign correctly */
static void
term_write(PolyTerm *term, FILE *f)
{
  int coef = (term->coef < 0) ? -term->coef : term->coef;

  if (coef == 1)
    if (term->exp == 0)
      fprintf(f, "1");
    else if (term->exp == 1)
      fprintf(f, "x");
    else
      fprintf(f, "x^%d", term->exp);
  else {
    fprintf(f, "%d", coef);
    if (term->exp == 1)
      fprintf(f, "x");
    else if (term->exp > 1)
      fprintf(f, "x^%d", term->exp);
  }
}


/*
 * Polynomial Functions
 */

void
poly_initialize(Polynomial *p)
{
  list_initialize(p);
}


void 
poly_read(Polynomial *p, FILE *f)
{
  int c, e;

  fscanf(f, "%d %d", &c, &e);
  while (c != 0) {
    list_append(p, (void *) term_create(c, e));
    fscanf(f, "%d %d", &c, &e);
  }
}


void 
poly_write(Polynomial *p, FILE *f)
{
  ListCursor ptr;
  PolyTerm *term;

  list_get_cursor(p, &ptr);
  if (cursor_at_end(ptr))
    return;

  term = (PolyTerm *) cursor_data(ptr);
  if (term->coef > 0)
    term_write(term, f);
  else {
    fprintf(f, "-");
    term_write(term, f);
  }
  term = cursor_advance(&ptr);

  while (!cursor_at_end(ptr)) {

    if (term->coef < 0) 
      fprintf(f, " - ");
    else
      fprintf(f, " + ");
    term_write(term, f);

    term = cursor_advance(&ptr);
  }
}


void 
poly_copy(Polynomial *src, Polynomial *dest)
{
  ListCursor ptr;
  PolyTerm *term;

  if (!list_is_empty(dest))
    poly_destroy(dest);

  if (list_is_empty(src))
    return;

  list_get_cursor(src, &ptr);
  term = (PolyTerm *) cursor_data(ptr);
  while (!cursor_at_end(ptr)) {
    list_append(dest, term_create(term->coef, term->exp));
    term = (PolyTerm *) cursor_advance(&ptr);
  }
}


void 
poly_add(Polynomial *poly1, Polynomial *poly2, Polynomial *result)
{
  ListCursor ptr1, ptr2;
  PolyTerm *p1, *p2;
  
  if (!list_is_empty(result))
    poly_destroy(result);

  list_get_cursor(poly1, &ptr1);
  list_get_cursor(poly2, &ptr2);

  while (!cursor_at_end(ptr1) && !cursor_at_end(ptr2)) {
    p1 = (PolyTerm *) cursor_data(ptr1);
    p2 = (PolyTerm *) cursor_data(ptr2);  

    if (p1->exp < p2->exp) {
      list_append(result, term_create(p1->coef, p1->exp));
      cursor_advance(&ptr1);
    }
    else if (p2->exp < p1->exp) {
      list_append(result, term_create(p2->coef, p2->exp));
      cursor_advance(&ptr2);
    }
    else if (p1->exp == p2->exp) {
      if ((p1->coef + p2->coef) != 0)
	list_append(result, term_create(p1->coef + p2->coef, p1->exp));
      cursor_advance(&ptr1);
      cursor_advance(&ptr2);
    }
  }

  while (!cursor_at_end(ptr1)) {
    p1 = (PolyTerm *) cursor_data(ptr1);
    list_append(result, term_create(p1->coef, p1->exp));
    cursor_advance(&ptr1);
  }
    
  while (!cursor_at_end(ptr2)) {
    p2 = (PolyTerm *) cursor_data(ptr2);
    list_append(result, term_create(p2->coef, p2->exp));
    cursor_advance(&ptr2);
  }
}


static void
poly_split(Polynomial *p1, Polynomial *half1, Polynomial *half2)
{
  ListCursor ptr;
  PolyTerm *term;

  list_get_cursor(p1, &ptr);
  term = (PolyTerm *) cursor_data(ptr);

  while (!cursor_at_end(ptr)) {
    list_append(half1, term);
    term = (PolyTerm *) cursor_advance(&ptr);
    if (!cursor_at_end(ptr)) {
      list_append(half2, term);
      term = (PolyTerm *) cursor_advance(&ptr);
    }
  }
}


static void
poly_mergesort(Polynomial *p, Polynomial *result)
{
  Polynomial half1, half2, half1_sorted, half2_sorted;
  ListCursor ptr;
  PolyTerm *term;

  if (list_is_empty(p))
    return;
  else if (p->head == p->tail) {
    list_get_cursor(p, &ptr);
    term = (PolyTerm *) cursor_data(ptr);
    list_append(result, term_create(term->coef, term->exp));
    return;
  }

  list_initialize(&half1);
  list_initialize(&half2);
  list_initialize(&half1_sorted);
  list_initialize(&half2_sorted);

  poly_split(p, &half1, &half2);
  poly_mergesort(&half1, &half1_sorted);
  poly_mergesort(&half2, &half2_sorted);
  poly_add(&half1_sorted, &half2_sorted, result);
  
  poly_destroy(&half1_sorted);
  poly_destroy(&half2_sorted);
  list_destroy(&half1);
  list_destroy(&half2);
}


void 
poly_multiply(Polynomial *poly1, Polynomial *poly2, Polynomial *result)
{
  ListCursor ptr1, ptr2;
  PolyTerm *t1, *t2;
  Polynomial all_terms;

  poly_initialize(&all_terms);
  list_get_cursor(poly1, &ptr1);

  while (!cursor_at_end(ptr1)) {
    t1 = (PolyTerm *) cursor_data(ptr1);
    list_get_cursor(poly2, &ptr2);
    while (!cursor_at_end(ptr2)) {
      t2 = (PolyTerm *) cursor_data(ptr2);
      list_append(&all_terms, term_create(t1->coef * t2->coef, 
					  t1->exp + t2->exp));
      cursor_advance(&ptr2);
    }
    cursor_advance(&ptr1);
  }
   
  poly_mergesort(&all_terms, result);
}


void 
poly_destroy(Polynomial *p)
{
  list_do(p, term_destroy, NULL); 
  list_destroy(p);
}