// ==================================================================
//      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 des macro-instructions afin
// de rendre la lecture du code plus aisée. On utilise également
// le type 'pointeur_sur_liste' plutôt que 'liste *' afin de
// spécifier le passage en paramètre de la liste dans les sous-
// programmes de manipulation
// ==================================================================

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

// l'accès à la tête de la liste se fait par pointeur
using pointeur_sur_liste = liste *;

// définition de macro-instructions qui permettent de rendre le
// code plus lisible

// contenu du pointeur
#define le_contenu_du_pointeur(l) (*l)

// élément suivant
#define le_suivant_de(l) l->suivant

// valeur d'un élément
#define la_valeur_de(l) l->valeur

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

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

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

    type_element_de_liste *nouvel_element = new type_element_de_liste;
    le_suivant_de(nouvel_element) = le_contenu_du_pointeur(l);
    la_valeur_de(nouvel_element) = valeur;

    le_contenu_du_pointeur(l) = nouvel_element;
}

// Ajout en queue de la liste
void liste_ajouter_en_queue(pointeur_sur_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 (le_contenu_du_pointeur(l) == liste_vide)
    {
        le_contenu_du_pointeur(l) = nouvel_element;
    }
    else
    {
        // rechercher le dernier élément
        liste dernier = le_contenu_du_pointeur(l);
        while (le_suivant_de(dernier) != liste_vide)
        {
            dernier = le_suivant_de(dernier);
        }

        le_suivant_de(dernier) = nouvel_element;
    }
}

// créer une liste à partir de données stokées
// dans une chaîne de caractères
void liste_creer(pointeur_sur_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(pointeur_sur_liste l)
{

    liste courant = le_contenu_du_pointeur(l);
    liste suivant;

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

    le_contenu_du_pointeur(l) = liste_vide;
}

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

    liste courant = le_contenu_du_pointeur(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(pointeur_sur_liste l)
{

    liste courant1 = le_contenu_du_pointeur(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);
    }
}

void liste_supprimer_doublons(pointeur_sur_liste l)
{

    liste courant = le_contenu_du_pointeur(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);
    }
}

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