// this is the EE/CpE345 homework 4 program file
// with corrections to avoid the errors that were generated
// by the file in the book
// There are probably compiler specific variations that
// are causing the problems that several people have seen
// As I have modified the file, it does not generate any
// errors under MS VC++ 6.0, although the MS header files
// that get called do generate errors for me.

#include <iostream> 
#include <queue>  
#include <math.h> // for sin/cos
#include <time.h> // for time
#include <stdlib.h> // for rand/srand

using namespace std;

void SetSeed(long seed)
{
	srand(seed);
}
double unif()
{
	// returns a random number on the open interval (0,1)
	int n;
	do { n = rand(); } while (n==0 || n==RAND_MAX);
	return double(n)/double(RAND_MAX);
}
double exponential(double mean)
{
	return -mean*log(unif());
}

double SaveNormal;
int    NumNormals = 0;

double normal(double mean, double sigma)
{
#define PI 3.1415927
	double ReturnNormal;
	
	// should we generate two normals?
	if(NumNormals == 0)
    {
		double r = sqrt(-2*log(unif()));
		double t = 2*PI*unif();
		ReturnNormal = r*cos(t);
		SaveNormal   = r*sin(t);
		NumNormals = 1; 
    }
    else
	{
		NumNormals = 0;
		ReturnNormal = SaveNormal;
	}
	return ReturnNormal*sigma + mean;
}

// event representation
class Event
{
	friend bool operator<(const Event& e1, const Event& e2);
	friend bool operator==(const Event& e1, const Event& e2);
	
public:
	Event();
	enum EvtType { arrival, departure };
	Event(EvtType type, double etime) : _type(type), _etime(etime){}
	EvtType get_type() { return _type; }
	double get_time() { return _etime; }
protected:
	EvtType _type;
	double _etime;
};

bool operator <(const Event &e1, const Event &e2)
{	
	return e2._etime < e1._etime;
}

bool operator ==(const Event &e1, const Event &e2)
{
	return e2._etime == e1._etime;
}

// global variables
double Clock, MeanInterArrivalTime, MeanServiceTime, SIGMA, LastEventTime,
TotalBusy, MaxQueueLength, SumResponseTime;
long   NumberOfCustomers, QueueLength, NumberInService, 
TotalCustomers, NumberOfDepartures, LongService;

priority_queue<Event> FutureEventList;

queue<Event> Customers;

// we could define prototypes of the functions here, but I prefer
// to just move the functions in front of where they are used
// this works when the routines are all in one file and there
// are no cross calls.

void Initialization()
{   //  initialize global variables
	Clock = 0.0;
	QueueLength = 0;
	NumberInService = 0;
	LastEventTime = 0.0;
	TotalBusy = 0;
	MaxQueueLength = 0;
	SumResponseTime = 0.0;
	NumberOfDepartures = 0;
	NumNormals = 0;
	LongService = 0;
	
	// create first arrival event
	Event evt(Event::arrival, exponential(MeanInterArrivalTime));
	FutureEventList.push(evt);
}

void ScheduleDeparture()
{
	double ServiceTime;
	// get the job at the head of the queue
	while( (ServiceTime = normal(MeanServiceTime, SIGMA)) < 0);
	Event depart(Event::departure, Clock+ServiceTime);
	FutureEventList.push(depart);
	NumberInService = 1;
	QueueLength--;      // this one isn't waiting anymore
}


void ProcessDeparture(Event evt)
{
	// get the customer description
	Event finished = Customers.front();
	Customers.pop();
	
	// if there are customers in the queue then schedule
	// the departure of the next one
	if ( QueueLength ) ScheduleDeparture();
	else NumberInService = 0;
	
	// measure the response time and add to the sum
	double response = (Clock - finished.get_time());
	SumResponseTime += response;
	if ( response > 4.0 ) LongService++;  // record long service
	TotalBusy += (Clock - LastEventTime); // we were busy
	
	NumberOfDepartures++;
	LastEventTime = Clock;
}

void ReportGeneration()
{
	double RHO  = TotalBusy/Clock;
	double AVGR = SumResponseTime/TotalCustomers;
	double PC4  = ((double)LongService)/TotalCustomers;
	
	//   The '' in the book work better with " for other compilers
	
	cout << "SINGLE SERVER QUEUE SIMULATION - GROCERY STORE CHECKOUT COUNTER \n"
		<< endl;
	cout << "\tMEAN INTERARRIVAL TIME                         "
		<< MeanInterArrivalTime << endl;
	cout << "\tMEAN SERVICE TIME                              "
		<< MeanServiceTime << endl;
	cout << "\tSTANDARD DEVIATION OF SERVICE TIMES            "
		<< SIGMA << endl;
	cout << "\tNUMBER OF CUSTOMERS SERVED                     "
		<< TotalCustomers << endl << endl;
	
	cout << "\tSERVER UTILIZATION                             "
		<< RHO << endl;
	cout << "\tMAXIMUM LINE LENGTH                            "
		<< MaxQueueLength << endl;
	cout << "\tAVERAGE RESPONSE TIME                          "
		<< AVGR << " MINUTES" << endl;
	cout << "\tPROPORTION WHO SPEND FOUR \n"
		<< "\t MINUTES OR MORE IN SYSTEM                     "
		<< PC4 << endl;
	cout << "\tSIMULATION RUNLENGTH                           "
		<< Clock << " MINUTES " << endl;
	cout << "\tNUMBER OF DEPARTURES                           "
		<< TotalCustomers << endl;
}

void ProcessArrival(Event evt)
{
	Customers.push(evt);             // push arrival onto the queue
	QueueLength++;                   // Increment number waiting
	
	// if the server is idle, fetch the event, do statistics,
	// and put into service
	if ( NumberInService == 0 ) ScheduleDeparture();
    else TotalBusy += (Clock - LastEventTime);  // server is busy
	
	// adjust max queue length statistics
	if ( MaxQueueLength < QueueLength ) MaxQueueLength = QueueLength;
	
	// schedule the next arrival
	Event next_arrival(Event::arrival,
		Clock+exponential(MeanInterArrivalTime));
	FutureEventList.push(next_arrival);
	LastEventTime = Clock;
}

int main(int argc, char* argv[])
{
	MeanInterArrivalTime = 4.5; MeanServiceTime = 3.2;
	SIGMA                = 0.6; TotalCustomers  = 1000;

	long seed;
	if (argc==2) seed = atoi(argv[1]);    // rng seed given as input
	else seed = time(0);
	SetSeed(seed);                // initialize rng stream
	Initialization();
	
	// Loop until first "TotalCustomers" have departed
	while(NumberOfDepartures < TotalCustomers)
    {
		Event evt = FutureEventList.top();    // get imminent event
		FutureEventList.pop();                // remove imminent event from queue
		Clock = evt.get_time();               // advance simulation time
		if ( evt.get_type() == Event::arrival )
			ProcessArrival(evt);
		else
			ProcessDeparture(evt);
    }
	ReportGeneration();  
	return 0;
}