#include "stdafx.h"
#include <iostream>
#include <stack>
#include <list>
#include <string>
#include <queue>

using namespace std;
class Data
{
	int i = 0;
	int width;
	int height;
	int column = 0;
	int country_num = 0;
	stack <int> stos;
	list<int> *adj_list;
	priority_queue<int> *pq;
	int *path;
	// values: 0 - wall, 1 - standard, 2 - border, 3 - road standard , 4 - road border;
	struct block
	{
		int country_id;
		int block_id;
		int status; // 0 - pusty, 1 - odwiedzony, 2 - zakonczony
		int level; // poziom na którym znajduje się wierzcholek
		bool road = false;
		block* top;
		block* right;
		block* bottom;
		block* left;
		block* parrent;
		int top_value;
		int right_value;
		int bottom_value;
		int left_value;

		int number;
	}*head, *last;
public:
	Data(int wid, int hei, int num_country)
	{
		this->width = wid;
		this->height = hei;
		this->head = nullptr;
		this->last = nullptr;
		this->country_num = num_country;
		path = new int[25];
		adj_list = new list<int>[25];
	}
	~Data()
	{

	}
	int check()
	{
		block* checker = head;
		block* start = head;
		int checked_country[25];
		for (int i = 0; i < country_num; i++)
		{
			checked_country[i] = 0;
		}
		while (start != nullptr)
		{
			while (checker != nullptr)
			{
				//  cout << "Node:" << checker->block_id << endl;
				if (checker->road == false)
				{
					if ((checker->left != nullptr) && (checker->left->road == false) && (checker->left_value == 2))
					{
						if (checker->block_id != 0)
							return checker->block_id;
						return 1;
					}
					if ((checker->bottom != nullptr) && (checker->bottom->road == false) && (checker->bottom_value == 2))
					{
						if (checker->block_id != 0)
							return checker->block_id;
						return 1;
					}
					if ((checker->right != nullptr) && (checker->right->road == false) && (checker->right_value == 2))
					{
						if (checker->block_id != 0)
							return checker->block_id;
						return 1;
					}
					if ((checker->top != nullptr) && (checker->top->road == false) && (checker->top_value == 2))
					{
						if (checker->block_id != 0)
							return checker->block_id;
						return 1;
					}

				}

				if (checker->left_value == 4)
				{
					checked_country[checker->country_id]++;
				}

				if (checker->bottom_value == 4)
				{
					checked_country[checker->country_id]++;
				}

				if (checker->right_value == 4)
				{
					checked_country[checker->country_id]++;
				}

				if (checker->top_value == 4)
				{
					checked_country[checker->country_id]++;
				}
				checker = checker->right;
			}
			start = start->bottom;
			checker = start;
		}
		//  cout << "-----" << endl;
		for (int x = 0; x < country_num; x++)
		{
			if (checked_country[x] != 2)
			{
				if (x != 0)
					return x;
				return 999;
			}

		}
		return 0;

	}
	void clearStatus()
	{
		block *vertical = head;
		block *horizontal = vertical;

		while (vertical != nullptr)
		{
			while (horizontal != nullptr)
			{
				horizontal->status = 0;
				horizontal = horizontal->right;
			}
			vertical = vertical->bottom;
			horizontal = vertical;
		}
	}
	void printStatus()
	{
		block *vertical = head;
		block *horizontal = vertical;

		while (vertical != nullptr)
		{
			while (horizontal != nullptr)
			{
				cout << horizontal->status << " ";
				horizontal = horizontal->right;
			}
			cout << endl;
			vertical = vertical->bottom;
			horizontal = vertical;
		}
	}
	// 18.05.18r.

