// Simplified solution to assignment 2, after stripping out all the
// stuff related to complicated graphs and shortest path calculations,
// leaving a pgm that is (just barely) capable of handling assignment 3.
//
// Original program was written by D. Berger, with many unnecessary 
// features removed and one small bug fix added by M. Molle.
//
// This is a second generation of the program, to fix the bug in
// Molle's bug fix (correction for interference by reverse travellers
// moved to the right place, so it doesn't increase quadratically),
// and to make better use of CSIM's built-in statistics gathering tools
// like meters and boxes

#include <stdexcept>
#include <iostream>
#include <sstream>
#include <cassert>
#include <fstream>
#include <vector>
#include <utility>

#include <stdio.h>      /* FILE *     */
#include <unistd.h>     /* getopt     */
#include <values.h>     /* MAXINT     */

#include "cpp.h"

using namespace std;

static const int BUF_SIZE=512;

static const int PERSON_WIDTH=3;          // fat people

// magic conversion from MPH to FPS, courtesy of units(1)
static const double MPH2FPS=1.4666667;
static const double MIN_WALK_FPS=2.0*MPH2FPS;
static const double MAX_WALK_FPS=4.0*MPH2FPS;

static const int EXIT_DELAY=3;            // time spent in the exit storage
static const int UPSTREAM_DELAY=3;        // time spent swimming upstream
static const int PER_TRAVELER_DELAY=2;    // time between two travelers
static const int XROADS_CAPACITY=50;      // how many people can mill about?
static const int XROADS_BASE_DELAY=20;    // we spend at least this long...
static const double XROADS_CROWD_DELAY=0.5;    // + per person at the crossroads

static const double TINY_DELAY=1.e-20;    // just a jiffy

double duration;                          // how long does the simulation last?

static int pedestrianNum = 0;

struct vertex {
  vertex(): seqno(0), x(0.0), y(0.0), ep(false), crossroad(NULL), name(""){ }
  unsigned int seqno;
  double x,y;
  bool ep;
  storage *crossroad;
  string name;
};

struct edge {
  edge(): start(0), end(0), width(0.0), length(0.0), speed(0.0), entranceGate(NULL),
   InTransit(NULL), exit(NULL), pedestrianExitCount(NULL), mirror(NULL),
   lastExitTime(0.0), name("") { }
  unsigned int start, end;
  // speed is in fps
  double width, length, speed;
  facility *entranceGate;
  box *InTransit;
  storage *exit;
  meter *pedestrianExitCount;
  edge * mirror;
  double lastExitTime;
  string name;
  };

vertex vertices [2];	// only two endpoints allowed

edge edges [1];		// only one existing path allowed
edge reverse_edges [1];		// but it runs both ways!

edge sidewalks[1];	// at most one moving sidewalk allowed
int sidewalk_count = 0;	// and so far we have not seen any....

double rates[2][2];	// traffic rate "matrix" is only 2x2

void usage(char *name) {
  cerr << "usage: " << name 
       << " -m mapFile -t trafficFile -o outFile -d duration " 
       << endl;
}

/* 
 * 
 * handle reading/parsing the vertex/edge/sidewalk input file.
 * 
 */
void readVertices(ifstream &inf) {
  // first line is the number of vertices
  // subsequent lines are of the form:
  // seqno        x       y       endpoint?[Y/N]  name
  char buf[BUF_SIZE];     
  string word;
  char tc;
  int num;

  // handle the first line
  inf.getline(buf, BUF_SIZE);
  stringstream ss(buf);
  ss >> num;
  if (num != 2) {
	cerr << "this program only supports one pair of endpoints \n";
	assert(false);
  }

  // handle the remaining lines
  for (int i = 0; i < num; ++i) {
    inf.getline(buf, BUF_SIZE);
    stringstream ss(buf);
    ss >> vertices[i].seqno;
    ss >> vertices[i].x;
    ss >> vertices[i].y;
    ss >> tc;
    // put the rest of the line into name
    ss >> vertices[i].name;
    while (ss >> word) {
      vertices[i].name += " " + word;
    }
    if (tc == 'Y' || tc == 'y') {
      vertices[i].ep = true;
      vertices[i].crossroad = new storage(vertices[i].name.data(),
                                          XROADS_CAPACITY);
    } else {
    } 
  }
}

