//Includes
#include <stdio.h>
#include <fcntl.h>
#include <sys/stat.h>
#include <string.h>
#include <iostream>

using std::cout;
using std::endl;
using namespace std;

int NUMBUCKETS;
int OVERFLOW_BUCKET;

class Record{
public:
	int key;
	int data;

	Record()
	{
		key = -1;
		data = -1;
	}
};

class Bucket{
public:
	int bucket_id;
	int next_bucket;
	int is_full;
	Record *bucket_record;

	Bucket()
	{
		bucket_record = new Record[4]();
		
		for(int i=0;i<4; i++)
		{
			bucket_record[i].key = -1;
			bucket_record[i].data = -1;
		}

		bucket_id = -1;
		next_bucket = -1;
		is_full = 0;
	}
};

class Hash_Table {
public:
	int *index;
	Bucket *hash_bucket;

	Hash_Table()
	{
		index = new int[NUMBUCKETS];
		hash_bucket = new Bucket[NUMBUCKETS];

				//Bucket creating_buckets;
		for(int i = 0; i< NUMBUCKETS; i++)
		{
			index[i] = i;	
			hash_bucket[i].bucket_id = i + 1;
		}
	}

	int hash_function(int);
	int insert_function(int, int);
};

int Hash_Table::hash_function (int key)
{
	int hash_index;
	hash_index = key % NUMBUCKETS;

	return hash_index;
}

//Hash_Table hashing;

void overflow_function(int new_bucket_id, int index_num, int key, int key_data)
{
	int j = 0;


	Bucket new_bucket;
	new_bucket.bucket_id = new_bucket_id;

	for(int i = 0; i<4; i++)
			{
				j = -1;

				if(new_bucket.bucket_record[i].data == -1)
				{
					j = i;
					break;
				}

			}

			if(j == -1)
			{
			 if (new_bucket.next_bucket == -1)
			 {
			 	 OVERFLOW_BUCKET++;
			 	 cout << "Second overflow bucket, recurrsion" << endl;
			 	  new_bucket.next_bucket = OVERFLOW_BUCKET;
			 	  overflow_function(new_bucket.next_bucket, index_num, key, key_data);
		 	 }
			 else
			 	overflow_function(new_bucket.next_bucket,index_num, key, key_data);
			}

			else
			{
				cout<< "new bucket id: " << new_bucket.bucket_id;
				//inserts the initial first values in the bucket
				new_bucket.bucket_record[j].key= key;
				cout << "  Key from Overflow: " << new_bucket.bucket_record[j].key;
				new_bucket.bucket_record[j].data= key_data;
				cout << "  Data from Overflow: " << new_bucket.bucket_record[j].data;
			}
}

//Hash_Table h;


int Hash_Table::insert_function(int user_key, int user_data)
{
	int key_index;
	int j = -1;
	int i =0;


	int d = 0;


	key_index =  this->hash_function(user_key);
	cout<<"Key Index: "<< key_index << endl;
	//cout<<"hhhh: " << hash_bucket[0].bucket_record[0].data << endl;

	for(i = 0; i<4; i++)
	{
		j = -1;

		if(  hash_bucket[key_index].bucket_record[i].data == -1)
		{
			j = i;
			break;
		}

	}

	if(j == -1)
	{
		// hash_bucket[key_index].is_full = 1;
	 	if (  hash_bucket[key_index].next_bucket == -1)
	 	{
		 	OVERFLOW_BUCKET++;
		  	 hash_bucket[key_index].next_bucket = OVERFLOW_BUCKET;
		  	overflow_function(  hash_bucket[key_index].next_bucket, key_index, user_key, user_data);
	 	}
	 	else
			overflow_function( hash_bucket[key_index].next_bucket,key_index, user_key, user_data);
	}

	else
	{
		//inserts the initial first values in the bucket
		  hash_bucket[key_index].bucket_record[j].key= user_key;
		  hash_bucket[key_index].bucket_record[j].data= user_data;
	}
	return 0;
}

void print()
{

	/*for(int i = 0; i< NUMBUCKETS; i++)
	{
		for(int g=0;g<4;g++)
		{
			cout << "Index: " << hashing.index[i];
			cout << " Bucket: " << hashing.hash_bucket[i].bucket_id;
			cout << " Record: " << g << " Key: " << hashing.hash_bucket[i].bucket_record[g].key;
			cout << " Data: " << hashing.hash_bucket[i].bucket_record[g].data << endl;
		}

	}*/
}


int main()
{
	int bucket_num = 0;
	int insert_key;
	int insert_data;
	Hash_Table *h = new Hash_Table();
	Hash_Table hashing;

	cout << "\nEnter Bucket Number: ";
	cin >> bucket_num;

	NUMBUCKETS = bucket_num;
	OVERFLOW_BUCKET = bucket_num;



	while (insert_key != 0 && insert_data != 0)
	{
		int j = -1;
		cout << "\n Insert Key and its Data: ";
		cin >> insert_key;
		cin >> insert_data;

		if (insert_key == 0 && insert_data == 0)
			break;

		hashing.insert_function(insert_key, insert_data);

	}

	print();
return 0;

}