/**
* author : kaidul
**/
using namespace std;
#include <iostream>
#include <cstdio>
#include <queue>
#include <bitset>
#define M 100
struct process {
int processId, arrivalTime, burstTime, priority;
int waitingTime, turnAroundTime, responseTime;
bool operator < (const process& a) const {
if(arrivalTime == a.arrivalTime) return burstTime > a.burstTime;
return arrivalTime > a.arrivalTime;
}
} pArray[M];
struct waitingProcess {
int processId, arrivalTime, burstTime, priority;
bool operator < (const waitingProcess& a) const {
if(burstTime == a.burstTime) return arrivalTime > a.arrivalTime;
return burstTime > a.burstTime;
}
} wp;
priority_queue<process> q;
priority_queue<waitingProcess> waitingList;
bitset <M> taken;
struct timeLine {
int proc, start, end;
} tmline[M];
int nProcess, timeInterval, averageTime;
float throughtputTime;
int main() {
freopen("input.txt", "r", stdin);
cin >> nProcess;
for (int i = 1; i <= nProcess ; i++) {
pArray[i].processId = i;
cin >> pArray[i].arrivalTime >> pArray[i].burstTime >> pArray[i].priority;
q.push(pArray[i]);
}
cin >> timeInterval;
cout << "Shortest Job First - Preemptive : \n";
int i = 1;
process next, top;
waitingProcess waiting;
tmline[0].start = 0, tmline[0].proc = 0, tmline[0].end = 0;
cout << "\nExecution Sequence : \n";
while (!waitingList.empty() || !q.empty()) {
tmline[i].start = tmline[i-1].end;
if(waitingList.empty() && !q.empty()) {
top = q.top();
q.pop();
if(!q.empty()) {
waitingProcess p;
next = q.top();
if(next.arrivalTime < (top.burstTime + tmline[i-1].end)) {
tmline[i].end = next.arrivalTime;
tmline[i].proc = top.processId;
int exeRemain = (top.burstTime + tmline[i-1].end) - next.arrivalTime;
p.processId = top.processId, p.arrivalTime = top.arrivalTime, p.priority = top.priority, p.burstTime = exeRemain;
waitingList.push(p);
} else {
tmline[i].end = tmline[i].start + top.burstTime;
tmline[i].proc = top.processId;
}
} else {
tmline[i].end = tmline[i].start + top.burstTime;
tmline[i].proc = top.processId;
}
} else if(!waitingList.empty() && q.empty()) { // queue khali, waiting list khali na - sobtheke soja case
waitingProcess wt = waitingList.top();
tmline[i].end = tmline[i].start + wt.burstTime;
tmline[i].proc = wt.processId;
waitingList.pop();
} else { // both queue have processes
top = q.top();
waiting = waitingList.top();
if(top.burstTime < waiting.burstTime) {
q.pop();
if(!q.empty()) {
waitingProcess wt;
next = q.top();
if(next.arrivalTime < (top.burstTime + tmline[i-1].end)) {
tmline[i].end = next.arrivalTime;
tmline[i].proc = top.processId;
int exeRemain = (top.burstTime + tmline[i-1].end) - next.arrivalTime;
wt.processId = top.processId, wt.arrivalTime = top.arrivalTime, wt.priority = top.priority, wt.burstTime = exeRemain;
waitingList.push(wt);
} else {
tmline[i].end = tmline[i].start + top.burstTime;
tmline[i].proc = top.processId;
}
} else {
tmline[i].end = tmline[i].start + top.burstTime;
tmline[i].proc = top.burstTime;
}
} else { // waitinglist and queue 2ta tei process ase, waiting er tar burst time kom, so se age execute hobe
q.pop();
waitingList.pop();
waitingProcess wt;
wt.processId = top.processId ,wt.arrivalTime = top.arrivalTime, wt.burstTime = top.burstTime, wt.priority = top.priority;
waitingList.push(wt);
tmline[i].end = tmline[i].start + waiting.burstTime;
tmline[i].proc = waiting.processId;
}
}
cout << tmline[i].start << " " << tmline[i].end << " " << tmline[i].proc << "\n";
i++;
}
cout << "\n";
taken.reset();
int range = i -1;
// calulating response time
for (int i = 1; i <= range; i++) {
if(taken.test(tmline[i].proc)) continue;
pArray[tmline[i].proc].responseTime = tmline[i].start - pArray[tmline[i].proc].arrivalTime;
taken.set(tmline[i].proc, 1);
}
// Calculating Turn-Around Time
taken.reset();
for (int i = range; i >= 1; i--) {
if(taken.test(tmline[i].proc)) continue;
pArray[tmline[i].proc].turnAroundTime = tmline[i].end - pArray[tmline[i].proc].arrivalTime;
taken.set(tmline[i].proc, 1);
}
// Calculating Waiting Time
/**
key: turn-around time = execution(burst) time + waiting time
**/
int total = 0;
for (int i = 1; i <= nProcess; i++ ) {
pArray[i].waitingTime = pArray[i].turnAroundTime - pArray[i].burstTime;
cout << pArray[i].processId << "\n";
cout << "Waiting Time : " << pArray[i].waitingTime << "\n";
total += pArray[i].waitingTime;
cout << "TurnAround Time : " << pArray[i].turnAroundTime << "\n";
cout << "Response Time : " << pArray[i].responseTime << "\n\n";
}
averageTime = total / nProcess;
cout << "Average waiting Time : " << averageTime << "\n";
throughtputTime = (float)nProcess / tmline[range].end;
cout << "Throughput Time : " << throughtputTime << "\n";
return false;
}
