#include <iostream>

using namespace std;

#define PROCESSES 5
#define BUFFER 100
#define sTypeFCFS 0
#define sTypeSJF  1

struct process {
	// this struct is used to be a single process. Schedules can also be built using an array of this struct (as in preemptive SJF)
	int burstTime;
	int arrivalTime;
	int id;
	int burstRemaining;
	int entranceTime;
} procs[PROCESSES];

// prototypes
void FCFS(process p[], int length);
void nonPreemptiveSJF(process p[], int length);
void nonPreemptive(process p[], int length, int scheduleType);
void preemptiveSJF(process p[], int length);
void printGantt(process p[], int length);

int main() {
	// collect 5 processes from users; requesting the arrival time and burst time.
	for (int i = 0; i < PROCESSES; ++i) {
		procs[i].id = i;
		procs[i].entranceTime = 0;
		cout << "Process: " << i << endl;
		cout << "Enter Arrival Time: ";
		cin >> procs[i].arrivalTime;
		cout << "Enter Burst Time: ";
		cin >> procs[i].burstTime;
		procs[i].burstRemaining = procs[i].burstTime;
		cout << endl << endl;
	}

	// calculate First Come First Serve, then nonpreemptive Shortest Job First, then preemptive Shortest Job First
	FCFS(procs, PROCESSES);
	nonPreemptiveSJF(procs, PROCESSES);
	preemptiveSJF(procs, PROCESSES);
	
	return 0;
}

void FCFS(process p[], int length) {
	// print title
	cout << "\n\nFirst Come, First Serve ----------------------------------------------" << endl;
	// call nonPreemptive scheduler to calculate FCFS
	nonPreemptive(p, length, sTypeFCFS);
}

void nonPreemptiveSJF(process p[], int length) {
	// print title
	cout << "\n\nNon-Preemptive Shortest Job First ------------------------------------" << endl;
	// call nonPreemptive scheduler to calculate nonpreemptive SJF
	nonPreemptive(p, length, sTypeSJF);
}

void nonPreemptive(process p[], int length, int scheduleType) {
	process temp;
	double awt(0.0);	// average wait time
	double atat(0.0);	// average turn around time
	int clock(0);

	// schedule job (bubble sort)
	// check which type first
	if(scheduleType == sTypeFCFS) {
		// schedule by arrivalTime
		for(int i = 0; i < length - 1; ++i) {
			for(int j = 0; j < length - 1 - i; ++j) {
				if(p[j+1].arrivalTime < p[j].arrivalTime) {
					temp = p[j];
					p[j] = p[j+1];
					p[j+1] = temp;
				}
			}
		}
	} else if(scheduleType == sTypeSJF) {
		// schedule by burstTime
		for(int i = 0; i < length - 1; ++i) {
			for(int j = 0; j < length - 1 - i; ++j) {
				if(p[j+1].burstTime < p[j].burstTime) {
					temp = p[j];
					p[j] = p[j+1];
					p[j+1] = temp;
				}
			}
		}
	}

	for(int i = 0; i < length; ++i) {
		// calculate average wait time
		awt += clock;
		clock += p[i].burstTime;
		atat += (clock - p[i].arrivalTime);
	}

	// calculate average wait time and average turn around time
	awt /= length;
	atat /= length;
	// printout average wait time and average turn around time
	cout << "\nAverage Wait Time: " << awt;
	cout << "\nAverage Turn Around Time: " << atat << endl << endl;

	// print gantt chart
	printGantt(p, PROCESSES);
	
} // void nonPreemptive(process p[], int length, int scheduleType)


