#include <stddef.h> // on y trouve la def de Null
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define DEBUG 1

/* Definition de la structure : liste_s*/
struct liste_s {
    int val;
    struct liste_s *next;
};

/* Definition du type pointeur sur la structure liste_s : liste_t*/
typedef struct liste_s *liste_t;

/**************************************
* Insere un element en tete de liste *
**************************************/
liste_t insereTete(int element, liste_t Q) {
if (DEBUG) printf ("Dans insereTete\n");   
    liste_t L;
    L = (liste_t)malloc(sizeof(struct liste_s)); // allocation de la zone
    L->val = element;
    L->next = Q;
    return L;
}
/***************************************
* Insere un element en queue de liste_t *
***************************************/
liste_t insereQueue(int element, liste_t Q) {
    liste_t L, tmp=Q;
    L = (liste_t)malloc(sizeof(struct liste_s)); // allocation de la zone
    L->val = element;
    L->next = NULL;
    if (Q == NULL){
        return L;
    }
// recherche du dernier
    while (tmp->next != NULL){ 
        tmp = tmp->next; 
    } 
    tmp->next = L;
    return Q;
}
/***************************************
* Recherche un element de liste_t 
* renvoie 0  en tete ; NULL en queue ou superieur ; le pointeur sinon
***************************************/
liste_t retourPosition(liste_t L, int pos) {
if (DEBUG) printf ("Dans retourPosition\n");    

    liste_t retour; //permet de garder la position precedente !
    
    if (pos==0){
        if (DEBUG) printf ("->position en tete\n");
        return L;
    }
    else{
        while (pos>0 && L != NULL){ 
            retour=L;
            L = L->next;
            pos--; 
        }
    } 
    if (pos==0) {
// cas ou on a trouve l'element
        if (L==NULL) {
            if (DEBUG) printf ("->position en queue\n ");
            return NULL;
        }
        else { 
            if (DEBUG) printf("->trouve dans la liste ok\n");
            return retour;
        }
    }
    else{
        if (DEBUG) printf ("->la position est trop grand mis en queue\n");
        return NULL;
    }
}

/***************************************
* insere un element apres la pos dans liste_t * Pos=0 est le debut
***************************************/
liste_t inserePosition(liste_t liste, int pos,int element) {
if (DEBUG) printf ("Dans inserePosition\n");         
    liste_t tmp;
    liste_t L;
    
    tmp=retourPosition(liste,pos);
    if (pos==0){// ne pas faire si tmp == liste car retour est la pos precedente
        if (DEBUG) printf ("-> Choix d inserer en tete ");
        return insereTete(element,liste);
    }
    else { 
        if (tmp==NULL){
            if (DEBUG) printf ("-> Choix d inserer en queue ");
            return insereQueue(element,liste);            
        }
        else {
            if (DEBUG) printf ("-> Choix d inserer en position %d ",pos);
//creation de l'element à inserer    
            L = (liste_t)malloc(sizeof(struct liste_s)); // allocation de la zone
            L->val = element;
            L->next = tmp->next; //car tmp est la position precedente
            tmp->next = L;
            return liste;
        }
    }
}



/***************************************
* Supprime l’element en tete de liste *
***************************************/
liste_t supprimeTete(liste_t L) {
    liste_t suivant = L;
    if (L != NULL) { // pour etre sur que L->next existe
        suivant= L->next;
        free(L); //liberation de l’espace alloue pour une cellule
    }
    return suivant;
}

/*****************************
* Supprime toute la liste L *
*****************************/
liste_t supprimeListe(liste_t L) {
    while (L != NULL){
        L = supprimeTete(L);
    }
    return L;
}

/************************************
* Affiche le contenu de la liste L *
************************************/
void printListe(liste_t L) {
    printf("\nliste = ");
    while (L != NULL) { 
        printf("%d ->",L->val);
        L = L->next;
    }
     printf("|\n");
}
/********************************************************/
int main() {
    liste_t L;
    L=NULL;
   L = insereTete(1,insereTete(2,insereTete(4,insereTete(5,NULL))));
    printListe(L);
    L = insereQueue(7,(insereQueue(6,L)));
    printListe(L);
//

    printListe(L);
    
    L= inserePosition(L,0,0);
    printListe(L);
    L= inserePosition(L,3,3);
    printListe(L);
    L= inserePosition(L,1,1);
    printListe(L);
    L= inserePosition(L,2,2);
    printListe(L);
    
    printf("\nSuppression de la tete:");
    L = supprimeTete(L);
    printListe(L);
    printf("\nSuppression des elements de la liste:");
    L = supprimeListe(L);
    printListe(L);
    system("PAUSE");	
  return 0;
}