#include <stdio.h>
#include <string.h>
#include <stdlib.h>

/****************  Définition d'une structure ******************/
typedef struct compteMot
{
  char * mot;
  int nbOcc;
}CompteMot;

/********************   Les constantes   ************************/
enum {MAXLONGUEUR = 200};

/* Le tableau où seront rangées les structures de type CompteMot */
CompteMot *tableau;

/* Le nombre de mots*/
int nbMots = 0;

/* La taille du tableau contenant les mots */
int tailleTableau = 50;

char chercherIndice(char *, int *);
char placer(char *, int);

/********************   La fonction principale   *******************
 Le programme : 
 - Ouvre en lecture un fichier contenant un texte, fichier dont le nom 
 est indiqué sur la ligne de commande. Dans le cas où l'utilisateur omet 
 de donner un nom de fichier d'entrée sur la ligne de commande, le programme 
 demande  à l'utilisateur d'indiquer le texte directement par le clavier. 
 - Trie les mots et compte le nombre d'occurence de chaque mot 
 - Indique la liste triée des mots, un mot par ligne, avec pour chaque mot, 
 son nombre d'occurences. Si l'utilisateur a donné sur la ligne de commande 
 deux noms de fichiers, le premier pour le fichier d'entrée 
 contenant le texte, le second pour un fichier de sortie, cette liste est 
 sauvée sur le fichier de sortie. Sinon, la liste est indiquée à l'écran. */
int main(int argc, char **argv)
{
  char ligne[MAXLONGUEUR], *s, *mot;
  int indice;
  FILE *fichier;
  int i;
  
  if (argc > 1)  fichier = fopen(argv[1], "r");
  else 
    {
      fichier = stdin;
      printf("Indiquez votre texte\n");
    }
  tableau = (CompteMot *) malloc(tailleTableau * sizeof(CompteMot));
  if (tableau == NULL) 
    {
      printf("problème d'allocation\n");
      exit(1);
    }
  while (fgets(ligne, MAXLONGUEUR, fichier) != NULL)
    {
      s = ligne;
      while ((mot = strtok(s, " []{}\\\n{}()*/\"#.;:,\t'?!-<>&%+=")) != NULL) 
	{
	  if (!chercherIndice(mot, &indice)) placer(mot, indice);
	  else tableau[indice].nbOcc++;
	  s = NULL;
	}
    }
  fclose(fichier);
  printf("\n");
  for (i = 0; i < nbMots; i++)
    printf("%s : %d fois\n", tableau[i].mot, tableau[i].nbOcc); 
  return 0;
}


/******************   La fonction chercherIndice   *****************/
/*Si le mot ne figure pas :
     - la fonction indique, avec la variable adrIndice, l'indice ou 
     il convient que le mot se trouve
     - la fonction retourne 0
  Si la donnee figure :  
     - la fonction indique, avec la variable adrIndice, l'indice ou 
     le mot figure
     - la fonction retourne 1*/
char chercherIndice(char *mot, int *adrIndice)
{
  int gauche = 0,  droite = nbMots - 1;
  int milieu;
  int compare;
  
  while (gauche <= droite)
    {
      milieu = (gauche + droite) / 2;
      compare = strcmp(mot, tableau[milieu].mot);
      if (compare < 0) droite = milieu - 1;
      else if (compare > 0) gauche = milieu + 1;
      else 
	{
	  *adrIndice = milieu;
	  return 1;
	}
    }
  *adrIndice = gauche;
  return 0;
}

/******************     La fonction placer     ******************/
/*Decale vers la gauche les mots qui se trouvent
  a des indices aux moins egaux a "indice" et met le mot "mot" 
  a l'indice "indice" dans le tableau.
  ATTENTION : il faut allouer de la mémoire pour y mettre le nouveau
  mot par une copie */
char placer(char  *mot, int indice)
{
  int i;
  char *leMot; 

  leMot = (char *) malloc((strlen(mot) + 1)*sizeof(char));
  if (leMot == NULL) 
    {
      printf("problème d'allocation\n");
      exit(1);
    }
  strcpy(leMot, mot); 
  if (nbMots == tailleTableau) 
    {    
      printf("Le tableau est plein, nous reallouons\n");
      tailleTableau += 50;
      tableau = (CompteMot *) realloc(tableau,
				      tailleTableau * sizeof(CompteMot));
      if (tableau == NULL) 
	{
	  printf("problème d'allocation\n");
	  exit(1);
	}
    }
  for (i = nbMots; i > indice; i--)  tableau[i] = tableau[i - 1];
  tableau[indice].mot = leMot;
  tableau[indice].nbOcc = 1;
  nbMots++;
  return 1;
}