/***********************************************************
  Programme d'exemple de liste chainee d'eleves
  http://www-sop.inria.fr/oasis/personnel/Carine.Courbis/c/
************************************************************/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX 25

typedef struct _Eleve{
    char * nom;
    int id;
    struct _Eleve * suiv; /* pointeur sur le suivant */
} Eleve;

/* tableau contenant le nom d'un eleve que l'on vient de saisir */ 
static char nomEleve[MAX];

/*
  Retourne un nouveau eleve (avec le champ suiv pointant sur nil).
  Parametre : 
     id le numero a attribuer au nouvel eleve
*/
Eleve * saisieEleve(int id) {
    int car, i=0;
    Eleve * newEleve;

    printf("Saisissez le nom de l'eleve\n");
    while(!isalpha(car = getchar()))
	;
    ungetc(car, stdin);
    while (((car = getchar()) != '\n') && (i<MAX-1)) {
	nomEleve[i++] = car;
    }

    if (car != '\n') {
	while (getchar() != '\n')
	    ;
    }
    nomEleve[i] = '\0';
  
    /* alloue de la place pour une donnee de type Eleve */
    newEleve = (Eleve *)malloc(sizeof(Eleve));
    /* alloue de la place pour le nom de l'eleve */
    newEleve->nom = (char *)malloc(sizeof(char)*(strlen(nomEleve) + 1));
    strcpy(newEleve->nom, nomEleve);
    newEleve->id = id;
    /* le suivant pointe sur null */
    newEleve->suiv = NULL;
    return newEleve;
}

/*
  Insere en tete de la liste l'eleve donne. Tete pointera sur le nouvel
  Eleve.
  Parametres : 
     tete un pointeur de pointeur sur la tete de la liste 
          (normalement tete est un pointeur sur le premier de la liste mais 
	  comme on va modifier cette valeur, il faut passer le pointeur de pointeur), 
	  Donnee en entree/sortie
     eleveAInserer un pointeur sur l'Eleve a inserer en tete
*/
void insertionEnTete(Eleve ** tete, Eleve * eleveAInserer) {
    eleveAInserer->suiv = (*tete);
    (*tete) = eleveAInserer;
}

/*
  Insere en queue de liste l'eleve donne. 
  Parametres : 
     tete un pointeur de pointeur sur la tete de la liste 
          (si tete est a nil, elle pointera sur le nouvel Eleve 
	  donc on modifie sa valeur d'ou le pointeur de pointeur), 
	  Donnee en entree/sortie
     eleveAInserer un pointeur sur l'Eleve a inserer a la fin de liste
*/
void insertionEnQueue(Eleve ** tete, Eleve * eleveAInserer) {
    Eleve * ptr;

    if (*tete != NULL) {
	ptr = * tete;
	while (ptr->suiv != NULL)
	    ptr = ptr->suiv;
	ptr->suiv = eleveAInserer;
    } else
	*tete = eleveAInserer; 
}

/*
  Insere l'eleve selon l'ordre alphabetique de son nom et de son prenom. 
  Si Tete etait a nil ou si l'eleve doit etre inserer en tete de la liste, 
  elle pointera sur le nouvel Eleve.
  Parametres : 
     tete un pointeur de pointeur sur la tete de la liste 
          (si tete est a nil ou si l'eleve doit etre inserer en tete de la liste, 
	  elle pointera sur le nouvel eleve.
	  Donc on modifie sa valeur d'ou le pointeur de pointeur), 
	  Donnee en entree/sortie
     eleveAInserer un pointeur sur l'Eleve a inserer selon l'ordre alphabetique
*/
void insertionAlphabetique(Eleve ** tete, Eleve * eleveAInserer) {
    if (*tete == NULL) { /* insertion en tete */
	*tete = eleveAInserer;
    } else { // recherche ou inserer
	if (strcmp((*tete)->nom, eleveAInserer->nom) > 0) {  
	    printf("Insertion en tete %s < %s\n", eleveAInserer->nom, (*tete)->nom);
	    insertionEnTete(tete, eleveAInserer); /* 1 er dans la liste, change valeur de (*tete) */
	} else { /* insertion au milieu de liste ou a la fin */
	    Eleve * ptr = *tete;
      
	    while ((ptr->suiv != NULL) && (strcmp(ptr->suiv->nom, eleveAInserer->nom) < 0)) { 
		printf("%s > %s\n", eleveAInserer->nom, ptr->suiv->nom);
		ptr = ptr->suiv;
	    }
	    eleveAInserer->suiv = ptr->suiv;
	    ptr->suiv = eleveAInserer;
	}
    }
} 

/* Supprime l'etudiant ayant le numero d'etudiant donne de la liste 
   S'il n'est pas present, affiche une message d'erreur.
   Parametres:
      tete un pointeur de pointeur sur la tete de la liste 
           La tete change de valeur si on enleve le premier element 
	   de la liste.
      id   le numero de l'eleve a enlever

*/
void enleveEtudiant(Eleve ** tete, int id) {
    if (*tete != NULL) {
	if ((*tete)->id == id) {
	    *tete = (*tete)->suiv;
	} else {
	    Eleve * ptr = (*tete)->suiv;
	    Eleve * precedent = *tete;
	    while ((ptr != NULL) && (ptr->id != id)) {
		precedent = ptr;
		ptr = ptr->suiv;
	    }
	    if (ptr != NULL) {
		precedent->suiv = ptr->suiv;
		free(ptr);
	    } else
		printf("Aucun etudiant a %d comme id\n", id);
	}
    } else
	printf("Il n'y a pas d'etudiant\n");
}

/* Affiche la liste des eleves (nom suivi du numero d'etudiant) */
void afficheListeDesEleves(Eleve * tete) {
    Eleve * ptr;

    ptr = tete;
    if (tete == NULL)
	printf("Pas d'etudiant inscrit\n");
    else {
	do {
	    printf("%d \t\t%s\n", ptr->id, ptr->nom);
	    ptr = ptr->suiv;
	} while (ptr != NULL);
    }
}

/* Affiche le menu du programme */
void afficheAide() {
    printf("s pour saisir un nouvel etudiant\n");
    printf("a pour afficher la liste des etudiants\n");
    printf("e pour enlever un etudiant\n");
    printf("q pour sortir\n");
    printf("? pour afficher ce menu\n");
    printf("Votre choix : ");
}

void main() {
    int car;
    int idEtudiantAEnlever;
    Eleve * tete = NULL;
    Eleve * eleve;
    int id = 1;
  
    afficheAide();
    while ((car = getchar()) != 'q') {
	if (isalpha(car) || car == '?') {
	    fflush(stdin);
	    switch (car) {
	    case 's':
		eleve = saisieEleve(id);
		if (eleve != NULL) {
		    id++;
		    insertionAlphabetique(&tete, eleve);
		}
		break;
	    case 'e':
		printf("Donner l'id de l'etudiant a enlever : "); 
		scanf("%d", &idEtudiantAEnlever);
		enleveEtudiant(&tete, idEtudiantAEnlever);
		break;
	    case 'a':
		afficheListeDesEleves(tete);
		break;
	    case '?':
		afficheAide();
		break;
	    default:
		printf("\nChoix incorrect\n");
		afficheAide();
		continue;
	    }
	    printf("Votre choix : ");
	}
    }
}