#include <fstream.h>
#include <string.h>

const int MAX_SIZE = 31;
const int MAX_LENGTH = 35;
typedef char string[MAX_LENGTH];

int calcHashKey(string searchKey) {
	int len = strlen(searchKey);
	int lRetVal = searchKey[0] - 64;
	for ( int i=1; i<len; i++ ) {
		lRetVal = lRetVal * 32 + searchKey[i] - 64;
	}
	return lRetVal;
}

int linearProbe(string hashTable[MAX_SIZE], int hashKey) {
	int iRetVal = -1;
	for ( int i=hashKey+1; i != hashKey; i++ ) {
		i %= MAX_SIZE;
		if ( strlen(hashTable[i]) == 0 ) {
			iRetVal = i;
			break;
		}
	}
	return iRetVal;
}

int quadraticProbe(string hashTable[MAX_SIZE], int hashKey) {
	int iRetVal = -1;
	int stepNbr = 0;
	int stepVal = 0;
	int index = 0;
	for ( int i=0; i<MAX_SIZE; i++ ) {
		stepNbr++;
		stepVal = stepNbr * stepNbr;
		index = (hashKey + stepVal) % MAX_SIZE;
		if ( strlen(hashTable[index]) == 0 ) {
			iRetVal = i;
			break;
		}
	}
	return iRetVal;
}

int doubleHash(string hashTable[MAX_SIZE], int hashKey) {
	int iRetVal = -1;
	int stepVal = 1;
	int index = hashKey;
	for ( int i=0; i<MAX_SIZE; i++ ) {
		index = (index + stepVal) % MAX_SIZE;
		if ( strlen(hashTable[index]) == 0 ) {
			iRetVal = i;
			break;
		}
	}
	return iRetVal;
}

void main() {
	string hashTable[MAX_SIZE];
	string input;
	int hashKey = 0;
	int probeMethod = 0;

	for ( int i=0; i<MAX_SIZE; i++ ) {
		strcpy(hashTable[i],"");
	}

	ifstream InFile("names.txt");

	while (InFile.peek() != EOF ) {
		InFile.getline(input, MAX_LENGTH);
		hashKey = calcHashKey(input) % MAX_SIZE;
		if ( strlen(hashTable[hashKey]) == 0 ) {
			strcpy(hashTable[hashKey], input);
		} else {
			switch (probeMethod) {
				case 0:
					hashKey = linearProbe(hashTable, hashKey);
					break;
				case 1:
					hashKey = quadraticProbe(hashTable, hashKey);
					break;
				case 2:
					hashKey = doubleHash(hashTable, hashKey);
					break;
			}
			if ( hashKey >= 0 ) {
				strcpy(hashTable[hashKey], input);
			} else {
				cout << "Could not place: " << input << "\n";
			}
		}
	}

	InFile.close();

	ofstream OutFile("output.txt");
	for (i=0; i<MAX_SIZE; i++) {
		OutFile << i << ": " << hashTable[i] << "\r\n";
	}
	OutFile.close();
}