#ifndef TP4_NOEUD_H
#define TP4_NOEUD_H

#include <vector>
#include <iostream>


template <typename TYPE>
class Noeud{
private:
    TYPE valeur;                            //valeur associée au Noeud
    Noeud* parent;                       //parent du Noeud, possiblement nullptr
    std::vector<Noeud*> enfants;              //liste des enfants du Noeud

    //Vous pouvez ajouter des fonctions privées, au besoin - mais PAS de fonctions publiques ni de variable membre

public:

    class iterator;
    friend class Noeud::iterator;				//pour que l'itérateur ait accès à la section privée de Noeud

    Noeud(const TYPE& valeur);                     // constructeur principal prenant la valeur associée au Noeud
    Noeud(const Noeud& source);                 // constructeur par copie
    ~Noeud();                                   // destructeur

    Noeud& operator=(const Noeud& source);      // affectateur (copie de la source)


    TYPE& val();                           		// retourne une référence MODIFIABLE vers la valeur associée au Noeud.
    Noeud* get_enfant(size_t i);				// retourne le i-ème enfant (le premier est indicé à 0)
    size_t get_nb_enfants() const;				// retourne le nombre d'enfants du Noeud
    Noeud* ajouter_enfant(const TYPE& valeur);		// créé un enfant ajouté à la fin de la liste d'enfants, et le retourne
    void supprimer_enfant(size_t i);            //supprime tout le sous-arbre enraciné en le i-ème enfant.  


    iterator begin();                            // retourne un itérateur postordre sur l'arbre
    iterator end();                              // retourne l'itérateur pointant sur la fin (et la fin n'est PAS un élément)

    void afficher_postordre() const;             // fait un parcours postordre RÉCURSIF en affichant les valeurs dans l'ordre.  Pour tester.

};





//Déclaration de la classe itérateur.
template <typename TYPE>
class Noeud<TYPE>::iterator{
private:

    //à vous de choisir une représentation de l'itérateur à l'aide de variables membres

    //ML
    Noeud* racine;
    Noeud* curnoeud;
    bool estfin;
    ///ML

public:

    //à ajouter: constructeurs, destructeur, constructeur par copie (au besoin)
    //ML

    iterator(Noeud* racine, Noeud* n, bool estFin){
        this->curnoeud = n;
        this->racine = racine;
        this->estfin = estFin;
    }
    ///ML

    iterator& operator++();                       // incrémente l'itérateur.
    iterator operator++(int i);                  // incrémente l'itérateur.  Le paramètre i est inutile.
    iterator& operator--();                       // décrémente l'itérateur.
    iterator operator--(int i);                  // décrémente l'itérateur.  Le paramètre i est inutile.

    TYPE& operator*();                           // retourne la valeur associée au noeud pointé par l'itérateur
    bool operator==(const iterator& it);  // vérifie si l'itérateur est égal à it
    bool operator!=(const iterator& it);  // vérifie si l'itérateur est différent de it
};




/********************************************************
Implémentation de la classe Noeud
********************************************************/


/**
 * Constructeur principal de Noeud.  val est la valeur associée au Noeud
 * À la construction, le parent est nullptr.
 */
template <typename TYPE>
Noeud<TYPE>::Noeud(const TYPE& valeur){
    this->valeur = valeur;
    this->parent = nullptr;
}

/**
 * Constructeur par copie.  On doit copier toute la structure.
 */
template <typename TYPE>
Noeud<TYPE>::Noeud(const Noeud& source){
    *this = source;
}



/**
Affectateur =.  this devient une copie de source.
**/
template <typename TYPE>
Noeud<TYPE>& Noeud<TYPE>::operator=(const Noeud& source) {
    if (this == &source)
        return *this;

    this->valeur = source.valeur;
    for (size_t i = 0; i < source.get_nb_enfants(); i++){
        Noeud* enfant = new Noeud(*(source.enfants[i]));
        enfant->parent = this;
        this->enfants.push_back(enfant);
    }

    return *this;
}



/**
 * Destructeur.  Chaque est responsable de supprimer ses enfants.
 */
template <typename TYPE>
Noeud<TYPE>::~Noeud(){
    for (size_t i = 0; i < enfants.size(); i++){
        delete enfants[i];  //entraîne une chaine de suppression chez les descendants
    }
    //question de réflexion: pourquoi on ne delete pas this?  Comment la racine va-t-elle se supprimer?
}



/**
 * Ajoute un enfant à la fin de la liste d'enfants, et le retourne.
 * val est la valeur associée au nouveau Noeud.
 * Le parent du nouveau Noeud est affecté au Noeud courant.
 */
template <typename TYPE>
Noeud<TYPE>* Noeud<TYPE>::ajouter_enfant(const TYPE& valeur){
    Noeud* n = new Noeud(valeur);
    n->parent = this;
    this->enfants.push_back(n);
    return n;
}




/**
 * Retourne une référence sur la valeur associée au Noeud.  On peut ensuite modifier val.
 */
template <typename TYPE>
TYPE& Noeud<TYPE>::val(){
    return valeur;
}






/**
 * Retourne le nombre d'enfants du Noeud.
 */
template <typename TYPE>
size_t Noeud<TYPE>::get_nb_enfants() const{
    return enfants.size();
}

/**
 * Retourne le i-ème enfant (le premier est indicé à 0).
 * C'est du C++, donc on ne fait aucune vérification.
 */
