// ==================================================================
//      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, un pointeur sur la liste à modifier
//
// Lors de l'appel de ces sous-programmes il faut donc passer
// l'adresse de la liste
//
// L'implantation donnée ici utilise la syntaxe du langage C
// ==================================================================

#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;

// ==================================================================
// Sous-programmes qui agissent sur une liste
//
// Implantation itérative
// ==================================================================

// Initialisation d'une liste
void liste_initialiser(liste *l)
{
    *l = liste_vide;
}

// Ajout en tete de la liste
void liste_ajouter_en_tete(liste *l, int valeur)
{

    type_element_de_liste *nouvel_element = new type_element_de_liste;
    nouvel_element->suivant = *l;
    nouvel_element->valeur = valeur;

    *l = nouvel_element;
}

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

    type_element_de_liste *nouvel_element = new type_element_de_liste;
    nouvel_element->suivant = liste_vide;
    nouvel_element->valeur = valeur;

    if (*l == liste_vide)
    {
        *l = nouvel_element;
    }
    else
    {
        // rechercher le dernier élément
        liste dernier = *l;
        while (dernier->suivant != liste_vide)
        {
            dernier = dernier->suivant;
        }

        dernier->suivant = nouvel_element;
    }
}

// créer une liste à partir de données stokées
// dans une chaîne de caractères
void liste_creer(liste *l, string data)
{

    istringstream iss(data);
    type_valeur valeur;

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

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

    liste courant = *l;
    liste suivant;

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

    *l = liste_vide;
}

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

    liste courant = *l;
    while (courant != liste_vide)
    {
        cout << courant->valeur << " ";
        courant = courant->suivant;
    }
    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 = courant1->suivant;
        while (courant2 != liste_vide)
        {
            if (courant1->valeur > courant2->valeur)
            {
                swap(courant1->valeur, courant2->valeur);
            }
            courant2 = courant2->suivant;
        }
        courant1 = courant1->suivant;
    }
}

void 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 = courant->suivant;

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

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

                doublon = suivant_doublon;
            }
            else
            {
                // sinon, passer à l'élément suivant
                precedent_doublon = doublon;
                doublon = doublon->suivant;
            }
        }

        courant = courant->suivant;
    }
}

// ==================================================================
// 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;

    liste_initialiser(&l);

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

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

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

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

    liste_trier(&l);

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

    liste_vider(&l);

    liste_creer(&l, "1 2 1 2 2 3 2 1");

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

    liste_supprimer_doublons(&l);

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

    liste_vider(&l);

    return EXIT_SUCCESS;
}