#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "abr.h"


/*
    struct abr {
        struct abr* gauche; 
        int valeur;
        struct abr* droit;
};
*/
static struct abr* new_feuille (int x){   
    
    struct abr* F;

    F = (struct abr*)malloc (sizeof (struct abr));
    F->gauche = NIL;
    F->valeur = x;
    F->droit = NIL;
    return F;
}


struct abr* ajout_abr_rec (int x, struct abr* A){
    if (A == NIL)
        return new_feuille (x);
    else if (x < A->valeur)
        A->gauche = ajout_abr_rec (x, A->gauche);
    else
        A->droit = ajout_abr_rec (x, A->droit);
    return A;
}

int max( int a, int b){
 
    if(a>b){
        return a;        
    }
    return b;
}

int hauteur_abr( struct abr* A){
   
    if(A == NIL){
        return -1;
    }
    return max(hauteur_abr(A->gauche),hauteur_abr(A->droit))+1;
    
}


bool recherche_abr_rec (int x, struct abr* A){
    bool b = false;
    if (A == NIL){
        return b;
    } else if ( x == A->valeur ){
        return true;
    } else if (x < A->valeur){
        b=recherche_abr_rec (x, A->gauche);
    } else{
        b=recherche_abr_rec (x, A->droit);
    }
    return b;
}


static void affiche_abr (struct abr* A){
    if( A!= NIL){
     affiche_abr(A->gauche);
     printf("- %d ", A-> valeur);
     affiche_abr(A->droit);
    }

}


void imprime_abr (struct abr* A){
    printf("Valeurs de l'arbre: \n");
    affiche_abr(A);
    printf(" -\n");
}


static void affiche_abrV2 (struct abr* A, int profondeur){
    if( A!= NIL){
        int i = 0;
        for(i=0; i<=profondeur; i++){
             printf("\t");
        }
       
        printf("%d\n ", A-> valeur);
        affiche_abrV2(A->droit, profondeur+1);
        affiche_abrV2(A->gauche, profondeur+1);
    }

}

void imprime_abrV2 (struct abr* A){
    printf("Valeurs de l'arbre: \n");
    affiche_abrV2(A, 0);
    printf("\n");
}

void clear_abr (struct abr* A)
{
    if (A != NIL)
    {   clear_abr (A->gauche);
        clear_abr (A->droit);
        free (A);
    }
}

void imprimeArbreDot( struct abr* A, FILE* f){
   if(A->gauche != NIL){
        fprintf(f,"%d -> %d [label=\"gauche\"];\n", A->valeur, A->gauche->valeur);
        imprimeArbreDot(A->gauche,f);
   } 
   if(A->droit != NIL){
        fprintf(f,"%d -> %d [label=\"droit\"];\n", A->valeur, A->droit->valeur);
        imprimeArbreDot(A->droit,f);
   }
}


void imprimeDot( struct abr* A){
    FILE* f;
    f = fopen("ABR.dot", "w");
    fprintf(f,"digraph G {\n");
    if(A==NIL){
        fprintf(f,"NIL\n");
    }else if (A->gauche == NIL && A->droit == NIL){
        fprintf(f,"%d\n", A->valeur);
    }else {
        imprimeArbreDot(A,f);
    }
    fprintf(f,"}\n");
    fclose(f);
    system("dot -Tpdf ABR.dot -GRANKDIR=LR -o ABR.pdf");
    system("evince ABR.pdf &");
}