/*program polynom
   polynom adds two polynomials and prints the result, the input polynomials
   reside in two text files, each line in a text file contains a singe 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);

  list L1, L2, L3;

  MAKENULL(&L1);
  MAKENULL(&L2);
  read_in("INDATP1",L1);
  print_out (L1);
  read_in("INDATP2",L2);
  print_out (L2);
  POLYADD (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);
    }
  }
}