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

typedef char Value;

typedef struct Element_ Element;
typedef Element* List;

struct Element_
{
  Value x;
  List next;

  // avec "week ptr":
  // int do_not_free_next; // 0 = normal, 1 = "weak" (== next is backward)

  // avec indicateur de boucle
  int visited;
};

/* avec pointeur sur fin :

typedef struct {
  Element* head;
  Element* tail;
} List;

MAIS ATTENTION !  next N'est PLUS de type List !
(différence entre « Suivant » (next) et « Liste »)
*/


// ======================================================================
void push_front(List* l, Value val)
{
  if (l != NULL) {
    // new element
    Element* const new = calloc(1, sizeof(Element));
    if (new != NULL) {
      new->x = val;
      new->visited = 0; // ne pas oublier d'initialiser les marqueurs de visite
      new->next = *l;

      // add it front
      *l = new;
    }
  }
}

// ======================================================================
// avec "weak ptr" : passer un argument suppl pour dire si free ou non ce ptr
void set_next(Element* el, const List suite) {
  if (el != NULL) {
    el->next = suite;
  }
}

// ======================================================================
void affiche(const List* l, int depth)
{
  if (l != NULL) {
    for (Element* el = *l; (el != NULL) && (depth --> 0); el = el->next) {
      putchar(el->x);
    }
    putchar('\n');
  }
}

// ======================================================================
/* utile pour remettre les « visited » à 0 après avoir utilisé un algorithme  *
 * qui les changes (p.ex. comparaison de nombres)                             */
void reset_visit(List* l) {
  if (l != NULL) {
    for (Element* el = *l; (el != NULL) && el->visited; el = el->next) {
      el->visited = 0;
    }
  }
}

// ======================================================================
void gc(List* l)
{
  if (l != NULL) {
    // 1. casse la boucle (on pourrait aussi faire un algo tout récursif, mais je n'ai pas voulu (stack overflow)
    Element* prev = NULL;
    for (Element* el = *l; (el != NULL) && !el->visited; el = el->next) {
      el->visited = 1;
      prev = el;
    }
    if (prev != NULL) prev->next = NULL;

    // 2. no loop anymore, free all
    Element* el = *l;
    while (el != NULL) {
      Element* next = el->next;
      printf("free(%c)\n", el->x);
      free(el);
      el = next;
    }
  }
}

// ======================================================================
int main(void)
{
  // 0.33...
  List un_tiers = NULL;
  push_front(&un_tiers, '3');
  set_next(un_tiers, un_tiers); // infinite loop
  push_front(&un_tiers, '0');

  List un_demi = NULL;
  push_front(&un_demi, '5');
  push_front(&un_demi, '0');

  // 0.0151515...
  List un_soixantesixieme = NULL;
  push_front(&un_soixantesixieme, '5');
  push_front(&un_soixantesixieme, '1');
  set_next(un_soixantesixieme->next, un_soixantesixieme); // infinite loop
  push_front(&un_soixantesixieme, '0');
  push_front(&un_soixantesixieme, '0');

  affiche(&un_tiers, 10);
  affiche(&un_demi,  10);
  affiche(&un_soixantesixieme, 10);

  gc(&un_soixantesixieme);
  gc(&un_demi);
  gc(&un_tiers);
  
  return 0;
}