/****************
 * ID NUMBERS	*
 * 02-025754	*
 * 01-055126	*
 ****************/


// Header files
#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>
#include <fstream.h>
#include <iomanip.h>
#include <math.h>
#include <string.h>
#define NUM_QUEUES 8


//Definition for Job Class
//*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-
class Job
{ 
	private:
		int pid;
		int artime;
	    int rmtime;
	    int pri;
	    int tw;
		int tio;
		int tt;
	    Job *next;
	public: 
		Job(int p,int a,int r):pid(p),artime(a),rmtime(r),pri(0),tw(0),tio(0),tt(0),next(NULL){}
		int getPid(){return pid;}
		int getArtime(){return artime;}
		int getPri(){return pri;}
		void setPri(int p){pri = p;}
		int getRmtime(){return rmtime;}
		void setRmtime(int r){rmtime =r;}
		int getTw() {return tw;}
		void setTw(int t){tw =t;}
		int getTio() {return tio;}
		void setTio(int t){tio =t;}
		int getTt() {return tt;}
		void setTt(int t){tt =t;}
		Job* getNext(){return next;}
		void setNext(Job* j){next = j;}
};
//*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-

//Definition for Queue class
//*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-
class Queue
{
	private:
		Job *first;
	public:
		Queue():first(NULL){}
		void inserta(Job* j);
		void insert_at_end(Job *j);
		Job* dequeue();
		void printq();
		bool empty(){return (first == NULL);}	
		Job* getFirst() {return first;}
		void setFirst(Job *j){first =j;}
		void incwait();
		void incio();
		
};
		
void Queue::inserta(Job *j)
{
	if(first == NULL)
	{
			j->setNext(first);
			first = j;
					
	}
	else
	{
		if(first->getArtime()>j->getArtime())
		{
			j->setNext(first);
			first = j;
			return;
		}
		Job *temp = first;
		while(temp->getNext() != NULL)
		{
			if((temp->getNext()->getArtime() )> j->getArtime())
			{
				j->setNext(temp->getNext());
				temp->setNext(j);
				return;
			}
			else
				temp = temp->getNext();
		}
		if(temp->getNext()==NULL)
		{
			temp->setNext(j);
			j->setNext(NULL);
		}
	}

}

void Queue::insert_at_end(Job *j)
{
	if(first == NULL)
	{
			j->setNext(first);
			first = j;
					
	}
	else
	{
		Job *temp = first;
		while(temp->getNext()!=NULL)
			temp =temp->getNext();
		temp->setNext(j);
		j->setNext(NULL);
	}
}

Job* Queue::dequeue()
{
	Job* head = first;
	first = first->getNext();
	head->setNext(NULL);
	return head;
}


void Queue::printq()
{
	Job* job = first;
	while(job!= NULL)
	{
		cout<<job->getPid()<<" "<<job->getArtime()<<" "<<job->getRmtime()<<" "<<job->getPri();
		cout<<" "<<job->getTw()<<" "<<job->getTio()<<endl;
		job = job->getNext();
	}
}
//*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-		



//Utility function used to test argument validity
int isarg(char *a)
{
	char args[NUM_QUEUES+6][3];
	strcpy(args[0],"-A");
	strcpy(args[1],"-r");
	strcpy(args[2],"-c");
	strcpy(args[3],"-v");
	strcpy(args[4],"-s");
	strcpy(args[5],"-N");
	for(int i = 6;i<NUM_QUEUES+6;i++)
	{
		sprintf(args[i],"-%d",i-6);
	}
	for(int i = 0;i<NUM_QUEUES+6;i++)
	{
		if(strcmp(args[i],a)==0)
			return 1;
	}
	return 0;
}

//Returns the next available job with the highest priority
Job* getnextjob(Queue* qs[NUM_QUEUES])
{
	Job* j;
	for(int i =0;i<NUM_QUEUES;i++)
	{
		if(!(qs[i]->empty()))
		{
			j =qs[i]->dequeue();
			return j;
			i++;
		}
	}
	return NULL;
}

//Test if a higher priority job is available
int higherp_avail(Queue *q[NUM_QUEUES],int n)
{
	for(int i =0;i<n;i++)
	{
		if(!(q[i]->empty()))
			return 1;
	}
	return 0;
}


void Queue::incwait()
{
	Job* j = first;
	
	while(j!=NULL)
	{
		j->setTw(j->getTw()+1);
		j=j->getNext();
	}

}
			
void Queue::incio()
{
	Job* j = first;
	
	while(j!=NULL)
	{
		j->setTio(j->getTio()+1);
		j=j->getNext();
	}

}