	// z naszego grafu musimy utworzyc adjancy list
	// dla naszego algorytmu będziemy musieli tworzyć nowę listę dla każdego z poziomów.
	void makeList()
	{
		block *start = head;
		block *row = head;
		while (row != nullptr)
		{
			while (start != nullptr)
			{
				if (start->bottom != nullptr)
					adj_list[start->block_id].push_back(start->bottom->block_id);
				if (start->right != nullptr)
					adj_list[start->block_id].push_back(start->right->block_id);
				if (start->top != nullptr)
					adj_list[start->block_id].push_back(start->top->block_id);
				if (start->left != nullptr)
					adj_list[start->block_id].push_back(start->left->block_id);

				start = start->right;
			}
			row = row->bottom;
			start = row;
		}

	}
	// musimy przeciazyc funkcje  w zależnosci od poziomu do którego możemy zejść
	void makeList(int depth)
	{
		block *start = head;
		block *row = head;
		while (row != nullptr)
		{
			while (start != nullptr)
			{
				if (start->bottom != nullptr  && start->bottom->level <= depth)
					adj_list[start->block_id].push_back(start->bottom->block_id);
				if (start->right != nullptr && start->right->level <= depth)
					adj_list[start->block_id].push_back(start->right->block_id);
				if (start->top != nullptr && start->top->level <= depth)
					adj_list[start->block_id].push_back(start->top->block_id);
				if (start->left != nullptr && start->left->level <= depth)
					adj_list[start->block_id].push_back(start->left->block_id);

				start = start->right;
			}
			row = row->bottom;
			start = row;
		}
	}
	void clearList()
	{
		for (int i = 0; i <= 24; i++)
		{
			adj_list[i].clear();
		}
	}
	void printList() // możemy sobie wyprintować  te adjancy list
	{
		cout << endl;
		for (int u = 0; u <= 24; u++)
		{
			//  cout << u << ":";
			list<int>::iterator i;
			for (i = adj_list[u].begin(); i != adj_list[u].end(); ++i)
			{

			}
			//          cout << *i << " ";
			//      cout << endl;
		}
	}

	/// 19.05.18
	void generatePath(block * box)
	{
		cout << "Znalazł";
	}
	void nextShortestPath(block *start)
	{
		start = head;
		block *current;
		block *nextStep;
		this->clearList();
		this->makeList();

		bool *visited = new bool[25];
		int path_index = 0;

		for (int i = 0; i < 25; i++)
			visited[i] = false;


			while (current != nullptr)
			{
				if (current->block_id == 1)
					this->generatePath(current);
				else
				{

					list<int>::iterator i;
					for (i = adj_list[current->block_id].begin(); i != adj_list[current->block_id].end(); ++i)
					{
						if (!visited[*i])
						{
							if (current->bottom != nullptr && current->bottom->block_id == *i)
							{
								nextStep = current->bottom;
							}
							else if (current->right != nullptr && current->right->block_id == *i)
							{
								nextStep = current->right;
							}
							pq->push(nextStep->block_id);
							// current = sąsiad
						}
					}
				}
				current = nextStep;
			}



	}

	/// 19.05.18

	void IDDFS()
	{
		int min_depth = 0;
		int max_depth = 8;

		for (int i = min_depth; i <= max_depth; i++)
		{
			this->clearList();
			cout << "======= LEVEL " << i << "===========" << endl;
			this->iterativeDFS(0, 1, i);
			// tutaj trzeba będzie sprawdzać czy na danym poziomie już znaleźliśmy rozwiązanie.
			// !!wywołujemy checkera!! Jeżeli checker == true -> przerywamy JEŻELI CHECKER NIE ZNALAZŁ ROZWIĄZANIA TO IDZIEMY DALEJ CO OZNACZA ŻE ZWIĘKSZAMY POZIOM
		}
	}
	void iterativeDFS(int s, int d, int depth)
	{
		this->makeList(depth);
		this->printList();
		cout << endl;

		bool *visited = new bool[25];

		int path_index = 0;

		for (int i = 0; i < 25; i++)
			visited[i] = false;

		recursiveDFS(s, d, visited, path, path_index);

	}