void preemptiveSJF(process p[], int length) {
	// preemptive shortest job first
	process q[BUFFER];
	int qlength(0);
	
	process temp;
	double awt(0.0);	// average wait time
	double atat(0.0);	// average turn around time
	int clock(0);
	int totalBurst(0);
	int currentWaitTime(0);
	int currentBurst(0);
	int cur(0), pre(0);
	int x(0);				// local variable needed for certain loops (see below)
	int i,j;
	// print title
	cout << "\n\nPreemptive Shortest Job First ----------------------------------------" << endl;
	
	// first sort by arrival time using bubble sort
	for(i = 0; i < length - 1; ++i) {
		for( j = 0; j < length - 1 - i; ++j) {
			if(p[j+1].arrivalTime < p[j].arrivalTime) {
				temp = p[j];
				p[j] = p[j+1];
				p[j+1] = temp;
			}
		}
	}
	// if 2 process times are the same, then we should adjust it based on the burstTime (second sort with bubble sort)
	for( i = 0; i < length - 1; ++i) {
		for( j = 0; j < length - 1 - i; ++j) {
			if(p[j+1].arrivalTime == p[j].arrivalTime && p[j+1].burstTime < p[j].burstTime) {
				temp = p[j];
				p[j] = p[j+1];
				p[j+1] = temp;
			}
		}
	}
	
	// get the total burstTime. this will be the schedule loop limiter
	for( i = 0; i < length; ++i) {
		totalBurst += p[i].burstTime;
	}
	
	// schedule processes
	for(x = 0; x < totalBurst; ++x) {
		if(cur != pre) {
			// current process is either preempted or finished. now we take the previous data collected.
			q[qlength] = p[pre];
			q[qlength].burstTime = currentBurst;
			q[qlength].entranceTime = (x - currentBurst);
			qlength++;
			currentBurst = 0;
		}
		
		// increment currentBurst
		currentBurst++;
		// decrement burstRemaining
		p[cur].burstRemaining--;
		// set previous index to current index and find new index to choose from
		pre = cur;
		cur = 0;
		// find next process
		for(int j = 0; j < (length - 1); ++j) {
			if(p[cur].burstRemaining < 1) {
				// this process is finished and we should move to the next process
				cur++;
			} else if(p[j+1].burstRemaining > 0) {
				if((p[j+1].burstRemaining < p[cur].burstRemaining) && (p[j+1].arrivalTime <= x+1)) {
					// if next index's burstRemaining is less than the current AND the next's arrivalTime is less than or equal to the NEXT clock time
					// then move current index to next index
					cur = j+1;
				}
			}
		}
	}
	// after loop finishes, collect data that was finished
	q[qlength] = p[pre];
	q[qlength].burstTime = currentBurst;
	q[qlength].entranceTime = (x - currentBurst);
	qlength++;
	
	// calculate average wait time and average turnaround time
	for( i = 0; i < length; ++i) {
		// start our current wait time with a negative arrival time
		currentWaitTime = -(p[i].arrivalTime);
		for( j = 0; j < qlength; ++j) {
			if(q[j].id == p[i].id) {
				// scheduled ID and process ID match. now we can calculate the current waiting time
				cur = j;
				// current wait time is calculated  by subtracting burst times of each instance
				currentWaitTime -= q[j].burstTime;
			}
		}
		// calculation is then corrected by adding the completion time - thus giving the total wait time for the process
		currentWaitTime += q[cur].entranceTime + q[cur].burstTime;
		// add this wait time to all the wait times
		awt += currentWaitTime;
		// take the completion time and subtract the arrival time
		atat += (q[cur].entranceTime + q[cur].burstTime) - p[i].arrivalTime;
	}
	
	// calculate the average wait time and average turn around time
	awt /= length;
	atat /= length;
	// print out average wait time and average turn around time
	cout << "\nAverage Wait Time: " << awt;
	cout << "\nAverage Turn Around Time: " << atat << endl << endl;
	
	// print gantt chart
	printGantt(q, qlength);
	
} // void preemptiveSJF(process p[], int length)


void printGantt(process p[], int length) {
// Assumes the process array is already ordered in the way it was processed in the scheduler
// this printout will handle printing the gantt charts for all scheduling algorithms

	int mid(0);			// used to place the processor ID in the middle of the gantt chart area for that process
	int totalBurst(0);
	int i,j;

	// print title
	cout << "Gantt Chart:" << endl << endl;
	
	// calculate the total burst time
	for( i = 0; i < length; ++i) {
		totalBurst += p[i].burstTime;
	}
	// don't forget to add the processor id's in the printout of gantt chart
	totalBurst += (length * 2) - 1;

	// printout top line
	cout << " ";
	for( i = 0; i < totalBurst; ++i) {
		cout << "-";
	}
	cout << "\n|";

	// start printing area portion (blank area with processor ID)
	for( i = 0; i < length; ++i) {
		mid = p[i].burstTime / 2;
		// print gantt chart
		for( j = 0; j < p[i].burstTime; ++j) {
			if(j == mid) {
				cout << "P" << p[i].id;
			} else {
				cout << " ";
			}
		}
		cout << "|";
	}
	cout << endl << " ";
	
	// printout bottom line
	for( i = 0; i < totalBurst; ++i) {
		cout << "-";
	}
	cout << endl;

	// now printout clock numbers
	totalBurst = 0;
	for( i = 0; i < length; ++i) {
		cout << totalBurst;

		// then print out spaces to next burst. make sure to count for the numbers themselves
		if((p[i].burstTime + totalBurst) < 10) {
			// print 1 extra space for gantt chart
			cout << " ";
		}

		for( j = 0; j < p[i].burstTime; ++j) {
			cout << " ";
		}

		totalBurst += p[i].burstTime;
	}
	// print completion time for last process
	cout << totalBurst << endl;
} // void printGantt(process p[], int length)