//Funtion prototypes
void transfer(Queue* io,Queue* ready[NUM_QUEUES],char compjobs[500],int);
Job* getnextjob(Queue* qs[]);
int higherp_avail(Queue *n[NUM_QUEUES],int n);
int empty(Queue* q[NUM_QUEUES]);
int isarg(char* a);
int isnum(char* n);
int IO_request(int);
int IO_complete(int); 
void smrand();
int mrand();	

//Global variable
int r = 0;	// rand location
int randarray[1000];
int CHANCE_OF_IO_REQUEST = 10; 
int CHANCE_OF_IO_COMPLETE = 4;
int seed = 1;


int main(int argc,char* argv[])
{
	int total_time =0;
	int comp_time;
	int use_srand = 0;
	char* arg;
	int verbose = 0;
	int alg = 0;
	int s;
	double slice[NUM_QUEUES];
	for(int q =0;q<NUM_QUEUES;q++)
		slice[q]= pow(2,q);
	
	//Validation of arguments
	//*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-
	for (int q = 1; q < argc; q++) {
	    arg = argv[q];
	    
		if ((arg[0]=='-')&&isnum(arg + 1)){
			if(((s = strtol(arg+1,NULL,10))<NUM_QUEUES)&&(q!=argc-1))
			{
				if(isnum(argv[q+1])){
				slice[s] = strtol(argv[q+1],NULL,10);
				q++;
				}
			}
			else
			{
				cerr<<"Improper parameter for option "<<argv[q]<<":"<<endl;
				exit(1);
			}
			
		}
		
	    else if (strcmp(arg,"-r")==0) 
		{   if(q!=argc -1 ){
				if(isnum(argv[q+1]))
				{
					CHANCE_OF_IO_REQUEST = strtol(argv[q+1],NULL,10);
					q++;
				}
				else
				{
				cerr<<"Improper parameter for option "<<argv[q]<<":"<<endl;
				exit(1);
				}
				
			}
			else
			{
				cerr<<"Improper parameter for option "<<argv[q]<<":"<<endl;
				exit(1);
			}
	    } 
		else if (strcmp(arg,"-c")==0) {
			if(q!=argc -1 ){	
				if(isnum(argv[q+1]))
				{
					CHANCE_OF_IO_COMPLETE = strtol(argv[q+1],NULL,10);
					q++;
				}
				else
				{
					cerr<<"Improper parameter for option "<<argv[q]<<":"<<endl;
					exit(1);
				}
			}
			else
			{
				cerr<<"Improper parameter for option "<<argv[q]<<":"<<endl;
				exit(1);
			}
	    } 
		else if (strcmp(arg,"-s")==0) {
			if(q!=argc -1 ){
				if(isnum(argv[q+1]))
				{
					seed = strtol(argv[q+1],NULL,10);
					q++;
					use_srand = 1;
				}
				else
				{
					cerr<<"Improper parameter for option "<<argv[q]<<":"<<endl;
					exit(1);
				}
			}
			else
			{
				cerr<<"Improper parameter for option "<<argv[q]<<":"<<endl;
				exit(1);
			}
	    }
		else if (strcmp(arg,"-v")==0) {
			verbose = 1;
	    }
		else if (strcmp(arg,"-N")==0) {
			
	    }
		else if (strcmp(arg,"-A")==0) {
			alg =1;
	    }
		else
		{
			cerr<<"Unrecognised option: "<<argv[q]<<endl;	
			exit(1);
		
		}
	}
	//*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-
	
	int ttio=0;
	int ttiw=0;
	int shortest = 1000000;
	int longest=0;
	int total_jobs=0;
	double slice_left;
	int swapped;
	Queue *comp_jobs = new Queue();
	char pid_string[4],job_status[20],time_rem[4],request[6],completed[500];
	
	Queue* pri_queues[NUM_QUEUES];//An array of ready queues
	
	for(int i=0;i<NUM_QUEUES;i++)
	{
		pri_queues[i]=new Queue();
	}
	
	Queue* alljobs = new Queue(); // Alljobs used to store sorted list of jobs in system
	int pid,artime,burst,pri,clock;
	Queue* ioqueue = new Queue();
	
	
    
	/* initialize clock */ 
	clock=0; 
	
	srand(seed);
	smrand();
	
	
	while((scanf("%d%d%d%d",&(pid),&(artime),&(burst),&(pri)))==4)
	{
		Job *job = new Job(pid,artime,burst);
		alljobs->inserta(job);
	}
	
	//Get all jobs that have an arrival time of 0
	while(alljobs->getFirst()->getArtime()==clock)
	{
		Job *j = alljobs->dequeue();
		pri_queues[0]->insert_at_end(j);
	}
	clock++;
	
	while( !(alljobs->empty()) || !(ioqueue->empty()) || !(empty(pri_queues))) // Tests if jobs are in the system 
	{ 
		Job* current; 
		current = getnextjob(pri_queues);
		if(current!=NULL)
			slice_left = slice[current->getPri()];
		
		
		while(1) // this loop is the main process management loop  
		{ 
			for(int i=0;i<NUM_QUEUES;i++)
			{
				pri_queues[i]->incwait(); // Increment total wait time for all jobs in ready queue
			}
			ioqueue->incio(); //Increment time in IO
			
			
			//Gets jobs which have arrival time equal to current clock value
			while(alljobs->getFirst()!=NULL)
			{
				if(alljobs->getFirst()->getArtime()>clock)
					break;
				
				if(alljobs->getFirst()->getArtime()==clock)
				{
					Job *j = alljobs->dequeue();
					pri_queues[0]->insert_at_end(j);
					
				}
				
			}
			
			//Transfer completed jobs back to ready queue;
			transfer(ioqueue,pri_queues,completed,use_srand);
			
			//If a current job isn't available then system is idling
			if(current==NULL)
			{
				strcpy(pid_string,"*");
				strcpy(time_rem,"x");
				strcpy(request,"false");
				strcpy(job_status,"idling");
				
			}
			else
			{
				strcpy(request,"false");
				swapped = 0;			
				sprintf(pid_string,"%d",current->getPid());
				strcpy(job_status,"still running");
	
				if(current->getRmtime()==1)			
				{
					comp_time = clock - current->getArtime();
					current->setTt(comp_time);
					comp_jobs->insert_at_end(current);
					total_jobs++;
					
					//*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
					//Adjust statistics on each job completion
					
					if(comp_time>longest)
						longest = comp_time;
					if(comp_time < shortest)
						shortest = comp_time;
					
					total_time+=comp_time;
					ttiw+=current->getTw();
					ttio+=current->getTio();
					//*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
					strcpy(job_status,"*exited");
				    swapped =1;
					//if this job has finished its work (if time remaining is 1) 
					
					//then mark current_job as swapped out (job complete, exit) 
				}
				
				
				//If agressive scheduler is being used then check if current job is to be pre-empted
				else if(alg && higherp_avail(pri_queues,current->getPri()))
				{
					//Running jobs priority is decremented unless it is already at 0
					if(current->getPri()!=0)
						current->setPri(current->getPri()-1);
					
					pri_queues[current->getPri()]->insert_at_end(current);
										
					strcpy(job_status,"pre-empted");
				    swapped =1;			
				
				}
				
				// check for I/O request from current_job 
				else if(IO_request(use_srand)) 
				{
					if(alg)//Jobs priority should be one less when it returns to queue 
					{
						if(current->getPri()!=0)
							current->setPri(current->getPri()-1);
					}
					else
						current->setPri(0);
											
					ioqueue->insert_at_end(current);
					strcpy(request,"true ");
					strcpy(job_status,"sleeping");
				    swapped =1;			
				}
							
			
								
				//Test for time slice expiry
				else if(slice_left==1)
				{
					if(current->getPri() == NUM_QUEUES -1)
					   pri_queues[current->getPri()]->insert_at_end(current);
					else
					{
						current->setPri(current->getPri()+1);
						pri_queues[current->getPri()]->insert_at_end(current);
					}
					strcpy(request,"false");
					strcpy(job_status,"time slice expired");
				    swapped =1;		
						
				}
				current->setRmtime(current->getRmtime()-1);
				sprintf(time_rem,"%d",current->getRmtime());
			}
		
			if(verbose)		
				cerr<<left<<setw(4)<<clock - 1<<":"<<setw(4)<<pid_string<<":"<<setw(3)<<time_rem<<": "<<request<<": "<<setw(20)<<completed<<": "<<job_status<<endl;
			slice_left--;	
			clock ++ ;
			if(swapped)
				break;
			 
		} // End while main process management loop 

	} // End while if there are jobs in the system */ 
	
	cout<<"=========+=================+=================+=============+"<<endl;
	cout<<"         | Total time      | Total time      | Total time  |"<<endl;
	cout<<"     Job#| in wait         | in sleeping on  | in system   |"<<endl;
	cout<<"         | state           | I/O state       |             |"<<endl;
	cout<<"=========+=================+=================+=============+"<<endl;
	Job *ended;
	
	//Print each jobs statistics
	while(!(comp_jobs->empty()))
	{
		ended = comp_jobs->dequeue();
		cout<<ended->getPid()<<"      |"<<setw(3)<<ended->getTw()<<"              |";
		cout<<setw(3)<<ended->getTio()<<"              |";
		cout<<setw(3)<<ended->getTt()<<"          |"<<endl;
		delete(ended);
		
	}
	cout<<"=========+=================+=================+=============+"<<endl;
	cout<<"Total simulation run time: "<<clock-1<<endl;
	cout<<"Total number of jobs: "<<total_jobs<<endl;
	cout<<"Shortest job completion time: "<<shortest<<endl;
	cout<<"Longest job completion time: "<<longest<<endl;
	cout<<"Average job completion time: "<<(float)total_time/total_jobs<<endl;
	cout<<"Average time in ready queue: "<<(float)ttiw/total_jobs<<endl;
	cout<<"Average time in sleeping on I/O state: "<<(float)ttio/total_jobs<<endl;
	
	//Garbage collection
	delete comp_jobs;
	delete ioqueue;
	delete alljobs;
	for(int i=0;i<NUM_QUEUES;i++)
		delete pri_queues[i];
	

return 0;
}

