// ==================================================================
//      Auteur : Jean-Michel RICHER
//      Email  : jean-michel.richer@univ-angers.fr
// Institution : Université d'Angers, Faculté des Sciences
// Département : Informatique
// ==================================================================
//
// Objectif : Implantation itérative de liste simplement chaînée
//
// Spécificité : On passe en paramètre des sous-programmes qui
// agissent sur les listes, la liste à modifier. Pour les sous-
// programmes qui modifie la liste (comme l'ajout d'un élément)
// on retourne la tête de la nouvelle liste modifiée.
//
// Lors de l'appel de ces sous-programmes il faut donc passer
// la liste en paramètre mais éventuellement récupérer la liste
// modifiée
//
// L'implantation donnée ici utilise des macro-instructions afin
// de rendre la lecture du code plus aisée.
// ==================================================================
#include <iostream>
#include <sstream>
using namespace std;

// ==================================================================
// structures communes
// ==================================================================

// définition du type de la valeur stockée par un élément de la liste
using type_valeur = int;

// définition d'un élément (maillon) de la liste
struct type_element_de_liste
{
    // pointeur sur l'élément suivant
    type_element_de_liste *suivant;
    // valeur stockée par cet élément
    type_valeur valeur;
};

// définition d'une liste comme un pointeur sur un élément
using liste = type_element_de_liste *;

// définition de la liste vide
const liste liste_vide = nullptr;

// ==================================================================
// structures spécifiques à cette implantation
// ==================================================================

#define le_suivant_de(l) l->suivant
#define la_valeur_de(l) l->valeur

// ==================================================================
// Sous-programmes qui agissent sur une liste
// ==================================================================

// Initialisation de la liste
liste liste_initialiser()
{
    return liste_vide;
}

// Ajout en tête de la liste
liste liste_ajouter_en_tete(liste l, int valeur)
{
    type_element_de_liste *nouvel_element = new type_element_de_liste;
    le_suivant_de(nouvel_element) = l;
    la_valeur_de(nouvel_element) = valeur;

    return nouvel_element;
}

// Ajout en queue de la liste
liste liste_ajouter_en_queue(liste l, int valeur)
{

    type_element_de_liste *nouvel_element = new type_element_de_liste;
    le_suivant_de(nouvel_element) = liste_vide;
    la_valeur_de(nouvel_element) = valeur;

    if (l == liste_vide)
    {
        return nouvel_element;
    }
    else
    {
        // rechercher le dernier élément
        liste dernier = l;
        while (le_suivant_de(dernier) != liste_vide)
        {
            dernier = le_suivant_de(dernier);
        }

        le_suivant_de(dernier) = nouvel_element;

        return l;
    }
}

// créer une liste à partir de données stokées
// dans une chaîne de caractères
liste liste_creer(string data)
{
    liste l = liste_vide;
    istringstream iss(data);
    type_valeur valeur;

    while (iss >> valeur)
    {
        l = liste_ajouter_en_queue(l, valeur);
    }

    return l;
}

// Vider une liste : supprimer tous ses éléments
liste liste_vider(liste l)
{

    liste courant = l;
    liste suivant;

    while (courant != liste_vide)
    {
        suivant = le_suivant_de(courant);
        delete courant;
        courant = suivant;
    }

    return liste_vide;
}

// Affichage de la liste
void liste_afficher(liste l)
{

    liste courant = l;
    while (courant != liste_vide)
    {
        cout << la_valeur_de(courant) << " ";
        courant = le_suivant_de(courant);
    }
    cout << endl;
}

// Tri de la liste sous forme de tri à bulle
void liste_trier(liste l)
{

    liste courant1 = l;
    while (courant1 != liste_vide)
    {
        liste courant2 = le_suivant_de(courant1);
        while (courant2 != liste_vide)
        {
            if (la_valeur_de(courant1) > la_valeur_de(courant2))
            {
                swap(la_valeur_de(courant1), la_valeur_de(courant2));
            }
            courant2 = le_suivant_de(courant2);
        }
        courant1 = le_suivant_de(courant1);
    }
}

liste liste_supprimer_doublons(liste l)
{

    liste courant = l;

    // on parcourt la liste initiale à la recherche d'un doublon
    // pour chaque élément
    while (courant != liste_vide)
    {
        liste doublon = le_suivant_de(courant);

        // parcours des éléments restants dans la liste
        liste precedent_doublon = courant;
        while (doublon != liste_vide)
        {

            // a t-on trouvé un doublon ?
            if (la_valeur_de(courant) == la_valeur_de(doublon))
            {
                // si oui, supprimer le doublon
                liste suivant_doublon = le_suivant_de(doublon);
                delete doublon;
                le_suivant_de(precedent_doublon) = suivant_doublon;

                doublon = suivant_doublon;
            }
            else
            {
                // sinon, passer à l'élément suivant
                precedent_doublon = doublon;
                doublon = le_suivant_de(doublon);
            }
        }

        courant = le_suivant_de(courant);
    }

    return l;
}

// ==================================================================
// Programme principal
// ==================================================================
// On insère des élément dans la liste (en tête, puis en queue) et
// on affiche le résultat : 11 4 3 2 1 5 6 7 8 9 10 -1
// on tri ensuite la liste : -1 1 2 3 4 5 6 7 8 9 10 11
// ==================================================================

int main()
{
    liste l;

    l = liste_initialiser();

    for (int i = 1; i < 5; ++i)
    {
        l = liste_ajouter_en_tete(l, i);
    }

    for (int i = 5; i < 11; ++i)
    {
        liste_ajouter_en_queue(l, i);
    }

    l = liste_ajouter_en_tete(l, 11);
    l = liste_ajouter_en_queue(l, -1);

    cout << "liste initiale = ";
    liste_afficher(l);

    liste_trier(l);

    cout << "liste triée = ";
    liste_afficher(l);

    l = liste_vider(l);

    l = liste_creer("1 2 1 2 2 3 2 1");

    cout << "liste avec doublons = ";
    liste_afficher(l);

    l = liste_supprimer_doublons(l);

    cout << "liste sans doublons = ";
    liste_afficher(l);

    l = liste_vider(l);

    return EXIT_SUCCESS;
}