#include <stdio.h>
#include <stdlib.h>
#include "string.h"
#include<conio.h>
#define N 100

typedef struct Pile
{
    int value;
    struct Pile  *prcd;
} Pile;

typedef struct
{
    char name[100], traduction[100];
    int left;
    int right;
} tree;
//algo pile
int pushPile(Pile ** p, int  valeur)
{
    Pile * nv_elem = NULL;
    nv_elem =(Pile * ) malloc(sizeof(Pile));
    if(nv_elem != NULL)
    {
        nv_elem->value =  valeur;
        nv_elem->prcd =  *p;
        *p = nv_elem;
        return 1;
    }

    return -1;

}

int * popPile(Pile **p)
{
    int   value;
    if((isEmpty_pile(*p) == 0))
    {
        if(p != NULL )
        {
            Pile * v = (*p)->prcd;
            value = (*p)->value;
            free(*p);
            *p = NULL;
            *p = v;

        }
    }

    return value;
}


Pile first(Pile *  p)
{
    Pile *t = NULL;
    t = p;
    while(t->prcd != NULL)
    {
        t = t->prcd;
    }
    return *t;
}
int isEmpty_pile(Pile *p)
{
    return (p == NULL) ? 1 : 0;
}
int insertTree(tree * array,int  * p, char * values, char * traduction)
{
    tree t;
    int i  = 0;
    values = strlwr(values);

    if(*p <= N)
    {
        if(searchTree(array,values,0,*p) == -1)
        {
            strcpy(t.name,values);
            strcpy(t.traduction,traduction);
            t.left  = -1;
            t.right = -1;
            array[*p] = t;
            if(*p > 0)
            {
                while(array[i].left !=  *p && array[i].right != *p)
                {
                    if(array[*p].name[0] >= array[i].name[0])
                    {
                        if(array[i].right == -1)
                        {
                            array[i].right = *p;
                        }
                        else
                        {
                            i = array[i].right;
                        }

                    }
                    else
                    {

                        if(array[i].left != -1)
                        {
                            i = array[i].left;
                        }
                        else
                        {

                            array[i].left = *p;
                        }
                    }
                }
            }

            (*p)++;
            return 0;
        }
        else
        {

            return -2;
        }

    }
    else
        return -1;

}

int searchTree(tree * array, char  * value, int i, int position )
{
    if(position > 0)
    {
        if(strcmp(value,array[i].name) == 0)
        {
            return i;
        }
        else
        {
            i = (strcmp(value,array[i].name) > 0 ? array[i].right  : array[i].left);
            if(i == -1)
                return -1;
            else
                searchTree(array,value,i,position);
        }
    }
    else
    {
        return -1;
    }

}

void displayTree(tree  * array, int i )
{
    if(i != -1)
    {
        displayTree(array,array[i].left);
        printf("%s\n",array[i].name);
        displayTree(array,array[i].right);
    }
}

/*void displayTreeIterator(tree * array )
{
    Pile   * p = NULL;
    tree   * t , * current = NULL;
    current = array;

    while(isEmpty_pile(p) == 0 || current != NULL )
    {

        if(current != NULL)
        {
            pushPile(&p,current);

            if(current->left == -1)
                current = NULL;
            else
                current = (array + current->left);

        }else
        {

            t = popPile(&p);

            printf("%s",t->name);

            if(t->right == -1)
                current = NULL;
            else
                current = (array + t->right);

        }
    }
}*/
void displayTreeIteratorWithoutPointer(tree * array )
{
    Pile   * p = NULL;
    int t, current;
    current = 0;

    while(isEmpty_pile(p) == 0 || (current != -1)  )
    {

        if(current != -1)
        {
            pushPile(&p,current);

            if(current == -1)
                current = -1;
            else
                current = array[current].left;

        }
        else
        {

            t = popPile(&p);
            printf("Mot : %s \n",array[t].name);
            printf("Traduction : %s \n",array[t].traduction);
            printf("-------------------------\n");

            if(t == -1)
                current = -1;
            else
            {
                current = array[t].right;
            }


        }
    }
}

int deleteTree(tree * array, int *p, int position)
{
    int i = 0,r ;
    tree newArray[100];
    r = 0;
    for(i = 0; i<*p; i++)
    {
        if(i != position)
            insertTree(newArray,&r,array[i].name,array[i].traduction);
    }
    for(i = 0; i<r; i++)
    {
        strcpy(array[i].name,newArray[i].name);
        strcpy(array[i].traduction,newArray[i].traduction);
        array[i].right = newArray[i].right;
        array[i].left = newArray[i].left;
    }
    (*p)--;
}
void ajouter(tree * menu, int * position)
{
    char mot[100],traduction[100];
    clrscr();
    printf("Entrer le mot : \n");
    scanf("%s",&mot);
    printf("Entrer le traduction : \n");
    scanf("%s",&traduction);
    if(insertTree(menu,position,mot,traduction) != 0)
    {
        printf("Le mot existe deja .");
        getch();
    }

    clrscr();
}
void rechercher(tree * menu, int  position)
{
    char mot[100];
    int rech;
    clrscr();
    printf("Veuillez entrez le mot : \n");
    scanf("%s",&mot);
    rech = searchTree(menu,&mot,0,position);
    if( rech == -1)
    {
        printf("Le mot n'existe pas .");
        getch();

    }
    else
    {
        clrscr();
        printf("Mot : %s\n",menu[rech].name);
        printf("Traduction : %s\n",menu[rech].traduction);
        getch();
    }

    clrscr();
}

