#include <iostream>
#include <cstdlib>
#include "liste.h"

using namespace std;


/****************************************/
/* Objectif : Constructeur d'un maillon contenant un entier.
/* Entrées : entier x
/* Sorties  :
/* Complexité : 0(1)
/****************************************/
maillon::maillon(int x)
{
    val = x;
    succ = pred = NULL;
}


/****************************************/
/* Objectif : Destructeur d'un maillon et de ses successeurs
/* Entrées :
/* Sorties  :
/* Complexité : 0(1)
/****************************************/
maillon::~maillon()
{
    if (succ)
    {
        delete (succ);
    }
}

/****************************************/
/* Objectif : Affichage du contenu d'un maillon.
/* Entrées :
/* Sorties  :
/* Complexité : 0(n) où n est la taille de liste.
de maillons dont le premier élément est l'objet appelant.
/****************************************/
void maillon::affichage()
{
    cout<<this->val;
}

/****************************************/
/* Objectif : Constructeur d'une liste doublement
chaînées d'entiers.
/* Entrées :
/* Sorties  :
/* Complexité : 0(1)
/****************************************/
liste::liste()
{
    tete = queue = NULL;
}


/****************************************/
/* Objectif : Destructeur d'une liste
/* Entrées :
/* Sorties  :
/* Complexité : 0(1)
/****************************************/
liste::~liste()
{
    if (tete)
    {
        delete (tete);
    }
}

/****************************************/
/* Objectif : Test de vacuité
/* Entrées :
/* Sorties  : booléan : vrai si la liste est vide
et faux sinon.
/* Complexité : 0(1)
/****************************************/
bool liste::vide()
{
    if (tete == NULL)
    {
        return true;
    }
    return(false);
}

/****************************************/
/* Objectif : Insertion en tête d'un maillon
x supposé non nul.
/* Entrées : Pointeur sur le maillon à insérer.
/* Sorties  :
/* Complexité : 0(1)
/****************************************/
void liste::insertionEnTete(maillon *x)
{
    x->succ= tete;
    if (!vide())
    {
        tete->pred = x;
        x->succ = tete;
        tete = x;
    }
    else {
        tete = queue = x;
    }
}

/****************************************/
/* Objectif : Insertion en queue d'un maillon
x supposé non nul
/* Entrées : Pointeur sur le maillon à insérer.
/* Sorties  :
/* Complexité : 0(1)
/****************************************/
void liste::insertionEnQueue(maillon *x)
{
    if (vide())
    {
        tete = queue = x;
    }
    else
    {
        queue->succ = x;
        x->pred = queue;
        queue = x;
    }
}


/****************************************/
/* Objectif : Insertion d'un maillon x dans une liste
supposée triée. x est supposé non nul.
/* Entrées : Pointeur sur le maillon à insérer.
/* Sorties  :
/* Complexité : 0(n)
/****************************************/
void liste::insertionTri(maillon *x)
{
    maillon * ptr = tete;
    if (vide())
    {
        tete = queue = x;
    }
    else
    {
        if (tete->val >= x->val)
        {
            insertionEnTete(x);
        }
        else if (queue -> val <= x->val)
        {
            insertionEnQueue(x);
        }
        else
        {
            while (ptr->val < x->val && ptr->succ != NULL)
            {
                ptr = ptr->succ;
            }
            maillon * tmp = ptr->pred;
            tmp->succ = x;
            x->pred = tmp;
            x->succ = ptr;
            ptr->pred = x;
        }
    }
}


/****************************************/
/* Objectif : affichage du contenu de la liste
/* Entrées :
/* Sorties  :
/* Complexité : 0(n) où n est le nombre de maillons
de la liste.
/****************************************/
void liste::affichage()
{
	maillon *tmp = tete;
    while ( tmp != NULL)
    {
        if ( tmp->succ != NULL)
        {
            cout<<tmp->val<< " -> ";
        }
        else
        {
            cout<<tmp->val;
        }
        tmp = tmp->succ;
    }
    cout<<endl;
}

/****************************************/
/* Objectif : Accès à l'attribut privé tete
/* Entrées :
/* Sorties  : tete
/* Complexité : 0(1)
/****************************************/
maillon *liste::debut()
{
	return tete;
}

/****************************************/
/* Objectif : Accès à l'attribut privé queue
/* Entrées :
/* Sorties  : tete
/* Complexité : 0(1)
/****************************************/
maillon *liste::fin()
{
	return queue;
}


/****************************************/
/* Objectif : Redirige la tete de liste vers
/* l'adresse x donnée en argument
/* Entrées : adresse d'un maillon
/* Sorties  :
/* Complexité : 0(1)
/****************************************/
void liste::redirige_debut_vers(maillon* x)
{
    maillon *tmp = tete->succ;
    maillon *tmp2 = x->pred;
    tete = x;
    x->pred = NULL;
    if(tmp == x){
        delete(tmp->pred);
    }
    else{
        while (tmp != tmp2){
            delete(tmp->pred);
            tmp = tmp->succ;
        }
        delete(tmp);
    }
}


/****************************************/
/* Objectif : Redirige la fin de liste vers
/* l'adresse x donnée en argument
/* Entrées : adresse d'un maillon
/* Sorties  :
/* Complexité : 0(1)
/****************************************/
void liste::redirige_fin_vers(maillon* x)
{
    maillon *tmp = queue->pred;
    maillon *tmp2 = x->succ;
    queue = x;
    x->succ = NULL;
    if(tmp == x){
        delete(tmp->succ);
    }
    else{
        while (tmp != tmp2){
            delete(tmp->succ);
            tmp = tmp->pred;
        }
        delete(tmp);
    }
}