#define ERROR_TABLE_FULL       -1
#define ERROR_RECORD_NOT_FOUND -1
#define ERROR_DUPLICATE_RECORD -1
 
class HashTable{
public:
	HashTable(int table_size);
	int insert(const string &record);
	int retrieve(const string &record);
 
private:
	int hash(const string &record);
	int hash_size;
	int record_count;
	string* table;
};
 
/**
 * Constructor accepting table_size
 */
HashTable::HashTable(int table_size){
	hash_size = table_size;
	table = new string[hash_size];
	record_count = 0;
}
 
/**
 * Hash function calculated using
 * product p of all the characters of the key
 * and then returns the index where index=s%hash_size
 */
int HashTable::hash(const string &record) {
	int value = 1;
	for (int position = 0; position < max_key_length; position++){
		if(record[position] == 0){
			break;
		}
		value *= record[position];
	}
	value %= hash_size;
	if (value < 0){
		value += hash_size;
	}
	return value;
}
 
/**
 * Insert new record into out table, making sure that the table is not full
 */
int HashTable::insert(const string &record){
	//Check if HashTable is full if it is then return overflow
	if(record_count == hash_size){
		return ERROR_TABLE_FULL;
	}
	int hash_key = hash(record);
	while(1){
		string tmp = table[hash_key];
		//Check if table bucket is empty
		if(tmp.empty()) {
			break;
		}//Position already taken, duplicate keys are not allowed 0 = equal
		else if(tmp.compare(record) == 0) {
			return ERROR_DUPLICATE_RECORD;
		}
		//Collision detected multiple records mapped to same location
		//Try next bucket
		else {
			hash_key = (hash_key+1) % hash_size;
		}
	}
	table[hash_key] = record;
	record_count++;
 
	return hash_key;
}
 
/**
 * Retrieve record index
 */
int HashTable::retrieve(const string &record){
	int hash_key = hash(record);
	while(1){
		string tmp = table[hash_key];
		//Record empty for the key
		if(tmp.empty()){
			break;
		}//if entry found return index
		else if(tmp.compare(record) == 0) {
			return hash_key;
		}
		else { //Resolving collision using linear probing
			hash_key = (hash_key+1) % hash_size;
		}
	}
 
	//No record Found
	return ERROR_RECORD_NOT_FOUND;
}