/* Sample solution for CPSC 441 Assignment 3      */
/* Written by Carey Williamson, February 26, 2001 */
/* Modified by Carey Williamson, January 10, 2012 */
/* Usage: cc -o route route.c                     */
/*        ./route                                 */
/* Requires two input files:                      */
/*        topology.txt   (network topology)       */
/*        trips.txt      (trip destinations)      */

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

/* Network topology and simulation info */
#define MAX_ROW 100
#define MAX_COL 100
#define MAX_EVENTS 20000
#define INFINITY 999999
#define BUSY     888888
#define BIGGIE   100
#define PRETTY 1

/* Call event types */
#define CALL_ARRIVAL 1
#define CALL_DEPARTURE 2

/* Routing algorithms */
#define SHORTEST_HOP_PATH 1
/* #define SHORTEST_DISTANCE_PATH 1 */
/* #define SHORTEST_TIME_PATH 1 */
/* #define LEAST_COST_PATH 1 */
/* #define MAX_TIMMIES_PATH 1 */

#define NEW 1

/* Debugging flags */
/* #define DEBUG 1 */
/* #define DEBUG2 1 */

/* Global data structures for network topology and state information */
float distance[MAX_ROW][MAX_COL];
float propdelay[MAX_ROW][MAX_COL];
float timmies[MAX_ROW][MAX_COL];
int capacity[MAX_ROW][MAX_COL];
int available[MAX_ROW][MAX_COL];
float cost[MAX_ROW][MAX_COL];
float mincost[MAX_ROW][MAX_COL];
int route[MAX_ROW];
int routes[MAX_EVENTS][MAX_ROW];
int hops[MAX_EVENTS];

int numnodes, numlinks, numevents, numhops;
int calls, success, blocked;
int tothops;
float pathdelay, totdelay;
int depth;
int bigpath[MAX_ROW];

FILE *fp1, *fp2;

struct Event
  {
    float event_time;
    int event_type;
    int tripid;
    int source;
    int destination;
    float duration;
  } EventList[MAX_EVENTS];

extern void qsort();

int mycompare(num1, num2)
     float *num1;
     float *num2;
{
  if( *num1 < *num2 )
    return( -1);
  else if( *num1 > *num2 )
    return( 1);
  else return(0);
}