template <typename TYPE>
Noeud<TYPE>* Noeud<TYPE>::get_enfant(size_t i){
    return enfants[i];
}




/**
Supprime tout le sous - arbre enraciné en le i - ème enfant.
*/
template <typename TYPE>
void Noeud<TYPE>::supprimer_enfant(size_t i) {
    delete enfants[i];

    enfants.erase(enfants.begin() + i);
}




template <typename TYPE>
void Noeud<TYPE>::afficher_postordre() const{
    for (size_t i = 0; i < enfants.size(); i++){
        enfants[i]->afficher_postordre();
    }

    std::cout << valeur << " ";
}






/**
 * Retourne le début un itérateur postordre sur l'arbre.
 * Le début devrait donc pointer sur le noeud le plus "à gauche".
 */
template <typename TYPE>
typename Noeud<TYPE>::iterator Noeud<TYPE>::begin(){
    //ML
    Noeud* plus_gauche = this;
    while (plus_gauche->enfants.size() > 0){
        plus_gauche = plus_gauche->enfants[0];
    }


    return Noeud::iterator(this, plus_gauche, false);
    ///ML
}

/**
 * Retourne un itérateur représentant la fin de l'arbre.
 * La fin n'est pas la même chose que le dernier élément.
 */
template <typename TYPE>
typename Noeud<TYPE>::iterator Noeud<TYPE>::end(){
    //ML
    return iterator(this, this, true);
    ///ML
}



template <typename TYPE>
typename Noeud<TYPE>::iterator Noeud<TYPE>::iterator::operator++(int i){
    iterator tmp = *this;
    ++(*this);
    return tmp;
}




/**
 * Incrémente l'itérateur.  Le comportement est non-défini si l'itérateur est égal à end()
 */
template <typename TYPE>
typename Noeud<TYPE>::iterator& Noeud<TYPE>::iterator::operator++(){
    //implémentez-moi
    //L'état interne de l'itérateur DOIT être modifié.

    //ML

    if (racine == curnoeud && !estfin)
    {
        estfin = true;
    }
    else
    {
        size_t monindice = 0;
        for (size_t i = 0; i < curnoeud->parent->enfants.size(); i++)
        {
            if (curnoeud->parent->enfants[i] == curnoeud)
            {
                monindice = i;
                break;
            }
        }

        if (monindice == curnoeud->parent->get_nb_enfants() - 1)
        {
            curnoeud = curnoeud->parent;
        }
        else
        {
            curnoeud = curnoeud->parent->enfants[monindice + 1];
            while (curnoeud->enfants.size() > 0)
            {
                curnoeud = curnoeud->enfants[0];
            }
        }
    }


    return (*this);
    ///
}





template <typename TYPE>
typename Noeud<TYPE>::iterator Noeud<TYPE>::iterator::operator--(int i){
    iterator tmp = *this;
    --(*this);
    return tmp;
}


/**
 * Décrémente l'itérateur.  Le comportement est non-défini si l'itérateur est begin().
 * Lorsque l'on fait
 * noeud::iterator it = n->end();
 * it--;
 * on s'attend à ce que it point sur n.
 */
template <typename TYPE>
typename Noeud<TYPE>::iterator& Noeud<TYPE>::iterator::operator--(){
    //implémentez-moi


    //ML
    if (estfin){
        estfin = false;
    }
    else if (curnoeud->enfants.size() > 0){
        curnoeud = curnoeud->enfants[curnoeud->enfants.size() - 1];
    }
    else{
        //retrouver le premier ancêtre qui a un voisin gauche
        while (curnoeud == curnoeud->parent->enfants[0]){
            curnoeud = curnoeud->parent;
        }

        //TODO: CODE DUPLIQUÉ!!!  (je fais exprès de le laisser ici pour vous)
        size_t monindice = 0;
        for (size_t i = 0; i <curnoeud->parent->enfants.size(); i++){
            if (curnoeud->parent->enfants[i] == curnoeud){
                monindice = i;
                break;
            }
        }

        curnoeud = curnoeud->parent->enfants[monindice - 1];

    }


    return (*this);
    ///ML
}



template <typename TYPE>
TYPE& Noeud<TYPE>::iterator::operator*(){
    //implémentez-moi

    //ML
    return curnoeud->valeur;
    ///ML
}



/**
 * Compare l'itérateur avec un autre.
 * La comparaison avec end() doit bien fonctionner.
 * On définit que deux itérateurs sur deux arbres ou sous-arbres différents ne peuvent
 * jamais être égaux.
 */
template <typename TYPE>
bool Noeud<TYPE>::iterator::operator==(const iterator& it){
    //implémentez-moi!

    //ML
    if (racine != it.racine)
        return false;

    if (estfin){
        return it.estfin;
    }
    else{
        return (curnoeud == it.curnoeud && !it.estfin);
    }
    ///ML
}



/**
 * Compare l'itérateur avec un autre, et retourne true s'ils sont différents.
 * La comparaison avec end() doit bien fonctionner.
 * On définit que deux itérateurs sur deux arbres ou sous-arbres différents ne peuvent
 * jamais être égaux.
 */
template <typename TYPE>
bool Noeud<TYPE>::iterator::operator!=(const iterator &it){
    return !( (*this) == it );
}





#endif //TP4_NOEUD_H