/* Solution: Wait in Line You Must */
/* E. Jason Riedy, ejr@cise.ufl.edu */
/*
  This is a completely standard queue simulation.  Each event is
  either permanently removed (ServiceEnds) or turned into a
  ServiceEnds event and re-inserted into the queue.  The head
  is always the next event, and thus defines the current time.
*/

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

enum { NIL = -1, MAX_PAIRS = 20, MAX_SERVERS = 10,
       MAX_EVENTS = MAX_PAIRS + MAX_SERVERS };

typedef enum { Arrival, ServiceEnds } event_type;

struct _event {
  event_type type;
  float time;
  int next;

  float service_time;
  float arrival_time;
};

typedef struct _event event;

/*
  Yeah, globals are supposedly bad.  Small simulations have so much
  state involved that you really don't lose much.  Of course, if you
  had multiple queues, each would need wrapped in a separate data
  structure...
*/
event Q[MAX_EVENTS];
int headQ = NIL;
int headL = NIL;
int tailL = NIL;
int num_servers;

/*
  The current time is global by its very nature...
*/
float time;

/*
  and so are the statistics...
*/
float line_length = 0.0;
float line_last_mod = 0.0;
float line_length_tot = 0.0;

float number_served = 0.0;
float total_wait_time = 0.0;

void insert_event( int which )
{
  int curr = headQ;
  int prev = NIL;

  if (NIL == curr) {
    Q[which].next = NIL;
    headQ = which;
    return;
  };

  /* Make sure the queue stays sorted... */
  while (curr != NIL && Q[curr].time <= Q[which].time) {
    prev = curr;
    curr = Q[curr].next;
  }

  Q[which].next = curr;
  if (NIL == prev)
    headQ = which;
  else
    Q[prev].next = which;

  /*
  printf("     >>> Inserted %d between %d and %d\n", which, prev, curr);
  /**/
}

int pop_event( )
{
  int out;
  
  out = headQ;
  if (NIL != out)
    headQ = Q[out].next;
  return out;
}

void add_line( int which )
{
  /* Update the statistics... */
  line_length_tot += (time - line_last_mod) * line_length;
  line_length += 1.0;
  line_last_mod = time;
  
  /* then send the fool to the line. */
  Q[which].next = NIL;

  if (NIL == tailL) {
    headL = tailL = which;
    return;
  }

  Q[tailL].next = which;
  tailL = which;
}

int pop_line( )
{
  int out;

  out = headL;
  if (NIL != out) {
    headL = Q[out].next;
    if (NIL == headL)
      tailL = NIL;

    /* The line has been modified, so update the stats again. */
    line_length_tot += (time - line_last_mod) * line_length;
    line_length -= 1.0;
    line_last_mod = time;
  }

  return out;
}

void handle_Arrival( int which )
{
  /*
  printf("Handling an arrival at %g, service time %g.\n", time,
	 Q[which].service_time);
  /**/

  Q[which].arrival_time = time;

  if (num_servers > 0) {
    num_servers--;

    number_served += 1.0;
    /* No wait time */
    
    Q[which].type = ServiceEnds;
    Q[which].time += Q[which].service_time;
    insert_event( which );

    /*
    printf(" -- taking up a server, leaving %d, will leave at %g...\n",
	   num_servers, Q[which].time);
   /**/

  }
  else {
    add_line(which);

    /*
    printf(" -- going to line...\n");
    /**/
  }
}

void handle_ServiceEnds( int which )
{
  int i;

  /*
  printf("Handling a service end at %g.\n", time);
  /**/

  if (NIL == tailL) {
    num_servers++;

    /*
    printf(" -- Freed server...\n");
    /**/
  }
  else {
    i = pop_line();

    /* One more served, so fix this stat... */
    number_served += 1.0;
    total_wait_time += time - Q[i].arrival_time;
    
    Q[i].time = time + Q[i].service_time;
    Q[i].type = ServiceEnds;
    insert_event(i);

    /*
    printf(" -- Now serving %d, will finish at %g.\n", i,
	   Q[i].time);
    /**/
  }
}

void run_Q(void)
{
  int which;

  while (NIL != headQ) {
    which = pop_event();
    time = Q[which].time;

    switch (Q[which].type) {
      case Arrival:
	handle_Arrival(which);
	break;
      case ServiceEnds:
	handle_ServiceEnds(which);
	break;
      default:
	fprintf(stderr, "Illegal event type, %d, at time %g.\n",
		Q[which].type, time);
    }
  }
}

void read_arrivals(void)
{
  float inter_arrival, service;
  float time = 0.0;
  int i = 0;
  
  printf("Inter-arrival and service times: ");
  scanf("%g %g", &inter_arrival, &service);
  
  while (inter_arrival != 0 || service != 0) {
    time += inter_arrival;
    Q[i].time = time;
    Q[i].service_time = service;
    Q[i].next = i+1;
    i++;
    
    printf("Inter-arrival and service times: ");
    scanf("%g %g", &inter_arrival, &service);
  }
  Q[i-1].next = NIL;
  headQ = 0;
}

void main(void)
{
  printf("Number of servers: ");
  scanf("%d", &num_servers);
  read_arrivals();

  run_Q();

  printf("\nThe line's average length was %.2f, and people generally\n"
	 "waited %.2f minutes before being served.\n",
	 line_length_tot / time,
	 total_wait_time / number_served);
}