float DoDijkstra(from, to)
    int from, to;
  {
    int donewith[MAX_ROW];
    int numdonewith, node, node2;
    int bywayof[MAX_ROW];
    int i, j, closestnode, done;
    float closestdistance;
    float howfar[MAX_ROW];
    float okay;
    float fix;

#ifdef DEBUG
    printf("DoDijkstra: trying to route from %c to %c\n", from+'A', to+'A');
#endif

    numdonewith = 0;
    donewith[numdonewith] = from;
    numdonewith++;
    for( i = 0; i < numnodes; i++ )
      {
	if( i == from )
	  continue;
#ifdef NEW
	if( cost[from][i] == BUSY )
	  {
#ifdef DEBUG2
	    printf("  Link from source %d to %d is already in use\n",
		   from, i);
#endif
	    howfar[i] = INFINITY;
	  }
	else 
#endif
	  if( cost[from][i] < INFINITY )
	  {
	    howfar[i] = cost[from][i];
	    bywayof[i] = from;
#ifdef DEBUG2
	    printf("  Node %c is directly reachable from %c in %f\n",
		   i+'A', from+'A', howfar[i]);
#endif
	  }
	else howfar[i] = INFINITY;
      }

    while( numdonewith < numnodes )
      {
	/* Find the node closest to source (from) that is */
	/* not yet in the done with set */
	closestdistance = INFINITY;
	closestnode = -1;
	for( i = 0; i < numnodes; i++ )
	  {
	    if( i == from )
	      continue;
	    /* make sure that it is not yet in the donewith set */
	    done = 0;
	    for( j = 0; j < numdonewith; j++ )
	      {
		if( donewith[j] == i )
		    done = 1;
	      }
	    if( done )
	      continue;
	    if( howfar[i] < closestdistance )
	      {
		closestdistance = howfar[i];
		closestnode = i;
	      }
	  }
	if( closestdistance >= BUSY )
	  return( 0 );

	if( closestnode < 0 )
	  {
	    printf("Problem!\n");
	  }
#ifdef DEBUG2
	printf("  Chose %c as the closest node not yet done with\n",
	       closestnode+'A');
#endif
	/* Put this node into the donewith set */
	donewith[numdonewith] = closestnode;
	numdonewith++;
#define HACK 1
#ifdef HACK
	if( closestnode == to )
	  break;
#endif

	/* Update distances, if necessary */
	for( i = 0; i < numnodes; i++ )
	  {
	    /* Find an adjacent node... */
	    if( cost[closestnode][i] == INFINITY )
	      continue;
#ifdef NEW
	    if( cost[closestnode][i] == BUSY )
#endif
	      {
#ifdef DEBUG2
		printf("  Link from %d to %d is already in use\n",
		       closestnode, i);
#endif
		continue;
	      }

	    /* that is not yet in the donewith set */
	    done = 0;
	    for( j = 0; j < numdonewith; j++ )
	      {
		if( donewith[j] == i )
		    done = 1;
	      }
	    if( done )
	      continue;

	    if( howfar[closestnode] + cost[closestnode][i] < howfar[i] )
	      {
		howfar[i] = howfar[closestnode] + cost[closestnode][i];
		bywayof[i] = closestnode;
#ifdef DEBUG2
		printf("Dijkstra chooses to route from %d to %d via %d\n",
		       from, i, closestnode);
#endif
	      }
	  }
      }
    /* Now record the route to use */
#ifdef DEBUG2
    printf("For source node %c, the routes are as follows: \n", from+'A');
    for( i = 0; i < numnodes; i++ )
      {
	if( howfar[i] < INFINITY )
	  {
	    if( i == from-'A' )
	      continue;
	    printf("  Destination %c is reachable in %f by way of %c\n",
		   i+'A', howfar[i], 'A'+bywayof[i]);
	  }
      }
#endif

    numhops = 0;
    pathdelay = 0.0;
    node = to;
    route[numhops] = node;
    numhops++;
    okay = 0;
    while( node != from )
      {
	node2 = bywayof[node];
	route[numhops] = node2;
	if( available[node][node2] <= 0 )
	  {
	    okay = 0;
	    /* 	    printf("%d %d  ", node, node2); */
	  }
	else okay += cost[node][node2];

	pathdelay += propdelay[node][node2];
	node = node2;
	numhops++;
      }
#ifdef DEBUG
    printf("Route to use is: ");
    for( i = numhops-1; i >= 0; i-- )
      {
	printf(" %c ", 'A' + route[i]);
      }
    printf("\n");
#endif
#ifdef PRETTY
    int prev, next;
    float minutes, km, tims;

    printf("%c     ", to+'A');
    minutes = 0;
    km = 0;
    tims = 0;
    prev = from;
    for( i = numhops-1; i >= 0; i-- )
      {
	next = route[i];
	printf(" %c ", 'A' + route[i]);
	minutes += propdelay[prev][next];
	km += distance[prev][next];
	tims += capacity[prev][next];
	prev = route[i];
      }
    for( i = numhops; i < 6; i++ )
      printf("   ");
    printf("%1d   %4.0f   %4.0f   %4.0f\n", numhops-1, km, minutes, tims);
#endif
    return( okay );
  }

