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

#include "hash_table.h"

#define MAX_HASH 100001




int hash(char *key)
{
    int i, h = 0, n = strlen(key);
    for (i = 0; i < n; i++) {
	h = (h + (unsigned char) key[i]) % MAX_HASH;
    }
    return h;
}


llist *new_hash_table(int n)
{
    int i;
    llist *T;
    T = (llist *) malloc(n * sizeof(llist));
    for (i = 0; i < n; i++) T[i].head = (elist*) NULL;
    return T;
}

elist *list_search(llist *L, char *key)
{
    elist *x = L->head;
    while (x != NULL && strcmp(x->key, key) != 0) {
	x = x -> next;
    }
    return x;
}


void *list_insert(llist *L, elist *x)
{
    elist *z;
    if (L->head == NULL) {
	L->head = x;
	x->next = (elist*) NULL;
	x->prev = (elist*) NULL;
    } else {
	z = L->head;
	z->prev = x;
	x->next = z;
	L->head = x;
    }
}


elist *chained_hash_search(llist *T, char *key)
{
    int h = hash(key);
    return list_search(&T[h], key);
}

void chained_hash_insert(llist *T, elist *x)
{
    int h = hash(x->key);
    /* printf("Inserting key='%s' into T[%d]\n", x->key, h); */
    list_insert(&T[h], x);
}


elist *make_elist(char *key)
{
    elist *e = (elist*) malloc(sizeof(elist));
    int len = strlen(key);
    e->key = (char *) malloc((len+1) * sizeof(char));
    strcpy(e->key, key);
    e->count = 1;
    return e;
}


void print_hash_table(llist *T, int n)
{
    int i;
    elist *x;
    for (i = 0; i < n; i++) {
	/* printf("%d---\n", i); */
	x = T[i].head;
	while (x != NULL) {
	    printf("%5d\t%s [%d]\n", x->count, x->key, i);
	    x = x->next;
	}
    }
}


/* Usage: ./hash_table <filename> */
int main(int argc, char **argv)
{
    int i;
    char word[1000];
    FILE *infile;
    llist *T;
    elist *e;
    if (argc != 2) {
	printf("\nUsage: %s <filename>\n\n", argv[0]);
	return 1;
    }
    infile = fopen(argv[1], "r");
    if (infile == NULL) {
	printf("\nFailed to open file: %s \n\n", argv[1]);
	return 2;
    }
    T = new_hash_table(MAX_HASH);
    while (fscanf(infile, "%s", word) == 1) {
	e = chained_hash_search(T, word);
	if (e != NULL) {
	    e->count++;
	} 
	else {
	    e = make_elist(word);
	    chained_hash_insert(T, e);
	}
    }
    fclose(infile);
    print_hash_table(T, MAX_HASH);
    return 0;
}