	void recursiveDFS(int u, int d, bool visited[], int path[], int &path_index)
	{
		visited[u] = true;
		path[path_index] = u;
		path_index++;

		if (u == d)
		{
			/*for (int i = 0; i<path_index; i++)
			cout << path[i] << " ";
			cout << endl;*/
			makeroute(path_index);

		}
		else
		{
			list<int>::iterator i;
			for (i = adj_list[u].begin(); i != adj_list[u].end(); ++i)
				if (!visited[*i])
					recursiveDFS(*i, d, visited, path, path_index);
		}

		path_index--;
		visited[u] = false;

	}
	// 18.05.18r.
	void makeroute(int pa_index)
	{   // values: 0 - wall, 1 - standard, 2 - border, 3 - road standard , 4 - road border;
		block* temp = head;
		if (temp->block_id != path[0])
		{
			cout << "Something went wrong" << endl;
			return;
		}
		temp->road = true;
		for (int i = 1; i < pa_index; i++)
		{
			if (temp->bottom != nullptr && temp->bottom->block_id == path[i])
			{
				temp = temp->bottom;
				temp->road = true;
				if (temp->top_value == 1)
				{
					temp->top_value = 3;
					temp->top->bottom_value = 3;
				}
				else if (temp->top_value == 2)
				{
					temp->top_value = 4;
					temp->top->bottom_value = 4;
				}

			}
			if (temp->right != nullptr && temp->right->block_id == path[i])
			{
				temp = temp->right;
				temp->road = true;
				if (temp->left_value == 1)
				{
					temp->left_value = 3;
					temp->left->right_value = 3;
				}
				else if (temp->left_value == 2)
				{
					temp->left_value = 4;
					temp->left->right_value = 4;
				}
			}
			if (temp->top != nullptr && temp->top->block_id == path[i])
			{
				temp = temp->top;
				temp->road = true;
				if (temp->bottom_value == 1)
				{
					temp->bottom_value = 3;
					temp->bottom->top_value = 3;
				}
				else if (temp->bottom_value == 2)
				{
					temp->bottom_value = 4;
					temp->bottom->top_value = 4;
				}
			}
			if (temp->left != nullptr && temp->left->block_id == path[i])
			{
				temp = temp->left;
				temp->road = true;
				if (temp->right_value == 1)
				{
					temp->right_value = 3;
					temp->right->left_value = 3;
				}
				else if (temp->right_value == 2)
				{
					temp->right_value = 4;
					temp->right->left_value = 4;
				}
			}

		}
		if (temp->left != nullptr && temp->left->block_id == 0)
		{
			temp->road = true;
			if (temp->left_value == 1)
			{
				temp->left_value = 3;
				temp->left->right_value = 3;
			}
			else if (temp->left_value == 2)
			{
				temp->left_value = 4;
				temp->left->right_value = 4;
			}
		}
		int work = check();
		if (work == 0)
		{
			cout << "Route FOUND !!!" << endl;
			this->printStat();
		}
		this->clearRoads();

	}

