Please use c++ to this program Objectives Design and implement a discrete event
ID: 3715968 • Letter: P
Question
Please use c++ to this program
Objectives
Design and implement a discrete event simulation
Choose and implement appropriate data structures
Adapt standard algorithms to a specific problem
Task
Consider the scenario of a license service center. Suppose two services are provided: applying for a new license (Service 1) and renewing an existing license (Service 2). There are three counters (1-3) for Service 1 and three counters (4-6) for Service 2. The customers are categorized based on the type of service they are asking for and each customer is given a ticket number. Each counter serves the customers asking for that particular service, following the order of their ticket numbers. If at the moment there is no customer for that service, the corresponding counter will help serve the customers asking for the other service. For example, Counters 1-3 serve the available customers asking for Service 1; if there is no customer for Service 1, Counter 1-3 help serve the customers asking for Service 2; and vice versa.
Please only write single program which simulates the queuing and service of the customers in this license service center.
Program
Your program should choose theproperqueuestrategyandrun discrete event simulation. The simulation should start at time 0 and run until all customers have been served. Your program should be readable and well commented.
Data Structures and Algorithms
Part of the purpose of this subject is to gain an in-depth understanding of data structures and algorithms. As
such, all programming tasks in this subject require you to choose appropriate data structures andalgorithms, and to implement them yourself. You may not take advantage of any built in data structures more complex than an array, but instead should provide your own implementation. The use of STL, Java Collection, or any collection framework in your language of choice, is disallowed. If you use any references other than the lecture notes, ensure you cite them or you may receive 0 . A clear comment in your code is sufficient.
Readme
Write text file named readme. Include clear instructions on how to compile and run your algorithm. Ensure that your program compiles and runs correctly . If your program does not compile, it will receive 0 marks. If it doesn't run according to the specification, you will receive very few marks. You may also include a makefile if you wish.
Analysis
Write file named analysis.pdf explaining the queue strategy and the data structures that you use in your code.
Input
Your program should read a file name from standard input, and run the simulation using the named file as the input file.
The input file has the following format:
The number of servers.
A set of lines each consisting of a customer arrival time followed by the corresponding service time, followed by the service type (1 or 2).
Times are in seconds, from the start of the simulation. Although a sample input file has been provided, your program should still run successfully on substantially larger inputs.
Output
Output should be to standard output.
The output should consist of the following data, clearly labelled:
Number of people served for each server.
Time that the last customer finished being served (total simulation time) for each server.
Average time a customer spends in queue.
Maximum time a customer spends in queue.
Maximum Length of queue.
Total idle time for each server.
the input.txt sample
6
0 351 1
128 511 2
351 309 1
457 383 2
510 313 2
567 329 2
1002 547 2
1412 508 2
1518 395 1
1747 585 1
1968 310 1
2276 431 2
2359 414 1
2360 529 2
2443 538 2
2675 356 2
2727 446 2
2851 433 2
2881 493 2
2933 512 2
3056 526 1
3260 382 1
3288 503 2
3296 496 2
3362 348 2
3445 335 2
3447 449 1
3454 587 2
3473 402 2
3494 475 1
Explanation / Answer
#include<iostream>
#include<fstream>
#include<iomanip>
using namespace std;
#define Nah 9999999999.0
double sysTime = 0;
double sysTimeM = 0;
int numBusy = -1;
int numBusyM = -1;
int numServer = 0;
int numCustomer = 0;
double sumServiceTime = 0;
double sumWaitTime = 0;
double sumWaitTimeM = 0;
double maxWaitTime = 0;
double maxWaitTimeM = 0;
int maxQueue = 0;
int maxQueueM = 0;
int numQueue = 0;
struct numQM {
int numQ;
int positionQ;
int positionSN;
};
struct waitNode {
double processTime;
double inTime;
waitNode* next;
};
struct serverNode {
double time;
double totalIdleTime;
double lastFinishTime;
int id;
int maxQ;
double sumWaitTimeM;
waitNode* snqh;
waitNode* snqe;
numQM* nq;
};
numQM** nQM = NULL;
serverNode* serverHeap = NULL;
serverNode* serverHeapM = NULL;
serverNode newArrive;
waitNode* qHead = NULL;
waitNode* qEnd = NULL;
//function declaration
void qPush(waitNode*&, waitNode*&, double, double, int);
double qPop(waitNode*&);
void serviceEnd(serverNode*, double, int&);
void serviceEndM(serverNode*, double, int&);
void arrive(serverNode*, double, double, int&);
void arriveM(serverNode*, double, double, int&);
void siftup(serverNode*, int);
void siftupM(serverNode*, int);
void siftup(int);
void siftdown(serverNode*, int, int);
void siftdownM(serverNode*, int, int);
void siftdown(int);
int main() {
char filename[100];
cout << "Please input file name : ";
cin >> filename;
newArrive.time = Nah;
newArrive.id = 0;
ifstream ins(filename);
if (!ins.is_open()) {
cerr << "File open error" << endl;
exit(-1);
}
double arriveTime = 0;
double processTime = 0;
double preprocessTime = 0;
ins >> numServer;
serverHeap = new serverNode[numServer];
serverHeapM = new serverNode[numServer];
nQM = (numQM**)new numQM*[numServer];
for (int i = 0; i < numServer; i++) {
serverHeap[i].id = i;
serverHeap[i].totalIdleTime = 0;
serverHeap[i].lastFinishTime = 0;
serverHeap[i].time = Nah;
serverHeap[i].snqh = NULL;
serverHeap[i].snqe = NULL;
}
for (int i = 0; i < numServer; i++) {
serverHeapM[i].id = i;
serverHeapM[i].totalIdleTime = 0;
serverHeapM[i].lastFinishTime = 0;
serverHeapM[i].time = Nah;
serverHeapM[i].maxQ = 0;
serverHeapM[i].snqh = NULL;
serverHeapM[i].snqe = NULL;
serverHeapM[i].sumWaitTimeM = 0;
serverHeapM[i].nq = new numQM;
serverHeapM[i].nq->positionQ = i;
serverHeapM[i].nq->positionSN = i;
serverHeapM[i].nq->numQ = 0;
nQM[i] = serverHeapM[i].nq;
}
while (!ins.eof()) {
if ((int)ins.get() == -1) {
arriveTime = Nah;
}
else if ((int)ins.peek() == -1) {
arriveTime = Nah;
}
else {
numCustomer++;
ins >> arriveTime;
ins >> processTime;
sumServiceTime += processTime;
}
while (1) {
if (newArrive.time == Nah && arriveTime != Nah) {
sysTime = 0;
newArrive.time = arriveTime;
preprocessTime = processTime;
}
else if (newArrive.time < serverHeap[0].time) {
sysTime = newArrive.time;
newArrive.time = arriveTime;
if (numBusy < numServer - 1) {
arrive(serverHeap, preprocessTime, sysTime, numBusy);
preprocessTime = processTime;
}
else {
qPush(qHead, qEnd, preprocessTime, sysTime, numQueue);
numQueue++;
if (numQueue > maxQueue) maxQueue = numQueue;
}
}
else if (serverHeap[0].time <= newArrive.time) {
sysTime = serverHeap[0].time;
serviceEnd(serverHeap, sysTime, numBusy);
if (numQueue > 0) {
sumWaitTime += (sysTime - qHead->inTime);
if (maxWaitTime < (sysTime - qHead->inTime)) maxWaitTime = sysTime - qHead->inTime;
double temp = qPop(qHead);
numQueue--;
arrive(serverHeap, temp, sysTime, numBusy);
}
}
if (newArrive.time < serverHeap[0].time) break;
if (newArrive.time == Nah && serverHeap[0].time == Nah) break;
}
}
ins.close();
cout << fixed << setprecision(3);
cout << "Single queue : " << endl;
cout << "The number of customers : " << numCustomer << endl;
cout << "The finishing time : " << sysTime << endl;
cout << "The average service time : " << sumServiceTime / numCustomer << endl;
cout << "The average time a customer spends in queue : " << sumWaitTime / numCustomer << endl;
cout << "The maximum time a customer spends in queue : " << maxWaitTime << endl;
cout << "The average length of queue : " << sumWaitTime / sysTime << endl;
cout << "The maximum length of queue : " << maxQueue << endl;
for (int i = 0; i < numServer; i++)
cout << " Total idle time for server " << i + 1 << " : " << serverHeap[i].totalIdleTime << endl;
numCustomer = 0;
arriveTime = 0;
processTime = 0;
preprocessTime = 0;
ins.open(filename);
ins >> numServer;
while (!ins.eof()) {
if ((int)ins.get() == -1) {
arriveTime = Nah;
}
else if ((int)ins.peek() == -1) {
arriveTime = Nah;
}
else {
numCustomer++;
ins >> arriveTime;
ins >> processTime;
}
while (1) {
if (newArrive.time == Nah && arriveTime != Nah) {
sysTimeM = 0;
newArrive.time = arriveTime;
preprocessTime = processTime;
}
else if (newArrive.time < serverHeapM[0].time) {
sysTimeM = newArrive.time;
newArrive.time = arriveTime;
if (numBusyM < numServer - 1) {
arriveM(serverHeapM, preprocessTime, sysTimeM, numBusyM);
preprocessTime = processTime;
}
else {
int qIndex = nQM[0]->positionSN;
qPush(serverHeapM[qIndex].snqh, serverHeapM[qIndex].snqe, preprocessTime, sysTimeM, serverHeapM[qIndex].nq->numQ);
serverHeapM[qIndex].nq->numQ++;
siftdown(serverHeapM[qIndex].nq->positionQ);
if (serverHeapM[qIndex].maxQ < serverHeapM[qIndex].nq->numQ)
serverHeapM[qIndex].maxQ = serverHeapM[qIndex].nq->numQ;
}
}
else if (serverHeapM[0].time <= newArrive.time) {
sysTimeM = serverHeapM[0].time;
serviceEndM(serverHeapM, sysTimeM, numBusyM);
if (serverHeapM[numBusyM + 1].nq->numQ > 0) {
sumWaitTimeM += (sysTimeM - serverHeapM[numBusyM + 1].snqh->inTime);
serverHeapM[numBusyM + 1].sumWaitTimeM += (sysTimeM - serverHeapM[numBusyM + 1].snqh->inTime);
if (maxWaitTimeM < (sysTimeM - serverHeapM[numBusyM + 1].snqh->inTime))
maxWaitTimeM = sysTimeM - serverHeapM[numBusyM + 1].snqh->inTime;
double temp = qPop(serverHeapM[numBusyM + 1].snqh);
serverHeapM[numBusyM + 1].nq->numQ--;
siftup(serverHeapM[numBusyM + 1].nq->positionQ);
arriveM(serverHeapM, temp, sysTimeM, numBusyM);
}
}
if (newArrive.time < serverHeapM[0].time) break;
if (newArrive.time == Nah && serverHeapM[0].time == Nah) break;
}
}
ins.close();
for (int i = 0; i < numServer; i++)
if (maxQueueM < serverHeapM[i].maxQ)
maxQueueM = serverHeapM[i].maxQ;
cout << "Multi queue : " << endl;
cout << "The number of customers : " << numCustomer << endl;
cout << "The finishing time : " << sysTimeM << endl;
cout << "The average service time : " << sumServiceTime / numCustomer << endl;
cout << "The average time a customer spends in all queue : " << sumWaitTimeM / numCustomer << endl;
cout << "The maximum time a customer spends in all queue : " << maxWaitTimeM << endl;
cout << "The average length of all queue : " << sumWaitTimeM / (sysTimeM * numServer) << endl;
for (int i = 0; i < numServer; i++)
cout << " The average length of queue " << i + 1 << " : " << serverHeapM[i].sumWaitTimeM / sysTimeM << endl;
cout << "The maximum length of all queue : " << maxQueueM << endl;
for (int i = 0; i < numServer; i++)
cout << " The maximum length of queue " << i + 1 << " : " << serverHeapM[i].maxQ << endl;
for (int i = 0; i < numServer; i++)
cout << "Total idle time for server " << i + 1 << " : " << serverHeapM[i].totalIdleTime << endl;
return 0;
}
//heap siftup - small up big down
void siftup(serverNode* sn, int c) {
if (c == 0) return;
int p = (c - 1) / 2;
if (sn[p].time > sn[c].time) {
swap(sn[c], sn[p]);
siftup(sn, p);
}
}
void siftupM(serverNode* sn, int c) {
if (c == 0) return;
int p = (c - 1) / 2;
if (sn[p].time > sn[c].time) {
swap(sn[c], sn[p]);
swap(sn[c].nq->positionQ, sn[p].nq->positionQ);
siftup(sn, p);
}
}
void siftup(int c) {
if (c == 0) return;
int p = (c - 1) / 2;
if (nQM[p]->numQ > nQM[c]->numQ) {
swap(nQM[c], nQM[p]);
swap(nQM[c]->positionQ, nQM[p]->positionQ);
siftup(p);
}
}
//heap siftdown - small up big down
void siftdown(serverNode* sn, int n, int p) {
if (p * 2 >= n) return;
int l = p * 2 + 1;
int r = p * 2 + 2;
int c = 0;
if (l < n) {
if (sn[l].time > sn[r].time)
c = r;
else c = l;
if (sn[c].time < sn[p].time) {
swap(sn[c], sn[p]);
p = c;
siftdown(sn, n, p);
}
}
else {
if (sn[l].time < sn[p].time) {
swap(sn[l], sn[p]);
p = l;
siftdown(sn, n, p);
}
}
}
void siftdownM(serverNode* sn, int n, int p) {
if (p * 2 >= n) return;
int l = p * 2 + 1;
int r = p * 2 + 2;
int c = 0;
if (l < n) {
if (sn[l].time > sn[r].time)
c = r;
else c = l;
if (sn[c].time < sn[p].time) {
swap(sn[c], sn[p]);
swap(sn[c].nq->positionSN, sn[p].nq->positionSN);
p = c;
siftdown(sn, n, p);
}
}
else {
if (sn[l].time < sn[p].time) {
swap(sn[l], sn[p]);
swap(sn[l].nq->positionSN, sn[p].nq->positionSN);
p = l;
siftdown(sn, n, p);
}
}
}
void siftdown(int p) {
if (p * 2 >= numServer) return;
int l = p * 2 + 1;
int r = p * 2 + 2;
int c = 0;
if (r <= numServer - 1) {
if (nQM[l]->numQ > nQM[r]->numQ)
c = r;
else c = l;
if (nQM[c]->numQ < nQM[p]->numQ) {
swap(nQM[c], nQM[p]);
swap(nQM[c]->positionQ, nQM[p]->positionQ);
p = c;
siftdown(p);
}
}
else {
if (nQM[l]->numQ < nQM[p]->numQ) {
swap(nQM[l], nQM[p]);
swap(nQM[l]->positionQ, nQM[p]->positionQ);
p = l;
siftdown(p);
}
}
}
void qPush(waitNode*& qh, waitNode*& qe,double t, double st, int nq) {
if (nq == 0) {
qh = new waitNode;
qh->processTime = t;
qh->inTime = st;
qh->next = NULL;
qe = qh;
}
else {
qe->next = new waitNode;
qe = qe->next;
qe->processTime = t;
qe->inTime = st;
qe->next = NULL;
}
}
double qPop(waitNode*& qh) {
double t = qh->processTime;
waitNode* temp = qh;
qh = qh->next;
delete temp;
return t;
}
void serviceEnd(serverNode* sn, double st, int& nb) {
sn[0].lastFinishTime = st;
sn[0].time = Nah;
swap(sn[0], sn[nb]);
siftdown(sn, nb, 0);
nb--;
}
void serviceEndM(serverNode* sn, double st, int& nb) {
sn[0].lastFinishTime = st;
sn[0].time = Nah;
swap(sn[0], sn[nb]);
swap(sn[0].nq->positionSN, sn[nb].nq->positionSN);
siftdownM(sn, nb, 0);
nb--;
}
void arrive(serverNode* sn, double pt, double st, int& nb) {
nb++;
sn[nb].totalIdleTime += (st - sn[nb].lastFinishTime);
sn[nb].time = pt + st;
siftup(sn, nb);
}
void arriveM(serverNode* sn, double pt, double st, int& nb) {
nb++;
sn[nb].totalIdleTime += (st - sn[nb].lastFinishTime);
sn[nb].time = pt + st;
siftupM(sn, nb);
}