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

/************************* Hash Table Definition *************************/

/* Parameters for hash table */

#define MAXWORDLEN 31   /* length of a word (includes terminating '\0') */
static int primenums[8] = { 1009, 2027, 4057, 8117, 20011, 40031, 80071, 111217 };

/* Hash table data type */

typedef enum { LINEAR, DOUBLE } HashType;

typedef struct {
    char word[MAXWORDLEN];
    int freq;
} TblEntry;                     /* hash table entry */

typedef struct {
    HashType type;              /* type of hash table (linear probing or double hashing) */
    TblEntry *entry;			/* table entries */
	int numextended;			/* number of times table has been extended */
	int tblsizes[10];			/* list of table sizes used */
    int numaccess;              /* total number of hash table accesses */
    int numwords;               /* number of distinct words */
    int numprobes;              /* total number of probes */
    int maxprobelen;            /* maximum length of a probe sequence */
	int pos;					/* used for rehashing. indicates the position (in entry) of
								   the word that's just been rehashed. */

} HashTbl;


/************************* Hash Table Routines - prototypes ***********************/


/* Hash function based on division method.
   The given word is treated as a number in base 128, and its remainder
   when divided by the given modulus is computed. */
static int DivMethod(const char *word, int modulus);

/* Initializes a hash table */
void InitHashTbl(HashTbl *tbl, HashType type);

/* Add a word into the hash table.  If the word exists, increment its count.
   Note that this function is also used when extending the hashtable.
   function returns 0.0 if no rehashing is done, otherwise
   it returns the time taken to rehash the table.  */
float AddWord(HashTbl *tbl, char *word);

/* Finds the most frequently occuring word in a hash table.
   Returns the frequency of that word, and stores that word in *maxword.  */
int FindMax(char **maxword, HashTbl *tbl);