#include <stdio.h>
#include <iostream.h>
#include <math.h>
#include "wordlist.h"
// Tester forskjellig HASH-funksjoner og måler deres evne
// til spredning. 

unsigned int hash1(char*, int);
unsigned int hash2(char*, int);
unsigned int hash3(char*, int);

#define BUFLEN 100
#define TABLESIZE 30007

void main() {
	int hashtab1[TABLESIZE];
	int hashtab2[TABLESIZE];
	int hashtab3[TABLESIZE];

	char inbuf[BUFLEN];
	int i, h1, h2, h3, antOrd;
	int overflow1, overflow2, overflow3;	// teller kollisjoner
	int used1, used2, used3;
	used1 = used2 = used3 = 0;
	overflow1 = overflow2 = overflow3 = 0;
	for (i=0; i < TABLESIZE; i++) 
		hashtab1[i] = hashtab2[i] = hashtab3[i] = 0;
	Wordlist *wl = new Wordlist("d:\\words.txt");
	i = wl->readWord(inbuf, BUFLEN);
	antOrd = 0;
	while (i != 0) {
		 cout << inbuf << endl;
		antOrd++;
		h1 = hash1(inbuf, TABLESIZE);
		h2 = hash1(inbuf, TABLESIZE);
		h3 = hash3(inbuf, TABLESIZE);
		if (hashtab1[h1] != 0) overflow1++;
		else hashtab1[h1] = 1;
		if (hashtab2[h2] != 0) overflow2++;
		else hashtab2[h2] = 1;
		if (hashtab3[h3] != 0) overflow3++;
		else hashtab3[h3] = 1;
		i = wl->readWord(inbuf, BUFLEN);
	}
	
	for (i=0; i<TABLESIZE; i++) {
		if (hashtab1[i]) used1++;
		if (hashtab2[i]) used2++;
		if (hashtab3[i]) used3++;
	}

	cout << "Antall ord behandlet: " << antOrd << endl;
	cout << "Hash1 (koll/utn): " << overflow1 << "," << used1 << endl;
	cout << "Hash2 (koll/utn): " << overflow2 << "," << used2 << endl;
	cout << "Hash3 (koll/utn): " << overflow3 << "," << used3 << endl;
}

// Denne funksjonen tar ikke hensyn til bokstavenes stilling i ordet.
// bare, areb, reba, ... får samme hashverdi
unsigned int hash1(char *key, int tablesize) {
	unsigned long hashval = 0;
	while (*key != '\0') {
		hashval += (int)*key;
		key ++;
	}
	return hashval % tablesize;
}

unsigned int hash2(char *key, int tablesize) {
	unsigned long hashval = 0;
	unsigned int i = 0;
	while (*key != '\0') {
		hashval += (pow(29,i)*(int)key[i]);
		i++;
		key++;
	}
	return hashval % tablesize;
}

unsigned int hash3(char *key, int tablesize) {
	unsigned long hashval = 0;
	while (*key != '\0') {
		hashval = (hashval << 3) + (int)*key;
		key++;
	}
	return hashval % tablesize;
}