/*program adtdemo
     adtdemo reads a file of single digit integers, one per line, and puts
     them into a list L. The list is then printed, purged of duplicate elements
     and printed again.

 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

      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 info;
  struct listype *next;
} *list;
typedef list position;


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

main()
{
  void ERROR(void);
  position FIRST(list L);
  position ENDLIS(list L);
  position NEXT(position p, list L);
  infotype RETRIEVE(position p, list L);
  void DELETE(position p, list L);
  void MAKENULL(list *L);
  void INSERT(infotype x, position p, list L);
  void print_out(list L);
  void purge(list L);
  int SAME(infotype a, infotype b);

  list L;
  position p;
  infotype v;
  FILE *fp;

  MAKENULL(&L);
  if((fp = fopen("INDATL", "r"))==NULL) ERROR();
  p= FIRST(L);
  do {
    fscanf(fp,"%d",&v);
    INSERT (v, p, L);
    p= NEXT(p, L);
  } while (!feof(fp));
  fclose(fp);
  print_out (L);
  purge(L);
  print_out (L);
  return 0;
}

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

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 RETRIEVE (position p, list L)
{
  return p->next->info;
}
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 INSERT (infotype x, position p, list L)
{
  position q;

  q= (position) malloc(sizeof(struct listype));
  q->info= x;
  q->next= p->next;
  p->next= q;
}
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");
  p= FIRST(L);
  while (p != ENDLIS(L)) {
    printf("%3d",RETRIEVE(p, L));
    p= NEXT(p, L);
  }
  printf("\n");
}

int SAME (infotype a, infotype b)
    /*SAME returns true if its arguments are identical, false otherwise*/
{
  return a==b;
}

void purge (list L)
    /*purge removes duplicate elements from list L*/
{
  position p, q;  /*p will be the "current" position in L, and q will move
                     ahead to find equal elements*/
  p= FIRST(L);
  while (p != ENDLIS(L)) {
    q= NEXT(p, L);
    while (q != ENDLIS(L)) {
      if (SAME (RETRIEVE(p, L), RETRIEVE(q, L))) DELETE(q, L);
      else q= NEXT(q, L);
    }
    p= NEXT(p, L);
  }
}