/* 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


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 ReadProblem(const char *fname);
   void ReadProblem2(const char *fname);
//   void AssignAllTasks(long,long);
//   void AssignmentReport(long,long);
   long	NodeNum(char*);
   long	NewNodeNum(char*);
//   long	MakeStation(long,long);
//   long	IsTie(long,long);
//   long  FindTaskFit(long);
//   void RankTasks(long);
//   long  Better(long,long,long);
//   void	PrintRanking(long);
   void	CountPreds();
   void	CountSuccessors();
   void	AddPreds(long);
   void	AddSuccessors(long);
   void ZeroNodeLabels();
   void ZeroNodePreds();
   void ZeroNodeSuccessors();
   void Printout();
   void NodeReport();
   void ArcReport();
   void Evaluate();
   void DoNode(long,string);
   void PutNode(long);
   void OutNodeLabel(long);
   void PutArc(long, string, long);
   void Driver(long,char**);
   void CPM();
   void reportCPM();
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];
   void 	SkipRestLine(ifstream &file);
   stack <long> nodestack;
};

/*
void project::AssignmentReport(long ct,long rule) {
	long i,idle,calc;
	double e;
	cout << endl << "  *** ASSEMBLY LINE SUMMARY ***" << endl << endl;

	printf("Problem:\n");
	printf("--------\n");
	printf("Number of tasks       %d\n",numNodes);
	printf("Total task time       %d\n",totaltime);
	printf("Longest task time     %d\n",tMax);
	printf("Target cycle time     %d\n\n",ct);

	printf("Assignment:\n");
	printf("-----------\n");
	printf("Rule                  %d\n",rule);
	for(i=1, calc=0; i <= numStations; ++i) {calc = MAX(calc,station[i].stationtime);}
	ct = calc;
	printf("Computed cycle time   %d\n",ct);
	printf("Stations used, N      %d\n",numStations);
	idle = 0;
	for(i=1; i <= numStations; ++i) {idle += (ct-station[i].stationtime);}

	printf("Output per hour, N'   %.2lf (if seconds)\n",3600.0/(double)ct);
	printf("                      %.2lf (if minutes)\n",60.0/(double)ct);
	printf("Station time/cycle    %d\n",numStations*ct);
	printf("Idle time/cycle       %d\n",idle);
	e = (double)totaltime/((double) numStations*(double)ct);
	printf("Efficiency, E         %lf\n",e);
	printf("Fraction idle, 1-E    %lf\n",1.0-e);
	printf("Balance delay         %lf\n",100.0*(1.0-e));
	}

void project::AssignAllTasks(long ct,long rule) {
	long i, tasksleft;
	cout << endl << "  *** WORKSTATION ASSIGNMENTS ***" << endl << endl;
	cout << "For cycle time = " << ct << ", using rule " << rule << endl ;
	if (ct < tMax) {
		cout << "Infeasible cycle time, reset to " << tMax << ", the largest task time"<< endl;
		ct = tMax;
		}
	cout << endl;

	for (i=1; i <= numNodes; ++i) node[i].label = node[i].bcount;

	for (numStations=0,tasksleft=numNodes; numStations <= numNodes && tasksleft; ) {
		++numStations;
		MakeStation(numStations,ct);
		tasksleft -= station[numStations].numTasks;
		}
	}

long project::MakeStation(long s, long cycletime) {      // assign tasks to workstation s, return # assigned
	long t,a,timeleft,cumtime;
	static STATION initstation = {0,0,0};

	timeleft = cycletime;
	cumtime  = 0;
	station[s] = initstation;
	// NodeReport();
	// ArcReport();

	// cout << endl<<"Station " << s << ":" << endl;
	// cout << "Task  Time  CumTime" << endl;
	// cout << "----  ----  -------" << endl;
	cout << "Station " << s << " tasks:" ;

	while ((timeleft > 0) && (t=FindTaskFit(timeleft)) > 0) {
		node[t].station = s;
		++station[s].numTasks;
		station[s].stationtime += node[t].tasktime;
		timeleft -= node[t].tasktime;
		// printf("%4d%6d%9d\n", t, node[t].tasktime, station[s].stationtime);
		cout << " " << node[t].nodename;
		a = node[t].fstar;
		while(a) { --node[arc[a].tonode].label; a = arc[a].fstar;}
		}

	cout << " (time = " << station[s].stationtime << ")" << endl;
	// cout <<"-------------------" << endl;
	}

long project::FindTaskFit(long timeleft) {    // Return next task that fits or 0
	long i,t;
	for (i=1; i <= numNodes; ++i) {
		t = tsort[i];
		if (t <= 0) continue;         // skip if already assigned
		if (node[t].label) continue;  // skip if all preds not assigned
		if (node[t].tasktime <= timeleft) {
			tsort[i] = -tsort[i];
			return t;
			}
		}
	return 0;
	}

void project::PrintRanking(long rule){
	long ties = 0;
	cout << "Tasks ranked by rule " << rule << ":" << endl;
	for (long i=1; i <= numNodes; ++i) {
		cout << " " << node[tsort[i]].nodename;
		if (IsTie(tsort[i],tsort[i-1])) {++ties; cout << "*"; }
		// if (IsTie(tsort[i],tsort[i-1]) || IsTie(tsort[i],tsort[i+1])) {++ties; cout << "*"; }
		}
	cout << endl;
	if (ties) cout << " (*task tied with prior task in ranking)" << endl;
	}

long project::IsTie(long i, long j) {
	if(i <1 || i > numNodes || j < 1 || j > numNodes) return 0;
	if (node[i].preds == node[j].preds && node[i].tasktime == node[j].tasktime) return 1;
	else return 0;
	}

void project::RankTasks(long rule) {
	long i,j,best,hold;
	for (i=1; i <= numNodes; ++i) tsort[i] = i;
	for (i=1; i < numNodes; ++i) {
		best = i;
		for (j=i+1; j <= numNodes; ++j) { if(Better(tsort[j],tsort[best],rule)) best = j; }
		if (best != i) {hold = tsort[i]; tsort[i]=tsort[best]; tsort[best] = hold;} // Swap
		}
	}

long project::Better(long j, long i, long rule) { // returns i or j, whichever is better
	switch (rule) {
		case 1:	if (node[j].preds > node[i].preds) return 0;
				else if (node[j].preds < node[i].preds) return 1;
				break;
		case 2:	if (node[j].successors < node[i].successors) return 0;
				else if (node[j].successors > node[i].successors) return 1;
				break;
		}
	// Tie-breaker: longer task time first
	if (node[j].tasktime > node[i].tasktime) return 1;
	else return 0;
	}
*/
void project::OutNodeLabel(long i){
	char buf[20];

	cout << i;
	}

