// ==================================================================
//      Auteur : Jean-Michel RICHER
//      Email  : jean-michel.richer@univ-angers.fr
// Institution : Université d'Angers, Faculté des Sciences
// Département : Informatique
// ==================================================================
//
// Objectif : Implantation récursive 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>
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 récursive
// ==================================================================

// 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)
{

    if (*l == liste_vide)
    {
        type_element_de_liste *nouvel_element = new type_element_de_liste;
        nouvel_element->suivant = liste_vide;
        nouvel_element->valeur = valeur;
        *l = nouvel_element;
    }
    else
    {
        liste_ajouter_en_queue(&(*l)->suivant, valeur);
    }
}

// Affichage de la liste
void liste_afficher(liste *l)
{
    if (*l != liste_vide)
    {

        cout << (*l)->valeur << " ";
        liste_afficher(&(*l)->suivant);
    }
    else
    {
        cout << endl;
    }
}

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

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_afficher(&l);

    return EXIT_SUCCESS;
}