#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <stdlib.h>
#include <cstdlib>
#include <algorithm>
#include <iomanip>

#define SJFNP 0
#define SJFP 1
#define RR 2
#define PP 3

int n = 12; //num processes

class Process {
public:
	Process() : id(0), cpu(false), burstTime(0), cpuBursts(0), t(0), b(0), userMode(false), turnaround(0), wait(0), priority(0), totalTurnaround(0), totalWait(0) {
	}
	//constant
	int id; //process id
	bool cpu; //false for interactive process, true for cpu process
	int burstTime; //burst time needed from the cpu
	int userTime; //time needed from i/o
	int cpuBursts; //num bursts before terminating (for cpu processes)
	int initialPriority;
	//varying
	int t; //time (starting at 0)
	int b; //count of cpu bursts
	bool userMode; //if waiting for i/o
	int turnaround; //turnaround time counter
	int wait; //wait time counter
	int priority;
	int totalTurnaround;
	int totalWait;

	//increment time
	void timeInc(bool active) {
		if (active){
			t++;
			turnaround++;
		} else {
			t++;
			wait++;
		}
	}

	void reset(){
		t = 0;
		b = 0;
		userMode = false;
		turnaround = 0;
		wait = 0;
		priority = initialPriority;
		totalTurnaround = 0;
		totalWait = 0;
	}

};

class CPU {
public:
	CPU() : process(NULL), processOut(NULL), useTime(0), notUseTime(0), contextSwitchTime(0), inContextSwitch(false) {
	}
	Process* process;
	Process* processOut; //process leaving during a context switch
	int useTime;
	int notUseTime;
	int contextSwitchTime;
	bool inContextSwitch;
	std::map<int, int> processesTime;
	void reset() {
		process = NULL;
		processOut = NULL;
		useTime = 0;
		notUseTime = 0;
		contextSwitchTime = 0;
		inContextSwitch = false;
		for (int i=0; i<n; i++){
			processesTime[i+1] = 0;
		}
	}
};

std::vector<CPU*> cpus;
std::vector<Process*> readyQueue;
std::vector<Process*> terminatedProcesses;
double pInt = .8; //percent of interactive processes
int iBMin = 20; //min burst time for interactive processes
int iBMax = 200; //max burst time for interactive processes
int uMin = 1000; //min user time
int uMax = 4500; //max user time
int cBMin = 200; //min burst time for cpu processes
int cBMax = 3000; //max burst time for cpu processes
int b = 8; //num burst for cpu processes before terminating
int ioMin = 1200; //min i/o block time
int ioMax = 3200; //max i/o block time
int m = 4; //num cpu's
int tSlice = 100; //time slice for RR
int tAging = 1200; //aging will cause lower-priority processes to increment after this time passes
int tCS = 2; //overhead time for completing a context switch

int t = 0; //time
int algorithm = SJFNP; //the algorithm currently simulated
int rrTimer = 0; //time counter for RR
int minTurnaround = 99999999;
int maxTurnaround = 0;
int totalTurnaround = 0;
int minWait = 99999999;
int maxWait = 0;
int totalWait = 0;

int randomVal(int low, int high) {
	return low + (high - low) * (rand() * 1.0 / RAND_MAX);
}

void addToReadyQueue(Process* proc, bool canPreempt = false);
void contextSwitch(Process* proc, CPU* cpu);

void makeProcesses() {
	for (int i=0; i<n; i++){
		Process* proc = new Process();
		proc->id = i+1;
		if (i < pInt*n){
			//interactive process
			proc->cpu = false;
			proc->burstTime = randomVal(iBMin, iBMax);
			proc->userTime = randomVal(uMin, uMax);
		} else {
			//cpu process
			proc->cpu = true;
			proc->burstTime = randomVal(cBMin, cBMax);
			proc->cpuBursts = b;
			proc->userTime = randomVal(ioMin, ioMax);
		}
		proc->initialPriority = rand() % 5;
		proc->priority = proc->initialPriority;
		addToReadyQueue(proc);
		for (int j=0; j<int(cpus.size()); j++){
			cpus[j]->processesTime[proc->id] = 0;
		}
	}

}
bool shorterProcess(Process* p1, Process* p2) { return p1->burstTime - p1->t < p2->burstTime - p2->t; }
int indexOfShortestProcess(std::vector<Process*> queue){
	int ret = 0;
	if (queue.empty()) return -1;
	Process* proc = queue[0];
	for (int i=1; i<int(queue.size()); i++){
		if (shorterProcess(queue[i], proc)){
			ret = i;
			proc = queue[i];
		}
	}
	return ret;
}
int indexOfHighestPriority(std::vector<Process*> queue){
	int ret = 0;
	if (queue.empty()) return -1;
	Process* proc = queue[0];
	for (int i=1; i<int(queue.size()); i++){
		if (queue[i]->priority < proc->priority){
			ret = i;
			proc = queue[i];
		}
	}
	return ret;
}

