/*
 * VOTRE EN-TÊTE ICI!
 */


#ifndef TP3_LISTCHAIN_H
#define TP3_LISTCHAIN_H


#include <iostream>


 /**
  * Classe pour une structure de données de liste chaînée de listes chaînées.
  */
template <typename TYPE>
class listchain
{
private:

    //Représente un noeud conteneur d'éléments
    struct Noeud {
        TYPE val;
        Noeud* next;

        Noeud() {
            next = nullptr;
        }
    };

    //Représente une chaîne de noeuds.
    struct SuperNoeud
    {
        Noeud* premier_noeud;
        Noeud* dernier_noeud;

        SuperNoeud* prev;
        SuperNoeud* next;
        size_t nbelem;      //nombre d'éléments dans la chaîne du super noeud

        SuperNoeud() {
            premier_noeud = dernier_noeud = nullptr;
            prev = next = nullptr;
            nbelem = 0;
        }
    };

    SuperNoeud* debut;   //premier super noeud, ou nullptr si vide
    SuperNoeud* fin;     //dernier super noeud, ou nullptr si vide
    size_t max_taille;   //nombre d'élément maximum qu'un super noeud peut contenir

public:

    listchain() : listchain(10) {};	//redirige vers l'autre constructeur avec max_taille = 10

    listchain(size_t max_taille_supernoeud);

    ~listchain();

    listchain(const listchain& source);

    listchain& operator=(const listchain& source);


    TYPE& operator[](size_t i);

    size_t size() const;

    void push_front(const TYPE& val);
    void push_back(const TYPE& val);
    void pop_front();
    void pop_back();


    //*** J'ai pensé demander le insert_at et le erase_at, mais concentrez-vous sur l'intra à la place
    //*** Vous pouvez quand même réfléchir à comment vous l'auriez implémenté
    //void erase_at(const size_t pos);
    //void insert_at(const size_t pos, const TYPE& val);

    void clear();	//remet la liste vide


    void afficher_contenu();    //Affiche le contenu avec une ligne par sous-tableau.  

};





/*------------------------------------------------------------------------------
IMPLÉMENTATION
------------------------------------------------------------------------------*/





/**
 * Constructeur qui initialise avec une liste vide.
 * tabsize est la taille des sous-tableaux
 */
template <typename TYPE>
listchain<TYPE>::listchain(size_t max_taille_supernoeud)
{
    //implémentez-moi

    debut = fin = nullptr;
    max_taille = max_taille_supernoeud;

}




/**
 * Destructeur qui désalloue toute la mémoire et nettoie
 */
template <typename TYPE>
listchain<TYPE>::~listchain()
{
    //implémentez-moi

    clear();
}







/**
 * Supprime tous les éléments et remet à l'état d'une liste vide.
 */
template <typename TYPE>
void listchain<TYPE>::clear()
{
    //implémentez-moi

    if (!debut)
        return;

    SuperNoeud* sn = debut;
    while (sn) {
        Noeud* v = sn->premier_noeud;
        while (v) {
            Noeud* tmp = v->next;
            delete v;
            v = tmp;
        }
        SuperNoeud* tmpsn = sn->next;
        delete sn;
        sn = tmpsn;
    }

    debut = fin = nullptr;
}


/**
 * Constructeur par copie: met la liste à vide et délègue tout à l'opérateur =
 */
template <typename TYPE>
listchain<TYPE>::listchain(const listchain& source)
{
    //implémentez-moi

    debut = fin = nullptr;
    (*this) = source;
}


/**
 * Opérateur =
 * Nettoie l'objet courant et copie tout de la source
 */
template <typename TYPE>
listchain<TYPE>& listchain<TYPE>::operator=(const listchain& src)
{
    //implémentez-moi
    //NOTE: puisque vous n'avez pas à recopier exactement les mêmes super noeuds 
    //Il faut juste que le contenu soit le même, mais pas nécessairement les nbelem des super noeuds

    debut = fin = nullptr;
    this->max_taille = src.max_taille;

    SuperNoeud* sn = src.debut;
    while (sn) {
        Noeud* v = sn->premier_noeud;
        while (v) {
            this->push_back(v->val);
            v = v->next;
        }
        sn = sn->next;
    }

}



/**
 * Retourne le i-ème élément.
 */
template <typename TYPE>
TYPE& listchain<TYPE>::operator[](size_t i)
{
    //implémentez-moi
    //aucune vérification de borne à faire

    size_t cpt = 0;

    SuperNoeud* sn = this->debut;
    bool fini = false;
    while (!fini) {
        if (cpt + sn->nbelem > i || !sn)
            fini = true;
        else {
            cpt += sn->nbelem;
            sn = sn->next;
        }
    }

    
    size_t offset = i - cpt;

    Noeud* v = sn->premier_noeud;

    for (size_t j = 0; j < offset; ++j) {
        v = v->next;
    }
    return v->val;

}



/**
 * Retourne le nombre d'éléments dans votre liste.
 */
