/* questo programma legge da un file le parole, e applica alcune funzioni
 * di hash viste a lezione
 * prende in ingresso un numero che e' poi il numero di bucket */

/* USO: hashw N 
 * con N numero di bucket */

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
#include<math.h>
#include"util.h"

#define FILE_IN "promessi.txt"
#define BUFFERLEN 20


char *leggi_parola(FILE *mio_file);
int ascii_hash(char *v, int n);
int random_ascii_hash(char *v, int n);

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

int main(int argc, char **argv)
{
 FILE *testo;
 char *parola_in_esame;
 int n,ii;
 int m1=0,m2=0;
 int z1=0,z2=0;
 float  v1=0, v2=0, t1=0, t2=0;
 unsigned int *hash1,*hash2;

 if(argc<2) exit(EXIT_FAILURE);
 n=atoi(argv[1]);
 if(n<=1)exit(EXIT_FAILURE);
	
 /* alloco due array inizializzandoli a 0 */
 hash1=Calloc(n,sizeof(unsigned int));
 hash2=Calloc(n,sizeof(unsigned int));

 /* apro il file */
 testo=Fopen(FILE_IN, "r");
 
 /* leggo parola a parola e calcolo le due funzioni di hash */
 while (1)
  {
   if(!(parola_in_esame=leggi_parola(testo)))
	   break;
   /* incremento i valori corrispondenti negli array */
   hash1[ascii_hash(parola_in_esame,n)]++;
   hash2[random_ascii_hash(parola_in_esame,n)]++;
   free(parola_in_esame);
  }
 /* stampo i valori e calcolo media, deviazione standard,
  * numero di zeri e valori massimi */
 for(ii=0;ii<n;++ii){
   printf("%d\t%d\t%d\n",ii,hash1[ii],hash2[ii]);
   t1+=hash1[ii];
   t2+=hash2[ii];
   if(m1<hash1[ii])m1=hash1[ii];
   if(m2<hash2[ii])m2=hash2[ii];
   if(!hash1[ii])z1++;
   if(!hash2[ii])z2++;
 }
 t1/=n;
 t2/=n;
 for(ii=0;ii<n;++ii){
   v1+=(hash1[ii]-t1)*(hash1[ii]-t1);
   v2+=(hash2[ii]-t2)*(hash2[ii]-t2);
 }
 v1=sqrt(v1/n);
 v2=sqrt(v2/n);
 /* ovviamente le medie devono essere eguali */
 printf("Valori medi h1=%f h2=%f\n", t1, t2);
 printf("deviazioni standard h1=%f h2=%f\n", v1, v2);
 printf("numero di zeri h1=%d h2=%d\n", z1, z2);
 printf("valori massimi h1=%d h2=%d\n", m1, m2);
 fclose(testo);
 free(hash1);
 free(hash2);
 return 0;
}

char *leggi_parola(FILE *mio_file)
{
 char c=' ';
 char *parola=NULL;
 int lenparola=1;
 int nbuff=1;

 while((!feof(mio_file))&&(!isalpha((int)c)))
  c=fgetc(mio_file);

 if(feof(mio_file))return NULL;
 
 /* alloco un primo buffer */
 parola=Malloc(sizeof(char)*BUFFERLEN*nbuff+sizeof(char));
 /* ci metto il valore letto */
 *parola=c;

 /* man mano leggo altri caratteri */
 while((!feof(mio_file))&&(isalpha((int)(c=fgetc(mio_file)))))
  {
   if(lenparola>(BUFFERLEN*nbuff))
       parola=Realloc(parola, sizeof(char)*BUFFERLEN*++nbuff+sizeof(char));
   parola[lenparola++]=c;
  }

  /* chiudo la stringa */
 parola[lenparola]='\0';
  
 return parola;
}

int ascii_hash(char *v, int n){
	int h=0;
	int a=127;
	for(;*v!='\0';++v)
	  h=(a*h+*v)%n;
	return h;
}

int random_ascii_hash(char *v, int n){
	int h=0;
	int a=31415;
	int b=27183;
	for(;*v!='\0';++v,a=a*b%(n-1))
	  h=(a*h+*v)%n;
	return h;
}

/* alcuni esempi di risultato con le parole dei promessi sposi (~220000) :
 * hashw 1001:
 * Valori medi h1=22.435564 h2=22.435564
 * deviazioni standard h1=4.737879 h2=5.109386
 * numero di zeri h1=0 h2=0
 * valori massimi h1=60 h2=65
 *
 * hashw 1000:
 * Valori medi h1=22.458000 h2=22.458000
 * deviazioni standard h1=4.897961 h2=16.314848
 * numero di zeri h1=0 h2=1
 * valori massimi h1=62 h2=104
 *
 * hashw 1016:
 * Valori medi h1=22.104330 h2=22.104330
 * deviazioni standard h1=110.839607 h2=14.059880
 * numero di zeri h1=850 h2=0
 * valori massimi h1=758 h2=76
 * (si noti che 1016=127*8) */