/* -*-coding: utf-8; -*- */
// le commentaire ci-dessus valide le codage de caractère utf-8 (défaut sous linux-ubuntu)
// ce qui permet d'utiliser les caractères accentués. ATTENTION : ne fonctionne
// probablement pas par défaut sous d'autres systèmes d'exploitation. 

// Exemples de structures de données chaînées : pile et liste d'entiers triés
// Attention, les allocations ne sont pas vérifiées...

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

// maillon de stockage pour un entier
typedef struct maillon {
  int val; // l'entier à stocker
  struct maillon *suiv; // pointeur sur l'élément suivant de la liste
} MAILLON; // nouveau nom de type

// prototypes des fonctions auxilliaires
int pile_vide(MAILLON *p);
void empiler(MAILLON**pp, int val);
int depiler(MAILLON**pp);
void exemple_pile(void);
void exemple_liste_triee(void);
void affiche_liste(MAILLON *liste);
void detruire_liste(MAILLON **pliste);
void inserer_ordre(MAILLON **pliste, int val);

// ##########
int main(void) {

  exemple_pile();
  exemple_liste_triee();

  return 0;
}

// ##########
void exemple_pile(void) {
  MAILLON *pile=0; // toujours initialiser à 0
  int val;

  // mémoriser des entiers dans la pile
  printf("Saisir des entiers, terminer la saisie par -1\n");
  while (1) { // boucle infinie => on sortira par break
    scanf("%d", &val);
    if (val == -1)
      break;
    empiler(&pile,val); // pile par adresse car elle va changer
  } // end while

  // rappeler les entiers de la pile
  printf("\nVoici vos entiers (en ordre inverse) :\n");
  while (! pile_vide(pile)) { // tant qu'il en reste
    val = depiler(&pile); // pile par adresse car elle va changer
    printf("%d\t", val);
  }
  printf("\n");
} // end exemple_pile

// ##########
int pile_vide(MAILLON *p) {
  return p == 0; // convention pour liste vide
} // end pile_vide

// ##########
void empiler(MAILLON**pp, int val) {
  MAILLON *tmp;
  // créer le nouveau maillon
  tmp = (MAILLON *) malloc(sizeof(MAILLON));
  // le remplir
  tmp->val=val;
  // mettre à jour le chaînage 
  tmp->suiv=*pp;  
  *pp=tmp;
} // end empiler

// ##########
int depiler(MAILLON**pp) {
  // ATTENTION : ne teste pas si la pile est vide
  // c'est à l'appelant à le faire
  MAILLON *tmp=*pp;
  int val = tmp->val; 
  *pp=tmp->suiv; // décrocher le 1er maillon
  free(tmp); // libérer la mémoire
  return val; // renvoyer l'ancien sommet de pile
} // end depiler

// ##########
void exemple_liste_triee(void) {
  MAILLON *liste=0; // toujours initialiser à 0
  int val;

  // mémoriser des entiers dans la liste
  printf("Saisir des entiers, terminer la saisie par -1\n");
  while (1) { // boucle infinie => on sortira par break
    scanf("%d", &val);
    if (val == -1)
      break;
    inserer_ordre(&liste,val); // file par adresse car elle va changer
  } // end while

  // rappeler les entiers de la liste
  printf("\nVoici vos entiers en ordre croissant :\n");
  affiche_liste(liste);
  // nettoyer la mémoire
  detruire_liste(&liste);
} // end exemple_pile

// ##########
void affiche_liste(MAILLON *liste) {
  int val;
  while (!liste == 0) { // tant qu'il reste un entier
    printf("%d\t", liste->val);
    // liste est passé par copie :
    // on peut modifier la copie sans abimer la liste
    liste=liste->suiv;
  }
  printf("\n");
} // end affiche_liste

// ##########
void detruire_liste(MAILLON **pliste) {
  // récursif (moins efficace qu'une version itérative)
  MAILLON *tmp=*pliste;
  if (tmp == 0) // si le maillon n'existe pas
    return; // arrêter la récursion

  // sinon le maillon existe :
  // détruire le reste de la liste
  detruire_liste(&(tmp->suiv));
  // et détruire le maillon
  free(tmp);
  *pliste=0;
}

// ##########
void inserer_ordre(MAILLON **pliste, int val) {
  // créer le nouveau maillon
  MAILLON *tmp=(MAILLON *) malloc(sizeof(MAILLON));
  tmp->val=val;

  // trouver l'endroit d'insertion
  MAILLON *prec,*cur; // precedent et courant
  cur=*pliste; // on se place au début
  prec=0; // donc pas de prédecesseur
  
  // tant qu'on n'est pas :
  // - sorti de la liste
  // - arrivé au bon endroit,
  // alors avancer dans la liste
  while (!cur ==0 && cur->val < val) {
    prec=cur;
    cur=cur->suiv;
  }

  // on a trouvé, insérer :
  // 1- brancher le reste de la liste (ou 0 si pas de reste)
  tmp->suiv=cur;
  // est-ce une insertion en tête ou au milieu ?
  if (! prec) // prec == 0 donc insertion en tête
    *pliste=tmp; // changeons la tête
  else // non, il y a un prédécesseur
    prec->suiv=tmp; // le tour est joué
} // end inserer_ordre