/* program ssq.c */

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>

#define NEW(type) (type *) malloc(sizeof(type))
#define ARRIVAL 1
#define DEPARTURE 2

/* Event by event simulation of a single server queue with infinite waiting
   room */


int
  gmt,     /* absolute time */
  q,       /* number of customers in the system */
  narr,    /* number of arrivals */
  q_sum,   /* sum of queue lengths at arrival instants */ 
  iat,    /* mean interarrival time */
  service_time,     /* mean holding time */
  total_events;      /* number of events to be simulated */

unsigned int
  seed;   /* seed for the random number generator */

typedef struct schedule_info{
  int time;                          /* Time that event occurs */
  int event_type;                    /* Type of event */
  struct schedule_info *next;        /* Pointer to next item in linked list */
  } EVENTLIST;

struct schedule_info
  *head,
  *tail;

int  act(void);
int  negexp(int);
void arrival(void);
void departure(void);
void schedule(int, int);
void sim_init(void);

/**************************************************************************/
main(){

  sim_init();


  while (narr < total_events){
    switch (act()){
      case ARRIVAL:
        arrival();
        break;
      case DEPARTURE:
        departure();
        break;
      default:
        printf("error in act procedure\n");
        exit(1);
        break;
      } /* end switch */
  }      /* end while */
  printf("The mean queue length seen by arriving customers is: %8.4f\n",
         ((float) q_sum) / narr);

  return(0);

} /* end main */
/**************************************************************************/
int negexp(int mean) /* returns a negexp rv with mean `mean' */

{
return ( (int)(- log((float) rand() / RAND_MAX) * mean + 0.5) );
}

/**************************************************************************/
void arrival() /* a customer arrives */

{
  narr += 1;                /* keep tally of number of arrivals */
  q_sum += q;
  schedule(negexp(iat), ARRIVAL); /* schedule the next arrival */
  q += 1;
  if (q == 1)
    schedule(negexp(service_time), DEPARTURE);
}

/**************************************************************************/
void departure()  /* a customer departs */

{
  q -= 1;
  if (q > 0)
    schedule(negexp(service_time), DEPARTURE);
}

/**************************************************************************/


/**************************************************************************/
void schedule(int time_interval, int event)  /* Schedules an event of type */
                                             /* 'event' at time 'time_interval' 
                                                 in the future */

{
int 
  event_time;

struct schedule_info
  *x,
  *t;

event_time = gmt + time_interval;
t = NEW(EVENTLIST);
for(x=head ; x->next->time<event_time && x->next!=tail ; x=x->next);
t->time = event_time;
t->event_type = event;
t->next = x->next;
x->next = t;
}
/**************************************************************************/
int act()    /* find the next event  and go to it */
{
int 
  type;
struct schedule_info 
  *x;

gmt = head->next->time; /* step time forward to the next event */
type = head->next->event_type; /*  Record type of this next event */
x = head->next;                 /* Delete event from linked list */
head->next = head->next->next;
free(x);
return type; /* return value is type of the next event */
}
/*************************************************************************/
/**************************************************************************/
void sim_init()
/* initialise the simulation */

{ 
  printf("\nenter the mean interarrival time and the mean holding time\n");
  scanf("%d%d", &iat, &service_time);
  printf("enter the total number of customers to be simulated\n");
  scanf("%d", &total_events);
  printf("enter the seed\n");
  scanf("%ld", &seed);
  srand(seed);

  head = NEW(EVENTLIST);
  tail = NEW(EVENTLIST);
  head->next = tail;
  tail->next = tail;

  q = 0;
  narr = 0;
  q_sum = 0;
  schedule(negexp(iat), ARRIVAL); /* schedule the first arrival */
}
/**************************************************************************/