/************************************************************************/
/* Auteur : S. Gueye							*/
/* TP : Arbres Binaires	de Recherche					*/
/* Date dernière maj : 05/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)
{
    // !!!!!  A FAIRE  !!!!! //
    noeud* x = r;
    while(x!=NULL && cle!=x->cle){
        if(cle < x->cle){
            x = x->fg;
        }
        else{
            x = x->fd;
        }
    }
    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)
{
    // !!!!!  A FAIRE  !!!!! //
    noeud* x = r;
    if(x == NULL){
        r = new noeud (cle);
        return(true);
    }
    while(1){
        if(cle == x->cle){
            return(false);
        }
        if(cle< x->cle){
            if(x->fg == NULL){
                x->fg = new noeud (cle);
                x->fg->pere = x;
                return(true);
            }
            else{
                x = x->fg;
            }
        }
        else{
            if(x->fd == NULL){
                x->fd = new noeud (cle);
                x->fd->pere = x;
                return(true);
            }
            else{
                x = x->fd;
            }
        }
    }
}


/****************************************/
/* Objectif : Recherche de l'adresse du noeud
de plus petite cle dans l'arbre de racine x
/****************************************/
noeud* ABR::minimum(noeud* x)
{
    // !!!!!  A FAIRE  !!!!! //
    noeud* tmp = x;
    while(tmp->fg!=NULL){
        tmp=tmp->fg;
    }
	return(tmp);
}

/****************************************/
/* Objectif : Recherche de l'adresse du noeud
de plus grande cle dans l'arbre de racine x
/****************************************/
noeud* ABR::maximum(noeud* x)
{
    noeud* tmp = x;
    while(tmp->fd!=NULL){
        tmp=tmp->fd;
    }
	return(tmp);
}


/****************************************/
/* 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 FAIRE  !!!!! //
    noeud* tmp = x;
    if(tmp->fg!=NULL)
	{
		return(maximum(tmp->fg));
	}
	noeud* y=tmp->pere;
	while((y!=NULL)&&(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 FAIRE  !!!!! //
    noeud* tmp = x;
    if(tmp->fd!=NULL)
	{
		return(minimum(tmp->fd));
	}
	noeud* y=tmp->pere;
	while((y!=NULL)&&(tmp==y->fd))
	{
		tmp=y;
		y=y->pere;
	}
	return(y);
}