#ifndef SCHEDULERS_H
#define SCHEDULERS_H

#include <iostream>
#include <unistd.h>
#include <sys/wait.h>
#include <vector>
#include <algorithm>
#include <cerrno>
#include <cstdlib>
#include <ctime>
#include <cmath>


//QUICK SORT
template<typename T>
int partition(T* s, int low, int high)
{
	T pivot = s[high];
	int i = low -1;

	for (int j = low; j< high; ++j){
		if (s[j]<pivot) {
			++i;
			std::swap(s[i], s[j]);
		}
	}

	std::swap(s[i+1], s[high]);
	return i+1;
}

template<typename T>
void quick_sort_recursive(T* s, int low, int high)
{
	if(low<high){
		int pi = partition(s, low, high);

		quick_sort_recursive(s, low, pi - 1);
		quick_sort_recursive(s, pi + 1, high);
	}
}

template<typename T>
void quick_sort(T* s, int size)
{
	if (size > 1)
		quick_sort_recursive(s, 0, size - 1);
}








//PROLIFIC

class ProlificScheduler{

public:

//FOR mainA: A(n,n)

void run(int *A, int n)
{
	pid_t root = getpid();
	std::vector<pid_t> pids;
	int worker_id=-1;
	int worker_count = n;

	//root spawns children and stores PIDs
	for(int i=0; i<n; ++i)
	{
		if(getpid() != root){
			break;
		}

		pid_t pid = fork();
		if (pid ==0)
		{
			std::cout << "[" << getpid() << "," <<i<<
				"]" << std::endl;
			worker_id=i;
			break;
		}
		else {
			pids.push_back(pid);
		}
	}

	//root reaping loop
	if(getpid() == root)
	{
		int status;
		while(1)
		{
			pid_t finished = waitpid(-1, &status, 0);

			if(finished >0)
			{
				std::cout<<"Reaped PID "<<finished <<"\n";

				pids.erase(std::remove(pids.begin(), 
					pids.end(), finished), pids.end());
				continue;
			}
			if (finished == -1 && errno == ECHILD)
				break;

			break;
		}
	}else
	{
		//work distribution (modulo)
		for(int i=0;i<n; ++i){
			if(i % worker_count == worker_id){
			quick_sort(A + i*n, n);
			std::cout<<"Worker "<<worker_id << 
				" sorted row "<< i << "\n";
			}
		}
		_exit(0);
	}

}


//FOR mainB: B(n, n, k)

void run(int *A, int n, int k)
{
	pid_t root = getpid();
	std::vector<pid_t> pids;
	int worker_id= -1;
//	int worker_count = k;
	//Root spawns children and stores PIDs
	for (int s=0; s<k; ++s)
	{
		if (getpid() != root){
			break;
			//_exit(0);
		}
		pid_t pid = fork();
		if (pid == 0)
		{
			std::cout << "[" << getpid() << "," << s 
			<< "]"<< std::endl;
			worker_id=s;
			break;
		}
		else {
			pids.push_back(pid);
		}
	}
	//ROOT reaping loop
	if(getpid() == root)
	{
		int status;
		while (1)
		{
			pid_t finished = waitpid(-1, &status, 0);

			if (finished > 0)
			{
			std::cout << "Reaped PID " << finished << "\n";

			pids.erase(std::remove(pids.begin(), pids.end(),
						finished), pids.end());
			continue;
			}
			if (finished == -1 && errno == ECHILD)
				break;
			break;
		}
	}
	else
	{
		//EACH WORKER SORTS ONE WHOLE SLICE
		for(int i=0; i<n; ++i){
			//if(i% worker_count == worker_id) {

			quick_sort(A + worker_id*n*n +i*n, n);
				//random_task(i);
				std::cout<<"Worker "<<worker_id <<
					" sorted row "<< i 
					<<" of slice " << worker_id 
					<< "\n";
				}
				_exit(0);
			//}
	}


}


};


//COLLECTIVE

class CollectiveScheduler{

public:
//FOR mainA: A(n,n);
void run(int *A, int n)
{
	pid_t root = getpid();
	pid_t child_pid = -1;
	int worker_id = -1;

	//collective fork: children continue the loop
	for(int i=0;i<n;i++)
	{
		pid_t pid = fork();

		if(pid == 0)
		{
			worker_id = i;
			std::cout<<"["<<getpid() <<","<<worker_id <<"]"<<
				std::endl;
			continue; //child continue to create new worker
		}
		else
		{
			child_pid = pid;
			break; //parent stops here
		}
	}

	//Root does not sort, only waits for chain
	if(getpid() == root)
	{
		int status;
		while(1)
		{
			pid_t finished = waitpid(-1, &status, 0);
			if(finished >0)
			{
				std::cout <<"Reaped PID "<< finished<<"\n";
				continue;
			}

			if(finished == -1 && errno == ECHILD )
				break;
		}
	}
	else
	{
		//Each worker sorts its own row
		if (worker_id >= 0 && worker_id <n)
		{
			quick_sort(A +worker_id*n, n);
			std::cout <<"Worker "<<worker_id
				<<" sorted row :" << worker_id << "\n";
		}


		//Wait for child created by this worker
		if (child_pid > 0)
		{
			int status;
			waitpid(child_pid, &status, 0);
		}
		_exit(0);
	}

}

//FOR mainB : B(n, n, k)
void run(int *A, int n, int k){

	pid_t root = getpid();
	pid_t child_pid = -1;
	int worker_id=-1;

	//Collective forkL children continue the loop
	for(int s=0; s<k; ++s)
	{
		pid_t pid = fork();

		if(pid == 0){
			worker_id=s;
			std::cout <<"["<<getpid() <<", worker " <<
				worker_id << "]\n";
			continue; //child continues to next worker
		}
		else
		{
			child_pid = pid;
			break;
		}
	}
/*	//Workers: all processes except root
	if (getpid() != root)
	{
		int worker_id = getpid() % root;
		int worker_count = pow(2,n)-1; //small deterministic count

		for (int i=0; i<n; ++i)
		{
			if(i % worker_count == worker_id % worker_count) {
			std::cout<< "[" << getpid()<<", "<< getppid() <<" id="
				<< worker_id;
			//random_task(i);
			quick_sort(A +worker_id)*n*n +i*n, n);
		}
		}

		_exit(0);
	}
*/

	//Root reaps all descendants
	//does not sort only waits for chain

	if(getpid() == root)
	{
		int status;
		while(1)
		{
			pid_t finished = waitpid(-1, &status, 0);

			if(finished > 0)
			{
			std::cout << "Reaped PID "<< finished<<"\n";
			continue;
			}

			if (finished == -1 && errno == ECHILD)
				break;
		break;
		}
	} else {
		//each worker sorts one whole slice
		if(worker_id >= 0 && worker_id <k)
		{
			for(int i=0; i<n; ++i)
			{
				quick_sort(A + worker_id*n*n +i*n, n);
				std::cout<<"Worker "<< worker_id <<
					" sorted row "<< i <<
					" of slice "<<worker_id << "\n";
			}
		}

		//wait for child created by this worker
		if(child_pid >0)
		{
			int status;
			waitpid(child_pid, &status, 0);
		}

		_exit(0);
	}
}

};



#endif