#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;
}