#include<iostream>
#include<cstdlib>
#include<iomanip>
#include<algorithm>
#include<deque>
#include<vector>
using namespace std;

struct Scheduling{
		int id,
			arrivetime,
			brusttime,
			priority,
			waitingtime,
			turnaroundtime;

		Scheduling() : id(0), arrivetime(0), brusttime(0), priority(0), waitingtime(0), turnaroundtime(0){};
};

class Method{
	private:
		deque<Scheduling> Process;
		deque<Scheduling> Process_clone;
		deque<Scheduling> Process_brust;
		vector<Scheduling> completion;

	public:
		Method(){};

		void Insert(Scheduling data);
		void Display_orig();
		void Display();
		void FCFS();
		void SJF_Non();
		void SRTF();
		void Priority_non();
		void RR(int quantum);
		void SWAP(deque<Scheduling>::iterator itr1, deque<Scheduling>::iterator itr2);
};

void Method::SWAP(deque<Scheduling>::iterator itr1, deque<Scheduling>::iterator itr2){
	deque<Scheduling>::iterator temp = itr1;
	itr1 = itr2;
	itr2 = temp;
}

void Method::Display(){

	cout << setw(3) << "Process" << setw(15) << "Waiting Time" << setw(18) << "Turnaround Time" <<endl;

	for (int i = 0; i < completion.size(); i++){
		cout << setw(3) << "P" << completion[i].id << setw(12) << completion[i].waitingtime << setw(15) << completion[i].turnaroundtime << endl;
	}
	cout << endl;
}

void Method::Display_orig(){

	cout << setw(3) << "Process" << setw(15) << "Arrival Time" << setw(15) << "Brust Time" << setw(15) << "Priority" << endl;

	for (int i = 0; i < Process.size(); i++){
		cout << setw(3) <<"P" << Process[i].id << setw(12) <<Process[i].arrivetime << setw(15) << Process[i].brusttime << setw(17) << Process[i].priority << endl;
	}
	cout << endl;
}

void Method::Insert(Scheduling data){

	Process.push_back(data);
	Process_clone.push_back(data);
	Process_brust.push_back(data);
}

bool comp_arrival(const Scheduling lhs, const Scheduling rhs){
	return lhs.arrivetime < rhs.arrivetime;
}

bool comp_brust(const Scheduling lhs, const Scheduling rhs){
	return lhs.brusttime < rhs.brusttime;
}

bool comp_priority(const Scheduling lhs, const Scheduling rhs){
	return lhs.priority < rhs.priority;
}

void Method::FCFS(){

	sort(Process.begin(), Process.end(), comp_arrival);
	int time = 0;
	deque<Scheduling>::iterator itr;
	for (itr = Process.begin(); itr != Process.end(); itr++){
		time += (*itr).brusttime;
		(*itr).waitingtime = time - (*itr).arrivetime - (*itr).brusttime;
		(*itr).turnaroundtime = time - (*itr).arrivetime;

		completion.push_back((*itr));
	}
		cout << "FCFS Algorithm: " << endl;

		Display();

		for (itr = Process.begin(); itr != Process.end(); itr++){
			itr->waitingtime = 0;
			itr->turnaroundtime = 0;
		}

		completion.clear();
}