//mrand funtion definition
int mrand()
{
	
	if(r==1000)
		r=0;
	return randarray[r++];
}

// Used to initialise random array
void smrand()
{
	fstream file("random.txt",ios::in);
	
	for(int j=0;j<1000;j++)
	{
		file>>randarray[j];
	}
}

int IO_request(int use_srand) 
{ 
	int prob;
	if(use_srand)
		prob = rand();
	else
		prob = mrand();
	
	if( prob % CHANCE_OF_IO_REQUEST == 0 ) 
		return 1;
	else
		return 0;
	
} 


int IO_complete(int use_srand) 
{ 
	int prob;
	if(use_srand)
		prob = rand();
	else
		prob = mrand();
	
	if( prob % CHANCE_OF_IO_COMPLETE == 0 ) 
		return 1;
	else
		return 0;
}

int isnum(char* n)
{
	int i = 0;
	while(n[i]!='\0')
	{
		if(!(isdigit(n[i])))
			return 0;
		i++;
	}
	return 1;
}

void transfer(Queue* io,Queue* ready[NUM_QUEUES],char compjobs[500],int use_srand)
{
	int i;
	char cpid[5];
	strcpy(compjobs,"");
	if(!(io->empty())) // If there are jobs in IO_queue
	{
		Job* temp = io->getFirst();
		while(temp!=NULL)
		{
			if((i=IO_complete(use_srand))){ //Call IO_complete for element at head
				sprintf(cpid,"%d",temp->getPid());
				io->setFirst(temp->getNext());
				temp->setNext(NULL);
				if(strcmp(compjobs,"")==0)
					strcat(compjobs,cpid);
				else
				{
					strcat(compjobs,",");
					strcat(compjobs,cpid);
				}
				ready[temp->getPri()]->insert_at_end(temp);
				temp = io->getFirst();
			}
			if(!i) // If IO_complete fails break from while loop
				break;
		
			
		}
		while(temp!=NULL)
		{
			if(temp->getNext()!=NULL)
			{
				if(IO_complete(use_srand)){ //Call IO_complete for remaining elements
					sprintf(cpid,"%d",temp->getNext()->getPid());
					if(strcmp(compjobs,"")==0)
						strcat(compjobs,cpid);
					else
					{
						strcat(compjobs,",");
						strcat(compjobs,cpid);
					}
					Job *temp2 = temp->getNext()->getNext();
					temp->getNext()->setNext(NULL);
						ready[temp->getNext()->getPri()]->insert_at_end(temp->getNext());
					temp->setNext(temp2);
				}
			}
			temp = temp->getNext();
			
		}
		if(strcmp(compjobs,"")==0)
			strcat(compjobs,"none");
	}
	else
		strcat(compjobs,"none");
}


//Tests if ready all ready queues are empty
int empty(Queue* q[NUM_QUEUES])
{
	for(int i= 0;i<NUM_QUEUES;i++)
	{
		if(!(q[i]->empty()))
			return 0;
	}
	return 1;
}	
//*-_*-_*-_*-_*-_*-_*-_*-_*-_*-_*-_*-_*-_*-_*-_*-_*-_*-_*-_*-_*-_*-_*-_*-_*-_*-_*-_*-_*-_*-_*-_*-_*-_*-_*-_*-_*-_*-_*-_*-_*-_*-_*-_*-_*-_