#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[])
// Action qui affiche tout le dictionnaire à partir de arbre (donc le numéro de lettre) sélectionné en stockant le début du mot qui est commun à tous les suivants dans mot initialisé à vide et le numéro de la lettre dans n_lettre initialisé à 0.
{
  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)
// Action qui libère la mémoire allouée pour stockée les données du dictionnaire *(*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)
// Action qui construit entièrement l'arbre, à partir du fichier fp, en partant de l'adresse parbre_originel qui correspond à la première cellule, parbre qui est la copie de l'arbre originel qui va nous permettre de nous balader entre les différentes lettres de chaque mot et de revenir à la première cellule à la fin de chaque mot. 
{
  char c;
  ptarbre rec;
   while (fscanf(fp,"%c",&c)!= EOF) // Lecture de tout le fichier fp.
    {
      if (c != '\n')
	{
	  if ((*parbre_originel)==NULL) // Cas où c'est le premier mot et premiere lettre du dictionnaire.
	    {
	      init_dico(parbre_originel,c);
	      (*parbre_prec)=(*parbre_originel); // On sauvegarde l'adresse de la lettre précédente.
	      (*parbre)=(*parbre_originel)->fils; // On passe à l'adresse de la cellule qui contiendra la prochaine lettre du même mot.
	    }
	  else if ((*parbre)==NULL) // Cas où c'est le premier mot de l'arbre mais pas la première lettre.
	    {
	      init_dico(parbre,c);
	      (*parbre_prec)=(*parbre);
	      (*parbre)=(*parbre)->fils;
	    }
	  
	  else // Cas où ce n'est pas le premier mot, il faut faire une recherche parmi les lettres de même indice (donc à l'étage '(*parbre)') déjà enregistrées dans l'arbre. 
	    {
	      rec=rech((*parbre),c);
	      if (rec->lettre!=c) // Cas où la lettre présente dans la cellule à l'adresse renvoyée par rech((*parbre),c) n'est pas la lettre recherchée.
		{

		  if (rec==(*parbre) && rec->lettre=='\0') // Cas où il n'y a pas de lettres à l'indice *parbre donc la recherche renvoie l'adresse de la première cellule qui est vide.
		    {
		      ajout_dico_tete(parbre,c);
		      (*parbre_prec)=(*parbre);
		      (*parbre)=(*parbre)->fils;
		    }
		      
		  else if (rec->suivant==NULL && rec->lettre!='\0') // Cas où il y a qu'une lettre à l'indice *parbre donc la recherche renvoie l'adresse de la première cellule qui ne contient pas la lettre recherchée.
		    {
		      ajout_dico(&(rec),&(rec->suivant),c);
		      (*parbre_prec)=rec->suivant;
		      (*parbre)=rec->suivant->fils;
		    }
		}
	  
	      else
		{// Cas où la recherche renvoie l'adresse d'une cellule dont la lettre est la lettre recherchée donc le début du mot existe déjà et on le complète.
		  (*parbre_prec)=rec;
		  (*parbre)=rec->fils; // On va à l'étage d'après pour former le mot dans l'arbre.
		 
		}
	    
	      
	    }
	}
      else { // Cas où c==\n donc le mot est terminé, il faut retourner en haut de l'arbre pour ajouter le prochain mot.
	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("Dictionnaire inaccessible \n");
  else
    printf("Dictionnaire accessible \n");
  cons_arbre(&arbre_originel, &arbre, &arbre_prec,fp);
  affiche_dico(arbre_originel,n_lettre,mot);
  free_tree(&arbre_originel);
  fclose(fp);
  

  return 0;
}