void Method::SJF_Non(){

	sort(Process.begin(), Process.end(), comp_arrival);

	deque<Scheduling>::iterator itr, itr_begin = Process.begin();


	deque<Scheduling> q;
	q.push_back((*itr_begin));

	int time = itr_begin->brusttime;
	itr_begin->waitingtime += time - itr_begin->brusttime - itr_begin->arrivetime;
	itr_begin->turnaroundtime += time - itr_begin->arrivetime;

	completion.push_back((*itr_begin));

	bool visited[10];

	for (int i = 0; i < 10; i++){
		visited[i] = false;
	}

	while (q.size()){

		if (q.front().arrivetime == Process.begin()->arrivetime){
			q.pop_front();
		}

		for (itr = Process.begin() + 1; itr != Process.end(); itr++){
			// check the process whether in the schedule or not
			if (itr->arrivetime <= time && visited[itr->id] == false){
				q.push_back((*itr));
				visited[itr->id] = true;
			}
		}

		sort (q.begin(), q.end(), comp_brust);
		deque<Scheduling>::iterator finish = q.begin();

		time += finish->brusttime;
		finish->waitingtime += time - finish->brusttime - finish->arrivetime;
		finish->turnaroundtime += time - finish->arrivetime;

		completion.push_back((*finish));

		q.pop_front();
	}

	cout << "SJF(Non-Preemptive) : " << endl;

	Display();

	for (itr = Process.begin(); itr != Process.end(); itr++){
			itr->waitingtime = 0;
			itr->turnaroundtime = 0;
		}

	completion.clear();
}

void Method::Priority_non(){

sort(Process.begin(), Process.end(), comp_arrival);

	deque<Scheduling>::iterator itr;

	deque<Scheduling> q;
	q.push_back((*Process.begin()));

	int time = Process.begin()->brusttime;
	Process.begin()->waitingtime += time - Process.begin()->brusttime - Process.begin()->arrivetime;
	Process.begin()->turnaroundtime += time - Process.begin()->arrivetime;

	completion.push_back((*Process.begin()));

	bool visited[10];  // record the status of the arrival process

	for (int i = 0; i < 10; i++){
		visited[i] = false;
	}

	while (q.size()){

		if (q.front().arrivetime == Process.begin()->arrivetime){
			q.pop_front();
		}

		for (itr = Process.begin() + 1; itr != Process.end(); itr++){
			// check the process whether in the schedule or not
			if (itr->arrivetime <= time && visited[itr->id] == false){
				q.push_back((*itr));
				visited[itr->id] = true;
			}
		}

		sort (q.begin(), q.end(), comp_priority);
		deque<Scheduling>::iterator finish = q.begin();

		time += finish->brusttime;
		finish->waitingtime += time - finish->brusttime - finish->arrivetime;
		finish->turnaroundtime += time - finish->arrivetime;

		completion.push_back((*finish));

		q.pop_front();
	}

	cout << "Priority : " << endl;

	Display();

	for (itr = Process.begin(); itr != Process.end(); itr++){
			itr->waitingtime = 0;
			itr->turnaroundtime = 0;
		}

	completion.clear();
}