float CheckThemAll(from, to)
    int from, to;
  {
    int i, bestchoice;
    float howfar[MAX_ROW];
    int bywayof[MAX_ROW];
    float bestsofar, answer, saver;

#ifdef DEBUG
    printf("CheckThemAll (%d): routing from %c to %c\n",
	   depth, from+'A', to+'A');
#endif

    if( from == to )
      {
	printf("Candidate path: ");
	for( i = 0; i < depth; i++ )
	  printf("%c", bigpath[i]+'A');
	printf("\n");
      }

#ifdef PRETTY
    if( from == to )
      {
	int prev, next;
	float minutes, km, tims;

	printf("%c     ", to+'A');
	minutes = 0;
	km = 0;
	tims = 0;
	prev = 'C' - 'A';
	for( i = 0; i < depth; i++ )
	  {
	    if( i == 0 )
	      printf(" %c ", prev+'A');
	    next = bigpath[i];
	    printf(" %c ", bigpath[i]+'A');
	    minutes += propdelay[prev][next];
	    km += distance[prev][next];
	    tims += capacity[prev][next];
	    prev = bigpath[i];
	  }
	for( i = depth; i < 9; i++ )
	  printf("   ");
	printf("%1d   %4.0f   %4.0f   %4.0f\n", depth, km, minutes, tims);
      }
#endif

    bestsofar = 0.0;
    bestchoice = -1;

    /* try every possible adjacent link that is not yet used */
    for( i = 0; i < numnodes; i++ )
      {
	if( i == from )
	  continue;
	if( cost[from][i] == INFINITY )
	  {
#ifdef DEBUG2
	    printf("  No link from %c to %c\n", from+'A', i+'A');
#endif
	    continue;
	  }
	if( available[from][i] == 0 )
	  {
#ifdef DEBUG2
	    printf("  Link from %c to %c is already in use\n",
		   from+'A', i+'A');
#endif
	    continue;
	  }
#ifdef DEBUG2
	printf("CheckThemAll (%d): trying node %c reachable from %c in %f\n",
	       depth, i+'A', from+'A', cost[from][i]);
#endif
	available[from][i]--;
	available[i][from]--;
	bigpath[depth] = i;
	depth++;
	answer = CheckThemAll(i, to);
#ifdef DEBUG2
	printf("  Answer via %c is %f\n", i+'A', answer);
#endif
	if( (answer < 0) || (i == to) )
	  {
	    answer += cost[from][i];
	  }
	available[from][i]++;
	available[i][from]++;
	depth--;

	if( answer < bestsofar )
	  {
	    bestsofar = answer;
	    bestchoice = i;
#ifdef DEBUG2
	    printf("CheckThemAll (%d): updating %c's bestchoice to be %c bestsofar %f\n",
		   depth, from+'A', i+'A', answer);
#endif
	  }
      }

#ifdef DEBUG2
    printf("CheckThemAll (%d): Returning answer of %f\n",
	   depth, bestsofar);
#endif
    return( bestsofar );
  }

RouteTrip(from, to, tripid)
    int from, to;
    int tripid;
  {
    int i;
    float totalcost;

#ifdef DEBUG
    printf("RouteTrip: trying to route trip %d from %c to %c\n",
	   tripid, from+'A', to+'A');
#endif

    if( from == to )
      {
	printf("RouteTrip: identical source and destination!\n");
	return(1);
      }

#ifdef MAX_TIMMIES_PATH
    totalcost = -CheckThemAll(from, to);
#else
    totalcost = DoDijkstra(from, to);
#endif

    if( totalcost > 0 )
      {
#ifdef DEBUG
	printf("Using a path of cost %4.3f\n", totalcost);
#endif
	/* Record the route for future reference */
	for( i = numhops-1; i >= 0; i-- )
	  {
	    routes[tripid][i] = route[i];
	    hops[tripid] = numhops;
	  }
	/* Record the existence of this call consuming resources */
	for( i = numhops-1; i >= 0; i-- )
	  {
	    int node1, node2;
	    node1 = route[i];
	    if( i > 0 )
	      {
		float temp;
		node2 = route[i-1];
		available[node1][node2] -= 1;
		available[node2][node1] -= 1;
#ifdef NEW
		if( available[node2][node1] == 0 )
		  {
		    cost[node2][node1] = BUSY;
		    cost[node1][node2] = BUSY;
		  }
#endif
	      }
	  }
	return(1);
      }
    else return(0);
  }

