#ifndef _ABR_
#define _ABR_
#include <cstring>
#include <iostream>
using namespace std;

class ABR
{
	private:
		struct Tcell {
						int clef;
						char * infos;
						Tcell * fg;
						Tcell * fd;
				 	};
		Tcell * racine;
		void pvid(Tcell *);
	
	public:
		ABR();
		~ABR();
		bool ajouter(char *, int);
		bool supprimer(int);
		char * valeur(int);
		void vider();
};


ABR::~ABR()
{
	vider();
}

ABR::ABR()
{
	racine = NULL;
}


void ABR::vider()
{
	pvid(racine);
	racine = NULL;
}

void ABR::pvid(Tcell * noeud)
{
	if(noeud != NULL)
	{
		pvid(noeud->fg);
		pvid(noeud->fd);
		delete noeud;
	}
}	


bool ABR::supprimer(int telclef)
{
	Tcell * noeud = racine;
	Tcell * pnoeud = NULL;
	Tcell * tmp, * ptmp, * pptmp;
	
	while(noeud != NULL && noeud->clef != telclef)
	{
		if(telclef < noeud->clef)
		{
			pnoeud = noeud;
			noeud = noeud->fg;
		}
		else
		{
			pnoeud = noeud;
			noeud = noeud->fd;
		}
	}
	if(noeud == NULL)
		return false;
	else if(noeud->fg == NULL && noeud->fd == NULL)
	{
		if(pnoeud != NULL)
		{
			if(pnoeud->fg == noeud)
				pnoeud->fg = NULL;
			else
				pnoeud->fd = NULL;
		}
		else
			racine = NULL;
		delete noeud;
	}
	else
	{
		pptmp = noeud;
		if(noeud->fg != NULL)
		{
			tmp = noeud->fg;
		}
		else
			tmp = noeud;
		ptmp = tmp;
		while(tmp != NULL && tmp->fd != NULL)
		{
			pptmp = ptmp;
			ptmp = tmp;
			tmp = tmp->fd;
		}
		if(pptmp->fg == ptmp)
			pptmp->fg = NULL;
		else
			pptmp->fd = NULL;
		noeud->clef = ptmp->clef;
		delete noeud->infos;
		noeud->infos = ptmp->infos;
		delete ptmp;
	}
return true;
}
	
	
	

bool ABR::ajouter(char * telinfos, int telclef)
{
	Tcell * noeud = racine;
	Tcell * pnoeud = NULL; /* élément père de noeud */
	
	while(noeud != NULL)
	{
		if(telclef < noeud->clef)
		{
			pnoeud = noeud;
			noeud = noeud->fg;
		}
		else if(telclef > noeud->clef)
		{
			pnoeud = noeud;
			noeud = noeud->fd;
		}
		else /* Si telclef == noeud->clef */
			return false;
	}
	noeud = new Tcell;
	noeud->clef = telclef;
	noeud->infos = strdup(telinfos);
	noeud->fd = NULL;
	noeud->fg = NULL;
	if(pnoeud != NULL && telclef < pnoeud->clef)
		pnoeud->fg = noeud;
	else if(pnoeud != NULL && telclef > pnoeud->clef)
		pnoeud->fd = noeud;
	else /* Si pnoeud est null */
		racine = noeud;
	return true;
}

char * ABR::valeur(int telclef)
{
	Tcell * noeud = racine;
	
	while(noeud != NULL && noeud->clef != telclef)
	{
		
		if(telclef < noeud->clef)
			noeud = noeud->fg;
		else
			noeud = noeud->fd;
	}
	if(noeud == NULL)
		return NULL;
	else
		return noeud->infos;
}

#endif