//PAC: simple hash table of trees example
//jleblanc: 2.23.06
//Requires a datain.txt file with words and a hashtable.txt file to write out to
//These examples are a bit fragile (e.g. words can be a max of only 50 characters and
//there is no error checking for them if overflow), but work within these current confines.
//The hash function is a simple string length function
/*
For this week, investigate the following issues:
>
> *  reading and writing strings
> *  working with tree structures -
>    declaring the type, adding an element,
>    traversing the tree
> *  creating a hash table, where the bins are trees
>    writing a hash function, "probing" the table,
>    displaying the contents of the table
>
> Then, combine these features, such that your program
> reads in from a file of words, one word per line,
> and
> proceeds to store the words in appropriate bins in
> the
> hash table (non-redundantly) ... when the file is
> finished, write the contents of the hash table out
> to
> a file called "hashtable.txt" (make it clear as to
> which bin each element comes from).
>
>
> A big part of this week's work is the independent
> investigation of the features.  The program itself
> will probably be fewer than 100 lines of code.
> Develop and test the features in stages, assuring
> for
> yourself that each works as you expect.
>
*/

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

#define num_bins 50

//STRUCTURES////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

//boolean type
typedef enum {FALSE, TRUE}  boolean; 

//tree node
struct tnode
{           
	char word[50];
	int count;
	struct tnode *child[2];
};
typedef struct tnode  tnode;

//tree
struct tree
{         
 	tnode  *top;
};
typedef struct tree  tree;

//hash table
struct hashtable
{
	int number_bins;
	struct tree hash[num_bins];
}; 
typedef struct hashtable hashtable;

//FUNCTION DECLARATIONS//////////////////////////////////////////////////////////////////////////////////////////////////////////////

//tree functions
boolean tempty(tree t);
boolean tfull (tree t);
void tinit(tree *t);
void add(tree *t, char item[]);
void addnode(tnode *n, char item[]);
void fprinttree(FILE *fp,tree *t);
void fprintnode(FILE *fp, tnode *n);
//hashtable functions
int hashfunction(char input[]);
void init_hash(hashtable *h);
void load_hash(char file[], hashtable *h);
void print_hash(char file[], hashtable *h);

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//MAIN FILE
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void main()
{
	hashtable hasht;
	char source_file[] = "datain.txt";
	char output_file[] = "hashtable.txt";

	//Initialize the Hash Table
	init_hash(&hasht);

	//Read the data into the Hash Table
	load_hash(source_file,&hasht);

	//Print out the contents of the Hash Table
	print_hash(output_file,&hasht);
}

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//FUNCTIONS
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

boolean tempty(tree t)
{  return ((boolean) (t.top == NULL)); } 
boolean tfull (tree t)
{  return FALSE; }

void tinit(tree *t)
{ t->top=NULL; }

//Add elements to the tree/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void add(tree *t, char item[])
{
	if(tempty(*t)==TRUE)
	{  	
		t->top=malloc(sizeof(tnode));
		strcpy( t->top ->word, item);
		t->top->count=1;
		t->top->child[0] =NULL;
		t->top->child[1] =NULL;
	}
	else
	{ addnode(t->top, item);}
}
	
void addnode(tnode *n, char item[])
{
	int direction;
	
	direction=strcmp(item, n->word);

	if(direction==0)
		{ n->count++;}	
	else
	{
		if( direction<0) //incoming less, look/add left
		{ direction=0;}
		else {direction=1;}
	
		if(n->child[direction] ==NULL)
		{
			n->child[direction] =malloc(sizeof(tnode));
			strcpy( n->child[direction] ->word, item);
			n->child[direction] ->count=1;
			n->child[direction] ->child[0]=NULL;
			n->child[direction] ->child[1]=NULL;
		}
		else//Recursive call
		{		
			addnode(n->child[direction], item);
		}
	}	
}

//Print the tree to a file///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

void fprinttree(FILE *fp,tree *t)
{
	if(tempty(*t)==TRUE)
		{ fprintf(fp, "tree is empty\n");}
	else
		{ fprintnode(fp, t->top);}
}

void fprintnode(FILE *fp, tnode *n)
{
	fprintf(fp,"\t%s occuring %d times\n", n->word, n->count);

	if(n->child[0] != NULL)
	{ fprintnode(fp, n->child[0] );}
	if(n->child[1]  !=NULL)
	{fprintnode(fp, n->child[1] );}
}

//Hash Function////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

int hashfunction(char input[])
{
	return (int) strlen(input);
}

//Functions Running the Hash Table////////////////////////////////////////////////////////////////////////////////////////////////////

void init_hash(hashtable *h)
{
	h->number_bins=num_bins;
	
	for(int i=0; i<h->number_bins; i++)
	{ tinit(&h->hash[i]);}
}

void load_hash(char file[], hashtable *h)
{
	char hold[50];
	int index;
	FILE *fp;
	
	fp = fopen(file, "r");	

	while ( !feof( fp )  )
 	{
		if(fscanf (fp,"%s", &hold) != EOF)
		{
			index=hashfunction(hold);
			if(index>-1 && index < h->number_bins)
				{add(&h->hash[index], hold);}
		}
 	}
	fclose(fp);
}

void print_hash(char file[], hashtable *h)
{
	FILE *fp;

	fp = fopen(file, "w");	
	fprintf(fp,"The Start\n");
	for(int i=0; i < h->number_bins; i++)
	{
		if(!tempty(h->hash[i]))
		{
			fprintf(fp,"\nIn hash bin %d:\n", i);
			fprinttree(fp, &h->hash[i]);
		}
	}
	fprintf(fp,"\n The End\n\n");
	fclose(fp);
}