#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()
{
}

/****************************************/
/* 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()
{
    if(succ){
        delete(succ);
    }
}

/****************************************/
/* 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;
    }
    else{
        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)
{
    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()){
        queue->succ = x;
        x->pred =  queue;
        queue = x;
    }
    else{
        tete = 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)
{
    if(vide()){
        tete = queue = x;
    }
    else{
        if(tete->val > x->val){
            insertionEnTete(x);
        }
        else if(queue->val < x->val){
            insertionEnQueue(x);
        }
        else{
            maillon *p = tete;
            maillon *s;
            if(x!=NULL){
                while(p->val < x->val){
                    p = p->succ;
                }
                s = p->pred;
                s->succ = x;
                p->pred = x;
                x->pred = s;
                x->succ = p;
            }
        }
    }
}


/****************************************/
/* 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()
{
	if(!vide())
		tete->affichage();
}

/****************************************/
/* 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)
{
	if(!vide()){
	    if(tete == x){
	        tete = x;
	    }
	    else if(queue == x){
	        maillon *p = x->pred;
	        insertionEnTete(x);
	        p = queue;
	    }
	    else{
	        maillon *p = x->pred;
	        maillon *s = x->succ;
	        insertionEnTete(x);
	        p->succ = s;
	        s->pred = p;
	    }
	}
}


/****************************************/
/* 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)
{
	if(!vide()){
	    if(tete == x){
	        maillon *s = x->succ;
	        insertionEnQueue(x);
	        s = tete;
	    }
	    else if(queue == x){
	        queue = x;
	    }
	    else{
	        maillon *p = x->pred;
	        maillon *s = x->succ;
	        insertionEnQueue(x);
	        p->succ = s;
	        s->pred = p;
	    }
	}
}


/****************************************/
/* Objectif : Fusion de la liste appelante avec
une Liste L donnée en argument.
La liste appelante et la liste L doivent se confondre.
/* Entrées : L
/* Sorties  :
/* Complexité : 0(1)
/****************************************/

void liste::fusion(liste& L)
{
    if(!vide()){
        maillon *cpt = L.tete;
        while(cpt->succ!=NULL){
            this->insertionTri(cpt);
            cpt = cpt->succ;
        }
    }
}