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

//Esrutura que representa o no de uma lista simplesmente encadeada
typedef struct tempno{
    char *palavra;
    int   n_vezes;
    struct  tempno  *prox;
} *no;

no inicio(no cabeca);
no fim_lista (no cabeca);
no avancar(no lista);
no percorrer(no cabeca,int posicao);
void inserir_apos(no lista,char string[]);
int calcular_posicao (char *string , int tamanho_vetor);
no achar (char *string, no cabeca);
no lista_vazia(void);
void escrever_arquivo (no cabeca, FILE *fp);


//Funcao para escrever uma lista encadeada no arquivo
void escrever_arquivo(no cabeca,FILE *fp){
	while((cabeca=avancar(cabeca))!=NULL){
		if (cabeca->n_vezes){
			fprintf(fp,"\n%s %d",cabeca->palavra , cabeca->n_vezes);
			fprintf(fp,"\n");
		}
	}
}

//Funcao para criar uma lista vazia
no lista_vazia(void){
    //Cria um sentinela para facilitar os algoritmos de inserção e remoção
    no sentinela=(no)malloc(sizeof(struct tempno));
    //Prox de sentinela aponta para nada
    sentinela->prox=NULL;
    return sentinela;
}

//Funcao para retornar a primeira posicao valida da lista
no inicio(no cabeca){
    return cabeca->prox;
}

//Funcao para retornar a última posicao valida da lista
no fim_lista (no cabeca){
	while (cabeca->prox != NULL)
		cabeca = avancar (cabeca);
	return cabeca;
}

//Funcao para retornar o endereco do proximo elemento da lista
no avancar(no lista){
    return lista->prox;
}

//Percorre a lista até uma determinada posicao
no percorrer(no cabeca,int posicao){
    int i;
    //chama avança na lista a cada iteração
    for (i=0;i<posicao;i++){
        cabeca=avancar(cabeca);
    }
    return cabeca;
}

//Funcao para inserir apos um no da lista
void inserir_apos(no lista ,char *string){
    //Aloca espaco para um novo no
    no novo = (no)malloc(sizeof(struct tempno));
    //Prox de novo aponta para o proximo da no atual
    novo->prox = avancar(lista);
    novo->palavra = (char*) malloc (sizeof(char) * strlen(string));
    strcpy(novo->palavra,string);
    novo->n_vezes=1;
    //Lista atual aponta para o novo no
    lista->prox=novo;
}

//Funcao hash para calcular a chave
int calcular_posicao (char *string , int tamanho_vetor){
	int i,posicao;
	posicao  = 0;
	for ( i = 0 ; i < strlen (string) ; i++ ){
		posicao += (int)string[i];
	}
	return posicao % tamanho_vetor;
}

//Funcao para encontrar determinada string na lista encadeada
no achar (char *string, no cabeca){
	while ((cabeca = avancar(cabeca)) != NULL){
		if (! (strcmp (cabeca->palavra , string)))
			return cabeca;
	}
	return 0;
}
	
	 		 
//Funcao principal
int main (int argc , char *argv[]){
	if (argc != 3){
		printf ("\nDigite o nome do arquivo de entrada e o tamanho inicial da tabela hash\n");
		exit (0);
	}
	
	int i,j,sair=0;
	int n_colisoes=0;
	char string[30];
	FILE *entrada, *saida;
	no *vetor;
	no aux;
	
	vetor  = (no*) malloc (sizeof (no) * atoi (argv[2]));
	
	//Cria listas vazias nas posicoes da tabela
	for (i=0 ; i < atoi (argv[2]) ; i++){
		vetor[i]=lista_vazia();
	}
	
	//Abre o arquivo de entrada
	if (!(entrada = fopen(argv[1],"r"))){
		printf ("\nO arquivo de entrada nao pode ser aberto\n");
		exit(0);
	}
	saida=fopen ("hash.out","w");
	
	while (sair!=EOF){
		sair=fscanf(entrada,"%s",string);
		if ((aux = achar (string , vetor[calcular_posicao (string, atoi (argv[2]))])))
			aux->n_vezes ++;
		else
			inserir_apos (fim_lista (vetor[calcular_posicao (string, atoi (argv[2]))]), string);
	}
	
	for (i=0 ; i < atoi (argv[2]) ; i++){
		escrever_arquivo(vetor[i],saida);
	}
	
	fclose (entrada);
	fclose (saida);
	return 0;
}