#include<bits/stdc++.h>
using namespace std;

int processes[100][3], NP, quantum, scheduler[1000],WT[100];
unsigned int timet= 0;

typedef struct el
{
	unsigned int p;
	struct el * next;
}Q;
Q * qeue = NULL;

void getSystem()
{
	int i;
	cout << "\nNumber of processes: ";
	cin >> NP;
	cout << "\nThe Quantum: ";
	cin >> quantum;
	
	for(i=0; i<NP; i++ )
	{
		cout << "\n Arrival Time of p" << i << ": ";
		cin >>processes[i][0];
		cout << "\n Burst time for p" << i << ": ";
		cin >> processes[i][1];
		processes[i][2] = processes[i][1];
		cout << "\n-----------";
	}
}
void printSystem()
{
	int i;
	cout << "\n\t\tOur System is :";
	cout << "\nQuantum: " << quantum;
	cout << "\nPi:  AT  BT RT";
	for(i=0; i<NP; i++)
	{
		cout << "\nP" << i << ": " << processes[i][0] << " " << processes[i][1] << " " << processes[i][2];
	}
	cout << "\nThe qeue: ";
	Q *n;
	for(n=qeue; n!=NULL; n=n->next)
	{
		cout << "P" << n->p;
	}
}
unsigned int executionRemained()
{
	int i;
	unsigned int x = 0;
	for(i=0; i<NP; i++)
	{
		if(processes[i][2] > 0)
		{
			x = 1;
		}
	}
	return x;
}
void addToQeue(int i)
{
	Q *n, *n1;
	n = (Q *)malloc(sizeof(Q));
	n->next = NULL;
	n->p = i;
	if(qeue == NULL)
	{
		
		qeue = n;
	}
	else
	{
		for(n1 = qeue ; n1->next!=NULL; n1=n1->next);
		n1 -> next = n;
	}
}
void addArrivedProcessesToQeue()
{
	int i;
	for(i=0; i<NP; i++)
	{
		if(processes[i][0] == timet)
		{
			addToQeue(i);
		}
	}
}
unsigned int getNextProcess()
{
	Q *n;
	int x;
	if(qeue == NULL)
	{
		return -1;
	}
	else
	{
		x = qeue -> p;
		n = qeue;
		qeue = qeue -> next;
		free(n);
		return x;
	}
}
void schedule()
{
	unsigned int np, toRun, q, i;
	q = 0;
	addArrivedProcessesToQeue();
	while(executionRemained())
	{
		np = getNextProcess();
		if(np == -1)
		{
			/*
			here if there is no process in waiting qeue
			which mean the process get IDLe state.
			here in this program we put -1 in scheduler[time]
			which mean that the processor get IDLE in this time.
			
			*/
			scheduler[timet] = -1;
			timet++;
			addArrivedProcessesToQeue();
		}
		else
		{
			q = quantum;
			if(processes[np][2] < q)
			{
				q = processes[np][2];
			}
			for(i = q; i>0; i--)
			{
				scheduler[timet]=np;
				timet++;
				processes[np][2]--;
				addArrivedProcessesToQeue();
			}
			if(processes[np][2] > 0)
			{
				addToQeue(np);
			}
		}
		
		
		printSystem();
		int x;
		
	}
}
void printScheduling()
{
	int i;
	cout << "\n\nScheduling: " << endl;
	for(i=0; i<timet; i++)
	{
		cout << "[" << i << "-" << i+1 << "] (P" << scheduler[i] << ") " << endl;
	}
	cout << "\n\nWaiting Time: " << endl;
	for(i=0; i<NP; i++)
	{
		cout << "\nP" << i << ": " <<  WT[i];
	}
	//counting Average Waiting Time...
	float AWT = 0.0;
	for(i=0; i<NP; i++)
	{
		AWT = AWT+WT[i];
	}
	AWT = AWT/NP;
	cout << "\n\nAverage Waiting Time: " << AWT;
}
void WatingTime()
{
	int i;
	unsigned int releaseTime, t;
	for(i=0; i<NP; i++)
	{
		
		for(t=timet-1; scheduler[t]!= i; t--);
		releaseTime = t+1;
		WT[i] = releaseTime - processes[i][0] - processes[i][1];
	}
}

main()
{
	getSystem();
	printSystem();
	schedule();
	WatingTime();
	printScheduling();
}