/**

 BINOME :
 <FABRE> <Maxime>
 <LEPOT> <Florian>

 FONCTIONS NON TRAITEES :
 <
 profSomMax
 listeFeuilles
 listeNoeudsG
 >

 SOURCES UTILISEES :
 <
 Aucune
 >

 */

#include <iostream>
#include <sstream>
#include <string>

#include "tp3util.h"

using namespace std;

/******************************************************************************
 1- ARBRES BINAIRES SIMPLES
 ******************************************************************************/

/**
 * Détermine si une structure est un arbre binaire.
 *
 * Paramètre r : noeud initial de la structure à examiner.
 *
 * Retourne : 1 si r est la racine d'un abre binaire et 0 sinon.
 *
 */
int estAB(noeud* r) {
    if(r == NULL)
        return 0;
    if(r->sag != NULL || r->sad != NULL)
        return 1;
    else return 0;
}

/**
 * Détermine si un arbre est parfait.
 *
 * Paramètre a : arbre à tester.
 *
 * Retourne : 1 si a est parfait et 0 sinon.
 *
 */
int estParfait(arbre a) {

    if(a == NULL) // Arbre vide
        return 0;

    if((a->sag == NULL && a->sad != NULL) || (a->sag != NULL && a->sad == NULL))
        return 0;

    if(a->sag != NULL && a->sad != NULL) // sad & sag sont définis : On continue le parcours de l'arbre
    {
        if(a->sag->sag != NULL && a->sag->sad != NULL && a->sad->sag != NULL && a->sad->sad != NULL)
        {
            estParfait(a->sag);
            estParfait(a->sad);
        }
        else if(a->sag->sag == NULL && a->sag->sad == NULL && a->sad->sag == NULL && a->sad->sad == NULL) return 1;
        else return 0;
    }
    else return 0;


}

/**
 * Détermine la plus petite des valeurs d'un arbre non vide.
 *
 * Paramètre a : arbre à examiner, obligatoirement non vide.
 *
 * Retourne : la plus petite des valeurs de a.
 *
 */
int min(arbre a) {
    if(a == NULL)
        return 0;

    int temp = 0, tmp_min = 0, min = 0;
    file f;
    arbre c;
    f = initFile();
    enfiler(&f, a);
    tmp_min = a->info;
    min = a ->info;

    while(!estFileVide(f))
    {
        defiler(&f, &c);
        temp = c->info;

        if(temp < tmp_min)
            min = temp;
        if(c->sag != NULL)
            enfiler(&f, c->sag);
        if(c->sad != NULL)
            enfiler(&f, c->sad);
        tmp_min = min;
    }
    return min;
}

/**
 * Détermine la plus grande des valeurs d'un arbre non vide.
 *
 * Paramètre a : arbre à examiner, obligatoirement non vide.
 *
 * Retourne : la plus grande des valeurs de a.
 *
 */
int max(arbre a) {
    if(a == NULL)
        return 0;

    int temp = 0, tmp_max = 0, max = 0;
    file f;
    arbre c;
    f = initFile();
    enfiler(&f, a);
    tmp_max = a->info;
    max = a ->info;

    while(!estFileVide(f))
    {
        defiler(&f, &c);
        temp = c->info;

        if(temp > tmp_max)
            max = temp;
        if(c->sag != NULL)
            enfiler(&f, c->sag);
        if(c->sad != NULL)
            enfiler(&f, c->sad);
        tmp_max = max;
    }
    return max;
}

/**
 * Calule la profondeur d'un arbre pour laquelle la somme des valeurs des noeuds
 * situés à cette profondeur est la plus grande.
 *
 * Paramètre a : arbre à examiner.
 *
 * Retourne : la profondeur cherchée ou -1 si l'arbre est vide.
 *
 */
int profSomMax(arbre a) {



    return 1;

}

/**
 * Etablit la liste des feuilles d'un arbre triée de droite à gauche.
 *
 * Paramètre a : arbre à examiner.
 *
 * Retourne : la liste cherchée.
 *
 */
liste listeFeuilles(arbre a) {

    liste l;

    return l;

}

