/************************************************************************/
/* Auteur : S. Gueye							*/
/* TP : Arbres Binaires	de Recherche					*/
/* Date dernière maj : 18/11/2019					*/
/************************************************************************/

#include <iostream>
#include <fstream>
#include "ABR.h"

using namespace std;

/****************************************/
/* Objectif : Constructeur d'un noeud dont les fils sont NULL
/* Entrées : entier x
/* Complexité : 0(1)
/****************************************/
noeud::noeud(int x)
{
	cle = x;
	fg = fd = pere =  NULL;
}


/****************************************/
/* Objectif : Destructeur d'un noeud
/****************************************/
noeud::~noeud()
{
	if(fg)
		delete(fg);
	if(fd)
		delete(fd);
}

/****************************************/
/* Objectif : Constructeur d'un ABR
/****************************************/
ABR::ABR()
{
	r = NULL;
}


/****************************************/
/* Objectif : Constructeur d'un ABR
/****************************************/
ABR::ABR(char* filename)
{
    r = NULL;
	ifstream file(filename);
	int n,tmp,cpt = 0;

	file >> n;
	for(int i = 0; i < n ; i++){
		file >> tmp;
		if(insertion(tmp))
			cpt++;
	}

	cout << "Nombre d'éléments insérés = " << cpt << endl;
	file >> e;
	infixe(r);
	cout << endl;
	file.close();
}



/****************************************/
/* Objectif : Destructeur d'un ABR
/****************************************/
ABR::~ABR()
{
	if(r)
		delete(r);
}

/****************************************/
/* Objectif : Accesseur à la racine r
/****************************************/
noeud* ABR::root()
{
	return(r);
}

/****************************************/
/* Objectif : Accès à e (un élément qui sera recherché)
/****************************************/
int ABR::gete()
{
	return(e);
}

/****************************************/
/* Objectif : Parcours infixe
/****************************************/
void ABR::infixe(noeud* x)
{
	if(x){
		infixe(x->fg);
		cout << " " << x->cle;
		infixe(x->fd);
	}
}

/****************************************/
/* Objectif : Recherche de la valeur cle.
La méthode retourne l'adresse de "cle" s'il existe
ou NULL sinon.
/****************************************/
noeud* ABR::recherche(int cle)
{
	noeud*  res = NULL;
	noeud* x = r;
	bool trouve = false;
	while(x && (!trouve)){
		if(x->cle < cle)
			x = x->fd;
			else
		if(x->cle > cle)
			x = x->fg;
		else
			trouve = true;
	}

	return(x);
}

/****************************************/
/* Objectif : Insertion de "cle" dans l'arbre
/* "cle" étant un identifiant unique, il faudra vérifier qu'il
n'existe pas déjà dans l'arbre, auquel cas il ne faudra pas l'insérer.

La méthode doit renvoyer "vrai" si l'insertion a pu être faite
et "faux" sinon.
/****************************************/
bool ABR::insertion(int cle)
{
	noeud * y;
	noeud* x = r;
	noeud* pere = NULL;
	bool existe = false;

	while(x != NULL){

		pere = x;
		if(cle < x->cle)
			x = x->fg;
		else
		if(cle > x->cle)
			x = x->fd;
		else{
			existe = true;
			x = NULL;
		}
	}

	if(! existe){
		y = new noeud(cle);

		if(pere == NULL)
			r  = y;
		else{
			y->pere = pere;
			if(cle < pere->cle)
				pere->fg = y;
			else
				pere->fd = y;
		}
	}

	return(!existe);
}


/****************************************/
/* Objectif : Recherche de l'adresse du noeud
de plus petite cle dans l'arbre de racine x
/****************************************/
noeud* ABR::minimum(noeud* x)
{
    // !!!!!  A recopier du précédent TP  !!!!! //
    noeud* y = x;
    if (r == NULL)
    {
        return (NULL);
    }
	else
	{
	    while (y->fg != NULL)
	    {
	        y = y->fg;
	    }
	    return(y);
	}
}

/****************************************/
/* Objectif : Recherche de l'adresse du noeud
de plus grande cle dans l'arbre de racine x
/****************************************/
noeud* ABR::maximum(noeud* x)
{
    // !!!!!  A recopier du précédent TP  !!!!! //
    noeud* y = x;

    if (r == NULL)
    {
        return (NULL);
    }
	else
	{
	    while (y->fd != NULL)
	    {
	        y = y->fd;
	    }
	    return(y);
	}
}


/****************************************/
/* Objectif : Recherche de l'adresse du noeud
predecesseur de x dans l'arbre de racine r
(l'attribut "r" de l'objet appelant).
/****************************************/
noeud* ABR::predecesseur(noeud* x)
{
    // !!!!!  A recopier du précédent TP  !!!!! //
    noeud* tmp = x;
    if (tmp->fg != NULL)
    {
        return (maximum(tmp->fg));
    }
    noeud *y = tmp->pere;
    while (y != NULL and tmp == y->fg)
    {
        tmp = y;
        y = y->pere;
    }
    return(y);
}

/****************************************/
/* Objectif : Recherche de l'adresse du noeud
predecesseur de x dans l'arbre de racine r
(l'attribut "r" de l'objet appelant).
/****************************************/
noeud* ABR::successeur(noeud* x)
{
    // !!!!!  A recopier du précédent TP  !!!!! //
    noeud* tmp = x;

    if (tmp->fd != NULL)
    {
        return (minimum(tmp->fd));
    }
    noeud *y = tmp->pere;
    while (y != NULL and tmp == y->fd)
    {
        tmp = y;
        y = y->pere;
    }
    return(y);
}

/****************************************/
/* Objectif : Deplacer le sous-arbre de racine v
à l'emplacement du sous-arbre de racine u.
u est supposé non nul
/****************************************/
void ABR::deplacer(noeud* u, noeud* v)
{
    // !!!!!  A FAIRE  !!!!! //
    if (u->pere == NULL)
    {
        r = v;
    }
    else
    {
        if (u == u->pere->fg)
        {
            u->pere->fg = v;
        }
        else
        {
            u->pere->fd = v;
        }
    }
    if (v != NULL)
    {
        v->pere = u->pere;
    }
}

/****************************************/
/* Objectif : Suppression du noeud x supposé existant
dans l'arbre
/****************************************/
void ABR::suppression(noeud* x)
{
    // !!!!!  A FAIRE  !!!!! //
    if (x->fg == NULL)
    {
        deplacer(x, x->fd);
    }
    else
    {
        if (x->fd == NULL)
        {
            deplacer(x, x->fg);
        }
        else
        {
            noeud* y = successeur(x);
            if (y->pere != x)
            {
                deplacer(y, y->fd);
                y->fd = x->fd;
                y->fd->pere = y;
            }
            deplacer(x, y);
            y->fg = x->fg;
            y->fg->pere = y;
        }
    }
}