/**

 BINOME :
 DAVID Aurélien
 RAMOS Adrien

 FONCTIONS NON TRAITEES :
 <
 Lister ici les fonctions non développées et/ou non testées. Exemple :
 - estAB : non développée
 - estABR : non testée
 >

 SOURCES UTILISEES :
 Aucune.

 */

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

#include "tp3util.h"

using namespace std;


/** Fonctions Utilitaires **/
bool estUneFeuille(noeud* a) {
    if(a == NULL) return false;
    if(a->sad == NULL && a->sag == NULL) return true;
    return false;
}
bool aOnlySag(noeud* a) {
    if(a == NULL) return false;
    if(a->sad == NULL && a->sag != NULL) return true;
    return false;
}

/******************************************************************************
 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) {
    //return !(r != NULL && r->sag != NULL && r->sad != NULL);
}

/**
 * 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) return 0;
    f = initFile();
    enfiler(&f,&a);
    bool ssArbrevide = false;
    do {
        defiler(&f,a);
    }*/

}

/**
 * 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) {
    pile p = initPile();
    empiler(&p,a);
    int min = a->info;
    while(!estPileVide(p)) {
        depiler(&p, &a);
        if(min > a->info) min = a->info;
        if(a->sad != NULL) empiler(&p,a->sad);
        if(a->sag != NULL) empiler(&p,a->sag);
    }
    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) {
    pile p = initPile();
    empiler(&p,a);
    int max = a->info;
    while(!estPileVide(p)) {
        depiler(&p, &a);
        if(max < a->info) max = a->info;
        if(a->sad != NULL) empiler(&p,a->sad);
        if(a->sag != NULL) empiler(&p,a->sag);
    }
    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) {
    if(a == NULL) return -1;
    int n = 0; // somme valeurs
    int p = 0; // profondeur
    int max = 0; // somme la plus grande
    int pmax = 0; // profondeur ayant la somme la plus grande
    file f = initFile();
    enfiler(&f,a);
    enfiler(&f,NULL); //On prend NULL comme marqueur entre les couches
    while(!estFileVide(f)) {
        defiler(&f,&a);
        if(a != NULL) { //si on a bien un noeud et non la marque
            n += a->info;
            if(a->sag != NULL) enfiler(&f,a->sag);
            if(a->sad != NULL) enfiler(&f,a->sad);
        }
        else { // on a la marque
            if(n > max) {
                max = n;
                pmax = p;
            }
            if(!estFileVide(f)) {
                n = 0;
                p++; //On passe à la profondeur suivante
                enfiler(&f,NULL); //On enfile la marque
            }
        }
    }
    return pmax;
}

/**
 * Etablit la liste des feuilles d'un abre triée de droite à gauche.
 *
 * Paramètre a : arbre à examiner.
 *
 * Retourne : la liste cherchée.
 *
 */
liste listeFeuilles(arbre a) {
    liste l = NULL;
    file f = initFile();
    enfiler(&f,a);
    while(!estFileVide(f)) {
        defiler(&f, &a);
        if(estUneFeuille(a)) {
            concatener(&l, singleton(a));
        }
        if(a->sag != NULL) enfiler(&f,a->sag);
        if(a->sad != NULL) enfiler(&f,a->sad);
    }
    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) {
   liste l = NULL;
   pile p = initPile();
   empiler(&p,a);
   while(!estPileVide(p)) {
        depiler(&p, &a);
        if(aOnlySag(a)) {
            concatener(&l, singleton(a));
        }
        if(a->sag != NULL) empiler(&p,a->sag);
        if(a->sad != NULL) empiler(&p,a->sad);
    }
    return l;
}

