/* dtree: Dick Barr's Critical Path Method, Activity-on-Node networks
*/

// #include <fstream.h>
#include <fstream>
#include "stdio.h"
#include <cmath>
#include <iostream>
#include <sstream>
#include <climits>
#include <stack>
//#include <stdlib.h>
#include <string>
#include <math.h>
//#include <stddef.h>
#include <cstring>
#include <cstdlib>

#define MAX(AA,BB) (((AA)>(BB))?(AA):(BB)) 
#define MAXNODES 100
#define MAXARCS  500
#define MAXDESC 50     //Arc descriptor length
#define MAXID 4        //Arc id length
#define NAMELEN 8
#define debug    1
#define FALSE 	0
#define TRUE	!FALSE


using namespace std;

struct activity{long num, dur; activity *next;};
struct NODE {		// Node = task or activity to be assigned to station
   		long		nodenumber;
		char		nodename[NAMELEN+1];
		long		tasktime;
		long		fstar;			// First arc in fstar linked list
		long		bstar;			// First arc in bstar linked list
		long		fcount;			// number of forward arcs out of this node
		long		bcount;			// number of backward arcs into this node
		long		preds;			// number of predecessor tasks
		long		successors;		// number of successor tasks
		long		rank;			// sorted rank of node
		long		station;		// assigned station number
		long		label;			// temporary label
		long		ES;			// earliest task start time
		long		EF;			// earliest finish time
		long		LS;			// latest start time
		long		LF;			// latest finish time
		long		slack;			// activity slack
		long		unsetpreds; 		// for forward pass
		long		unsetsuccs; 		// for backward pass
		char		nodeid[MAXID+1];	// Node identifier string
		char		nodeDesc[MAXDESC+1];	// Node descriptor
		};

struct ARC {		// Arc = dependency between two nodes
   		long		arcnumber;		// unique arc id number
		long		fromnode;		// from node id
		long		tonode;			// to node id
		long		fstar;			// Next arc in fstar linked list
		long		bstar;			// First arc in bstar linked list
		};

struct STATION {
	long	stationtime;			// total time for all assigned tasks
	long numTasks;				// number of assigned tasks
	long stationNum;				// station sequence number
	};

class project {
public:
   project(){tMax = 0; numNodes=numArcs=0;}
   long min, n; // Minimum event number and n = max - min + 1
   void ReadProblem2(const char *fname);
   long	NodeNum(char*);
   long	NewNodeNum(char*);
   void NodeReport();
   void ArcReport();
   void Driver(long,char**);
   void CPM();
   void reportCPM();
   void printCritical();
private:
   long  	tMax;
   long 	numNodes;
   long 	numArcs;				// number of arcs
   long		numStations;
   long		numCritical;			// # critical activities
   long 	root;
   long		totaltime;
   long		istart; 			// the start node
   long		iend; 				// the end node
   NODE		node[MAXNODES+1];
   ARC  	arc[MAXARCS+1];
   STATION 	station[MAXNODES+1];
   long		tsort[MAXNODES+1];
   stack <long> nodestack;
};

long project::NodeNum(char* s) {
	if (numNodes == 0) return NewNodeNum(s);
	for (long i=1; i <= numNodes; ++i) { if (!strncmp(s,node[i].nodename,NAMELEN)) return i; }
	return NewNodeNum(s);
	}

long project::NewNodeNum(char* s) {
	++numNodes;
	memcpy(node[numNodes].nodename, s, sizeof(char)*(NAMELEN));
	node[numNodes].nodename[NAMELEN+1] = '\0';
	return numNodes;
	}

void project::ReadProblem2(const char *fname)
{  	long  ifrom, jto, tasktime;
	int nstart, nend;   // number of start/end nodes (with 0 preds/succs)
	char buf[256],save[256];
	char *token;
	int i;

	ifstream file;
	file.open(fname, ios_base::in);
   	if (file.fail()) {  cout << "Cannot open input file.\n"; exit(1); }

   	for (numArcs=0;;)
   	  {  
	  file.getline (buf,256);
      	  if (file.eof()) break;
	  //memcpy(save,buf,sizeof(char)*256);

	  token	= strtok(buf," \t");	// Node/task name
	  if (token == NULL) continue;
	  jto = NodeNum(token);

	  token = strtok(NULL," \t");
	  node[jto].tasktime = atoi(token);
	  if (node[jto].tasktime > tMax) tMax = node[jto].tasktime;
	  totaltime += node[jto].tasktime;

	  while (token = strtok(NULL," \t") ) {
		ifrom = NodeNum(token);
	  	++numArcs;
	  	arc[numArcs].fromnode = ifrom;
	  	arc[numArcs].tonode 	= jto;
	  	arc[numArcs].bstar 	= node[jto].bstar;
	  	node[jto].bstar		= numArcs;
	  	arc[numArcs].fstar 	= node[ifrom].fstar;
	  	node[ifrom].fstar	= numArcs;
	  	++node[ifrom].fcount;
	  	++node[jto].bcount;
	  	}
	}

   file.close();
	// ArcReport();
	// NodeReport();
  for (i=1, nstart=nend=0; i <= numNodes; ++i) {
	if (node[i].bcount == 0) { istart = i; ++nstart;}
	if (node[i].fcount == 0) { iend = i; ++nend;}
	}
   printf("Project has:\n%8ld Activity nodes\n%8ld Precedence arcs\n%8ld Total time units for all activities\n",
		numNodes,numArcs,totaltime);
   if(nstart != 1) { cout << nstart << " Exactly 1 start node (with no predecessors) is required.\n"; exit(1); }
   if(nend != 1) { cout << nend << " Exactly 1 end node (with no successors) is required.\n"; exit(1); }
}

