#include <iostream>
#include <string>

template <typename T>
class Array {
private:
	const int multip = 2;

	void increase()
	{
		this->MAX_CAP *= this->multip;
		T* new_array = new T[MAX_CAP];

		for (unsigned int i = 0; i < this->counter; i++)
			new_array[i] = this->array[i];

		delete[] this->array;
		array = new_array;
	}

	void set(unsigned int number, T data)
	{
		if (number < this->counter)
			this->array[number] = data;
	}

public:
	T* array;
	unsigned int counter;
	unsigned int MAX_CAP;
	Array()
	{
		this->MAX_CAP = 1;
		this->counter = 0;
		this->array = new T[MAX_CAP];
	}

	virtual ~Array()
	{
		//for (unsigned int i = 0; i < this->counter; i++)
			//delete array[i];
		delete[] array;
	}

	void add_(T data)
	{
		if (this->counter < this->MAX_CAP)
		{
			this->array[this->counter] = data;
			counter++;
		}
		else
		{
			this->increase();
			this->array[this->counter] = data;
			counter++;
		}
	}

	T return_(unsigned int number)
	{
		if (number < this->counter)
			return this->array[number];
		else
			return NULL;
	}

	std::string to_string()
	{
		std::string str;
		if (this->counter == 0)
			return "empty";

		for (unsigned int i = 0; i < this->counter && i < 5; i++)
			str = str + array[i].to_string() + " -> ";
		return str;
	}

	void reset_()
	{
		this->MAX_CAP = 1;
		this->counter = 0;

		T* new_array = new T[MAX_CAP];

		delete[] this->array;
		this->array = new_array;
	}
};

template<typename T>
class Node
{
public:
	std::string name;
	T data;

	std::string to_string()
	{
		return name + " " + std::to_string(data);
	}

	Node()
	{

	}

	Node(std::string str, T data)
	{
		this->name = str;
		this->data = data;
	}

	bool operator==(Node data)
	{
		if (this->data == data.data && this->name == data.name)
			return true;
		else
			return false;
	}
};

template<typename T>
class Hasz
{
private:

	int Max_cap;
	int Act_cap;

	void rehash()
	{
		int newmax = Max_cap * 2;
		Array<T>* newtab = new Array<T>[newmax];

		for (int i = 0; i < this->Act_cap; i++)
		{
			for (int j = 0; j < table[i].counter; j++)
			{
				T tmp = table[i].array[j];

				std::string nazwa = tmp.name;
				int lenght = nazwa.length();
				int suma = 0;

				for (int i = 0; i < lenght; i++)
				{
					int x = lenght - i - 1;
					suma = suma + nazwa[i] * pow(31, x);
				}
				suma = suma % newmax;
				newtab[abs(suma)].add_(tmp);
			}
		}
		delete[] table;
		Max_cap = newmax;
		table = newtab;
	}

	int getHash(std::string data)
	{
		int lenght = data.length();
		int suma = 0;

		for (int i = 0; i < lenght; i++)
		{
			int x = lenght - i - 1;
			suma = suma + data[i] * pow(31, x);
		}
		suma = suma % Max_cap;
		return abs(suma);
	}

public:
	Array<T>* table;
	Hasz()
	{
		Max_cap = 2;
		Act_cap = 0;
		table = new Array<T>[Max_cap];
	}

	void add(T data)
	{
		if (Act_cap >= (float)Max_cap * 0.75)
			this->rehash();

		std::string nazwa = data.name;
		int lenght = nazwa.length();
		int suma = 0;
		for (int i = 0; i < lenght; i++)
		{
			int x = lenght - i - 1;
			suma = suma + nazwa[i] * pow(31, x);
		}
		suma = suma % Max_cap;

		table[abs(suma)].add_(data);
		Act_cap++;
	}

	std::string to_string()
	{
		std::string str;

		for (int i = 0; i < Max_cap && i < 10; i++)
		{
			str = str + table[i].to_string() + "\n";
		}
		return str;
	}

	T* findHash(T data)
	{
		int hasz = getHash(data.name);
		for (int i = 0; i < table[hasz].counter; i++)
		{
			if (table[hasz].array[i] == data)
				return &table[hasz].array[i];
		}
	}

	bool deleteHash(T data)
	{
		int hasz = getHash(data.name);
		int i;
		if (table[hasz].counter == 0)
			return false;
		for (i = 0; i < table[hasz].counter; i++)
		{
			if (table[hasz].array[i] == data)
				break;
			return false;
		}

		table[hasz].array[i] = table[hasz].array[table[hasz].counter-1];
		table[hasz].counter--;
		return true;
	}
};

int main()
{
	Node<int> data("string", 6);
	Node<int> data1("kusi", 1);
	Node<int> data2("kek", 2);
	Node<int> data3("XD", 69);
	Node<int> nowy("nowy", 10);

	Hasz<Node<int>>* hasz = new Hasz<Node<int>>;

	hasz->add(data);
	std::cout << hasz->to_string() << std::endl << std::endl;
	hasz->add(data1);
	std::cout << hasz->to_string() << std::endl << std::endl;
	hasz->add(data2);
	std::cout << hasz->to_string() << std::endl << std::endl;
	hasz->add(data3);
	std::cout << hasz->to_string() << std::endl << std::endl;
}