void Method::SRTF(){

	int time_total = 0, time_diff = 0;
	int brust_orig[10];

	for (deque<Scheduling>::iterator itr_curr = Process.begin(); itr_curr != Process.end(); itr_curr++){
		brust_orig[itr_curr->id] = itr_curr->brusttime;
	}

	sort(Process.begin(), Process.end(), comp_arrival);

	deque<Scheduling>::iterator itr;
	deque<Scheduling>::iterator itr_curr;
	deque<Scheduling>::iterator itr_smallest;
	for (itr = Process.begin(); itr != Process.end(); itr++){

		deque<Scheduling>::iterator temp = itr;
		deque<Scheduling>::iterator itr_next = ++temp;
		if (itr == Process.begin()){
			time_diff += itr_next->arrivetime - itr->arrivetime;
			time_total += time_diff;
			itr->brusttime -= time_diff;
		}
		else if (itr_next == Process.end()){  // the lastest arrival process has no time difference
			break;
		}
		else{
			sort(Process_brust.begin(), Process_brust.end(), comp_brust);

			for (itr_curr = Process_brust.begin(); itr_curr != Process_brust.end(); itr_curr++){
				if (itr_curr->brusttime == 0){
					Process_brust.erase(itr_curr);
					continue;
				}
				else if (itr->brusttime > itr_curr->brusttime && itr_curr->arrivetime <= time_total){
					itr_smallest = itr_curr;
					break;
			    }
			    else{
			    	itr_smallest = itr;
				}
		    }
		    time_diff = 0;
		 	time_diff += itr_next->arrivetime - itr->arrivetime;
		 	time_total += time_diff;
		 	itr_smallest->brusttime -= time_diff;

		 	// the same operation should do to another deque of process. Process <-> Process_brust
		 	if (itr_smallest == itr){
		 		for (itr_curr = Process_brust.begin(); itr_curr != Process_brust.end(); itr_curr++){
		 			int temptime = itr_smallest->brusttime;
		 			if (itr_curr->brusttime == temptime + time_diff)
		 				itr_curr->brusttime -= time_diff;
				 }
			 }
			else{
			 	for (itr_curr = Process.begin(); itr_curr != Process.end(); itr_curr++){
		 			int temptime = itr_smallest->brusttime;
		 			if (itr_curr->brusttime == temptime + time_diff)
		 				itr_curr->brusttime -= time_diff;
				 }
			 }

		 	if (itr_smallest->brusttime == 0){  // check the process whether completed in advance or not
			   	itr_smallest->waitingtime += time_total - itr_smallest->arrivetime - brust_orig[itr_smallest->id];
			   	itr_smallest->turnaroundtime += time_total - itr_smallest->arrivetime;
		 		completion.push_back((*itr_smallest));
			 }
		}
	}
		sort(Process_brust.begin(), Process_brust.end(), comp_brust);

		for (deque<Scheduling>::iterator itr_curr = Process_brust.begin(); itr_curr != Process_brust.end(); itr_curr++){
			time_total += itr_curr->brusttime;
			itr_curr->waitingtime += time_total - itr_curr->arrivetime - brust_orig[itr_curr->id];
			itr_curr->turnaroundtime += time_total - itr_curr->arrivetime;
			completion.push_back((*itr_curr));
		}

	cout << "Shortest Remaining Time First : " << endl;

	Display();

	for (itr = Process.begin(); itr != Process.end(); itr++){
			itr->waitingtime = 0;
			itr->turnaroundtime = 0;
		}

	completion.clear();
}

void Method::RR(int quantum){

	sort(Process_clone.begin(), Process_clone.end(), comp_arrival);
	int time = 0;
	int brust_orig[10];

	// duplicate the original data of brusttime
	for (deque<Scheduling>::iterator itr_curr = Process_clone.begin(); itr_curr != Process_clone.end(); itr_curr++){
		brust_orig[itr_curr->id] = itr_curr->brusttime;
	}

	deque<Scheduling>::iterator itr;
	for (itr = Process_clone.begin(); itr != Process_clone.end() ; itr++){
		// process's brusttime runs out
		if (itr->brusttime <= quantum){
			time += itr->brusttime;
			itr->waitingtime += time - itr->arrivetime - brust_orig[itr->id];
			itr->turnaroundtime += time - itr->arrivetime;
			completion.push_back((*itr));
		}
		// continuous to run
		else{
			time += quantum;
			itr->brusttime -= quantum;
			Process_clone.push_back((*itr));
		}
	}
	cout << "RR : " << endl;

	Display();
}

int main(){
	FILE *fin;
	fin = fopen("scheduling.txt", "r");
	if (fin == NULL){
		printf ("File not found. \n");
		exit(EXIT_FAILURE);
	}

	int sum = 0, num[50];
	while (feof(fin) == 0){
		fscanf(fin, "%d ", &num[sum]);
		sum++;
	}

	Method work;

    struct Scheduling data;

	int c = 1, i;
	for (i = 0; i < sum; i++){
		if (!(i % 3)){
			data.id = c++;
			data.arrivetime = num[i];
			data.brusttime = num[i + 1];
			data.priority = num[i + 2];
			work.Insert(data);
		}
	}

	work.Display_orig();

	work.FCFS();
	work.SJF_Non();
	work.Priority_non();
	work.SRTF();

	int quantum = 2;

	work.RR(quantum);

    fclose(fin);
	return 0;
}