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