//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++//
// Filename	: qlnklst.cpp				      //
// Author	: Loreto E. Aquino Jr.			      //
// Date		: Feb 2004				      //
// Remarks	: Sample program using Linked-List Queue in   //
//  			a Round-Robin Scheduling Simulation   //
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++//

//header files
#include <iostream.h>
#include <fstream.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>

// node and queue structure
struct queuenode
{
	char name[4];	 		// process name
	int  time;			// burst time
	struct  queuenode *link;    	// pointer to next node
};
typedef struct queuenode queuenode;

struct queue
{
	queuenode *front;		// queue front pointer
	queuenode *rear;		// queue rear pointer
};
typedef struct queue queue;

// function prototypes

// append new node to queue structure by receiving the current queue
// structure and the process and burst time to be added.
queue *enqueue(queue *q, char *p, int t);

queue *dequeue(queue *q, char *p, int &t);


// main program
void main()
{
	queue *q;			// declare pointer to structure
	ifstream instream;		// declare input stream
	char process[4];		// an array for the process name
	int quantumtime, bursttime;	// holder for quantum and burst time
	int time = 0;			// time counter

	// allocate memory for front and rear pointer
	q->front = (queuenode *) malloc(sizeof(queuenode));
	q->rear = q->front;

	// open input file
	instream.open("process.txt");
	if (instream.fail()) {
		cout << endl << "Opening input file FAILED!";
		exit(1);
	}

	clrscr();

	// read quantum
	instream >> quantumtime;

	cout << "Time:" << time << "\t";
	cout << "Process ";
	time++;

	// read all processes and burst time until EOF
	while (instream >> process)
	{
		instream >> bursttime;

		// enqueue each process and burst time into linked-list
		q = enqueue(q, process, bursttime);
		cout << process << " ";
	}
	cout << "arrives in the queue, quantum time = ";
	cout << quantumtime << " ms" << endl;

	// execute each process until queue is empty
	while (q->rear != q->front)
	{
		// dequeue a process
		q = dequeue(q, process, bursttime);

		// simulate
		cout << "\t" << "Process " << process << " is dequeued" << endl;
		cout << "Time:" << time << "\t";
		cout << "Process " << process << " uses the CPU, ";
		cout << "burst time = " << bursttime << endl;

		// enqueue if burst time is greater than the quantum
		if (bursttime > quantumtime)
		{
			time = time + quantumtime;
			cout << "Time:" << time << "\t";
			cout << "Process " << process << " is enqueued, ";
			bursttime = bursttime - quantumtime;
			cout << "remaining burst time = " << bursttime << endl;

			// enqueue process with remaining burst time
			q = enqueue(q, process, bursttime);
		}
		else // otherwise terminate process
		{
			time = time + bursttime;
			cout << "Time:" << time << "\t";
			cout << "Process " << process << " is finished, " << endl;
		}

	}

	cout << "\t" << "The queue is empty" << endl;
	cout << "\t" << "SIMULATION ENDS! ";

	// close file
	instream.close();

	getch();
} // end of main()


// append new node to queue structure by receiving the current queue
// structure and the process and burst time to be added.
queue *enqueue(queue *q, char *p, int t)
{
	queuenode *n;

	// allocate memory for new node pointer
	n = (queuenode *)malloc(sizeof(queuenode));

	// move process name and burst time into queue structure
	strcpy(n->name, p);
	n->time = t;

	n->link = NULL; 		// make new node as rear
	q->rear->link = n;		// point rear node to new node
	q->rear = n;			// make new node the rear
	return q;				// return appended queue
}


queue *dequeue(queue *q, char *p, int &t)
{
	queuenode *n;

	if (q->rear != q->front)
	{
		n = q->front->link;
		strcpy(p, n->name);
		t = n->time;
	}

	if (q->rear != q->front)
	{
		n = q->front->link;
		q->front->link = n->link;
		if (q->rear == n)
			q->rear = q->front;
	}
	return q;

}

// c0dewr8er
// end of line