template <typename TYPE>
size_t listchain<TYPE>::size() const
{
    //implémentez moi

    size_t cpt = 0;
    SuperNoeud* sn = this->debut;
    while (sn) {
        cpt += sn->nbelem;
        sn = sn->next;
    }
    return cpt;
}



/**
 * Ajouter en début de liste.  Insérer une nouvelle cellule au début si nécessaire.
 */
template <typename TYPE>
void listchain<TYPE>::push_front(const TYPE& val)
{
    //implémentez moi
    //si debut->nbelem < max_taille, ajoutez dans la chaîne debut
    //sinon, créez un nouveau super noeud au début, avec un seul élément
    //N'oubliez pas de maintenir les nbelem

    Noeud* v = new Noeud();
    v->val = val;

    if (debut && debut->nbelem < max_taille){
        Noeud* tmp = debut->premier_noeud;
        debut->premier_noeud = v;
        v->next = tmp;
        debut->nbelem++;
    }
    else {
        SuperNoeud* sn = new SuperNoeud();
        sn->premier_noeud = sn->dernier_noeud = v;
        sn->nbelem = 1;

        if (!debut)
            debut = fin = sn;
        else {
            SuperNoeud* tmpsn = debut;
            debut = sn;
            debut->next = tmpsn;
            tmpsn->prev = sn;
        }
    }
}

/**
 * Ajouter en fin de liste.  Ajouter une nouvelle cellule à la fin si nécessaire.
 */
template <typename TYPE>
void listchain<TYPE>::push_back(const TYPE& val)
{
    //implémentez-moi
    //il y a 2 cas à gérer: si la liste est vide ou si fin->nbelem == max_taille,
    //il faut créer un nouveau super noeud pour v. 
    //Sinon, il faut juste ajouter à la fin du dernier super noeud.
    //N'oubliez pas de maintenir les nbelem

    Noeud* v = new Noeud();
    v->val = val;

    //cas où il faut créer un nouveau super noeud pour v
    if (!fin || fin->nbelem == max_taille) {
        SuperNoeud* sn = new SuperNoeud();
        sn->premier_noeud = sn->dernier_noeud = v;
        sn->nbelem = 1;

        if (!fin)
            debut = fin = sn;
        else {
            SuperNoeud* tmp_fin = fin;
            fin = sn;
            sn->prev = tmp_fin;
            tmp_fin->next = sn;
        }
    }
    //cas où on ajoute v au dernier super noeud
    else {
        Noeud* tmp_dernier = fin->dernier_noeud;
        fin->dernier_noeud = v;
        tmp_dernier->next = v;
        fin->nbelem++;
    }
}










/**
 * Enlève l'élément en tête de liste.  Ne vérifie rien.
 */
template <typename TYPE>
void listchain<TYPE>::pop_front()
{
    //implémentez-moi

    if (!debut)
        return;

    if (debut->nbelem == 1) {
        delete debut->premier_noeud;
        
        SuperNoeud* debutnext = debut->next;
        delete debut;
        debut = debutnext;

        if (!debut)
            fin = nullptr;
        else
            debut->prev = nullptr;
    }
    else {
        Noeud* tmp = debut->premier_noeud->next;
        delete debut->premier_noeud;
        debut->premier_noeud = tmp;
        debut->nbelem--;
    }
}


/**
 * Enlève l'élément en fin de liste.  Ne vérifie rien.
 */
template <typename TYPE>
void listchain<TYPE>::pop_back()
{
    if (!fin)   //liste vide
        return;

    //cas où le dernier super noeud a un seul element -> il va disparaître
    if (fin->nbelem == 1) {
        delete fin->premier_noeud;

        SuperNoeud* finprev = fin->prev;
        delete fin;
        fin = finprev;

        
        if (!finprev)   //cas où on vient de supprimer le dernier super noeud
            debut = nullptr;
        else
            fin->next = nullptr;
    }
    //cas où on doit supprimer le dernier elt de fin.  On est obligé de boucler pour aller chercher l'avant-dernier
    else {
        Noeud* v_prev = fin->premier_noeud;
        Noeud* v = fin->premier_noeud->next;

        while (v->next) {
            v_prev = v;
            v = v->next;
        }
        delete v;
        v_prev->next = nullptr;

        fin->nbelem--;
    }

}


/**
 * Affiche le contenu avec une ligne par sous-tableau.  Un X veut dire "case non-utilisée"
 */
template <typename TYPE>
void listchain<TYPE>::afficher_contenu()
{
    std::cout << "-------------------------------------" << std::endl;
    std::cout << "size() = " << size() << std::endl;

    SuperNoeud* sn = debut;
    while (sn) {

        std::cout << "[" << sn->nbelem << "] ";
        Noeud* v = sn->premier_noeud;
        while (v) {
            std::cout << v->val << " ";
            v = v->next;
        }
        std::cout << std::endl;

        sn = sn->next;
    }

}



#endif //TP3_LISTCHAIN_H