void readEdges(ifstream &inf) {
  // first line is the number of edges
  // subsequent lines are of the form:
  // initial_vertex       final_vertex    width   length
  char buf[BUF_SIZE];     
  int num;

  // handle the first line
  inf.getline(buf, BUF_SIZE);
  stringstream ss(buf);
  ss >> num;
  if (num != 1) {
	cerr << "this program only supports one existing path \n";
	assert(false);
  }

  // handle the remaining lines
  for (int i = 0; i < num; ++i) {
    // remember that the input file only gives info for one direction
    // even though the existing paths are bi-directional by definition.

    inf.getline(buf, BUF_SIZE);
    stringstream ss(buf);

    // set starting vertex
    ss >> edges[i].start;
    reverse_edges[i].end = edges[i].start;

    // set ending vertex
    ss >> edges[i].end;
    reverse_edges[i].start = edges[i].end;

    // set path width
    ss >> edges[i].width;
    reverse_edges[i].width = edges[i].width;

    // set path name
    stringstream s("");

    s << edges[i].start << " path " << edges[i].end;
    edges[i].name = s.str();

    s.str("");
    s << reverse_edges[i].start << " path " << reverse_edges[i].end;
    reverse_edges[i].name = s.str();

    // create an entrance facility to serialize travel time calculations
    // for this path.  Note that we spend zero (simulated) time inside
    // this object so it is *extremely* unlikely that two pedestrians
    // will enter the path from opposite ends at the same time and try
    // to read and update their shared state info at the same time.
    // However, since this is just simulated concurrency on a uniprocessor
    // we don't need to worry about an error caused by some sort of race
    // conditions. Even in the worst case, everything would be great as
    // long as individual CSIM statements such as entering/leaving a 
    // facility or passing a meter are treated as "atomic" operations.

    edges[i].entranceGate = new facility(edges[i].name.data());
    reverse_edges[i].entranceGate =  new facility(reverse_edges[i].name.data());

    // for extra fun, make a box to track time spent along the path

    edges[i].InTransit = new box(edges[i].name.data());
    reverse_edges[i].InTransit = new box(reverse_edges[i].name.data());

    // create exit storages for each direction
    long int people = (long) floor(edges[i].width/PERSON_WIDTH);
    edges[i].exit = new storage(edges[i].name.data(), people);
    reverse_edges[i].exit = new storage(reverse_edges[i].name.data(), people);

    ss >> edges[i].length;
    reverse_edges[i].length = edges[i].length;

    // we could check that the length given is at least as long as Euclidean distance
 
    // create meters to count pedestrian departures for both directions
    // (input facility already lets us track pedestrian arrivals)
    
    edges[i].pedestrianExitCount = new meter(edges[i].name.data());
    reverse_edges[i].pedestrianExitCount = new meter(reverse_edges[i].name.data());

    // finally, link up the two paths so we can find the reverse statistics
    edges[i].mirror = &reverse_edges[i];
    reverse_edges[i].mirror = &edges[i];
  }
}

void readSidewalks(ifstream &inf) {
  // first line is the number of sidewalks
  // subsequent lines are of the form:
  // initial_vertex       final_vertex    width   length  speed
  char buf[BUF_SIZE];     
  int num;

  // handle the first line
  inf.getline(buf, BUF_SIZE);
  stringstream ss(buf);
  ss >> sidewalk_count;
  if (sidewalk_count > 1) {
	cerr << "this program supports at most one moving sidewalk \n";
	assert(false);
  }


  // handle the remaining lines
  for (int i = 0; i < sidewalk_count; ++i) {
    inf.getline(buf, BUF_SIZE);
    stringstream ss(buf);
    ss >> sidewalks[i].start;
    ss >> sidewalks[i].end;
    ss >> sidewalks[i].width;
    ss >> sidewalks[i].length;
    ss >> sidewalks[i].speed;
    sidewalks[i].speed *= MPH2FPS;
    stringstream s("");
    s << sidewalks[i].start << " move " << sidewalks[i].end;
    sidewalks[i].name = s.str();
    
    // create the usual set of CSIM statistics gathering tools...
    sidewalks[i].entranceGate = new facility(sidewalks[i].name.data());
    sidewalks[i].InTransit = new box(sidewalks[i].name.data());
    sidewalks[i].pedestrianExitCount = new meter(sidewalks[i].name.data());
    sidewalks[i].exit = new storage(sidewalks[i].name.data(), 
                                    (long)floor(edges[i].width/PERSON_WIDTH));
  }
}

