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


using namespace std;

struct activity{int 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
		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;			// First arc in fstar linked list
		long		bstar;			// First arc in bstar linked list
		};

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

class project {
public:
   project(){tMax = 0; numNodes=numArcs=0;}
   int min, n; // Minimum event number and n = max - min + 1
   void ReadProblem(const char *fname);
   void ReadProblem2(const char *fname);
   void AssignAllTasks(int,int);
   void AssignmentReport(int,int);
   long	NodeNum(char*);
   int	NewNodeNum(char*);
   int	MakeStation(int,int);
   int	IsTie(int,int);
   int  FindTaskFit(int);
   void RankTasks(int);
   int  Better(int,int,int);
   void	PrintRanking(int);
   void	CountPreds();
   void	CountSuccessors();
   void	AddPreds(int);
   void	AddSuccessors(int);
   void ZeroNodeLabels();
   void ZeroNodePreds();
   void ZeroNodeSuccessors();
   void Printout();
   void NodeReport();
   void ArcReport();
   void Evaluate();
   void DoNode(int,string);
   void PutNode(int);
   void OutNodeLabel(int);
   void PutArc(int, string, int);
   void Driver(int,char**);
private:
   int  tMax;
   int 	numNodes;
   int 	numArcs;				// number of arcs
   int	numStations;
   int 	root;
   int	totaltime;
   NODE	node[MAXNODES+1];
   ARC  arc[MAXARCS+1];
   STATION station[MAXNODES+1];
   int	tsort[MAXNODES+1];
   void SkipRestLine(ifstream &file);
};

void project::AssignmentReport(int ct,int rule) {
	int 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(int ct,int rule) {
	int 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;
		}
	}

int project::MakeStation(int s, int cycletime) {      // assign tasks to workstation s, return # assigned
	int 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;
	}

int project::FindTaskFit(int timeleft) {    // Return next task that fits or 0
	int 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(int rule){
	int ties = 0;
	cout << "Tasks ranked by rule " << rule << ":" << endl;
	for (int 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;
	}

int project::IsTie(int i, int 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(int rule) {
	int 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
		}
	}

int project::Better(int j, int i, int 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(int i){
	char buf[20];

	cout << i;
	}

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

	cp = tab.c_str();
	return;
	}

void  project::DoNode(int i, string tab1)
// Process node[i] and all outbound branches
	{
	int 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');
}


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

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

void project::ReadProblem2(const char *fname)
{  	int  ifrom, jto, tasktime;
	char buf[256],save[256];
	char *token;

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

   file.close();
   cout << numNodes << " task nodes, " << numArcs << " precedence arcs";
   cout << ", and " << totaltime << " time units for all tasks" << endl;
}

void project::CountPreds(){
	int i;
	ZeroNodePreds();
	for (i=1; i <= numNodes; ++i) {
		ZeroNodeLabels();
		AddPreds(i);
		}
	return;
	}

void project::AddPreds(int i){
	int 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(int i=1; i<= numNodes; ++i) node[i].label = 0;
	}

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


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

void project::AddSuccessors(int i){
	int 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(int i=1; i<= numNodes; ++i) node[i].successors = -1;
	}

void project::Evaluate(){
	int i;
	int queue[MAXNODES+1];
	int qlen;
	int evnode; // node being evaluated
	int evarc;
	int pred;
	int 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(){
   int 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",
			node[i].fstar, node[i].bstar, node[i].fcount, node[i].bcount, node[i].label);
		cout << endl;
		}
	cout << endl;
}

void project::ArcReport(){
   int 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::Driver(int argc, char *argv[])
	{
   	char *fname; 
	int 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
	CountPreds();
	CountSuccessors();
	NodeReport();
	RankTasks(irule);
	PrintRanking(irule);
	AssignAllTasks(cycletm,irule);
	AssignmentReport(cycletm,irule);
	}

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

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