#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_ori, char lettre)

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

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

  {

    ptarbre arbre;
    arbre=arbre_ori;

    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 print_tout(struct cell *arbre, int cpt, char *debut_mot)
  {
    //Return si aucune lettre stockée
    if(arbre==NULL){
      return;
    }
  
    printf("%c", arbre->lettre);
  
  
    //Si fin de mot, retour à la ligne
    if(arbre->fin_mot == true){
      printf("\n");
      
      //Si fin de mot mais encore des lettres dans 'Son' (-> merci mercier), on affiche la base commune
      if (arbre->fils != NULL){
        debut_mot[cpt] = arbre->lettre;
        printf("%s", debut_mot);
      }
    }
    
    //On avance dans Son, on stock la lettre dans début_mot
    debut_mot[cpt] = arbre->lettre;
    cpt ++;
    
    
    //On print Son
    print_tout(arbre->fils, cpt, debut_mot);
  
    //On remonte l'arbre, on enleve une lettre de la racine commune
    cpt --;
    debut_mot[cpt] = '\0';
    
   
    //Si lettre dans arbre Brother -> nouveau mot -> Retour à la ligne (changement de mot)
    if(arbre->suivant != NULL){
  
      //On imprime alors la racine commune
      printf("%s", debut_mot);
    }
  
    //On print
    print_tout(arbre->suivant, cpt, debut_mot);
  }

  
  void init_dico(ptarbre* parbre, char lettre)

  {

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

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

    (*parbre)->fils->lettre= '\0'; // Permet de savoir qu'il n'y a pas de lettre dans l'étage en dessous pour différencier s'il faut utiliser ajout tete ou ajout dico

    (*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;

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

  }
  

  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)

  	{

  	  mot[n_lettre]=arbre->lettre;
  	  n_lettre++;

  	}

        
        printf("%c",arbre->lettre);
        affiche_dico(arbre->fils,n_lettre,mot);
        if (arbre->fin_mot)
  	printf("\n");

        if (arbre->suivant != NULL)
  	{

  	  printf("%s",mot);
  	  // mot[n_lettre]=arbre->lettre;

  	}

        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 print_suiv(ptarbre arbre)
  {
    if (arbre!=NULL)
      {
        while(arbre->suivant!=NULL)
  	{printf("-%c_", arbre->lettre);
  	  arbre=arbre->suivant;
  	}
      }
    printf("\n");
  }
  

  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_prec)=(*parbre);

  	      (*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) && rec->lettre=='\0') // 1ere lettre de la liste

  		    {
  		      printf("1ere lettre\n");
  		      ajout_dico_tete(parbre,c);

  		      (*parbre_prec)=(*parbre);

  		      (*parbre)=(*parbre)->fils;
  		    }
  		      

  		  else if (rec->suivant==NULL && rec->lettre!='\0')

  		    {
  		 
  		      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("lettre trouvee %c\n", rec->lettre);

  		  (*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("adr arbre prec %p et lettre %c \n", (*parbre_prec),(*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");

  	print_suiv((*parbre));

  	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;

    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);

    //affiche_dico(arbre_originel,n_lettre,mot);
    print_tout(arbre_originel,n_lettre, mot);

    free_tree(&arbre);

    fclose(fp);
  

    return 0;
  }