/**
 * Etablit la liste des noeuds d'un arbre n'ayant qu'un fils : le fils gauche.
 * La liste est triée en ordre dgr.
 *
 * Paramètre a : arbre à examiner.
 *
 * Retourne : la liste cherchée.
 *
 */
liste listeNoeudsG(arbre a) {
    throw "non traité";
}

/**
 * Détruit un arbre. Chacun des ses noeuds est libéré.
 *
 * Paramètre a : arbre à détruire.
 *
 * Retourne : 1 si succès et 0 sinon.
 *
 */
int detruire(arbre* a) {

    if(a != NULL)
    {
        if((*a)->sag != NULL)
            detruire(&(*a)->sag);

        if((*a)->sad != NULL)
            detruire(&(*a)->sad);

        delete *a;
        *a = NULL;

    }
    else return 0;
    return 1;

}


/******************************************************************************
 2- ARBRES BINAIRES DE RECHERCHE (ABR)
 ******************************************************************************/

/**
 * Déterminer si un arbre est un ABR G <= R < D.
 *
 * Paramètre a : arbre à tester.
 *
 * Retourne : 1 si a est un ABR G <= R < D et 0 sinon.
 *
 */
int estABR(arbre a) {
    throw "non traité";
}

/**
 * Insère une valeur dans un ABR. L'ordre de l'abre est G <= R < D. Il peut
 * contenir plusieurs fois la même valeur.
 *
 * La fonction doit être écrite de façon itérative.
 *
 * Paramètre a : arbre dans lequel insérer.
 * Paramètre v : valeur à insérer.
 *
 * Retourne : 0 si la valeur v existait déjà, 1 si elle est insérée pour la
 * première fois, ou -1 si un des paramètres est incorrect.
 *
 */
int inserer(arbre* a, int v) {

    cout << "a->info : " << (*a)->info << endl;
    if(a == NULL)
	{
	    cout << "Condition 1" << endl;
	    (*a)->sag = new noeud;
		(*a)->sag->info = v;
		cout << "Fin condition 1" << endl;
	}
	else if((*a)->sag == NULL)
	{
	    cout << "Condition 2" << endl;
	    (*a)->sag = new noeud;
		(*a)->sag->info = v;
		cout << "Fin condition 2" << endl;
	}
	else if((*a)->sad == NULL)
	{
	    cout << "Condition 3" << endl;
	    (*a)->sad = new noeud;
		(*a)->sad->info = v;
		cout << "Fin condition 3" << endl;
	}
	else if((*a)->sag != NULL && (*a)->sad != NULL)
	{
	    cout << "Condition 4" << endl;
		if (v < (*a)->info)
		{
		    inserer(&(*a)->sag, v);
		    cout << "Apres insertion g" << endl;
		}
		else
		{
			inserer(&(*a)->sad, v);
		    cout << "Apres insertion d" << endl;
		}
        cout << "Fin condition 4" << endl;
	}
	else return 0;

    cout << "Return" << endl;
    return 1;
}

/**
 * Recherche une valeur dans un ABR. La fonction s'arrête à la première
 * occurrence trouvée.
 *
 * La fonction doit être écrite de façon récursive.
 *
 * Paramètre a : arbre à examiner.
 * Paramètre v : valeur à chercher.
 *
 * Retourne : le pointeur vers un noeud portant la valeur v, ou NULL si aucun
 * noeud ne porte la valeur v.
 *
 */
noeud* chercher(arbre a, int v) {
    throw "non traité";
}

/**
 * Supprime une valeur d'un ABR. La fonction ne supprime qu'une occurrence de la
 * valeur spécifiée.
 *
 * Paramètre a : arbre dans lequel supprimer.
 * Paramètre v : valeur à supprimer.
 *
 * Retourne : 0 si la valeur v n'est pas trouvée, 1 si la valeur v est trouvée,
 * ou -1 si un des paramètres est incorrect.
 *
 */
int supprimer(arbre* a, int v)  {
    throw "non traité";
}

