#include <stdio.h>
  #include <stdlib.h>
  #include <stdbool.h>
  #define MAX 30

  #define NB_CARAC 26
  #define nb_car 5

  
  typedef struct node* Node;
  
  typedef struct node {
    char letter;

    Node next[NB_CARAC];

    bool endWord;
  }node;
  

  bool is_empty_tree(Node Tree)

  {

    return(Tree==NULL);

  }
  

  bool is_leaf(Node Tree)

  {

    for(int i=0; i<NB_CARAC; i++)
      if(Tree->next[i] != NULL)
        return false;
    return true;

  }
  
  void init_tree(Node* Tree)
  {

    if(is_empty_tree(*Tree))

      {

        *Tree = malloc(sizeof(node));

        (*Tree)->letter = '?';
        (* Tree)->endWord = false;

        for(int i=0; i<NB_CARAC; i++)

  	(*Tree)->next[i] = NULL;
      }
  }
  

  void add_in_tree(Node Tree, char word[])

  {

    int j=0;

    Node Tree2 = Tree;
    while(word[j] != '\0')

      {

        if(is_leaf(Tree2))
          printf("empty\t");

        char letter = word[j];

        if(Tree2->next[letter-'a']!=NULL)
  	{
  	  Tree2 = Tree2->next[letter-'a'];
  	  printf("%c %d\t", letter, letter-'a');
  	  printf("okA %d\n", j);
  	}

        else
  	{
  	  Node new = NULL;

  	  new = malloc(sizeof(node));

  	  new->letter = letter;
  	  for(int i=0; i<26; i++)
  	    {
  	      new->next[i]=NULL;
  	    }

  	  Tree2->next[letter-'a'] = new;

  	  if(!(Tree2->endWord))
  	    Tree2->endWord = false;

  	  Tree2=Tree2->next[letter-'a'];
  	  printf("%c %d\t", letter, letter-'a');
  	  printf("okB %d\n", j);

  	}
        j++;

        if(word[j]=='\0')
  	Tree2->endWord = true;
      }
    printf("ok\n");
  }
  
  bool is_end_caract(char letter)
  {

    if(letter==0) return true;
    if((letter>=32 && letter<=47)||(letter>=58 && letter<=64)||(letter>=123 && letter<=126)||(letter==128)) return true;

    return false;
  }
  
  char max_index(char word[])
  {
    int index = 0;
    while(!is_end_caract(word[index]))
      index++;
    return index;
  }
  

  void scan_word(Node Tree, char word[], int* error) // si un mot démarre juste après un caractère de fin, la fonction ne lit pas les mots séparément

  {

    bool endWord;
    bool stop = false;

    int ind = 0;
    char letter;
    Node Tree2 = Tree;
    while(!is_end_caract(word[ind]))
    {

      stop = false;

      letter = word[ind];
      if(Tree2->next[letter-'a']!=NULL)
      {
        ind++;
        Tree2 = Tree2->next[letter-'a'];

        endWord = Tree2->endWord;
        if(endWord) printf("end :: %s ::\n", word);

      }
      else
      {
        printf("mot : %s erreur :%c %d \n", word, word[ind], word[ind]);
        (*error)++;

        printf("%d\n", ind);

        ind = max_index(word);

        printf("%d\n", ind);
        stop = true;

      }

    }

    if(!endWord && !stop)
      {
        (*error)++;
        printf("---%s---\n", word);
      }

  }
  
  void read_txt(FILE* fp, Node* Tree, int* error)
  {
    char word[MAX];
    while(1)
    {
      if(fscanf(fp, "%s", word)!=1)
        return;
      scan_word(*Tree, word, error);
    }

  }
  
  void read_lib(FILE* fp, Node* Tree)
  {
    char word[MAX];
    while(1)
      {

        if(fscanf(fp, "%s", word)!=1)
  	return;
        printf("--%s--\n", word);
        //fflush(stdout);
        add_in_tree(*Tree, word);

      }
  }
  
  void print_tree(Node Tree, int index)
  {

    if(is_empty_tree(Tree))
      return;
    Node cpTree = NULL;
    cpTree = Tree;
    if(cpTree->next[index]==NULL && index<26)
      {
        print_tree(cpTree, index+1);
      }
    else if(index == 26)
      {
        return;
      }

    else

      {
        printf("%c\n", (cpTree->next[index])->letter);
        if((cpTree->next[index])->endWord)
  	{
  	  printf("fin\n");
  	  //print_tree(cpTree, 0);
  	  return;
  	}
        print_tree(cpTree->next[index], 0);
      }
  }
  
  int find_index(Node tree)
  {
    Node cpTree = tree;
    int index = 0;
    while(cpTree->next[index]==NULL && index < NB_CARAC)
      index++;
    return index;
  }
  
  void print_first(Node Tree)
  {
    Node cpTree = Tree;
    int index = 0;

    while(!is_leaf(cpTree) || !(cpTree->endWord))

      {
        index = find_index(cpTree);
        printf("%c\n", (cpTree->next[index])->letter);

        if(cpTree->next[index]->endWord) printf("fin\n");

        cpTree=cpTree->next[index];
      }

  }
  
  int main(int argc, char *argv[])
  {

    Node tree = NULL;
    int error = 0;
    FILE* fp_lib;
    FILE* fp_txt;
    fp_lib = fopen(argv[argc-2], "r");
    fp_txt = fopen(argv[argc-1], "r");
  
    init_tree(&tree);
    read_lib(fp_lib, &tree);
    read_txt(fp_txt, &tree, &error);
  

    // printf("%p\n", tree);

  
    print_first(tree);

    //printf("\n");
    //print_tree(tree, 0);

    
    printf("erreurs : %d\n", error);
  

    return 0;
  }