#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 &key) {
	int value = 1;
	for (int position = 0; position < max_key_length; position++){
		if(key[position] == 0){
			break;
		}
		value *= key[position];
	}
	value %= hash_size;
	if (value < 0){
		value += hash_size;
	}
	return value;
}
/**
 * Insert new record
 * Collision function uses h+i^2
 *
 */
int HashTable::insert(const string &record){
	if(record_count == hash_size){
		return ERROR_TABLE_FULL;
	}
 
	int hash_key = hash(record);
	int increment = 1;
 
	int probe_counter=0;
	int hash_mid=(hash_size+1)/2;
 
	while(1){
		//Check for overflow
		if(probe_counter > hash_mid){
			return ERROR_RECORD_NOT_FOUND;
		}
		string tmp = table[hash_key];
		//Empty slot
		if(tmp.empty()){
			break;
		}//Position already taken, duplicate keys are not allowed
		else if(tmp.compare(record) == 0) {
			return ERROR_DUPLICATE_RECORD;
		}
		else{
			//Handles collision using h+i^2
			hash_key = (hash_key+increment) % hash_size;
			increment+=2;
			probe_counter++;
		}
	}
	table[hash_key] = record;
	record_count++;
	return hash_key;
 
}
/**
 * Retrieve record index
 */
int HashTable::retrieve(const string &record){
	int hash_key = hash(record);
	int increment = 1;
 
	int probe_counter=0;
	int hash_mid=(hash_size+1)/2;
 
	while(1){
		//Overflow encountered if the probe is bigger than hash_size/2
		if(probe_counter > hash_mid){
			return ERROR_RECORD_NOT_FOUND;
		}
		string tmp = table[hash_key];
		//Record empty for the key
		if(tmp.empty()) {
			break;
		}
		else if(tmp.compare(record) == 0){
			return hash_key;
		}
		else{
			hash_key = (hash_key+increment) % hash_size;
			increment+=2;
			probe_counter++;
		}
	}
	return ERROR_RECORD_NOT_FOUND;
}

/**
 * Implementation of Level order traversal
 * Prints nodes at each level left to right
 */
template <class Record>
void AVL_tree<Record>::level_order() {
	cout << "++++++++++++++++++++++" << endl;
	if(this->root == NULL){
		cout << "EMPTY TREE" << endl;
	}else{
		cout << endl;
		queue<Binary_node<Record>*> nodeQueu;
		nodeQueu.push(this->root);
		while(!nodeQueu.empty()){
			Binary_node<Record>* entry=nodeQueu.front();
			cout<<entry->data<<" ";
			if(entry->left != NULL){
				nodeQueu.push(entry->left);
			}
			if(entry->right != NULL){
				nodeQueu.push(entry->right);
			}
			nodeQueu.pop();
		}
	}
	cout << "\n++++++++++++++++++++++" << endl;
}