/**
 * 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) {
        detruire(&(*a)->sag);
        detruire(&(*a)->sad);
        delete(*a);
        *a = NULL; //On a libéré donc on pointe vers NULL
        return 1;
    }
    return 0;
}


/******************************************************************************
 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) {
    if(a == NULL ) return -1;
    int n = 1;
    if (*a == NULL) *a = singleton(v);
    else {
        noeud* pred = NULL; //retient l'adresse du maillon prédecesseur
        noeud* curr = NULL;
        curr = (*a);
        while( curr != NULL && n != 0) {
            pred = curr;
            if(v == curr->info) {
                n = 0;
            }
            else if(v <= curr->info) curr = curr->sag;
            else curr = curr->sad;
        }
        curr = singleton(v);
        if(v <= pred->info) pred->sag = curr;
        else pred->sad = curr;
    }
    return n;
}

/**
 * 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) {
    if(a == NULL) return NULL;
    if(a->info == v) return a;
    return (v < a->info ) ? chercher(a->sag,v) : chercher(a->sad,v);
}

/**
 * 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) {
    if(r == NULL) return 0;
    if(ISOP(a->info)) {
        if(a->sag == NULL || a->sad == NULL) return 0;
        int left, right;
        evaluer(a->sag, &left);
        evaluer(a->sad, &right);
        switch(a->info) {
            case O2V('+'): *r = left + right; break;
            case O2V('-'): *r = left - right; break;
            case O2V('*'): *r = left * right; break;
            case O2V('/'): *r = left / right; break;
        }
    } else
        *r = a->info;
    return 1;
}

/**
 * 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(7, (int[]) {1, 2, 3, 4, 5, 6, 7});
	cout << "arbre a : " << endl << chainea(a) << endl;
	a = arbret(7, (int[]) {1, 2, -3, 4, -5, 6, 7});
	cout << "arbre a : " << endl << chainea(a) << endl;

    cout << "\nESTAB arbres simples\n";
	cout << "\nESTPARFAIT arbres simples\n";

    cout << "\nMIN arbres simples\n";
    a = arbret(7, (int[]) {1, 2, 3, 4, 5, 6, 7});
	cout << "arbre a : " << endl << chainea(a) << endl;
	cout << "Min: " << min(a) << endl;
	a = arbret(7, (int[]) {1337, 42, 0, 2, 4, 8, 16});
	cout << "arbre a : " << endl << chainea(a) << endl;
	cout << "Min: " << min(a) << endl;

    cout << "\nMAX arbres simples\n";
    a = arbret(7, (int[]) {1, 2, 3, 4, 5, 6, 7});
	cout << "arbre a : " << endl << chainea(a) << endl;
	cout << "Max: " << max(a) << endl;
	a = arbret(7, (int[]) {1337, 42, 0, 2, 4, 8, 16});
	cout << "arbre a : " << endl << chainea(a) << endl;
	cout << "Max: " << max(a) << endl;

    cout << "\nPROFSOMMAX arbres simples\n";
    a = arbret(7, (int[]) {1, 2, 3, 4, 5, 6, 7});
    cout << "arbre a : " << endl << chainea(a) << endl;
    cout << "profSomMax: " << profSomMax(a) << endl;

    cout << "\nLISTEFEUILLES arbres simples\n";
    a = arbret(7, (int[]) {1, 2, 3, 4, 5, 6, 7});
    cout << "arbre a : " << endl << chainea(a) << endl;
    cout << "listeFeuilles: " << chainel(listeFeuilles(a)) << endl;

    cout << "\nLISTENOEUDSG arbres simples\n";
    a = arbret(14, (int[]) {1, 2, 3, 4, -5, 6, 7, 8,-9, 10 ,-11, 12,-13,14});
    cout << "arbre a : " << endl << chainea(a) << endl;
    cout << "listeNoeudsG: " << chainel(listeNoeudsG(a)) << endl;

    cout << "\nDETRUIRE arbres simples\n";
    a = arbret(7, (int[]) {1, 2, 3, 4, 5, 6, 7});
	cout << "arbre a : " << endl << chainea(a) << endl;
	cout << "Detruire: " << detruire(&a) << endl;
	cout << "arbre a : " << endl << chainea(a) << endl;
	cout << "Detruire: " << detruire(&a) << endl;

	/**************************************************************************
	 2- ARBRES BINAIRES DE RECHERCHE (ABR)
	 **************************************************************************/
	cout << "\nARBRES BINAIRES DE RECHERCHE\n";
    a = arbret(7, (int[]) {1, 2, 3, 4, 5, 6, 7});
	cout << "arbre a : " << endl << chainea(a) << endl;
	//cout << "estABR: " << estABR(a) << endl;

	cout << "\nESTABR arbres de recherche\n";

    cout << "\nINSERER arbres de recherche\n";
    a = NULL;
    inserer(&a,1);
    inserer(&a,1);
    inserer(&a,2);
    inserer(&a,2);
    inserer(&a,3);
    inserer(&a,3);
    inserer(&a,4);
    cout << "arbre a : " << endl << chainea(a) << endl;


	/**************************************************************************
	 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;
}