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


typedef struct cell {
  int val;
  struct cell *next;
} Cell;

typedef Cell *Set;

void afficher(Set s)
{
  printf("{");
  while (s != NULL) {
    printf("%d",s->val);
    s = s->next;
    if (s != NULL)
      printf(" ");
  }
  printf("}");
}

Set cons(int v,Set next)
{
  Set r;

  r = (Set)malloc(sizeof(Cell));
  if (r == NULL) {
    fprintf(stderr,"Plus de memoire !!!\n");
    exit(-1);
  }
  r->val = v;
  r->next = next;
  return r;
}


int dedans(int i,Set s)
{
  for (; s != NULL ; s = s->next)
    if (s->val == i)
      return 1;
  return 0;
}

Set ajouter(int i,Set s)
{
  Set p;

  for (p=s ; p != NULL ; p=p->next) {
    if (p->val == i)
      return s;
  }
  return cons(i,s);
}

Set reunion(Set p,Set q)
{
  for (;p != NULL; p = p->next) {
    q = ajouter(p->val,q);
  }
  return q;
}

Set inter(Set p,Set q)
{
  Set r=NULL;

  for (;p != NULL; p = p->next)
    if (dedans(p->val,q))
      r = cons(p->val,r);
  return r;
}


int inclus(Set p,Set q)
{
  for (; p!= NULL; p = p->next)
    if (!dedans(p->val,q))
        return 0;
  return 1;
}

int egal(Set p,Set q)
{
  return inclus(p,q) && inclus(q,p);
}

Set moins(Set s)
{
  Set r = NULL;
  Set p,q;

 
  for (p = s; p != NULL ; p = p->next) {
    for (q = p; q != NULL ; q = q-> next) {
      r = ajouter(abs(q->val - p->val),r);
    }
  }
  return r;
}

Set fixe(Set s)
{
  Set prev;
  int k=0;

  do {
    printf("s%d = ",k);
    afficher(s);
    printf("\n");

    prev=s;
    s = reunion(s,moins(s));
    k++;
  } while (!egal(prev,s));
  return s;
}


void main(void)
{
  Set s1 = ajouter(1,ajouter(2,ajouter(3,NULL)));
  Set s2 = ajouter(3,ajouter(4,ajouter(5,NULL)));
  Set r,s;

  afficher(s1);
  printf("\n");
  afficher(s2);
  printf("\n");

  afficher(reunion(s1,s2));
  printf("\n");
  afficher(inter(s1,s2));
  printf("\n");

  s = ajouter(9,ajouter(24,NULL));
  printf("Fermeture par soustraction de ");
  afficher(s);
  printf(":\n");
  r = fixe(s);
  printf("limite = ");
  afficher(r);
  printf("\n");
}