void resetCPUs(){
	for (int i=0; i<int(cpus.size()); i++){
		CPU* cpu = cpus[i];
		cpu->process = NULL;
		cpu->useTime = 0;
		cpu->notUseTime = 0;
	}
}

void addToReadyQueue(Process* proc, bool canPreempt){
	readyQueue.push_back(proc);

	std::cout << "[time " << int(t) << "ms] ";
	if (proc->cpu){
		std::cout << "CPU-bound";
	} else {
		std::cout << "Interactive";
	}
	std::cout << " process ID " << proc->id;
	std::cout << " entered ready queue (";
	std::cout << "requires " << int(proc->burstTime) << "ms CPU time; ";
	std::cout << "priority " << proc->priority << ")";
	std::cout << std::endl;

	//if can preempt, check if other job should be interrupted
	if (canPreempt &&
		algorithm == SJFP){
		for (int i=0; i<int(cpus.size()); i++){
			CPU* cpu = cpus[i];
			if (cpu->process != NULL && !cpu->inContextSwitch
				&& !cpu->process->userMode){
				if (proc->burstTime < cpu->process->burstTime - cpu->process->t){
					contextSwitch(proc, cpu);
					break;
				}
			}
		}
	}
	if (canPreempt &&
		algorithm == PP){
		for (int i=0; i<int(cpus.size()); i++){
			CPU* cpu = cpus[i];
			if (cpu->process != NULL && !cpu->inContextSwitch
				&& !cpu->process->userMode){
				if (proc->priority < cpu->process->priority){
					contextSwitch(proc, cpu);
					break;
				}
			}
		}
	}
}

void removeFromReadyQueue(Process* proc) {
	int index = -1;
	for (int i=0; i<int(readyQueue.size()); i++){
		if (readyQueue[i] == proc){
			index = i;
			break;
		}
	}
	if (index == -1) return;
	readyQueue.erase(readyQueue.begin()+index);
}

void contextSwitch(Process* proc, CPU* cpu) {
	Process* cpuProc = cpu->process;
	if (proc != NULL){
		removeFromReadyQueue(proc);
	}
	std::cout << "[time " << t << "ms] Context switch (";
	if (cpuProc == NULL){
	} else {
		std::cout << "swapping out process ID " << cpuProc->id;
		if (proc == NULL){
			std::cout << ")";
		} else {
			std::cout << " for ";
		}
		cpu->processOut = cpuProc;
	}
	if (proc != NULL){
		std::cout << "process ID " << proc->id << ")";
	}
	std::cout << std::endl;
	cpu->process = proc;
	cpu->inContextSwitch = true;
	cpu->contextSwitchTime = 0;

}

void increasePriority(Process* proc) {
	if (proc->priority <= 0)
		return;
	proc->priority--;
	std::cout << "[time " << t << "ms] Increased priority of ";
	if (proc->cpu) std::cout << "CPU-bound ";
	else std::cout << "Interactive ";
	std::cout << "process ID " << proc->id << " to " << proc->priority << " due to aging";
	std::cout << std::endl;
}

void terminateProcess(Process* proc) {
	std::cout << "[time " << t << "ms] CPU-bound process ID " << proc->id << " terminated ";
	std::cout << "(avg turnaround time " << (proc->totalTurnaround / proc->cpuBursts);
	std::cout << ", avg total wait time " << (proc->totalWait / proc->cpuBursts) << ")";
	std::cout << std::endl;
	terminatedProcesses.push_back(proc);
}