	void clearRoads()
	{
		block* temp = head;
		block* start = head;
		while (start != nullptr)
		{
			while (temp != nullptr)
			{
				if (temp->bottom_value == 3 || temp->bottom_value == 4)
					temp->bottom_value = temp->bottom_value - 2;
				if (temp->top_value == 3 || temp->top_value == 4)
					temp->top_value = temp->top_value - 2;
				if (temp->left_value == 3 || temp->left_value == 4)
					temp->left_value = temp->left_value - 2;
				if (temp->right_value == 3 || temp->right_value == 4)
					temp->right_value = temp->right_value - 2;

				temp->road = false;
				temp = temp->right;
			}
			start = start->bottom;
			temp = start;
		}
	}
	void printStat()
	{
		block* temp = head;
		block* start = head;
		while (start != nullptr)
		{
			while (temp != nullptr)
			{
				cout << "     " << temp->country_id << "C " << temp->road << "  " << temp->left_value << "-" << temp->bottom_value << "-" << temp->right_value << "-" << temp->top_value;
				temp = temp->right;
			}
			cout << endl;
			start = start->bottom;
			temp = start;
		}
	}
	void printStack()
	{
		int size = stos.size();

		while (stos.empty() == false)
		{
			cout << stos.top() << " <- ";
			stos.pop();
		}
	}
	void print()
	{
		/*o -+- o -+- x
		+ --- + --- |
		o -+- x --- x
		| --- + --- |
		x -+- x --- x*/
		block* temp;
		block* start;
		temp = head;
		start = temp;
		while (start != nullptr)
		{
			while (temp != nullptr)
			{
				cout << "o ";
				if (temp->right_value == 2)
					cout << "-+- ";
				else if (temp->right_value == 1)
					cout << "--- ";
				else if (temp->right_value == 2)
				{

				}
				temp = temp->right;

			}
			cout << endl;
			temp = start;
			while (temp != nullptr && temp->bottom != nullptr)
			{
				if (temp->bottom_value == 1)
				{
					cout << "|";
					if (temp->right != nullptr)
					{
						cout << " --- ";
					}
				}
				if (temp->bottom_value == 2)
				{
					cout << "+";
					if (temp->right != nullptr)
					{
						cout << " --- ";
					}
				}
				temp = temp->right;
			}


			cout << endl;

			temp = start->bottom;
			start = temp;
		}

	}
	void add(int value, int value_2, int country, int level)
	{
		block *temp = new block;

		temp->parrent = nullptr;
		temp->country_id = country;
		temp->block_id = i;
		i++;
		temp->right_value = value;
		temp->bottom_value = value_2;
		temp->bottom = nullptr;
		temp->right = nullptr;
		temp->level = level;
		if (head == nullptr) // we are adding head block - postiion (0,0)
		{
			temp->top_value = 0;
			temp->left_value = 0;
			temp->right_value = value;
			temp->bottom_value = value_2;
			temp->top = nullptr;
			temp->right = nullptr;
			temp->bottom = nullptr;
			temp->left = nullptr;
			last = temp;
			head = temp;
			column = 1;
			return;
		}
		if (column == this->width)
		{
			block *finder;
			finder = last;
			last->right_value = 0;
			while (finder->left != nullptr)
			{
				finder = finder->left;
			}
			finder->bottom = temp;
			temp->top_value = finder->bottom_value;
			temp->top = finder;
			temp->bottom = nullptr;
			temp->right = nullptr;
			temp->right_value = value;
			temp->bottom_value = value_2;
			temp->left = nullptr;
			temp->left_value = 0;
			last = temp;
			column = 1;
			finder = nullptr;
		}
		else
		{
			last->right = temp;
			temp->left = last;

			temp->left_value = last->right_value;
			if (last->top != nullptr)
			{
				temp->top = last->top->right;
				last->top->right->bottom = temp;
				temp->top_value = last->top->right->bottom_value;
			}
			else
			{
				temp->top = nullptr;
				temp->top_value = 0;
			}
			last = temp;
			this->column++;
			return;
		}
	}
	void path_ex()
	{
		///values: 0 - wall, 1 - standard, 2 - border, 3 - road standard, 4 - road border;
		block* roader = head;
		roader->road = true;
		roader->right_value = 3;
		cout << roader->block_id << endl;

		roader = roader->right;
		roader->left_value = 3;
		roader->right_value = 3;
		roader->road = true;
		cout << roader->block_id << endl;

		roader = roader->right;
		roader->left_value = 3;
		roader->right_value = 3;
		roader->road = true;
		cout << roader->block_id << endl;

		roader = roader->right;
		roader->left_value = 3;
		roader->right_value = 3;
		roader->road = true;
		cout << roader->block_id << endl;

		roader = roader->right;
		roader->left_value = 3;
		roader->bottom_value = 4;
		roader->road = true;
		cout << roader->block_id << endl;

		roader = roader->bottom;
		roader->top_value = 4;
		roader->left_value = 3;
		roader->road = true;
		cout << roader->block_id << endl;

		roader = roader->left;
		roader->right_value = 3;
		roader->bottom_value = 3;
		roader->road = true;
		cout << roader->block_id << endl;

		roader = roader->bottom;
		roader->top_value = 3;
		roader->right_value = 4;
		roader->road = true;
		cout << roader->block_id << endl;

		roader = roader->right;
		roader->left_value = 4;
		roader->bottom_value = 3;
		roader->road = true;
		cout << roader->block_id << endl;

		roader = roader->bottom;
		roader->top_value = 3;
		roader->left_value = 4;
		roader->road = true;
		cout << roader->block_id << endl;

		roader = roader->left;
		roader->right_value = 4;
		roader->bottom_value = 3;
		roader->road = true;
		cout << roader->block_id << endl;

		roader = roader->bottom;
		roader->top_value = 3;
		roader->left_value = 3;
		roader->road = true;
		cout << roader->block_id << endl;

		roader = roader->left;
		roader->right_value = 3;
		roader->left_value = 3;
		roader->road = true;
		cout << roader->block_id << endl;

		roader = roader->left;
		roader->right_value = 3;
		roader->left_value = 4;
		roader->road = true;
		cout << roader->block_id << endl;

		roader = roader->left;
		roader->right_value = 4;
		roader->top_value = 4;
		roader->road = true;
		cout << roader->block_id << endl;

		roader = roader->top;
		roader->bottom_value = 4;
		roader->top_value = 4;
		roader->road = true;
		cout << roader->block_id << endl;

		roader = roader->top;
		roader->bottom_value = 4;
		roader->right_value = 4;
		roader->road = true;
		cout << roader->block_id << endl;

		roader = roader->right;
		roader->left_value = 4;
		roader->top_value = 3;
		roader->road = true;
		cout << roader->block_id << endl;

		roader = roader->top;
		roader->bottom_value = 3;
		roader->left_value = 3;
		roader->road = true;
		cout << roader->block_id << endl;

		roader = roader->left;
		roader->right_value = 3;
		roader->top_value = 4;
		roader->road = true;
		cout << roader->block_id << endl;

		roader = roader->top;
		roader->bottom_value = 4;
		cout << roader->block_id << endl;


	}
};


