#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include <time.h>
#include <math.h>

#define HARRAY_SIZE	6211
#define X6				308915776
#define X5				11881376
#define X4				456976				/*2983*/	/* mod(26^4,3691) */
#define X3				17576					/*2812*/	/* mod(26^3,3691) */
#define X2				676					/* 26^2 */
#define X1				26

struct dictionary{
	char *word;
	struct dictionary *next;
};

typedef struct dictionary dictionary;

int hash_function(char l0, char l1, char lxx, char lyy, int L);
int probe_function(char l0, char l1, char lxx, char lyy, int L);
dictionary *allocate (char *word);

int main(int argc, char **argv){

	int hash_num, i, j, line_length, letter, q, num, probe;
	char line[1024], l0, l1, lxx, lyy;
	FILE *input;
	dictionary *hash[HARRAY_SIZE];
	dictionary *start, *current;

	/*** HASHING ***/
	for (i=0; i<HARRAY_SIZE; i++){ hash[i] = NULL; }

	start = current = allocate("hello");
	if (argc != 2){
		printf("\nYou have to type the filename as well!\n");
		exit(2);
	}
	
	input = fopen(argv[1],"r");

	while ( fgets(line,1024,input) != NULL ){
		current->next = allocate(&line[0]);

		l0 = line[0]; l1 = line[1]; lxx = line[2]; 
		if (line[3] == '\n'){
			lyy = ' ';
		}
		else{
			lyy = line[3];
		}
		
		line_length = strlen(line);

		hash_num = hash_function(l0,l1,lxx,lyy,strlen(current->next->word));

		current = current->next;
		if (hash[hash_num] == NULL){
			hash[hash_num] = current;
		}
		else{
			probe = probe_function(l0,l1,lxx,lyy,strlen(current->word));
			i = hash_num + probe;
			while(1){
				if (hash[i] == NULL){ hash[i] = current; break; }
				i = i + probe;
				if (i >= HARRAY_SIZE - 1){
					i = i -(HARRAY_SIZE - 1);
				}

			}
		}
	}
	current->next = NULL;

	fclose(input);

	j = 0;
	for (i = 0; i < HARRAY_SIZE; i++){
		if (hash[i] == NULL){ /*printf("\n%d.Hash Value: Empty",i);*/ }
		else{
			/*printf("\n%d.Hash Value: %d -- %s", i,hash[i]->phone_num, hash[i]->name);*/
			j++;
		}
	}
	printf("\n\nInserted Values Number: %d", j);

	/**** USER INPUT ****/
	while(1){
		i = 0;

		/**** type the name ****/
		printf("\n\nGive me the word: ");
		while ((letter = getchar()) != '\n'){ line[i++] = tolower(letter); }
		line[i] = '\0';

		l0 = line[0]; l1 = line[1]; lxx = line[2]; lyy = line[3];
		line_length = strlen(line);

		i = hash_function(l0,l1,lxx,lyy,strlen(line));
		probe = probe_function(l0,l1,lxx,lyy,strlen(line));

		q = 0; num = 0;
		while (1){
			if (hash[i] != NULL){
				num++; printf("\n%d. '%s' -> '%s'",i,hash[i]->word,line);
				if (strcmp(hash[i]->word,line) == 0){ break; }
			}
			i = i + probe;
			if (i >= HARRAY_SIZE - 1){i = i - (HARRAY_SIZE - 1);}

			q++;
			if (q >= (HARRAY_SIZE - 1)/probe){ break; }
		}

		if (q >= (HARRAY_SIZE - 1)/probe){ printf("\n\nThe word %s is not spelled correct. YOU ARE WRONG!",line); }
		else{ printf("\n\nYOU ARE CORRECT in your spelling!"/*, line*/); }

		printf("\n");
	}
	return 0;
}

int hash_function(char l0, char l1, char lxx, char lyy, int L){
	unsigned long int h = 0/*5381*/;
	int A,B,C,D;

	A = (tolower((int)l0) )%26; B = (tolower((int)l1) )%26;
	C = (tolower((int)lxx))%26; D = (tolower((int)lyy))%26;
	
	h = h * 33 + A;
	h = h * 33 + B;
	h = h * 33 + C;
	if (L == 4){
		h = h * 33 + D;
	}
	h = h * 33 + L;
	h = h%HARRAY_SIZE;
	
	return ((int)h);
}

int probe_function(char l0, char l1, char lxx, char lyy, int L){
	int h;
	int A,B,C;

	A = (tolower((int)l0) )%26; B = (tolower((int)l1) )%26;
	C = (tolower((int)lxx))%26;

	h = ((X3*(C+B) + X2*(B+L) + A)/25567)%(HARRAY_SIZE - 1963);

	if (h < 1){ return 1; } else{ return h; }
}

dictionary *allocate (char *word){
	dictionary *p;
	int i = 0, j = 1;

	p = (dictionary *)malloc(sizeof(dictionary));
	if (p == NULL){ printf("\nCannot allocate memory!\n"); exit(2); }
	p->word = (char *)malloc((strlen(word))*sizeof(char));
	if (p->word == NULL){ printf("\nCannot allocate memory!\n"); exit(2); }

	while(*(word + i) != '\n'){ *((p->word) + i) = *(word + i); i++; }
	*((p->word) + i) = '\0';

	while (*((p->word) + i - j) == ' '){ *((p->word) + i - j) = '\0'; j++; }

	return p;
}