/**
 * Crée un ABR à partir d'un abre simple. L'arbre d'origine n'est pas modifié.
 * Les noeuds de l'abre créé sont des copies des noeuds d'origine.
 *
 * Paramètre a : arbre à transformer en ABR.
 *
 * Retourne : l'ABR équivalent à a, sous forme de copie.
 *
 */
arbre copieABR(arbre a)  {
    throw "non traité";
}

/**
 * Inverse l'ordre d'un ABR. L'abre est modifié en place.
 *
 * Paramètre a : arbre à transformer en ABR.
 *
 * Retourne : 1 si succès et 0 sinon.
 *
 */
int inverser(arbre* a)  {
    throw "non traité";
}

/**
 * Détermine l'ensemble des ABR qu'on peut construire à partir d'une liste de
 * valeurs distinctes données. La fonction les retourne sous forme d'un tableau
 * alloué dynamiquement.
 *
 * Paramètre n : nombre de valeurs.
 * Paramètre t : tableau des valeurs.
 * Paramètre r : tableau d'arbres résultat.
 *
 * Retourne : le nombre d'éléments du tableau résultat.
 *
 */
int ensembleABR(int n, const int t[], arbre** r)  {
	throw "non traité";
}


/******************************************************************************
 3- ARBRES BINAIRES REPRESENTANT UNE EXPRESSIONS ARITHMETIQUE
 ******************************************************************************/

/**
 * Evalue un arbre binaire représentant une expression arithmétique. Chaque
 * noeud est :
 * - soit un opérande : il est stocké dans le champ info du noeud, dans les deux
 * 	 octets de poids faible.
 * - soit un opérateur (+, -, *, /, - unaire) : il est également stocké dans le
 *   champ info, mais dans le 3ieme octet de poids faible.
 *
 * Utiliser la macro ISOP() ("est opérateur") pour tester si le champ info est
 * opérateur ou non. S'il l'est, utiliser la macro V2O() ("de valeur à
 * opérateur") pour le convertir en caractère '+', '-', etc.
 *
 * Un exemple d'arbre représentant une expression arithmétique est donné dans
 * la fonction main. Il utilise la macro inverse de V20() : O2V().
 *
 * Paramètre a : arbre à examiner.
 * Paramètre r : résultat de l'évaluation.
 *
 * Retourne : 1 si succès et 0 sinon (l'arbre est incorrect).
 *
 */
int evaluer(arbre a, int* r) {
    throw "non traité";
}

/**
 * Ecrit en notation préfixe l'expression arithmétique que représente un arbre.
 *
 * Utiliser une variable r de type ostringstream (output string stream) : on
 * peut y écrire comme dans cout. Pour convertir le résultat final en string,
 * faire : r.str();
 *
 * Paramètre a : arbre à traduire, supposé correct syntaxiquement.
 *
 * Retourne : l'expression que a représente en notation préfixe.
 *
 */
string prefixe(arbre a) {
    throw "non traité";
}

/**
 * Ecrit en notation postfixe l'expression arithmétique que représente un arbre.
 *
 * Utiliser une variable r de type ostringstream (output string stream) : on
 * peut y écrire comme dans cout. Pour convertir le résultat final en string,
 * faire : r.str();
 *
 * Paramètre a : arbre à traduire, supposé correct syntaxiquement.
 *
 * Retourne : l'expression que a représente en notation postfixe.
 *
 */
string postfixe(arbre a) {
    throw "non traité";
}

/**
 * Ecrit en notation infixe l'expression arithmétique que représente un arbre.
 * Des parenthèses doivent être insérées quand elles sont nécessaires.
 *
 * Utiliser une variable r de type ostringstream (output string stream) : on
 * peut y écrire comme dans cout. Pour convertir le résultat final en string,
 * faire : r.str();
 *
 * Paramètre a : arbre à traduire, supposé correct syntaxiquement.
 *
 * Retourne : l'expression que a représente en notation infixe.
 *
 */
string infixe(arbre a) {
    throw "non traité";
}