void project::PutArc(long a, string tab, long usetab)
// Print arc[a], if usetab then print tab first
	{
	const char* cp;
	char buf[10];

	cp = tab.c_str();
	return;
	}

void  project::DoNode(long i, string tab1)
// Process node[i] and all outbound branches
	{
	long a,j,lvl,t;
	string postfix;
	
	a = node[i].bstar;
	t = 0;
	while (a) {
		PutArc(a,tab1,t);
		DoNode(arc[a].tonode,postfix);
		a = arc[a].bstar;
		t = 1;
		}
	cout << tab1 << endl;
	return;
	}

	
void project::SkipRestLine(ifstream &file)
{  char ch;
   do file.get(ch); while (!file.fail() && ch != '\n');
}


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
	  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;
	  	}
	  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;}
		}
	 	
      }

   file.close();
   printf("Project has:\n%8ld Activity nodes\n%8ld Precedence arcs\n%8ld Total time units for all activities\n",
		numNodes,numArcs,totaltime);
//   cout << numNodes << " task nodes, " << numArcs << " precedence arcs";
//   cout << ", and " << totaltime << " time units for all tasks" << endl;
   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::CountPreds(){
	long i;
	ZeroNodePreds();
	for (i=1; i <= numNodes; ++i) {
		ZeroNodeLabels();
		AddPreds(i);
		}
	return;
	}

void project::AddPreds(long i){
	long a;
	if (node[i].label) return;
	++node[i].preds;
	node[i].label = 1;
	a = node[i].fstar;
	while(a) {
		AddPreds(arc[a].tonode);
		a = arc[a].fstar;
		}
	return;
	}

void project::ZeroNodeLabels(){
	for(long i=1; i<= numNodes; ++i) node[i].label = 0;
	}

void project::ZeroNodePreds(){
	for(long i=1; i<= numNodes; ++i) node[i].preds = -1;
	}


void project::CountSuccessors(){
	long i;
	ZeroNodeSuccessors();
	for (i=1; i <= numNodes; ++i) {
		ZeroNodeLabels();
		AddSuccessors(i);
		}
	return;
	}

void project::AddSuccessors(long i){
	long a;
	if (node[i].label) return;
	++node[i].successors;
	node[i].label = 1;
	a = node[i].bstar;
	while(a) {
		AddSuccessors(arc[a].fromnode);
		a = arc[a].bstar;
		}
	return;
	}

void project::ZeroNodeSuccessors(){
	for(long i=1; i<= numNodes; ++i) node[i].successors = -1;
	}

void project::Evaluate(){
	long i;
	long queue[MAXNODES+1];
	long qlen;
	long evnode; // node being evaluated
	long evarc;
	long pred;
	long evcount;

	qlen = 0;
    for(i = 1; i <=numNodes; ++i) {
		}

	evcount = numNodes;
	while (qlen > 0) {
		evnode = queue[qlen--];
		--evcount;
		evarc  = node[evnode].fstar;
		pred   = node[evnode].bstar;
		--node[pred].label;
		if (debug) {cout << "Evaluating node " << evnode << "  Q = {";
		    for (i=1; i<= qlen; ++i) cout << queue[i] << " ";
			cout << "}" << endl;
			}
			
			node[pred].bstar = evarc;  // add to chain of child arcs for pred node
			if ((node[pred].label) <= 0) queue[++qlen] = pred;
		}

	if (evcount) cout << "** There are " << evcount << " unevaluated nodes" << endl;
	root = evnode;
	}

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

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

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);
	}

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();
//	CountPreds();
//	CountSuccessors();
//	NodeReport();
//	RankTasks(irule);
//	PrintRanking(irule);
//	AssignAllTasks(cycletm,irule);
//	AssignmentReport(cycletm,irule);
	}

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;
		}
	}

int main(int argc, char *argv[])
{  project g;

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