void modifier(tree * menu, int  position)
{
    char mot[100], traduction[100];
    int rech;
    clrscr();
    printf("Veuillez entrez le mot : \n");
    scanf("%s",&mot);
    rech = searchTree(menu,&mot,0,position);
    if( rech == -1)
    {
        printf("Le mot n'existe pas .");
        getch();

    }
    else
    {
        clrscr();
        printf("Nouvelle traduction : \n");
        scanf("%s",&traduction);
        strcpy(menu[rech].traduction,traduction);
        printf("Modification effectuée ! ");
        getch();
    }

    clrscr();

}
void supprimer(tree * menu, int   * position)
{

    char mot[100] ;
    int rech;
    clrscr();
    printf("Veuillez entrez le mot : \n");
    scanf("%s",&mot);
    rech = searchTree(menu,&mot,0,*position);
    if( rech == -1)
    {
        printf("Le mot n'existe pas .");
        getch();

    }
    else
    {
        clrscr();
        deleteTree(menu,position,rech);
        printf("Suppression effectuee ! ");
        getch();
    }

    clrscr();
}

void save(tree * tab, int  position)
{

    char nom[100];
    int i =0;
    int rech;
    FILE *file;
    clrscr();
    printf("Veuillez entrez le nom du fichier : \n");
    scanf("%s",&nom);
    file = fopen(strcat(nom,".txt"), "wt");
    if(file)
        remove(strcat(nom,".txt"));

    for( i; i<position; i++)
    {
        fprintf(file,"%s %s %d %d\n",tab[i].name,tab[i].traduction,tab[i].left,tab[i].right);
    }
    fclose(file);
    printf("Fichier sauvgarder !");
    getch();
    clrscr();
}

void charger(tree * tab, int *position )
{
    int i =0,left,right;
    char nom[100],traduction[100];
    FILE * file;
    clrscr();
    printf("Veuillez entrez le nom du fichier : \n");
    scanf("%s",&nom);


    file = fopen(strcat(nom,".txt"),"rt");

    if(file == NULL)
    {
        printf("Le fichier n'existe pas !");
        getch();
    }
    else
    {
        while(fscanf(file,"%s %s %d %d",&nom,&traduction,&left,&right)!= EOF)
        {
            tab[i].left = left;
            tab[i].right = right;
            strcpy(tab[i].name,nom);
            strcpy(tab[i].traduction,traduction);
            i++;
        }
        *position = i;
        printf("Chargement effectuee!");
        getch();

    }

    fclose(file);
    clrscr();
}

int main()
{
    int menu = 0, position = 0,i;
    tree tab[100];


    do
    {
        printf("1 - Ajouter un mot\n");
        printf("2 - Rechercher un mot\n");
        printf("3 - Modifier un mot\n");
        printf("4 - Supprimer un mot\n");
        printf("5 - Afficher par ordre alphabetique\n");
        printf("6 - Afficher la structure interne\n");
        printf("7 - Sauvgarder un fichier\n");
        printf("8 - Charger un fichier\n");
        printf("9 - Sortir \n");
        printf("Choix : ");
        scanf("%d",&menu);
        if(menu == 1)
        {
            ajouter(tab,&position);
        }
        else if(menu == 2)
        {
            rechercher(tab,position);
        }
        else if(menu == 3)
        {
            modifier(tab,position);
        }
        else if(menu == 4)
        {
            supprimer(tab,&position);
        }
        else if(menu == 5)
        {
            clrscr();
            if(position > 0)
                displayTreeIteratorWithoutPointer(tab);
            else
                printf("Arbre vide !");
            getch();
            clrscr();

        }
        else if(menu == 6)
        {
            clrscr();
            if(position > 0)
            {

                for(i = 0; i<position; i++)
                {
                    printf("Mot : %s\n",tab[i].name);
                    printf("Traduction : %s\n",tab[i].traduction);
                    printf("Droit : %d\n",tab[i].right);
                    printf("Gauche : %d\n",tab[i].left);
                    printf("--------------------------\n");

                }
            }
            else
                printf("Arbre vide !");
            getch();
            clrscr();

        }
        else if(menu == 7)
        {
            save(tab,position);
        }
        else if(menu == 8)
        {
            charger(tab,&position);
        }

    }
    while( menu == 1  || menu == 2 || menu == 3 || menu == 4 || menu == 5 || menu == 6 || menu == 7 || menu == 8);
    return 0;
}