void project::NodeReport(){
   long i;
   char buf[25];

   cout <<endl<<"      *** TASK SUMMARY ***"<< endl << endl ;
   cout << " i     Task   Time   ";
   cout << "Fstar Bstar   Fcount Bcount   Label";
   cout << endl;
   for(i=1;i<=numNodes; ++i) {
		printf("%2d %8.8s   %4ld  ",i,node[i].nodename,node[i].tasktime); 
		printf("%5ld  %5ld    %5ld %5ld   %5ld",
			node[i].fstar, node[i].bstar, node[i].fcount, node[i].bcount, node[i].label);
		printf("\n");
		}
	printf("\n");
}

void project::ArcReport(){
   long i;

   cout << endl << "  *** TASK PRECEDENCE REQUIREMENTS ***"<< endl << endl;
   printf(" Arc  From   To   Fstar  Bstar\n");
   printf("----- ---------   -----  -----\n");

   for(i=1;i<=numArcs; ++i) {
		printf("%3d  %3d  %3d   %5d  %5d\n", 
		i, arc[i].fromnode, arc[i].tonode, arc[i].fstar, arc[i].bstar);
		}
	}

void project::reportCPM() {
	int i;

	cout <<endl << "             *** ACTIVITY SUMMARY ***" << endl <<endl;
	printf(" Activity   Time      ES    EF    LS    LF   Slack\n");
	for(i=1; i <= numNodes; ++i) {
		if(node[i].slack == 0) printf(" *");
		else printf("  ");
		printf(" %-8.8s %4ld   %5ld %5ld %5ld %5ld %7ld\n",
		node[i].nodename,node[i].tasktime, node[i].ES, node[i].EF,
		node[i].LS, node[i].LF, node[i].slack); 
		}
		
	printf("\n * Critical activity\n\n   Minimum project time:  %ld\n   Number of critical activities:  %ld\n",
	      node[iend].EF, numCritical);
	printf("   Critical path: ");
	printCritical();
	}
void project::CPM ()
	{
//   Forward pass
	long i,j,n,EFi,LSi,jarc;

	for (i=1; i <= numNodes; ++i) {
		node[i].unsetpreds 	= node[i].bcount;
		node[i].unsetsuccs 	= node[i].fcount;
		node[i].ES			= 0;
		node[i].LF			= LONG_MAX;

		}

	node[istart].ES	= 0;
	nodestack.push(istart);
	do 	{
		i = nodestack.top();
		nodestack.pop();
		EFi = node[i].EF	= node[i].ES + node[i].tasktime;
		// Explore fstar list for node i and add complete ones to stack
		if (node[i].fcount > 0) {
			jarc = node[i].fstar;
			do {
				j = arc[jarc].tonode; // next successor
				if(EFi > node[j].ES) node[j].ES = EFi;
				if((--node[j].unsetpreds) == 0) {nodestack.push(j); }
				jarc = arc[jarc].fstar;
				} while(jarc);
			}
		} while(!nodestack.empty());

//    Backward pass

	node[iend].LF	= node[iend].EF;
	nodestack.push(iend);
	do 	{
		i	= nodestack.top();
		nodestack.pop();
		LSi 	= node[i].LS 	= node[i].LF - node[i].tasktime;
		if(node[i].bcount > 0) {
			jarc = node[i].bstar;    // next predecessor node
			do {
				j = arc[jarc].fromnode;
				if(LSi < node[j].LF) node[j].LF = LSi;   // new min LSj
				if((--node[j].unsetsuccs) == 0) nodestack.push(j);
				jarc = arc[jarc].bstar;	// next pred in bstar list
				} while(jarc);
			}
		} while(!nodestack.empty());

//    Compute slacks
	
	
	for(i=1,numCritical=0; i<= numNodes; ++i) {
		node[i].slack = node[i].LS - node[i].ES;
		if(node[i].slack == 0) ++numCritical;
		}
	}

void project::printCritical() {
	stack <long> critstack;
	int i, j, jarc,numfind;

	for (i=1; i<= numNodes; ++i) node[i].label = FALSE;  // TRUE = visited node previously
	
	critstack.push(istart);
	numfind = 0;
	while (!critstack.empty()){
		i = critstack.top();
		critstack.pop();
		node[i].label = TRUE;
		if (node[i].slack == 0) cout << node[i].nodename << " ";
		++numfind;
		jarc	= node[i].fstar;
		while (jarc) {
			j = arc[jarc].tonode;
			if (node[j].slack == 0 && !node[j].label) { critstack.push(j); break;}
			jarc = arc[jarc].fstar;
		}
		if (i == iend) break;
	}
	if(numfind < numCritical) printf("   (multiple paths exist)");
	printf("\n");
	
}
int main(int argc, char *argv[])
{  project g;

	g.Driver(argc,argv);
   return 0;
}

void project::Driver(long argc, char *argv[])
	{
   	char *fname; 
	long cycletm, irule;

   	if (argc != 2) {
	   	cout << "Usage:  aon  inputFilename \n";
	   	exit(1);
   	}
   	fname = argv[1];
	cout << "*** CPM-AON Critical Path Method, Activity-on-Node *** " << endl << endl;
   	ReadProblem2(fname);     // Find range of event numbers
//	ArcReport();
//	NodeReport();
	CPM();
	reportCPM();
	}