//does all actions that takes place in 1 ms
void step() {

	//finish context switches
	for (int i=0; i<int(cpus.size()); i++){
		CPU* cpu = cpus[i];
		if (cpu->inContextSwitch && cpu->contextSwitchTime >= tCS){
			if (cpu->processOut != NULL){
				addToReadyQueue(cpu->processOut, true);
			}
			cpu->processOut = NULL;
			cpu->inContextSwitch = false;
		}
	}

	//processes completing
	for (int i=0; i<int(cpus.size()); i++){
		CPU* cpu = cpus[i];
		if (cpu->process == NULL || cpu->inContextSwitch) continue;
		Process* proc = cpu->process;
		if (proc->userMode){ //i/o completed
			if (proc->t >= proc->userTime){
				//user i/o completed, go back to ready queue
				proc->turnaround = 0;
				proc->wait = 0;
				proc->priority = proc->initialPriority;
				proc->userMode = false;
				proc->t = 0;
				contextSwitch(NULL, cpu);
			}
		} else { //cpu burst completed
			std::cout << "[time " << t << "ms] ";
			if (proc->cpu) std::cout << "CPU-bound";
			else std::cout << "Interactive";
			std::cout << " process ID " << proc->id << " CPU burst done (turnaround time ";
			std::cout << proc->turnaround << "ms, total wait time ";
			std::cout << proc->wait << "ms)";
			std::cout << std::endl;

			if (proc->turnaround < minTurnaround) minTurnaround = proc->turnaround;
			if (proc->turnaround > maxTurnaround) maxTurnaround = proc->turnaround;
			totalTurnaround += proc->turnaround;
			if (proc->wait < minWait) minWait = proc->wait;
			if (proc->wait > maxWait) maxWait = proc->wait;
			totalWait += proc->wait;

			proc->totalTurnaround += proc->turnaround;
			proc->totalWait += proc->wait;

			if (proc->t >= proc->burstTime){
				if (proc->cpu){ //cpu-bound, keep track of cpu bursts
					proc->b++;
					if (proc->b >= proc->cpuBursts){
						//process done, should be terminated
						cpu->process = NULL;
						terminateProcess(proc);
					} else {
						//enter user mode
						proc->userMode = true;
						proc->t = 0;
					}
				} else { //interactive process
					//enter user mode
					proc->userMode = true;
					proc->t = 0;
				}

			}
		}
	}



	int index;
	Process* proc;
	switch (algorithm){
	case SJFNP:
	case SJFP:
		for (int i=0; i<int(cpus.size()); i++){
			CPU* cpu = cpus[i];
			if (cpu->process == NULL && !cpu->inContextSwitch){
				//process with shortest job enters CPU
				if (!readyQueue.empty()){
					index = indexOfShortestProcess(readyQueue);
					proc = readyQueue[index];
					contextSwitch(proc, cpu);
				}
			}
		}
		break;
	case RR:
		for (int i=0; i<int(cpus.size()); i++){
			CPU* cpu = cpus[i];
			//fill all cpus' with a process
			if (cpu->process == NULL && !cpu->inContextSwitch){
				if (!readyQueue.empty()){
					index = 0; //since processes are pushed to the back of the readyQueue
					proc = readyQueue[index];
					contextSwitch(proc, cpu);
				}
			}
		}

		rrTimer++;
		if (rrTimer >= tSlice){
			//preform round robin
			for (int i=0; i<int(cpus.size()); i++){
				CPU* cpu = cpus[i];
				if (cpu->inContextSwitch) continue; //would prevent cpu from RR, not sure how to fix
				if (readyQueue.empty()) break;
				proc = readyQueue[0];
				contextSwitch(proc, cpu);
			}

			rrTimer = 0;
		}
		break;
	case PP:
		for (int i=0; i<int(cpus.size()); i++){
			CPU* cpu = cpus[i];
			if (cpu->process == NULL && !cpu->inContextSwitch){
				//process with highest priority enters CPU
				if (!readyQueue.empty()){
					index = indexOfHighestPriority(readyQueue);
					proc = readyQueue[index];
					contextSwitch(proc, cpu);
				}
			}
		}
		break;
	}




	//increment time values
	for (int i=0; i<int(cpus.size()); i++){
		CPU* cpu = cpus[i];
		if (cpu->inContextSwitch){
			cpu->contextSwitchTime++;
			cpu->useTime++;
			if (cpu->process != NULL){
				cpu->process->timeInc(true);
			}
			if (cpu->processOut != NULL){
				cpu->processOut->timeInc(true);
			}
		} else if (cpu->process != NULL){
			cpu->useTime++;
			if (cpu->process != NULL){
				cpu->processesTime[cpu->process->id]++;
				cpu->process->timeInc(true);
			}
		} else {
			cpu->notUseTime++;
		}
	}
	for (int i=0; i<int(readyQueue.size()); i++){
		Process* proc = readyQueue[i];
		proc->timeInc(false);
		if (algorithm == PP){ //detect changing priority
			if (proc->wait % tAging == 0){
				increasePriority(proc);
			}
		}
	}

	t++;
}

