/*
  .__       .           .     
  [__) _  _.|_  _ ._. _.|_  _ 
  |  \(/,(_.[ )(/,[  (_.[ )(/,...
     _     _                                          
    | |__ (_) __ _ _ __ __ _ _ __ ___  _ __ ___   ___ 
    | '_ \| |/ _` | '__/ _` | '_ ` _ \| '_ ` _ \ / _ \
    | |_) | | (_| | | | (_| | | | | | | | | | | |  __/
    |_.__/|_|\__, |_|  \__,_|_| |_| |_|_| |_| |_|\___|
             |___/                                    
	   
AUTEURS	: Aymeric & Ramazan
GROUPE	: RT (5)
DATE	: 21/03/2003
FICHIER	: arbre.cpp

*/


#include <iostream.h>
#include "arbre.h"
#include <math.h>


// ---------------------------------------------------------------- //
// ------------------------- CONSTRUCTEUR ------------------------- //
// ---------------------------------------------------------------- //

Arbre::Arbre()
{
	racine = NULL;
	nb_elt = 0;
}


// ---------------------------------------------------------------- //
// ------------------------- DESTRUCTEUR -------------------------- //
// ---------------------------------------------------------------- //

Arbre::~Arbre()
{
	liberearbre(racine);
}

void Arbre::liberearbre(Noeud * aux)
{
	if (aux == NULL) return;
	liberearbre(aux->fg);
	liberearbre(aux->fd);
	delete aux;
}


// ---------------------------------------------------------------- //
// -------------------------- FONCTIONS --------------------------- //
// ---------------------------------------------------------------- //

// cette fonction permet de comparer 2 bigrammes entres eux
// si m1 est superieur a m2, true est retourne, sinon false
bool Arbre::mot1PlusGrandmot2(Information mot1, Information mot2)
{
	if (mot1.m1 > mot2.m1) return(true);
	if (mot1.m1 < mot2.m1) return(false);
	if (mot1.m1 == mot2.m1)
	{
		if (mot1.m2 > mot2.m2) return(true);
		else return(false);
	}
}

// cette fonction permet de creer un nouveau Noeud
Noeud * Arbre::nouveau_Noeud(Noeud * d, Noeud * g, Information val)
{
	// creation d'un nouveau Noeud
	Noeud *pt=new Noeud;
	
	// enregistrement des caracteristiques du noeud
	pt->fg=g;
	pt->fd=d;
	pt->info.m1=val.m1;
	pt->info.m2=val.m2;
	pt->info.p=val.p;
	
	// on retourne le nouveau noeud nouvellement cree
	return (pt);
}


// cette fonction permet de trouver si l'information val est presente dans l'arbre
// elle retourne la probabilite trouvee, sinon retourne 0
float Arbre::presentRecur(Information val, long &fonda)
{
	Noeud * aux=new Noeud;
	aux=presentRecur_Noeud(racine,val,fonda);
	if (aux == NULL) return(0);
	return(aux->info.p);
}

Noeud * Arbre::presentRecur_Noeud(Noeud *aux, Information val, long &fonda)
{
	fonda++;
	if (aux == NULL) return(aux);
	if ((aux->info.m1 == val.m1) && (aux->info.m2 == val.m2)) return(aux);
	if (mot1PlusGrandmot2(val,aux->info)) return(presentRecur_Noeud(aux->fd,val,fonda));
	return(presentRecur_Noeud(aux->fg,val,fonda));
}


// cette fonction ajoute une feuille È l'arbre avec les informations passees en parametre
int Arbre::ajoute_feuille(Information val)
{
	racine=ajoute_feuille_Noeud(racine,val);
	nb_elt++;
	return(nb_elt);
}

Noeud * Arbre::ajoute_feuille_Noeud(Noeud *r, Information val)
{
	if (r == NULL) return (nouveau_Noeud(NULL,NULL,val));
	
	// si val < r->info on part dans le fils gauche
	// sinon on part dans le fils droit
	if (!mot1PlusGrandmot2(val,r->info)) r->fg=ajoute_feuille_Noeud(r->fg,val);
	else if (mot1PlusGrandmot2(val,r->info)) r->fd=ajoute_feuille_Noeud(r->fd,val);
	return r;
}