/* Trace-driven simulation of Banff park entry queue     */
/*                                                       */
/* Written by Carey Williamson, University of Calgary    */
/*                                                       */
/* Usage: cc -o parksim parksim.c -lm                    */
/*        ./parksim                                      */

#include <stdio.h>
#include <stdlib.h>
#include <math.h> /* use man 3 log for the math functions */

#define NUM_CARS 10000   /* Number of cars to simulate */
#define END_OF_TIME 99999.9 /* Time far in the future */

/* Debugging output */
/* #define DEBUG 1 */

/***********************************************************************/
/*                 RANDOM NUMBER GENERATION STUFF                      */
/***********************************************************************/

/* Parameters for random number generation. */
#define MAX_INT 2147483647       /* Maximum positive integer 2^31 - 1 */

/* Generate a random floating point value uniformly distributed in [0,1] */
float Uniform01()
  {
    float randnum;

    /* get a random positive integer from random() */
    randnum = (float) 1.0 * random();

    /* divide by max int to get something in 0..1  */
    randnum = (float) randnum / (1.0 * MAX_INT); 

    return( randnum );
  }

/***********************************************************************/
/*                 MAIN PROGRAM                                        */
/***********************************************************************/

int main()
  {
    int i, arrivals, departures, qsize, frontcar, maxq;
    float now, nextarrival, nextdeparture, fdone, gdone, rand;
    float arrivaltimes[NUM_CARS], servicetimes[NUM_CARS];
    float waittimes[NUM_CARS], sojourntimes[NUM_CARS];
    float meanwait, varwait, stdwait;
    float last, meanqueue;
    FILE *arrivalfile, *servicefile;

    /* Read in arrival time information all at once */
    arrivalfile = fopen("arrivaltimes.dat", "r");
    if( arrivalfile == NULL )
      {
	fprintf(stderr, "Unable to open file arrivaltimes.dat!\n");
	exit(0);
      }
    for( i = 0; i < NUM_CARS; i++ )
      {
	if( fscanf(arrivalfile, "%f", &arrivaltimes[i]) < 1 )
	  {
	    fprintf(stderr, "Only %d lines in arrivaltimes.dat file!\n", i);
	    exit(0);
	  }
#ifdef DEBUG
	printf("Car %d is scheduled to arrive at time %8.6f\n",
	       i, arrivaltimes[i]);
#endif
      }
    fclose(arrivalfile);

    /* Read in service time information all at once */
    servicefile = fopen("servicetimes.dat", "r");
    if( servicefile == NULL )
      {
	fprintf(stderr, "Unable to open file servicetimes.dat!\n");
	exit(0);
      }
    for( i = 0; i < NUM_CARS; i++ )
      {
	if( fscanf(servicefile, "%f", &servicetimes[i]) < 1 )
	  {
	    fprintf(stderr, "Only %d lines in servicetimes.dat file!\n", i);
	    exit(0);
	  }
	
#ifdef DEBUG
	printf("Car %d will have service time %8.6f\n",
	       i, servicetimes[i]);
#endif
      }
    fclose(servicefile);

    /* Initialization */
    arrivals = 0;
    departures = 0;
    qsize = 0;
    meanqueue = 0.0;
    last = 0.0;
    maxq = 0;
    now = 0.0;
    frontcar = 0;
    nextarrival = arrivaltimes[frontcar];
    nextdeparture = END_OF_TIME;

#ifdef DEBUG
    printf("Beginning trace-driven simulation now...\n");
#endif

    while( departures < NUM_CARS )
      {
	/* determine next event */
	if( nextarrival < nextdeparture )
	  {
	    now = nextarrival;
#ifdef DEBUG
	    printf("Car %d arrives at time %8.6f\n", arrivals, now);
#endif

	    /* Update and/or report the current queue size */
	    meanqueue += (now - last)*qsize;
	    last = now;
	    qsize++;
#ifdef DEBUG
	    printf("Lineup at booth now has %d cars!\n", qsize);
#endif
	    if( qsize > maxq )
	      maxq = qsize;

	    /* schedule departure event, if queue was empty before */
	    if( qsize == 1 )
	      {
		frontcar = arrivals;
		nextdeparture = now + servicetimes[frontcar];
#ifdef DEBUG
		printf("Car %d will be completing service at time %8.6f\n",
		       frontcar, nextdeparture);
#endif
	      }

	    /* schedule next arrival, if any */
	    arrivals++;
	    if( arrivals < NUM_CARS )
	      nextarrival = arrivaltimes[arrivals];
	    else nextarrival = END_OF_TIME;
	  }
	else   /* departure */
	  {
#ifdef DEBUG
	    printf("Next event is service completion for car %d at time %8.6f\n",
		   frontcar, nextdeparture);
#endif
	    now = nextdeparture;
	    sojourntimes[frontcar] = now - arrivaltimes[frontcar];
	    waittimes[frontcar] = sojourntimes[frontcar] - servicetimes[frontcar];
	    departures++;
	    meanqueue += (now - last)*qsize;
	    last = now;
	    qsize--;
#ifdef DEBUG
	    printf("Lineup at booth now has %d cars\n", qsize);
#endif
	    if( qsize > 0 )
	      {
		frontcar = departures;
		nextdeparture = now + servicetimes[frontcar];
#ifdef DEBUG
		printf("Front car %d has service time %8.6f departure %8.6f\n",
		       frontcar, servicetimes[frontcar], nextdeparture);
#endif
	      }
	    else
	      {
		nextdeparture = END_OF_TIME;
	      }
	  }
      }

    printf("\n");
    printf("Banff Park Entry Simulation Model:\n");
    printf("Number of cars: %d\n", NUM_CARS);
    printf("Time: %8.6f  Arrivals: %d  Departures: %d  Queue: %d\n",
	   now, arrivals, departures, qsize);
    printf("Mean queue size: %5.3f\n", meanqueue/now);
    printf("Maximum queue size observed: %d\n", maxq);

#ifdef DEBUG
    /* print detailed report */
    printf(" Car    Arrival     Wait        Service     Sojourn\n");
    for( i = 0; i < NUM_CARS; i++ )
      {
	printf(" %3d  %10.6f  %10.6f  %10.6f  %10.6f\n",
	       i, arrivaltimes[i], waittimes[i],
	       servicetimes[i], sojourntimes[i]);
      }
#endif
    
    /* calculate and report statistics */
    meanwait = 0.0;
    for( i = 0; i < NUM_CARS; i++ )
      meanwait += waittimes[i];
    meanwait /= NUM_CARS;
    varwait = 0.0;
    for( i = 0; i < NUM_CARS; i++ )
      varwait += (waittimes[i] - meanwait)*(waittimes[i] - meanwait);
    varwait /= NUM_CARS;
    stdwait = sqrt(varwait);
    printf("Mean wait time: %8.6f\n", meanwait);
    printf("Standard deviation of wait time: %8.6f\n", stdwait);
  }