//prints data after simulation
void analysis(){

	int cpuUseTime = 0;
	int cpuTotalTime = 0;
	std::vector<int> cpuProcessesTime(n);
	for (int i=0; i<int(cpus.size()); i++){
		CPU* cpu = cpus[i];
		cpuUseTime += cpu->useTime;
		cpuTotalTime += cpu->useTime + cpu->notUseTime;// + cpu->contextSwitchTime;
		for (int j=0; j<n; j++){
			cpuProcessesTime[j] += cpu->processesTime[j+1];
		}
	}

	std::cout << std::endl;
	std::cout << "Turnaround time: min " << minTurnaround << " ms; ";
	std::cout << "avg " << std::setprecision(12) << (totalTurnaround*1.0 / n) << " ms; ";
	std::cout << "max " << maxTurnaround << " ms\n";
	std::cout << "Total wait time: min " << minWait << " ms; ";
	std::cout << "avg " << std::setprecision(12) << (totalWait*1.0 / n) << " ms; ";
	std::cout << "max " << maxWait << " ms\n";
	std::cout << "Average CPU utilization: " << std::setprecision(12) << (100.0*cpuUseTime / cpuTotalTime) << "%\n\n";
	std::cout << "Average CPU utilization per process: \n";
	for (int i=0; i<int(cpuProcessesTime.size()); i++){
		std::cout << (i+1) << ": " << std::setprecision(12) << (100.0*cpuProcessesTime[i] / cpuTotalTime) << "%\n";
	}
}

void reset() {
	t = 0;
	rrTimer = 0;
	minTurnaround = 99999999;
	maxTurnaround = 0;
	totalTurnaround = 0;
	minWait = 99999999;
	maxWait = 0;
	totalWait = 0;

	for (int i=0; i<int(cpus.size()); i++){
		CPU* cpu = cpus[i];
		if (cpu->process != NULL)
			terminatedProcesses.push_back(cpu->process);
		if (cpu->processOut != NULL)
			terminatedProcesses.push_back(cpu->processOut);
		cpu->reset();
	}

	for(int i=0; i<int(readyQueue.size()); i++){
		terminatedProcesses.push_back(readyQueue[i]);
	}
	readyQueue.clear();
	for(int i=0; i<int(terminatedProcesses.size()); i++){
		terminatedProcesses[i]->reset();
		addToReadyQueue(terminatedProcesses[i]);
	}
	terminatedProcesses.clear();


}

void run(){
	while (int(terminatedProcesses.size()) < int((1-pInt) * n)){
		step();
	}
}

int main(int argc, const char* argv[]) {

	//parse argv
	for (int i=1; i<argc; i++) {
		//example: pInt=.7 (variable = value)
		std::string arg(argv[i]);
		int index = (int) arg.find('=');
		if (index == -1) continue;
		std::string varStr = arg.substr(0, index);
		const char* c = arg.substr(index+1).c_str();
		if (varStr == "n") n = atoi(c);
		else if (varStr == "pInt") pInt = atof(c);
		else if (varStr == "iBMin") iBMin = atoi(c);
		else if (varStr == "iBMax") iBMax = atoi(c);
		else if (varStr == "uMin") uMin = atoi(c);
		else if (varStr == "uMax") uMax = atoi(c);
		else if (varStr == "cBMin") cBMin = atoi(c);
		else if (varStr == "cBMax") cBMax = atoi(c);
		else if (varStr == "b") b = atoi(c);
		else if (varStr == "ioMin") ioMin = atoi(c);
		else if (varStr == "ioMax") ioMax = atoi(c);
		else if (varStr == "m") m = atoi(c);
		else if (varStr == "tSlice") tSlice = atoi(c);
		else if (varStr == "tAging") tAging = atoi(c);
		else if (varStr == "tCS") tCS = atoi(c);
	}

	//make cpu's
	for (int i=0; i<m; i++){
		CPU* cpu = new CPU();
		cpus.push_back(cpu);
	}

	//run
	algorithm = SJFNP;
	std::cout << "Shortest-Job-First with no preemption:\n\n";
	makeProcesses();
	run();
	analysis();

	algorithm = SJFP;
	std::cout << "\n\nShortest-Job-First with preemption:\n\n";
	reset();
	run();
	analysis();

	algorithm = RR;
	std::cout << "\n\nRound-Robin:\n\n";
	reset();
	run();
	analysis();

	algorithm = PP;
	std::cout << "\n\nPreemptive Priority:\n\n";
	reset();
	run();
	analysis();

	//cleanup
	for (int i=0; i<(int) cpus.size(); i++){
		delete cpus[i];
	}
	cpus.clear();
}