//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//				
//    Nom       : abr.c
//    Type      : C ANSI
//    Contient  : Implémentation complète d'un arbre binaire de
//                recherche comprenant des mots. 
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#include <stdio.h>
#include <math.h>                        /* Compiler avec option -lm */

#define TRUE 1
#define FALSE 0
#define alloc(t) (t *) malloc(sizeof(t))


//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// Structure de données

struct cell {
  char mot[22] ;
  struct cell *fg ; 
  struct cell *fd ; 
} ;

typedef struct cell cellule ;

cellule * racine ;

//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// Utilitaires d'affichage et de sortie de l'ABR

void aff_tree (cellule * r, int p)
{
  int i ;
  if (r == NULL) {
    //    for (i=0 ; i<p ; i++) printf("%c", ' ') ;
    //    printf("....\n") ;
  }
  else {
    aff_tree(r->fg, p+3) ;
    for (i=0 ; i<p ; i++) printf("%c", ' ') ;
    printf("%s\n", r->mot) ;
    aff_tree(r->fd, p+3) ;
  }
}

void trie_tree (cellule * r)
{
  if (r == NULL) return ;
  trie_tree (r->fg) ;
  printf("%s\n", r->mot) ;
  trie_tree (r->fd) ;
}

//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// Calculs sur la structure : nombre de noeuds, profondeur

int nb_mots (cellule * r)
{
  if (r == NULL) return 0 ;
  return 1 + nb_mots(r->fg) + nb_mots(r->fd) ;
}

int max(int a, int b) {   return a>b?a:b ; }

int profondeur (cellule * r)
{
  if (r == NULL) return 0 ;
  return max(profondeur(r->fg),profondeur(r->fd)) + 1 ;
}
  
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// Primitives de création et de manipulation de l'ABR

cellule * cree_cell(char * mot)
{
  cellule * x = alloc(cellule) ;
  if (x == NULL) { fprintf(stderr, "Erreur d'allocation\n") ; exit(1) ;}
  strcpy(x->mot, mot) ;
  x->fg = x->fd = NULL ;
  return x ;
}

void ajout (char * mot, cellule * r) 
{
  int cmp ;

  cmp = strcmp(r->mot, mot) ;
  if (cmp==0) return ;   // Si le mot est déjà là on ne fait rien
  if (cmp<0) 
    if (r->fd != NULL) ajout(mot, r->fd) ;
    else r->fd = cree_cell(mot) ;
  else /* cmp>0 */
    if (r->fg != NULL) ajout(mot, r->fg) ;
    else r->fg = cree_cell(mot) ;
}

int appartient (char * mot, cellule * r) 
{
  int cmp ;

  if (r==NULL) return FALSE ;
  cmp = strcmp(r->mot, mot) ;
  if (cmp==0) return TRUE ;
  if (cmp<0) 
    return appartient(mot, r->fd) ;
  else /* cmp>0 */
    return appartient(mot, r->fg) ;
}
    
// Cette fonction lit un fichier texte, qu'elle segmente grossièrement
// en mots, puis range chaque mot dans l'ABR (fonction ajout())

void lecture(char * fic) 
{
  FILE * f ;
  char mot[22], buffer[BUFSIZ] ;
  int i, j , c = 0;

  f = fopen(fic,"r") ;

  while (fgets(buffer,BUFSIZ,f) != NULL) {
    i = 0 ;
    while (buffer[i] != '\0') {
      while (buffer[i]!='\0' && !isalpha(buffer[i])) 
	i++ ;
      mot[0] = '\0' ; j = 0 ;
      while (buffer[i]!='\0' && isalpha(buffer[i]))
	mot[j++] = buffer[i++] ;
      if (j>0) {
	mot[j] = '\0' ;
	printf("Mot lu n°%d : %s\n",c,mot) ;
	ajout(mot,racine) ;
	c++ ;
      }
    }
  }
  printf("Lus et chargés %d mots\n", c) ;

  fclose(f) ;
}

main(int argc, char * argv[])
{
  char rep[22] ;
  int cm, pf ;

  racine = cree_cell("fond") ;
  /*  ajout("bien",racine) ;
  ajout("plie",racine) ;
  ajout("fouet",racine) ;
  ajout("truc",racine) ;
  ajout("chat",racine) ;
  ajout("cric",racine) ;
  ajout("abbé",racine) ; */

  if (argc>1) lecture(argv[1]) ;

  aff_tree(racine, 0) ;

  printf("Profondeur : %d\n", pf=profondeur(racine)) ;
  printf("Nb noeuds : %d \n", cm=nb_mots(racine)) ;
  printf("Log_2(%d) = %f\n", cm, log10(cm)/log10(2) ) ;
  printf("Taux de remplissage : %f\n", cm/(pow(2,pf)-1)*100) ;

  //  exit(0) ;

  // Boucle infinie (à interrompre par CTRL-C) pour tester la fonction
  // d'appartenance 
  while (1) {
    printf("Mot ? ") ;
    scanf("%s", rep) ;
    if (appartient(rep, racine)) printf("Oui !\n") ;
    else printf("Non !\n") ;
  }

}