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


ptarbre rech(ptarbre arbre, char lettre)
// Fonction qui cherche une lettre passée en paramètre à partir d'une cellule à l'adresse arbre et qui retourne l'adresse d'une cellule, soit parce qu'il n'y a plus de cellules après, soit car c'est la cellule où se trouve la lettre passée en paramètre.
{
  if (arbre!=NULL)
    {
      while ((arbre->suivant!=NULL) && (arbre->lettre != lettre))
	{
	  arbre=(arbre->suivant);
	}
    }
  return arbre;
}

void init_dico(ptarbre* parbre, char lettre)
// Action qui initialise une cellule de type cell à l'adresse (*parbre) et qui ajoute à cette cellule la première lettre du texte, alloue de la mémoire pour le fils .
{
  (*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. Par exemple, si on est en train de construire le mot voir, avec 'v' et 'o' déjà dans l'arbre, arpès la lettre 'o' on met '\0' pour différencier s'il faut utiliser ajout tete ou ajout dico pour ajouter le 'i'.
  (*parbre)->suivant=NULL;
  (*parbre)->lettre=lettre;
  (*parbre)->fin_mot=false;
}

void ajout_dico_tete(ptarbre *parbre, char lettre)
// Action qui ajoute la première cellule d'un étage, utile pour le premier mot et pour les mots suivants qui sont plus longs que les précédents. Pour le premier mot 'voir', on utilise init_dico et pour les 3 autres lettres on utilise ajout_dico_tete. Ensuite, pour voile, on utilise ajout_dico pour 'v','o','i','l' et ajout_dico pour 'e'.
{
  (*parbre)->fils=malloc(sizeof(cell));
  (*parbre)->fils->suivant=NULL;
  (*parbre)->suivant=NULL;
  (*parbre)->lettre=lettre;
  (*parbre)->fin_mot=false;
}

void ajout_dico(ptarbre *parbre, ptarbre *parbresuiv, char lettre)
// Action qui ajoute une lettre dans un étage existant, en faisant le lien entre la cellule d'avant à l'adresse *parbre et la nouvelle cellule à l'adresse *parbresuiv en ajoutant la lettre passée en paramètre à la nouvelle cellule.
{
  *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;
}

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++;
	}
      if (arbre->fin_mot)
	{
	  printf("%s",mot);
	  printf("\n");
	}
      
      affiche_dico(arbre->fils,n_lettre,mot);
      if (arbre->suivant != NULL)
	{
	  n_lettre--;
	  mot[n_lettre]='\0';
	}
      affiche_dico(arbre->suivant, n_lettre, mot);
      n_lettre--;
      mot[n_lettre]='\0';
	  
    }
 
}

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
    {
      if (c != '\n')
	{
	  if ((*parbre_originel)==NULL) // Cas où c'est le premier mot premiere lettre
	    {
	      init_dico(parbre_originel,c);;
	      (*parbre_prec)=(*parbre_originel);
	      (*parbre)=(*parbre_originel)->fils;
	    }
	  else if ((*parbre)==NULL) // premier mot de l'arbre
	    {
	      init_dico(parbre,c);
	      (*parbre_prec)=(*parbre);
	      (*parbre)=(*parbre)->fils;
	    }
	  
	  else // Cas où le dico n'est pas vide
	    {
	      rec=rech((*parbre),c);
	      if (rec->lettre!=c)
		{

		  if (rec==(*parbre) && rec->lettre=='\0') // 1ere lettre de la liste
		    {
		      ajout_dico_tete(parbre,c);
		      (*parbre_prec)=(*parbre);
		      (*parbre)=(*parbre)->fils;
		    }
		      
		  else if (rec->suivant==NULL && rec->lettre!='\0')
		    {
		      ajout_dico(&(rec),&(rec->suivant),c);
		      (*parbre_prec)=(*parbre);
		      (*parbre)=rec->suivant->fils;
		    }
		}
	  
	      else
		{// Cas où le début du mot existe déjà et qu'on le complète
		  (*parbre_prec)=(*parbre);
		  (*parbre)=rec->fils; // On va à l'étage d'après pour former le mot dans l'arbre
		 
		}
	    
	      
	    }
	}
      else {
	if ((*parbre_originel)!=NULL)
	  {
	    (*parbre_prec)->fin_mot=true; // Cette lettre est la dernière du mot
	  }
	(*parbre)=(*parbre_originel); // On revient en haut de l'arbre pour commencer un nouveau mot
      }
    }
}

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("words","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);
  free_tree(&arbre);
  fclose(fp);

  return 0;
}