void readMap(char *fname) {
  ifstream mapf;
  mapf.open(fname);
  if (! mapf.good()) {
    invalid_argument e("error opening map file (" + string(fname) 
                       + ") for input");
    throw e;
  }
  readVertices(mapf);
  readEdges(mapf);
  readSidewalks(mapf);
}

/*
 * 
 * read/parse the traffic matrix
 * 
 */
 
void readTraffic(char *fname) {
  ifstream traf;
  traf.open(fname);
  if (! traf.good()) {
    invalid_argument e("error opening traffic file (" + string(fname) + 
                       ") for input");
    throw e;
  }

  // file must contain 2 rows, each containing 2 columns
  char buf[BUF_SIZE];     
  double d;
  for (int i = 0; i < 2; ++i) {
    traf.getline(buf, BUF_SIZE);
    stringstream ss(buf);
    int j = 0;
    while (ss >> d) {
      rates[i][j] = d;
      ++j;
    }
    if (rates[i][i] > 0.0) {
      cout << "traffic pattern has people going from " << i << " to " << i
           << " which is silly." << endl;
      assert(false);
    }
    assert(j == 2);
  }
}

/*
 * 
 * generate pedestrians
 * 
 */
 
void pedestrian(unsigned int num, edge *myEdge, double mySpeed, bool lazy) {
    create("p");
    assert(myEdge != NULL);
    double travelTime;

    cout << "_" << num << "_\t" << clock << "\t leaving ";
    cout << myEdge->start << " for " << myEdge->end;
    cout << " at " << mySpeed << "fps";
    if (lazy) {
      cout << " being lazy";
    }
    cout << endl;

    if (!myEdge->speed > 0.0) {
      // this is a bi-directional path, so we need to swim upstream a bit
      cout << "_" << num << "_\t" << clock << "\t waiting to enter path " 
           << myEdge->name << endl;
      myEdge->mirror->exit->allocate(1);
      hold(UPSTREAM_DELAY);
      myEdge->mirror->exit->deallocate(1);
    }

    cout << "_" << num << "_\t" << clock << "\t entered " << myEdge->name ;

    myEdge->entranceGate->reserve();
    
    // calculate travel time based on my walking speed, plus
    // laziness correction (if using a moving sidewalk), plus
    // reverse traffic interference (if bi-directional path),
    // plus delay due to slower people ahead whom I can't pass.
    
    if (!myEdge->speed > 0.0) {
     
      // this path doesn't move - so our base travel time is 
      // just path length (in feet) divided by mySpeed (in fps)

      travelTime = myEdge->length / mySpeed;

      // however, we do experience additional delay as we pass
      // each of the reverse travellers currently on the same path
      
      const int reverse_travellers = myEdge->mirror->entranceGate->completions() - myEdge->mirror->pedestrianExitCount->cnt();
      if (reverse_travellers > 0) {
        travelTime += reverse_travellers * 2;
        cout << "against " << reverse_travellers << " on-coming travelers";
      }
    } else {
      
      // this is a uni-directional moving sidewalk

      if (lazy) {
        // if we're lazy, our travel time depends on the length 
        // of the path (in feet) and its speed (in fps)
        travelTime = myEdge->length / myEdge->speed;
      } else {
        // if we're not lazy, we'll walk at mySpeed relative to
	// the path while it moves at speed relative to the ground
	// (both in fps)
        travelTime = myEdge->length / (myEdge->speed + mySpeed);
      }
    }
    cout << endl;

    // now - see if there's someone else on the same path who's 
    // slower than we are and adjust our travel time accordingly
    double minTravelTime = myEdge->lastExitTime + 2 - clock;
    if (minTravelTime > travelTime) {
      cout << "_" << num << "_\t" << clock << "\t being held up for " 
	   << minTravelTime - travelTime << " on path " 
           << myEdge->name << endl;       
      travelTime = minTravelTime;
    }
    cout << "_" << num << "_\t" << clock << "\t will arrive at " << myEdge->end << " in " 
         << travelTime << " seconds" << endl;
    myEdge->lastExitTime = clock + travelTime;

    const double myStartTime = myEdge->InTransit->enter();
    myEdge->entranceGate->release();
    
    // we're on the sidewalk, yahoo!
    hold(travelTime);

    // Time to wake up and try to get out of here.
    myEdge->exit->allocate(1);

    // carry out exiting step
    hold(EXIT_DELAY);

    // finished exiting
    myEdge->InTransit->exit(myStartTime);
    myEdge->pedestrianExitCount->note_passage();
    myEdge->exit->deallocate(1);

    // finally, take care of congestion at the crossroads (if appropriate)
    int exit_node = myEdge->end;
    if (vertices[exit_node].ep) {
      long avail = vertices[exit_node].crossroad->avail();
      if (avail <= 0) {
        cerr << "ERROR: a pedestrian got squashed trying to get"
             << " into the crossroads at "
             << vertices[exit_node].name << endl;
      }
      assert(avail > 0);
      vertices[exit_node].crossroad->allocate(1);
      cout << "_" << num << "_\t" << clock << "\t at " << vertices[exit_node].name 
           << " with " << XROADS_CAPACITY-avail << " other people" << endl;
      hold(expntl(
            XROADS_BASE_DELAY+(XROADS_CROWD_DELAY*(XROADS_CAPACITY-avail))));
      vertices[exit_node].crossroad->deallocate(1);
      cout << "_" << num << "_\t" << clock << "\t leaving " 
           << vertices[exit_node].name << endl;      
    }
    cout << "_" << num << "_\t" << clock << "\t arrived at destination!" << endl;
}

