/*********************************************************************

 Programa freq.c.             Versao 2

 Este programa foi gerado inicialmente pelo CWEB, a partir de freq.w.

 Provisoriamente, vamos simplesmente fazer uma alteracao no proprio
 codigo gerado em C.
 No programa freq.c, foi feita, aqui, a seguinte alteracao:

 A cada busca bem sucedida, o elemento encontrado e' levado para o 
 inicio da lista de colisao.

 O objetivo disso e' melhorar o desempenho do programa baseado na 
 nocao intuitiva de que, se os elementos mais frequentes estiverem
 no inicio da lista, o numero total de comparacoes feitas nas buscas
 vai diminuir.
 
*********************************************************************/

#define COMP_MAX 50
#define HASH_PRIME 1009
#define o n_comp++

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

typedef struct celula_struct
  {
    char *palavra;
    int n_ocorrencias;
    struct celula_struct *prox;
  }
celula;

int 
hash_div (char *s)
{
  int h;
  for (h = 0; *s != '\0'; s++)
    h = (258 * h + (unsigned char) *s) % HASH_PRIME;
  return h;
}

int 
main ()
{

  char s[COMP_MAX];
  long n_pals = 0;
  long n_pals_dist = 0;

  celula *tab[HASH_PRIME];

  long n_comp = 0;

  {
    int i;
    for (i = 0; i < HASH_PRIME; i++)
      tab[i] = NULL;
  }

  while (gets (s))
    {
      int h_valor;
      n_pals++;
      h_valor = hash_div (s);

      {
	int achou = 0;
	celula *ptr = tab[h_valor],
               *p1  = 0,            
               *p2;
	/* Alterado na versao 2: foram acrescentados os      */
	/* ponteiros p1 e p2, que servirao como auxiliares.  */

	while ((!achou) && ptr)
	  if (o, strcmp (s, ptr->palavra) == 0)
	    achou = 1;
 	  else {
	    p1  = ptr;         /* p1 fica 1 elemento atras de ptr */
	    ptr = ptr->prox;
          }
        /* O codigo original e' o seguinte:   */
        /*   if (achou)                       */
	/*     ptr->n_ocorrencias++;          */
        /* Alteracao para a versao 2:         */
        /* A seguir, o codigo esta' alterado para que, quando um  */
        /* elemento e' encontrado, ele seja tirado de sua posicao */ 
        /* e levado para o inicio da lista de colisao.            */ 
 	if (achou) {
	  ptr->n_ocorrencias++;
          if (p1){
            p2           = ptr->prox;
            ptr->prox    = tab[h_valor] ;
            tab[h_valor] = ptr;
            p1->prox     = p2;
          }
        } 
	else
	  {
	    celula *cel_nova;
	    char *t;
	    cel_nova = (celula *) malloc (sizeof (celula));
	    if (cel_nova == NULL)
	      {
		fprintf (stderr, "freq: faltou memoria para celulas!\n");
		return -1;
	      }
	    t = (char *) malloc (strlen (s) + 1);
	    if (t == NULL)
	      {
		fprintf (stderr, "freq: faltou memoria para caracteres!\n");
		return -2;
	      }
	    strcpy (t, s);
	    cel_nova->palavra = t;
	    cel_nova->n_ocorrencias = 1;

	    n_pals_dist++;
	    cel_nova->prox = tab[h_valor];
	    tab[h_valor] = cel_nova;
	  }
      }
    }
  {
    int i;
    for (i = 0; i < HASH_PRIME; i++)
      {
	celula *ptr = tab[i];
	for (; ptr; ptr = ptr->prox)
	  printf ("%s %d\n", ptr->palavra, ptr->n_ocorrencias);
      }
  }

  printf ("Numero de palavras lidas = %ld\n", n_pals);
  printf ("Numero de comparacoes feitas = %ld\n", n_comp);
  printf ("Numero medio de comparacoes feitas por palavra lida = %f\n",
	  (double) n_comp / n_pals);
  printf ("Numero de palavras distintas = %ld\n", n_pals_dist);
  printf ("Numero esperado de palavras por lista ligada = %f\n",
	  (double) n_pals_dist / HASH_PRIME);

  return 0;
}