/* Correction TP n°1 - Exercice 2 - Listes doublement chaînées */

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

struct s_maillon {
    struct s_maillon * prec;
    struct s_maillon * suiv;
    int val;
};

typedef struct s_maillon Maillon;

struct s_listeDC {
    Maillon* prem;
    Maillon* dern;
};

typedef struct s_listeDC ListeDC;

// on alloue un maillon dans le tas, on initialise ses champs
ListeDC* creeListe(){
    ListeDC* liste = (ListeDC*) malloc(1*sizeof(ListeDC));
    liste->prem = NULL;
    liste->dern = NULL;
    return liste;
}

// on suit la chaîne des maillons qu'on libère un par un.
// NB : attention de bien récupérer l'adresse du maillon suivant
// avant de libérer le maillon courant
// on libere la liste
void detruireListe(ListeDC* liste){
    Maillon* ptr = liste->prem;
    while (ptr != NULL) {
        Maillon* ptr_a_liberer = ptr;
        ptr = ptr->suiv;
        free(ptr_a_liberer);
    }
    free(liste);
}

// le booléen prem indique qu'ajout du côté du premier maillon
// attention au cas particuler de la liste vide
void ajouter(ListeDC* liste, int val, bool prem){
    Maillon* nouv = (Maillon*) malloc(1*sizeof(Maillon));
    nouv->val = val;
    if (prem) { // ajout au début
        nouv->prec = NULL;
        if (liste->prem == NULL) { // cas de la liste vide
            assert(liste->dern == NULL);
            // le nouveau maillon devient à la fois le premier et le dernier !!
            nouv->suiv = NULL;
            liste->prem = nouv;
            liste->dern = nouv;
        } else { // cas d'une liste non vide
            nouv->suiv = liste->prem;
            liste->prem->prec = nouv;
            liste->prem = nouv;
        }
    } else { // ajout en fin, de manière symétrique
        nouv->suiv = NULL;
        if (liste->dern == NULL) { // cas de la liste vide
            assert(liste->prem == NULL);
            nouv->prec = NULL;
            liste->dern = nouv;
            liste->prem = nouv;
        } else { // cas d'une liste non vide
            nouv->prec = liste->dern;
            liste->dern->suiv = nouv;
            liste->dern = nouv;
        }
    }
}

// on suit la chaîne de maillons (dans un sens ou dans l'autre !)
void afficher(ListeDC* liste, bool prem){
    if (prem) {
        Maillon* ptr = liste->prem;
        while (ptr != NULL) {
            printf("%d-", ptr->val);
            ptr = ptr->suiv;
        }
        printf("\n");
    } else {
        Maillon* ptr = liste->dern;
        while (ptr != NULL) {
            printf("%d-", ptr->val);
            ptr = ptr->prec;
        }
        printf("\n");
    }
}

// on parcourt la chaine jusqu'à trouver la valeur, ou atteindre la fin de chaine
// si la valeur est trouvée, on met à jour les pointeurs des voisins puis on supprime le maillon 
// NB : cas particulier si on supprime sur le dernier maillon
// ou le premier maillon : il faut mettre à jour les champs prem ou dern de la liste
bool supprimer(ListeDC* liste, int val, bool prem){
    Maillon* ptr = NULL;
    // recherche du maillon
    if (prem) {
        ptr = liste->prem;
        while (ptr != NULL && ptr->val != val) { // paresseux
            ptr = ptr->suiv;
        }
    } else {
        ptr = liste->dern;
        while (ptr != NULL && ptr->val != val) { // paresseux
            ptr = ptr->prec;
        }
    }
    
    if (ptr == NULL) return false; // valeur absente : rien à faire
    else {
        // mise à jour des pointeurs des voisins :
        if (ptr->suiv == NULL) { // cas particulier dernier maillon
            liste->dern = ptr->prec;
        } else { // cas général
            ptr->suiv->prec = ptr->prec;
        }
        if (ptr->prec == NULL) { // cas particulier premier maillon
            liste->prem = ptr->suiv;
        } else { // cas général
            ptr->prec->suiv = ptr->suiv;
        }

        free(ptr); // liberation
        return true;
    }
}

int main() {
    ListeDC* liste = creeListe();
    ajouter(liste, 4, true);
    ajouter(liste, 5, false); 
    afficher(liste, true); // 4-5
    afficher(liste, false); // 5-4
    ajouter(liste, 3, true);
    ajouter(liste, 6, false); 
    afficher(liste, true); // 3-4-5-6
    afficher(liste, false); // 6-5-4-3
    ajouter(liste, 4, true);
    ajouter(liste, 5, false); 
    afficher(liste, true); // 4-3-4-5-6-5
    afficher(liste, false); // 5-6-5-4-3-4
    supprimer(liste, 5, true); 
    afficher(liste, true); // 4-3-4-6-5
    afficher(liste, false); // 5-6-4-3-4
    supprimer(liste, 4, false); 
    afficher(liste, true); // 4-3-6-5
    afficher(liste, false); // 5-6-3-4
    detruireListe(liste);
    return 0;
}