void generatePedestrians(int origin, int dest, double rate) {
  create("pedestrian generator");
  edge *e;
  //
  // first, see if there is a moving sidewalk available and it is going the right way...
  //
  if((sidewalk_count>0) && (sidewalks[0].start == origin) && (sidewalks[0].end == dest)) {
	e = &sidewalks[0];
  }
  else {
	  //
	  // so sad, we must use the existing path...
	  //
	  if((edges[0].start == origin) && (edges[0].end == dest)){
	  	e = &edges[0];
	  }
	  else if ((reverse_edges[0].start == origin) && (reverse_edges[0].end == dest)){
	  	e = &reverse_edges[0];
	  }
	  else {
		  cerr << "no path available from " << origin << " to " << dest << endl;
		  assert(false);
	  }

  }

  while (clock < duration) {
    hold(expntl(1/rate));
    // time for a pedestrian to appear at origin and go to dest
    bool lazy = prob() < .4 ? false : true;
    pedestrian(++pedestrianNum, e,
               uniform(MIN_WALK_FPS,MAX_WALK_FPS), lazy);
  }
} 

void generatePedestrianGenerators() {
  const int size = 2;
  for (int i = 0; i < size; ++i) {
    for (int j = 0; j < size; ++j) {
      if (rates[i][j] != 0.0)   {
        generatePedestrians(i+1,j+1,rates[i][j]);
      }               
    }
  }
}


extern "C" void sim(int argc, char *argv[]) {
  FILE *fp;
  int c;  

  // parse arguments
  if (argc != 9) {
    usage(argv[0]);
    exit(-1);
  }       
  while (( c = getopt( argc, argv, "m:t:d:o:")) != -1) {
    switch(c) {
    case 'm':
      readMap(optarg);
      break;  
    case 't':
      readTraffic(optarg);
      break;
    case 'd':
      duration = atof(optarg);
      if (duration == 0) {
        usage(argv[0]);
        exit (-1);
      }
      break;
    case 'o':
      fp = fopen(optarg, "w");
      if (fp == NULL) {
        cerr << "unable to open output file (" << optarg 
             << ") for writing" << endl;
        exit(-1);
      }
      set_output_file(fp);
      break;
    case '?':
    default:
      usage(argv[0]);
      exit (-1);
      break;    
    }
  }
  max_processes(4000);
  create("sim");
  generatePedestrianGenerators();
  hold(duration);
  report();
}