//Makefile
CXX=g++

main: main.o hash.o
	${CXX} -o main -std=c++11 main.o hash.o

clean:
	rm -f *.o main

//hash.h
#include<list>
class Hash 
{ 
	private:
		int BUCKET;    // No. of buckets 
		int curr_size;
		std::list<int> *table; // Pointer to an array containing buckets 
	public: 
		Hash(int V);  // Constructor
		void insertItem(int x); // inserts a key into hash table 
		void searchItem(int key);
		void deleteItem(int key); // deletes a key from hash table 
		int hashFunction(int x); // hash function to map values to key
	 	void displayHash(); 
}; 

//hash.cpp
#include<iostream>
#include "hash.h"

using namespace std;

Hash::Hash(int b) 
{ 
	this->BUCKET = b; 
	table = new list<int>[BUCKET]; 
} 
  
void Hash::insertItem(int key) 
{ 
	if(curr_size == this->BUCKET){
		cout << "Cannot insert " << key << " -- table is full" << endl;
		return;
	}

	int index = hashFunction(key); 

	cout << "Inserting:" << key << " at index: " << index << endl;
	if(table[index].empty()){
		table[index].push_back(key);  
	}
	else{
		int new_index = index;
		while(true){
			cout << new_index << " was occupied -- trying next index " << endl;
			new_index = (new_index+1)%(this->BUCKET);
			if(table[new_index].empty()){
				table[new_index].push_back(key); 
				break;			
			}
		}
	}
	curr_size++;
} 
  
void Hash::deleteItem(int key) 
{ 
	// get the hash index of key 
	int index = hashFunction(key); 

	if(*(table[index].begin()) == key){
		table[index].erase(table[index].begin()); 
	}
	else{
		int new_index = index;
		while(true){
			new_index = (new_index+1)%(this->BUCKET);
			
			if(*(table[new_index].begin()) == key){
				table[new_index].erase(table[new_index].begin());
				curr_size--;
				break;			
			}
			if(new_index == index){
				cout << "Item not found" << endl;
				break;
			}
		}
	}

} 

void Hash::searchItem(int key) 
{ 
	// get the hash index of key 
	int index = hashFunction(key);
	if(*(table[index].begin()) == key){
		cout << "Item: " << key << " found at: " << index <<  endl;
	}
	else{
		int new_index = index;
		while(true){
			new_index = (new_index+1)%(this->BUCKET);
			
			if(*(table[new_index].begin()) == key){
				cout << "Item: " << key << " found at: " << new_index <<  endl; 
				break;			
			}
			if(new_index == index){
				cout << "Item not found" << endl;
				break;
			}
		}
	}
} 
  
// function to display hash table 
void Hash::displayHash() { 
	cout << endl << "Printing:" << endl;
	for (int i = 0; i < BUCKET; i++) { 
		cout << i; 
		for (auto x : table[i]) 
			cout << " --> " << x; 
		cout << endl; 
	} 
	cout << endl;
} 

int Hash::hashFunction(int x) { 
	return (x % BUCKET); 
} 

//main.cpp
#include "hash.h"

   
int main() 
{ 
	// array that contains keys to be mapped 
	int a[] = {15, 11, 27, 8, 12}; 
	//int a[] = {15, 11, 27, 8, 12, 18, 22}; 
	//int a[] = {15, 11, 27, 8, 12, 18, 22, 29}; 
	int n = sizeof(a)/sizeof(a[0]); // length of the array

	
	Hash h(7);   // 7 is count of buckets in hash table 

	// insert the keys into the hash table:
	h.displayHash();
	for (int i = 0; i < n; i++){ 
		h.insertItem(a[i]);   
		h.displayHash();
  	}

	h.searchItem(12); 
	h.deleteItem(12);
	h.displayHash();

	h.searchItem(8); 
	h.deleteItem(8); 
	h.displayHash();  

	return 0; 
} 

// Add to hash.h
int hashFunction2(int x); // hash function to map values to key

// modify hash.cpp
  
void Hash::insertItem(int key) 
{ 

	if(curr_size == this->BUCKET){
		cout << "Cannot insert " << key << " -- table is full" << endl;
		return;
	}
	int index = hashFunction(key); 

	cout << "Inserting: " << key << " at index: " << index << endl;
	// second hashing:
	int index2 = hashFunction2(key);
	int i = 0;
	while(true){
		int new_index = (index + i * index2) % (this->BUCKET); 
		
		if(table[new_index].empty()){
			table[new_index].push_back(key); 
			break;			
		}
		cout << new_index << " was occupied -- trying next index " << new_index << endl;
		i++;
	}
	curr_size++;
} 
  
void Hash::deleteItem(int key) 
{ 
	// get the hash index of key 
	int index = hashFunction(key); 
	int index2 = hashFunction2(key);
	int i = 0;
	while(true){
		int new_index = (index + i * index2) % (this->BUCKET); 
		
		if(*(table[new_index].begin()) == key){
			table[new_index].erase(table[new_index].begin());
			curr_size--;
			break;
						
		}
		i++;
	}
} 

void Hash::searchItem(int key) 
{ 

	int index = hashFunction(key); 
	int index2 = hashFunction2(key);
	int i = 0;
	while(true){
		int new_index = (index + i * index2) % (this->BUCKET); 
		
		if(*(table[new_index].begin()) == key){
			cout << "Item: " << key << " found at: " << new_index <<  endl; 
			break;		
		}
		i++;
	}
} 
  
int Hash::hashFunction2(int x) { 
	return 5 - (x % 5); 
} 

// modify hash.cpp

void Hash::insertItem(int key) 
{ 
	int index = hashFunction(key); 
	table[index].push_back(key);  
	cout << "Inserting:" << key << " at index: " << index << endl;
} 
  
void Hash::deleteItem(int key) 
{ 
	// get the hash index of key 
	int index = hashFunction(key); 
	
	// find the key in (inex)th list 
	list <int> :: iterator i; 
	for (i = table[index].begin(); i != table[index].end(); i++) { 
		if (*i == key) break; 
	} 

  	// if key is found in hash table, remove it 
	if (i != table[index].end()) 
		table[index].erase(i); 
} 

void Hash::searchItem(int key) 
{ 
	// get the hash index of key 
	int index = hashFunction(key); 

	// find the key in (inex)th list 
	list <int> :: iterator i; 
	for (i = table[index].begin(); i != table[index].end(); i++) { 
		if (*i == key) break; 
	} 

  	// if key is found in hash table: 
	if (i != table[index].end()){
		cout << "Item: " << key << " found at: " << index <<  endl;
	}
	else{
		cout << "Item not found" << endl;
	}
}