int main()
{   // values: 0 - wall, 1 - standard, 2 - border, 3 - road;
	Data* ss = new Data(5, 5, 8);
	ss->add(1, 2, 0, 0);
	ss->add(1, 2, 0, 1);
	ss->add(1, 2, 0, 2);
	ss->add(1, 2, 0, 3);
	ss->add(0, 2, 0, 4);

	ss->add(1, 2, 1, 1);
	ss->add(2, 1, 1, 2);
	ss->add(2, 1, 2, 3);
	ss->add(1, 1, 3, 4);
	ss->add(0, 2, 3, 5);

	ss->add(2, 2, 4, 2);
	ss->add(2, 2, 1, 3);
	ss->add(2, 1, 2, 4);
	ss->add(2, 2, 3, 5);
	ss->add(0, 1, 5, 6);

	ss->add(1, 2, 2, 3);
	ss->add(1, 2, 2, 4);
	ss->add(2, 2, 2, 5);
	ss->add(2, 1, 6, 6);
	ss->add(0, 1, 5, 7);

	ss->add(2, 0, 7, 4);
	ss->add(1, 0, 6, 5);
	ss->add(1, 0, 6, 6);
	ss->add(2, 0, 6, 7);
	ss->add(0, 0, 5, 8);
	ss->print();
	//ss->printAllCycles(0,1);
	//ss->iterativeDFS();
	cout << endl;

	cout << endl;
	ss->IDDFS();
	cout << " Koniec";
	//ss->printStatus();
	//ss->path_ex();
	//ss->check();
	getchar();

}