ReleaseCall(from, to, tripid)
    int from, to;
    int tripid;
  {
    int i;
    numhops = hops[tripid];
    for( i = numhops-1; i >= 0; i-- )
      {
	int node1, node2;
	node1 = routes[tripid][i];
	if( i > 0 )
	  {
	    float temp;
	    node2 = routes[tripid][i-1];
	    available[node1][node2] += 1;
	    available[node2][node1] += 1;
#ifdef NEW
	    if( available[node2][node1] == 1 )
	      {
#ifdef SHORTEST_HOP_PATH
		cost[node2][node1] = 1;
		cost[node1][node2] = 1;
#endif
#ifdef SHORTEST_DISTANCE_PATH
		cost[node2][node1] = distance[node2][node1];
		cost[node1][node2] = distance[node1][node2];
#endif
#ifdef SHORTEST_TIME_PATH
		cost[node2][node1] = propdelay[node2][node1];
		cost[node1][node2] = propdelay[node1][node2];
#endif
#ifdef LEAST_COST_PATH
		cost[node2][node1] = timmies[node2][node1];
		cost[node1][node2] = timmies[node1][node2];
#endif
#ifdef MAX_TIMMIES_PATH
		cost[node2][node1] = -timmies[node2][node1];
		cost[node1][node2] = -timmies[node1][node2];
#endif
	      }
#endif
	  }
      }
  }

