#include "hashtable.h"
#include <stdio.h>
#include <stdlib.h>
//#pragma once
//#ifndef HASH_TABLE_H_INCLUDED
//#define HASH_TABLE_H_INCLUDED

typedef struct element
{
	int key;
	int data;
	struct element* next;
} list;

typedef struct
{
	int max_lenght;
	int size;
	int amount_blocks;
	list** table;
} hash_table;

int control_lenght;
int index_max_lenght;

int get_hash(int a, int m)
{
	return (a % m);
}

list* get_last(list* head)
{
	while (head->next)
		head = head->next;
	return head;
}

void add(hash_table* head, int k, int x)
{
	if (*head == NULL)
	{
		*head = (list*)malloc(sizeof(list));
		(*head)->key = k;
		(*head)->data = x;
		(*head)->next = NULL;
	}
	else
	{
		list* last = get_last(*head);
		list* new_last = (list*)malloc(sizeof(list));
		new_last->key = k;
		new_last->data = x;
		new_last->next = NULL;
		last->next = new_last;
	}
}

void print(list* head)
{
	while (head)
	{
		printf("key %d : value %d\n", head->key, head->data);
		head = head->next;
	}
	printf("\n");
}

void print_table(hash_table* hash)
{
	int i;
	for (i = 0; i < size_block * amount_blocks; i++)
	{
		printf("%d block\n", i);
		print(hash[i]);
	}
}

void free_memory(list* head)
{
	while (head)
	{
		list* next = head->next;
		free(head);
		head = next;
	}
}

int find(list* head, int k)
{
	while (head)
	{
		if (head->key == k)
			return (head->data);
		head = head->next;
	}
	return -1;
}


int delete_by_key(hash_table* head, int k)
{
	if (*head)
	{
		if ((*head)->key == k)
		{
			list* curr = *head;
			*head = (*head)->next;
			free(curr);
			return 1;
		}
		list* prev = (*head);
		list* curr = (*head)->next;
		while (curr)
		{
			if (curr->key == k)
			{
				prev->next = curr->next;
				free(curr);
				return 1;
			}
			prev = curr;
			curr = curr->next;
		}
	}
	return 0;
}

hash_table* rebalance()
{
	int i;
//	   printf("\nrebalance\n");                                   //  убрать
	amount_blocks++;
	int m = size_block * amount_blocks;
	hash_table* new_hash = (hash_table*)malloc(sizeof(list) * m);
	for (i = 0; i < m; i++)
		new_hash[i] = NULL;
	free(lenght);
	lenght = (int*)calloc(m, sizeof(int));
	control_lenght = 0;
	index_max_lenght = 0;
	for (i = 0; i < m - size_block; i++)
	{
		list* head = hash[i];
		while (head)
		{
			int k = head->key;
			int hash_k = get_hash(k, size_block);
			int d = head->data;
			int curr_box = rand() % amount_blocks;
			add(&new_hash[hash_k + size_block * curr_box], k, d);
			lenght[hash_k + size_block * curr_box]++;
			if (lenght[hash_k + size_block * curr_box] > control_lenght)
			{
				control_lenght = lenght[hash_k + size_block * curr_box];
				index_max_lenght = hash_k + size_block * curr_box;
			}
			head = head->next;
		}
	}
	for (i = 0; i < m - size_block; i++)
		free_memory(hash[i]);
	free(hash);

//	   printf("\nend rebalance\n"); //  убрать
//	   print_table(new_hash); //  убрать
//	   printf("\nend rebalance\n"); //  убрать
	return new_hash;
}

void find_and_delete(hash_table* hash, int key)
{
	int k = get_hash(key, size_block);
	int i;
	for (i = 0; i < amount_blocks; i++)
	{
		if (delete_by_key(&hash[size_block * i + k], key))
		{
			lenght[size_block * i + k]--;
			if (size_block * i + k == index_max_lenght)
				control_lenght--;
		}
	}
}

hash_table* insert(hash_table* hash, int key, int x)
{
//	print_table(hash);                                      // убрать
	int k = get_hash(key, size_block);
//	    printf("in block %d insert key = %d  value = %d\n<<<<<<<>>>>>>>>>>>\n",k,key,x); //убрать

	int curr_box = rand() % amount_blocks;
	find_and_delete(hash, key);                                  //я не понимаю этот вызов здесь к или кеу?, с кеу работает random_number_padding
	add(&hash[k + size_block * curr_box], key, x);
	lenght[k + size_block * curr_box]++;
	if (lenght[k + size_block * curr_box] > control_lenght)
	{
		control_lenght = lenght[k + size_block * curr_box];
		index_max_lenght = k + size_block * curr_box;
	}
	if (control_lenght > size_block)
	{

		hash = rebalance();

	}
	return hash;
}

hash_table* init()
{
	hash = (hash_table*)malloc(sizeof(hash_table));
	hash -> size = 5;
	hash -> max_lenght = 0;
	hash -> amount_blocks = 1;
	hash -> table = (list**)malloc(sizeof(list*) * (hash -> size) * (hash -> amount_blocks));
	//int i;
	for (int i = 0; i < (hash -> size) * (hash -> amount_blocks); i++)
	{
		hash -> table[i] = NULL;
	}
	return hash;
}

int search(int input_key)
{
	int k = get_hash(input_key, size_block);
	int i;
	for (i = 1; i < amount_blocks + 1; i++)
	{
		return find(hash[k * i], input_key);
	}
}

void free_table(hash_table* hash)
{
	int i;
	for (i = 0; i < size_block * amount_blocks; i++)
		free_memory(hash[i]);
	free(hash);
}


//#endif // HASH_TABLE_H_INCLUDED