/**
 * Construit l'arbre binaire représentant une expression arithmétique en
 * notation infixe. Les opérandes des chiffres (0 à 9), les opérateurs sont
 * +, -, *, /, avec des parenthèses. Les différents éléments de l'expression
 * sont donc des caractères uniques.
 *
 * Un squelette de la fonction est donné ci-dessous.
 *
 * Paramètre e : expression infixe à traduire.
 *
 * Retourne : l'arbre représentant e, ou NULL si e est incorrecte.
 *
 */
arbre arbrexp(const char* e) {
	// tant que la chaîne n'est pas terminée
	while (*e != '\0') {
	    if ('0' <= *e && *e <= '9') {
       	    // si le caractère est un opérande
       	    int opd = *e - '0';
       	    cout << "operande : " << opd << endl;

	    } else if (*e == '+' || *e == '-' || *e == '*' || *e == '/') {
       	    // si le caractère est un opérateur
       	    char opt = *e;
       	    cout << "opérateur : " << opt << endl;
       	    // mettre O2V(opt) dans le champ info

	    } else if  (*e == '(' || *e == ')') {
	        // si le caractère est une parenthèse
	        cout << "parenthèse : " << *e << endl;

	    } else if (*e != ' ') {
	        // si le caractère est inconnu
	        cout << "caractère inconnu : " << *e << endl;

	    }
	    // passer au caractère suivant
	    e += 1;
	}
    throw "non traité";
}


/******************************************************************************
 PROGRAMME DE TEST - Tester ici chaque fonction développée
 ******************************************************************************/

int main(int argc, char* argv[]) {

 	// Variables utilisées par tous les tests
	arbre a;

    /**************************************************************************
	 1- ARBRES BINAIRES SIMPLES
	 **************************************************************************/
	cout << "ARBRES BINAIRES SIMPLES\n";

	// Affichage d'arbres binaires simples
	cout << "\nAFFICHAGE arbres simples\n";

	a = arbret(15, (int[]) {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15});
	cout << "Affichage de l'arbre a : " << endl << chainea(a) << endl << endl;
	cout << "estAB(a) : " << estAB(a) << endl << endl;
	cout << "estParfait(a) : " << estParfait(a) << endl << endl;
	cout << "Valeur min de l arbre  : " << min(a) << endl;
    cout << "Valeur max de l arbre  : " << max(a) << endl;
    cout << "profSomMax(a) : " << profSomMax(a) << endl << endl;

	a = arbret(7, (int[]) {1, 2, 3, -4, -5, -6, 7});
	cout << "Affichage de l'arbre a : " << endl << chainea(a) << endl << endl;
	cout << "estAB(a) : " << estAB(a) << endl << endl;
	cout << "estParfait(a) : " << estParfait(a) << endl << endl;
	cout << "Valeur min de l arbre  : " << min(a) << endl;
    cout << "Valeur max de l arbre  : " << max(a) << endl;

    cout << "Insertion" << endl;
    inserer(&a, 3);
    cout << "Affichage de l'arbre a : " << endl << chainea(a) << endl << endl;
	cout << "estAB(a) : " << estAB(a) << endl << endl;
	cout << "estParfait(a) : " << estParfait(a) << endl << endl;
	cout << "Valeur min de l arbre  : " << min(a) << endl;
    cout << "Valeur max de l arbre  : " << max(a) << endl;

    detruire(&a);

    cout << "Affichage de l'arbre a detruit : " << endl << chainea(a) << endl << endl;


	/**************************************************************************
	 2- ARBRES BINAIRES DE RECHERCHE (ABR)
	 **************************************************************************/
	cout << "\nARBRES BINAIRES DE RECHERCHE\n";


	/**************************************************************************
	 3- ARBRES BINAIRES REPRESENTANT UNE EXPRESSION ARITHMETIQUE
	 **************************************************************************/
	cout << "\nARBRES BINAIRES REPRESENTANT UNE EXPRESSION ARITHMETIQUE\n";

	// Affichage d'arbres binaires représentant une expression arithmétique
	// (2 + 3) * (6 - 7)
	cout << "\nAFFICHAGE arbres expression arithmétique\n";
	a = arbret(7, (int[]) {O2V('*'), O2V('+'), O2V('-'), 2, 3, 6, 7});
	cout << "arbre a : " << endl << chainea(a) << endl;

	return 0;
}