main()
  {
    int row, col, i, j, tripid, type, current_event;
    int delay, dist;
    int cap;
    int src, dst;
    char source, dest;
    float start, duration;
    
    fp1 = fopen("topology.txt", "r");
    if( fp1 == NULL )
      {
	fprintf(stderr, "Unable to open file topology.txt!\n");
	exit(1);
      }
    for( i = 0; i < MAX_ROW; i++ )
      for( j = 0; j < MAX_ROW; j++ )
	if( i == j )
	  cost[i][j] = 0;
	else cost[i][j] = INFINITY;
    for( i = 0; i < MAX_EVENTS; i++ )
      EventList[i].event_time = INFINITY;

    calls = 0;
    success = 0;
    blocked = 0;
    tothops = 0;
    totdelay = 0.0;
    numnodes = 0;
    numlinks = 0;
    while( (i = fscanf(fp1, "%c %c %d %d %d\n", &source, &dest, &dist, &delay, &cap)) == 5 )
      {
	float temp;
	src = source - 'A';
	dst = dest - 'A';
	row = src;
	col = dst;
	if( row > MAX_ROW )
	  {
	    printf("Too many rows to index!!\n");
	    exit(0);
	  }
	if( row >= numnodes )
	  numnodes = row + 1;
	if( col >= numnodes )
	  numnodes = col + 1;

	propdelay[row][col] = delay;
	propdelay[col][row] = delay;
	distance[row][col] = dist;
	distance[col][row] = dist;
	capacity[row][col] = cap;
	capacity[col][row] = cap;
	available[row][col] = cap;
	available[col][row] = cap;
#ifdef SHORTEST_HOP_PATH
	cost[row][col] = 1;
	cost[col][row] = 1;
#endif
#ifdef SHORTEST_DISTANCE_PATH
	cost[row][col] = dist;
	cost[col][row] = dist;
#endif
#ifdef SHORTEST_TIME_PATH
	cost[row][col] = delay;
	cost[col][row] = delay;
#endif
#ifdef LEAST_COST_PATH
	cost[row][col] = cap;
	cost[col][row] = cap;
#endif
#ifdef MAX_TIMMIES_PATH
	cost[row][col] = -cap;
	cost[col][row] = -cap;
	available[row][col] = 1;
	available[col][row] = 1;
#endif
	numlinks++;
      }
    fclose(fp1);

#ifdef DEBUG
    printf("Read in a total of %d links\n", numlinks);
#endif

    fp2 = fopen("trips.txt", "r");
    if( fp2 == NULL )
      {
	fprintf(stderr, "Unable to open file trips.txt!\n");
	exit(1);
      }

    /* Process the call workload file */
    numevents = 0;
    tripid = 0;
    while( (i = fscanf(fp2, "%f %c %c %f\n", &start, &source, &dest, &duration)) == 4 )
      {
	src = source - 'A';
	dst = dest - 'A';
#ifdef DEBUG
	printf("Trip %d from %c to %c starts at %8.6f lasts %8.6f\n",
	       tripid, source, dest, start, duration);
#endif

	/* Enter this call arrival into the event list */
	EventList[numevents].event_type = CALL_ARRIVAL;
	EventList[numevents].event_time = start;
	EventList[numevents].source = src;
	EventList[numevents].destination = dst;
	EventList[numevents].tripid = tripid;
	EventList[numevents].duration = duration;
	numevents++;
	if( numevents == MAX_EVENTS )
	  {
	    printf("Ooops! Too many events to handle. Quitting.\n");
	    exit(0);
	  }

	tripid++;
	calls++;
      }
    fclose(fp2);

#ifdef PRETTY
    printf("Dest          Route              Hops   Dist  Time  Timmies\n");
    printf("-----------------------------------------------------------\n");
#endif


    /* Now simulate the call arrivals and departures */
    current_event = 0;
    depth = 0;
    while( numevents > 0 )
      {
	numevents--;

	/* Get information about the current event */
	type = EventList[current_event].event_type;
	start = EventList[current_event].event_time;
	src = EventList[current_event].source;
	dst = EventList[current_event].destination;
	tripid = EventList[current_event].tripid;
	duration = EventList[current_event].duration;

#ifdef DEBUG
	printf("Event of type %d at time %8.6f (call %d from %c to %c)\n",
	       type, start, tripid, source, dest);
#endif

	if( type == CALL_ARRIVAL )
	  {
	    if( RouteTrip(src, dst, tripid) > 0 )
	      {
#ifdef DEBUG
		printf("Trip succeeded!\n");
#endif
		success++;
		tothops += numhops - 1;
		totdelay += pathdelay;

		/* Enter this call completion into the event list */
		EventList[current_event].event_type = CALL_DEPARTURE;
		EventList[current_event].event_time = start + duration;
		EventList[current_event].tripid = tripid;
		EventList[current_event].source = src;
		EventList[current_event].destination = dst;
		EventList[current_event].duration = 0;
		numevents++;
		if( numevents == MAX_EVENTS )
		  {
		    printf("Ooops! Too many events to handle. Tired. Quitting.\n");
		    exit(0);
		  }

		/* sort the event list by time */
		qsort(EventList, MAX_EVENTS, sizeof(struct Event), mycompare);
	      }
	    else
	      {
#ifdef DEBUG
		printf("Trip blocked!\n");
printf("Blocked trip %d from %c to %c at time %4.3f\n", tripid, src+'A', dst+'A', start);
#endif
printf("Blocked trip %d from %c to %c at time %4.3f\n", tripid, src+'A', dst+'A', start);
                blocked++;
		current_event++;
	      }
	  }
	else if( type == CALL_DEPARTURE )
	  {
	    ReleaseCall(src, dst, tripid);
	    current_event++;
	  }
	else
	  {
	    printf("Unknown event type %d\n", type);
	    current_event++;
	  }
      }
#ifdef SUMMARY
    printf("Total trips: %d\n", calls);
    printf("Mean hops per successful trip: %4.2f\n",
	   (float) 1.0 * tothops/success);
    printf("Mean cost per successful trip: %3.1f\n",
	   (float) 1.0 * totdelay/success);
#endif
  }