#include <sys/types.h>
#include <sys/stat.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>

#define HASHSIZE 311
#define MAXLINE 1024

typedef struct HashTableNode
{
	char *sortedWord;
	char *word;
	struct	HashTableNode*	next;
}hashtable;

static hashtable *hashtab[HASHSIZE];

static FILE* open_file(char *filename);
static int getline(char *s, int lim, FILE *fp);
static char* getword(char *s, const char *sep);
static int strcasecmp(char *s, char *t);
static void sort_word(char *s);
static unsigned int hash(char *s);
static void insert(char *word);
static hashtable* lookup(char *word);
static void print_anagrams_imp(char *word);

int print_anagrams(char *dict, char *word)
{
	FILE *fp;
	char line[MAXLINE];
	char *sep = "!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~\t \n";

	/* open input dictionary */
	fp = open_file(dict);
	if(fp == NULL)
		return 0;

	/* read line until EOF */
	while(getline(line, sizeof(line), fp))
	{
		char *p;

		/* read word until EOL */
		for(p = getword(line, sep); p; p = getword(NULL, sep))		/* insert in hash table */			
			insert(p);
	}

	/* lookup the anagrams of given word in hash table and print them */
	print_anagrams_imp(word);
	return 1;
}

static void print_anagrams_imp(char *word)
{
	hashtable *p;
	char *sorted_word;

	sorted_word = strdup(word);
	sort_word(sorted_word);

	for(p = hashtab[hash(sorted_word)]; p; p = p->next)
		if(strcasecmp(sorted_word, p->sortedWord) == 0)
			printf("%s	", p->word);

	printf("\n\n");
}

/* sorting using insertion sort */
static void sort_word(char *s)
{
	char *p, *q, c;

	if(s == NULL || s[0] == '\0' || s[1] == '\0')
		return;

	/* move smallest character to left */
	for(p = s+1, q = s; *p != '\0'; p++)
		if(tolower(*q) > tolower(*p))
			q = p;

	/* swap q with s */
	c = *s;
	*s = *q;
	*q = c;

	/* sort the word */
	for(p = s+1; *p != '\0'; p++)
	{
		for(q = p-1, c = *p; tolower(*q) > tolower(c); q--)
			*(q+1) = *q;

		*(q+1) = c;
	}
}

static unsigned int hash(char *s)
{
	unsigned hashval;

	for (hashval = 0; *s != '\0'; s++)
		hashval = tolower(*s) + 31 * hashval;

	return hashval % HASHSIZE;
}

static void insert(char *word)
{
	hashtable *p;
	char *sorted_word;
	unsigned int val;

	if(lookup(word) == NULL)
	{
		sorted_word = strdup(word);
		sort_word(sorted_word);
		p = (hashtable*)malloc(sizeof(*p));
		if(p == NULL)
		{
			printf("memory allocation error");
			exit(1);
		}

		p->word = strdup(word);
		p->sortedWord = strdup(sorted_word);

		val = hash(sorted_word);
		p->next = hashtab[val];
		hashtab[val] = p;

		free(sorted_word);
	}
}

static hashtable* lookup(char *word)
{
	hashtable *p;
	char *sorted_word;

	sorted_word = strdup(word);
	sort_word(sorted_word);

	for(p = hashtab[hash(sorted_word)], free(sorted_word); p; p = p->next)
		if(strcasecmp(word, p->word) == 0)
			return p;

	return NULL;
}

static int strcasecmp(char *s, char *t)
{
	for(; tolower(*s) == tolower(*t); s++, t++)
	{
		if(*s == '\0')
			return 0;
	}
		
	return *s - *t;
}

static FILE* open_file(char *filename)
{
	struct _stat buffer;
	int status;
	FILE *fp;

	/* check file status */
	status = _stat(filename, &buffer);

	/* file doesn't exist */
	if(status != 0)
		return NULL;

	/* path specifies an ordinary file and the file has read permission */
	if((buffer.st_mode & _S_IFREG) && (buffer.st_mode & _S_IREAD))
	{
		/* file is empty */
		if(buffer.st_size == 0)
			return NULL;

		/* open file in read mode */
		fp = fopen(filename, "r");

		if(fp == NULL)
			return NULL;

		return fp;
	}

	return NULL;
}

static int getline(char *s, int lim, FILE *fp)
{
	int i;
	char c;

	for(i = 0; i < (lim-1) && (c = getc(fp)) != EOF && c != '\n'; i++)
		s[i] = c;

	if(c == '\n')
		s[i++] = c;

	s[i] = '\0';

	return i;
}

static char* getword(char *s, const char *sep)
{
	char *p, *tokenptr;

	/* static pointer pointing to the current position in s */
	static char *currentp = NULL;

	/* if s is not NULL, point currentp to starting of NULL */
	if(s != NULL)
		currentp = s;

	/* when the function is called for the first time and s is NULL, return NULL */
	if(s == NULL && currentp == NULL)
		return NULL;

	/* bypass the initial seperator characters */
	for(p = currentp; *p != '\0'; p++)
	{
		const char *sep_p;

		/* check if the character is seperator */
		for(sep_p = sep; *sep_p != '\0'; sep_p++)
		{
			if(*sep_p == *p)
				break;
		}

		if(*sep_p == '\0')
			break;						/* if character other then separator is found, break out of the loop */
	}

	/* end of string is reached */
	if(*p == '\0')
	{
		currentp = NULL;
		return NULL;
	}

	/* find the next seperator character */
	for(tokenptr = p; *p != '\0'; p++)
	{
		const char *sep_p;

		for(sep_p = sep; *sep_p != '\0'; sep_p++)
		{
			if(*sep_p == *p)
				break;
		}

		if(*sep_p != '\0')
			break;					/* if the character is separator then break out of loop */
	}

	if(*p == '\0')
		currentp = p;
	else
	{
		currentp = p+1;
		*p = '\0';
	}
	return tokenptr;
}