#include<iostream>
using namespace std;

class Tacka3D
{public:

	int x, y, z;

	Tacka3D(int x = 0, int y = 0, int z = 0)
	{
		this->x = x;
		this->y = y;
		this->z = z;
	}
};

class OtvorenoHesiranje
{
	int brojac;
	int max_vel;
	Tacka3D* niz;
	bool* zauzeto;

	bool Pun() { return brojac == max_vel; }
	bool Prazan() { return brojac == 0; }
	int hashFunkcija(Tacka3D k, int i=0)
	{
		int pozicija = (int)(sqrt(pow((k.x + k.y + k.z), 2)) + i * sqrt(pow(k.x, 2) / 3 + pow(k.y, 2) / 3 + pow(k.z, 2) / 3)) % max_vel;
		return pozicija;
	}

public:
	OtvorenoHesiranje(int max = 10)
	{
		brojac = 0;
		max_vel = max;
		niz = new Tacka3D[max];
		zauzeto = new bool[max];
		for (int i = 0; i < max; i++)
		{
			zauzeto[i] = false;
		}
	}

	bool Dodaj(Tacka3D t)
	{
		if (Pun())
			return false;
		int pozicija = hashFunkcija(t);
		int brojPokusaja = 0;

		while (zauzeto[pozicija])
		{
			brojPokusaja++;
			pozicija = hashFunkcija(t, brojPokusaja);
		}

		niz[pozicija] = t;
		brojac++;
		zauzeto[pozicija] = true;
		return true;
	}

	bool Ukloni(Tacka3D t)
	{
		if (Prazan())
			return false;

		int pozicija = hashFunkcija(t);
		int brojPokusaja = 0;

		while (brojPokusaja<max_vel)
		{
			if (zauzeto[pozicija] && niz[pozicija].x == t.x && niz[pozicija].y == t.y && niz[pozicija].z == t.z)
			{
				zauzeto[pozicija] = false;
				brojac--;
				return true;
			}

			brojPokusaja++;
			pozicija = hashFunkcija(t, brojPokusaja);
		}

		return false;
	}

	bool Pretrazi(Tacka3D t)
	{
		if (Prazan())
			return false;

		int pozicija = hashFunkcija(t);
		int brojPokusaja = 0;

		while (brojPokusaja < max_vel)
		{
			if (zauzeto[pozicija] && niz[pozicija].x == t.x && niz[pozicija].y == t.y && niz[pozicija].z == t.z)
			{
				return true;
			}

			brojPokusaja++;
			pozicija = hashFunkcija(t, brojPokusaja);
		}

		return false;
	}
};


int main()
{
	Tacka3D t1(1, 2, 3), t2(4, 5, 6), t3(7, 8, 9);
	OtvorenoHesiranje h;
	if (h.Dodaj(t1))
		cout << "Uspjesno" << endl;
	if (h.Dodaj(t2))
		cout << "Uspjesno" << endl;
	if (h.Dodaj(t3))
		cout << "Uspjesno" << endl;

	if (h.Ukloni(t3))
		cout << "Uspjesno" << endl;

	if (!h.Pretrazi(t3))
		cout << "Nije uspjesno" << endl;
	system("pause>0");
	return 0;
}