#include <iostream>
#include <cstdlib>
#include <time.h>
#include <thread>
#include <mutex>
#include <string>
#include <Windows.h>
#include <condition_variable>
#include <vector>

using namespace std;

/*Sekcja krytczyna (ang. critical section) jest to wydzielony fragment kodu, który nie może być wykonywany równolegle w programie wielowątkowym.

Sekcje krytyczne stosuje się w celu zapewnienia bezpiecznego dostępu do współdzielonych danych, znajdujących się w pamięci. */

mutex obiekt;
mutex mtx;
condition_variable cv;
//mutex **semafory;
int suma=-1;
bool ready=false;
bool koniec=false;
int Number=0;

struct Value{
	string kto;
	int x;
	int y;
	int liczba;
};

vector<Value>tablica;

int f(int n, int x, int y)
{
        return (x + y*2 + 1)%n;
}

void Wpisz_Rozwiazanie(int liczba,string kto){

	obiekt.lock();
	suma=liczba;
	cout<<"Rozwiazanie wprowadzil "<<kto<<". Suma = "<<suma<<endl;
	obiekt.unlock();
}

void logi(){

	for(int i=0;i<tablica.size();i++){
		cout<<endl<<tablica[i].kto<<"  "<<i<<"  Wprowadzil wartosc = "<<tablica[i].liczba<<".  (x,y) ="<<tablica[i].x<<","<<tablica[i].y;
	}

}

void Show(int **Kwadrat,int n){
	cout<<endl;
	for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++)
					printf("%3d ",Kwadrat[i][j]);

				cout<<endl;
	}
}

void Wprowadz_Wynik(int **kwadrat){
	std::unique_lock<std::mutex> lck(mtx);
	while(!koniec){
	while (!ready) cv.wait(lck);
	kwadrat[tablica[Number].x][tablica[Number].y]=tablica[Number].liczba;
	Number++;
	ready=false;
	cv.notify_one();
	}
}

void Wygas(int **Kwadrat,int n){
		int x,y;

		do{
		x=rand()%n;
		y=rand()%n;
		} while((Kwadrat[x][y]==-1)||(!x));

		Kwadrat[x][y]=-1;
}

bool Sprawdz(int **Kwadrat,int n){

	for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++){
					if(Kwadrat[i][j]==-1)
						return false;
				}
	}

	return true;
}

void Rozwiaz_Wierszami(int **Kwadrat,int n){
		int sumtemp=0;
		int x,y,flaga=0,liczba=0;

		Value temp;

		string Watek_W="Watek_W";

		while(!Sprawdz(Kwadrat,n)){
		//	this_thread::sleep_for (std::chrono::seconds(1));
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if((Kwadrat[i][j]==-1)&&(flaga==0)){
					if(suma==-1){
						flaga=1;
						break;
					}
					x=i;
					y=j;
					flaga=1;
				}
				else if((Kwadrat[i][j]==-1)&&(flaga)){
					flaga = 0;
					break;
				}
				else
				sumtemp+=Kwadrat[i][j];


			}
			if((!flaga)&&(suma==-1)){

				Wpisz_Rozwiazanie(sumtemp,Watek_W);
			}
			if(flaga){
			std::unique_lock<std::mutex> lck(mtx);
			temp.kto=Watek_W , temp.x=x , temp.y=y, temp.liczba=suma-sumtemp;
			tablica.push_back(temp);
			ready = true;
			cv.notify_one();
			while (ready) cv.wait(lck);
			flaga=0;
			}
			sumtemp=0;
		}
		liczba++;
		Sleep(10);
		if(liczba==100) return;
		}
}

void Rozwiaz_Kolumnami(int **Kwadrat,int n){
		int sumtemp=0;
		int x,y,flaga=0,liczba=0;

		string Watek_K="Watek_K";

		Value temp;

		while(!Sprawdz(Kwadrat,n)){
		//	this_thread::sleep_for (std::chrono::seconds(1));
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if((Kwadrat[j][i]==-1)&&(flaga==0)){
					if(suma==-1){
						flaga=1;
						break;
					}
					x=j;
					y=i;
					flaga=1;
				}
				else if((Kwadrat[j][i]==-1)&&(flaga)){
					flaga = 0;
					break;
				}
				else
				sumtemp+=Kwadrat[j][i];


			}
			if((!flaga)&&(suma==-1)){

				Wpisz_Rozwiazanie(sumtemp,Watek_K);
			}
			if((flaga)&&(suma!=-1)){
			std::unique_lock<std::mutex> lck(mtx);
			temp.kto=Watek_K , temp.x=x , temp.y=y, temp.liczba=suma-sumtemp;
			tablica.push_back(temp);
			ready = true;
			cv.notify_one();
			while (ready) cv.wait(lck);
			flaga=0;
			}
			sumtemp=0;
			flaga=0;
		}
		liczba++;
		Sleep(10);
		if(liczba==100) return;
		}
}

