#include <stdio.h>
  #include <stdlib.h>

  #include <stdbool.h>

  #include <string.h>

  
  
  typedef struct cell* ptarbre;
  typedef struct cell* ptcellule;
  
  typedef struct cell {

    char lettre;

    ptarbre fils; // Descend d'un étage dans le mot (lettre suivante du mot)

    ptcellule suivant; // Lettre suivante stockée à l'étage arbre en (ieme position)

    bool fin_mot;

  } cell;
  
  /* Pas utile 
  void init_dico()
  {
    ptarbre arbre;
    arbre=NULL;
  }
  */

  ptarbre rech(ptarbre arbre, char lettre)

  // recherche une lettre en ième position (correspondant à arbre)

  // Retourne l'adresse de l'arbre contenant la lettre à cette position

  {

    printf("rech adr abre deb %p \n", arbre);

    if (arbre!=NULL)

      {

        printf("arbre lettre %c \n", arbre->lettre);
        while ((arbre->suivant!=NULL) && (arbre->lettre != lettre))
  	{

  	   printf("lettre : %c lettre cherchee : %c adr arbre %p \n", arbre->lettre,lettre, arbre);

  	  arbre=(arbre->suivant);

  	  printf("adr arbre while %p \n", arbre);

  	}

      }

    printf("retourne adr %p lettre %c\n", arbre, arbre->lettre);

    return arbre;
  }

  
  void init_dico(ptarbre* parbre, char lettre)

  {

    (*parbre)=malloc(sizeof(cell));

    (*parbre)->fils=malloc(sizeof(cell));

    (*parbre)->suivant=NULL;
    (*parbre)->lettre=lettre;
    (*parbre)->fin_mot=false;
  }
  
  void ajout_dico_tete(ptarbre *parbre, char lettre)
  {
    (*parbre)->fils=malloc(sizeof(cell));

    (*parbre)->fils->suivant=NULL;

    (*parbre)->suivant=NULL;

    (*parbre)->lettre=lettre;

    (*parbre)->fin_mot=false;

    printf("ajout dico tete adr %p\n",(* parbre));

  }
  

  void ajout_dico(ptarbre *parbre, ptarbre *parbresuiv, char lettre)

  {

    *parbresuiv=malloc(sizeof(cell));
    (*parbre)->suivant=*parbresuiv; // On relie la nouvelle lettre à l'avant dernière lettre

    (*parbresuiv)->fils=malloc(sizeof(cell));
    (*parbresuiv)->fils->suivant=NULL;

    (*parbresuiv)->suivant=NULL;

    (*parbresuiv)->fin_mot=false;

    (*parbre)->lettre=lettre;
    printf("ajout lettre : %c à %p \n",(*parbre)->lettre, parbre);

  }
  

  void affiche_dico(ptarbre arbre, int n_lettre, char mot[])

  // affiche tout le dictionnaire à partir de l'arbre (donc le numéro de lettre) sélectionné
  {

    if(arbre == NULL)
      {
      return;
      }
    else
      {

        if (arbre->fils != NULL)

  	{

  	  printf("%c",arbre->lettre);
  	  mot[n_lettre]=arbre->lettre;
  	  n_lettre++;
  	  affiche_dico(arbre->fils,n_lettre,mot);

  	}

         printf("\n");

        if (arbre->suivant != NULL)
  	{
  	   printf("%s",mot);
  	  affiche_dico(arbre->suivant, n_lettre, mot);
  	}
        mot[n_lettre]=0;
        n_lettre--;
  	  
      }	

  }

  
  void free_tree(cell **ptr_tree)
  {
  	 if ((*ptr_tree)==NULL)
      printf("L'arbre est vide\n"); 
    else
      {
        if ((*ptr_tree)->fils!=NULL)
  	free_tree(&((*ptr_tree)->fils));
        if ((*ptr_tree)->suivant!=NULL)
  	free_tree(&(*ptr_tree)->suivant);
  	 free(*ptr_tree);
      }
  }
  

  void cons_arbre(ptarbre *parbre_originel, ptarbre *parbre, ptarbre *parbre_prec, FILE* fp)
  {
    
    char c,t;
    ptarbre rec;
     while (fscanf(fp,"%c",&c)!= EOF) // lecture de tout le fichier
      {
        printf("c= %c \n",c);
        if (c != '\n')
  	{
  	  if ((*parbre_originel)==NULL) // Cas où c'est le premier mot premiere lettre
  	    {
  	      printf("arbre ori =NULL \n");
  	      init_dico(parbre_originel,c);
  	      printf("lettre arbre :%c \n",(*parbre_originel)->lettre);
  	      (*parbre_prec)=(*parbre_originel);
  	      (*parbre)=(*parbre_originel)->fils;
  	    }
  	  else if ((*parbre)==NULL) // premier mot de l'arbre
  	    {
  	      printf("arbre null\n");
  	      init_dico(parbre,c);
  	      (*parbre)=(*parbre)->fils;
  	    }
  	  
  	  else // Cas où le dico n'est pas vide
  	    {
  	      // printf("lettre arbre :%c \n",arbre->lettre);
  	      printf(" dico pas vide c: %c\n", c);
  	      rec=rech((*parbre),c);
  	      if (rec->lettre!=c)
  		{
  
  		  if (rec==(*parbre)) // 1ere lettre de la liste
  		    {
  		      printf("1ere lettre\n");
  		      ajout_dico_tete(parbre,c);
  		      (*parbre)=(*parbre)->fils;
  		    }
  		      
  		  if (rec->suivant==NULL)
  		    {
  		 
  		      printf("rech suiv  = NUll \n");
  		      ajout_dico(&(rec),&(rec->suivant),c);
  
  		      // printf("ajout de : %c à %p et fils :%p\n", rec->lettre, rec, rec->fils);
  		      (*parbre_prec)=(*parbre);
  		      (*parbre)=rec->suivant->fils;
  		    }
  		}
  	  
  	      else
  		{// Cas où le début du mot existe déjà et qu'on le complète
  		  //printf("rech lettre =lettre rec lettre %c rec lettre fils %c%c\n", rec->lettre, rec->fils->lettre);
  		  // printf("adr rec %p adr rec fils %p\n", rec, rec->fils);
  		  (*parbre_prec)=(*parbre);
  		  (*parbre)=rec->fils; // On va à l'étage d'après pour former le mot dans l'arbre
  		  //
  		}
  	    
  	      
  	    }
  	}
        else {
  	printf("c==n \n");
  	if ((*parbre_originel)!=NULL)
  	  {
  	    printf("%c \n", (*parbre_prec)->lettre); 
  	    (*parbre_prec)->fin_mot=true; // Cette lettre est la dernière du mot
  	  }
  	//	affiche_dico((*parbre_originel),n_lettre,mot);
  	printf("remise à 0\n");
  	printf("avant egal arbre %p arbre ori %p \n", (*parbre), (*parbre_originel));
  	(*parbre)=(*parbre_originel); // On revient en haut de l'arbre pour commencer un nouveau mot
  	printf("apres egal arbre %p arbre ori %p \n", (*parbre), (*parbre_originel));
        }
        //arbre=arbre_originel; 
      }
  }

  
  int main()
  {

    char mot[30];
    int n_lettre=0;

    ptarbre arbre_originel,arbre,arbre_prec;

    arbre_originel=NULL;

    printf("adr arbre _ori %p\n", &arbre_originel);

    arbre=NULL;

    // Ouvrir fichier
    FILE *fp = fopen("words1.txt","r");
    if (fp==NULL)
      printf("words1 inaccessible \n",fp);
    else
      printf("words1 accessible \n",fp);

    cons_arbre(&arbre_originel, &arbre, &arbre_prec,fp);
    /* while (fscanf(fp,"%c",&c)!= EOF) // lecture de tout le fichier

      {

        if (c != '\n')
  	{

  	  if (arbre_originel==NULL) // Cas où c'est le premier mot premiere lettre

  	    {

  	      printf("arbre =NULL \n");
  	      init_dico(&arbre_originel,c);

  	      printf("lettre arbre :%c \n",arbre_originel->lettre);
  	      arbre_prec=arbre_originel;
  	      arbre=arbre_originel->fils;

  	    }
  	  else if (arbre==NULL) // premier mot de l'arbre
  	    {
  	      init_dico(&arbre,c);
  	      arbre=arbre->fils;
  	    }

  	  else // Cas où le dico n'est pas vide

  	    {

  	      // printf("lettre arbre :%c \n",arbre->lettre);

  	      printf(" c: %c\n", c);
  	      rec=rech(arbre,c);

  	      if (rec->lettre!=c)

  		{

  
  		  if (rec==arbre) // 1ere lettre de la liste
  		    {
  		      printf("1ere lettre\n");
  		      ajout_dico_tete(&arbre,c);
  		      arbre=arbre->fils;
  		    }
  		      
  		  if (rec->suivant==NULL)
  		    {

  		      printf("rech suiv  = NUll \n");
  		      ajout_dico(&(rec),&(rec->suivant),c);
  
  		      // printf("ajout de : %c à %p et fils :%p\n", rec->lettre, rec, rec->fils);
  		      arbre_prec=arbre;
  		      arbre=rec->suivant->fils;
  		    }

  		}

  	  
  	      else
  		{// Cas où le début du mot existe déjà et qu'on le complète

  		  //printf("rech lettre =lettre rec lettre %c rec lettre fils %c%c\n", rec->lettre, rec->fils->lettre);
  		  // printf("adr rec %p adr rec fils %p\n", rec, rec->fils);

  		  arbre_prec=arbre;
  		  arbre=rec->fils; // On va à l'étage d'après pour former le mot dans l'arbre
  		  //

  		}

  	    }

  	}

        else {

  	printf("c=='\ n' \n");

  	if (arbre_originel!=NULL)
  	  {
  	    printf("%c \n", arbre_prec->lettre); 
  	    arbre_prec->fin_mot=true; // Cette lettre est la dernière du mot
  	  }
  

  	affiche_dico(arbre_originel,n_lettre,mot);

  	printf("remise à 0\n");

  	printf("avant egal arbre %p arbre ori %p \n", arbre, arbre_originel);

  	arbre=arbre_originel; // On revient en haut de l'arbre pour commencer un nouveau mot

  	printf("apres egal arbre %p arbre ori %p \n", arbre, arbre_originel);

        }

        //arbre=arbre_originel; 

      }

    */
    // printf("arbre originel lettre %c \n", arbre_originel->fils->lettre);

    affiche_dico(arbre_originel,n_lettre,mot);

    free_tree(&arbre);

    fclose(fp);
  
  
    return 0;
  }