/*program polynom2
   polynom2 multiplies two polynomials and prints the result, the input
   polynomials reside in two text files, each line in a text file contains a
   single term (the coefficient, followed by a space, then the exponent).
   The polynomials can be any length.
   
 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

      LIST ADT (a LINKED LIST (with header cell) implementation)

NOTES:-    1. NO ERROR CHECKING is performed in this implementation.
              The caller has responsibility for ensuring that the
              position to be RETRIEVE'd or DELETED actually exists.

           2. The position operated on by RETRIEVE, INSERT and DELETE
              is the position FOLLOWING the one pointed to by the
              position pointer (ENDLIS returns a pointer to the last
              element, and FIRST to the header cell (NOT the first element)).*/


#include <stdio.h>
#include <stdlib.h>

typedef int infotype;
typedef struct listype {
  infotype coef;
  infotype expnt;
  struct listype *next;
} *list;
typedef list position;

/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/

main()
{
  void ERROR(void);
  position FIRST(list);
  position ENDLIS(list);
  position NEXT(position, list);
  infotype RETRIEVEC(position, list);
  infotype RETRIEVEE(position, list);
  void DELETE(position, list);
  void MAKENULL(list *);
  void INSERTP(position, infotype, infotype, list);
  void POLYADD(list, list, list *);
  void read_in(char [], list);
  void print_out(list);
  void CASTOFF(list);
  void REPLACE(list, list *);
  void POLYMULT(list, list, list *);

  list L1, L2, L3;

  MAKENULL(&L1);
  MAKENULL(&L2);
  read_in("INDATP1",L1);
  print_out (L1);
  read_in("INDATP2",L2);
  print_out (L2);
  POLYMULT (L1, L2, &L3);
  print_out (L3);
  return 0;
}

/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/

void read_in (char fnam[], list L)
   /*read_in reads the input text file and puts the elements in list L. One
     single digit integer per line is the expected file format.*/
{
  position p;
  infotype c, e;
  FILE *fp;

  if((fp = fopen(fnam, "r"))==NULL) ERROR();
  p= FIRST(L);
  do {
    fscanf(fp,"%d%d",&c,&e);
    INSERTP(p,c,e,L);
    p= NEXT(p,L);
  } while (!feof(fp));
  fclose(fp);
}

void print_out (list L)
   /*print_out prints list L, after a linefeed. The elements are expected to be
     single digit integers (a field width of 2 is used with no formatting) if
     this is not the case the output will look confused.*/
{
  position p;

  printf("\n\n");
  p= FIRST(L);
  while (p != ENDLIS(L)) {
    printf("%1dx%1d",RETRIEVEC(p, L),RETRIEVEE(p, L));
    p= NEXT(p, L);
    if (p != ENDLIS(L)) printf(" + ");
  }
}
void ERROR (void)
{
  exit (1);
}
position FIRST (list L)
{
  return L;
}
position ENDLIS (list L)
{
  position p;

  p= L;
  while (p->next != 0) p= p->next;
  return p;
}
position NEXT (position p, list L)
{
  return p->next;
}
infotype RETRIEVEC (position p, list L)
{
  return p->next->coef;
}
infotype RETRIEVEE (position p, list L)
{
  return p->next->expnt;
}
void DELETE (position p, list L)
{
  p->next= p->next->next;
}
void MAKENULL (list *L)
{
  *L= (list) malloc(sizeof(struct listype));
  (*L)->next= 0;
}
void INSERTP (position p, infotype c, infotype e, list L)
{
  position q;

  q= (position) malloc(sizeof(struct listype));
  q->coef= c;
  q->expnt= e;
  q->next= p->next;
  p->next= q;
}
void POLYADD (list L1, list L2, list *L3)
{
  infotype c1, c2, e1, e2;
  position p1, p2, p3;

  MAKENULL(L3);
  p1=FIRST(L1);
  p2=FIRST(L2);
  p3=FIRST(*L3);
  while ((p1 != ENDLIS(L1)) || (p2 != ENDLIS(L2))) {
    if (p2 != ENDLIS(L2)) {
      if (p1 != ENDLIS(L1)) {
        c2= RETRIEVEC (p2, L2);
        e2= RETRIEVEE (p2, L2);
        c1= RETRIEVEC (p1, L1);
        e1= RETRIEVEE (p1, L1);
        if (e1==e2) {
          INSERTP(p3, c1+c2, e1, *L3);
	  p1= NEXT(p1, L1);
	  p2= NEXT(p2, L2);
        }
        else {
          if (e1>e2) {
            INSERTP(p3, c1, e1, *L3);
            p1= NEXT(p1, L1);
          }
          else {
            INSERTP(p3, c2, e2, *L3);
            p2= NEXT(p2, L2);
          }
        }
        p3= NEXT(p3, *L3);
      }
      else {
        INSERTP(p3, RETRIEVEC(p2, L2), RETRIEVEE(p2, L2), *L3);
        p3= NEXT(p3, *L3);
        p2= NEXT(p2, L2);
      }
    }
    else {
      INSERTP(p3, RETRIEVEC(p1, L1), RETRIEVEE(p1, L1), *L3);
      p3= NEXT(p3, *L3);
      p1= NEXT(p1, L1);
    }
  }
}
void REPLACE (list L4, list *L5)
{
  position p, q, s;

  p= FIRST(L4);
  q= NEXT(p, L4);
  while (q != 0) {
    s= NEXT(q, L4);
    free(q);
    q= s;
  }
  p->next= NEXT(*L5, *L5);
  free(*L5);
}
void CASTOFF (list L)
{
  position p, q, s;

  p= FIRST(L);
  q= NEXT(p, L);
  while (q != 0) {
    s= NEXT(q, L);
    free(q);
    q= s;
  }
  p->next= 0;
}

void POLYMULT (list L1, list L2, list *L4)
{
  list L3, L5;
  infotype c1, e1;
  position p, q;

  MAKENULL(&L3);
  MAKENULL(L4);
  p= FIRST(L1);
  while (p != ENDLIS(L1)) {
    c1= RETRIEVEC(p, L1);
    e1= RETRIEVEE(p, L1);
    q= FIRST(L2);
    while (q != ENDLIS(L2)) {
      INSERTP (ENDLIS(L3), RETRIEVEC(q, L2) * c1,
                              RETRIEVEE(q, L2) + e1, L3);
      q= NEXT(q, L2);
    }
    POLYADD(L3, *L4, &L5);
    REPLACE(*L4, &L5);
    CASTOFF(L3);
    p= NEXT(p, L1);
  }
}