void Rozwiaz_Przekatna(int **Kwadrat,int n){

		int sumtemp=0;
		int x,y,flaga=0,liczba=0;
		int j=0;

		string Watek_P="Watek_P";

		Value temp;

		while(!Sprawdz(Kwadrat,n)){
			//this_thread::sleep_for (std::chrono::seconds(1));
		for(int i=n-1;i>=0;i--){
				if((Kwadrat[i][j]==-1)&&(flaga==0)){
					if(suma==-1){
						flaga=1;
						break;
					}
					else{
					x=i;
					y=j;
					flaga=1;
					}
				}
				else if((Kwadrat[i][j]==-1)&&(flaga)){
					flaga = 0;
					break;
				}
				else
				sumtemp+=Kwadrat[i][j];
				j++;


			}
			if((!flaga)&&(suma==-1)){

				Wpisz_Rozwiazanie(sumtemp,Watek_P);
			}
			if((flaga)&&(suma!=-1)){
			std::unique_lock<std::mutex> lck(mtx);
			temp.kto=Watek_P , temp.x=x , temp.y=y, temp.liczba=suma-sumtemp;
			tablica.push_back(temp);
			ready = true;
			cv.notify_one();
			while (ready) cv.wait(lck);
			flaga=0;
			}
			sumtemp=0;


		j=0;
		flaga=0;
		for(int i=0;i<n;i++){
				if((Kwadrat[i][j]==-1)&&(flaga==0)){
					if(suma==-1){
						flaga=1;
						break;
					}
					x=i;
					y=j;
					flaga=1;
				}
				else if((Kwadrat[i][j]==-1)&&(flaga)){
					flaga = 0;
					break;
				}
				else
				sumtemp+=Kwadrat[i][j];
				j++;


			}
			if((!flaga)&&(suma==-1)){

				Wpisz_Rozwiazanie(sumtemp,Watek_P);
			}
			if((flaga)&&(suma!=-1)){
			std::unique_lock<std::mutex> lck(mtx);
			temp.kto=Watek_P , temp.x=x , temp.y=y, temp.liczba=suma-sumtemp;
			tablica.push_back(temp);
			ready = true;
			cv.notify_one();
			while (ready) cv.wait(lck);
			flaga=0;
			}
			sumtemp=0;
			flaga=0;
			j=0;
			liczba++;
			Sleep(10);
			if(liczba==100) return;
		}
}


int main()
{
		srand(time(NULL));
        int i,j,n,liczba,rozwiazanie;
		int **Kwadrat;

		do{
		system("cls");
		cout<<"Wprowadz n ";
		cin>>n;
		}while(n%2==0);

		Kwadrat = new int*[n];
        for (i = 0; i < n; i++) {
			Kwadrat[i] = new int[n];
                for (j = 0; j < n; j++){
					Kwadrat[i][j] = f(n, n - j - 1, i)*n + f(n, j, i) + 1;
				}
		}

		/*semafory = new mutex*[n];
        for (i = 0; i < n; i++) {
					semafory[i] = new mutex[n];
				}
			*/
		Show(Kwadrat,n);
		cout<<"Ile kwadratow wygasic?";
		cin>>liczba;



		for(i=0;i<liczba;i++)
			Wygas(Kwadrat,n);

		Show(Kwadrat,n);

		cout<<"Start?";
		getchar();getchar();



		thread Semafor (Wprowadz_Wynik,Kwadrat);
		thread kolumna (Rozwiaz_Kolumnami,Kwadrat,n);
		thread wiersz (Rozwiaz_Wierszami,Kwadrat,n);
		thread przekatna (Rozwiaz_Przekatna,Kwadrat,n);


		//cout<<endl<<kolumna.get_id();
		wiersz.join();
		kolumna.join();
		przekatna.join();

		logi();
		//Show(Kwadrat,n);
		if(Sprawdz(Kwadrat,n)){
		cout<<endl;
		Show(Kwadrat,n);
		}
		else{
			cout<<endl<<"\nNie da sie rozwiazac";
			Show(Kwadrat,n);
		}



		return 0;
}