/* dtree: Dick Barr's decision tree program, based on
 * cpm: Critical path method with an input file, containing
   a line for each activity with two (integer)
   event numbers, a duration (integer), and an
	optional description. The range of the event
	numbers influences the amount of memory needed.
	Apart from this, there are no limitations
	imposed on the number of events or on the way
	they are numbered, nor are there any restrictions
   on the number of activities or on their order in
   the input file, except for memory limitations of
   the machine on which the program runs.
*/

#include <fstream.h>
#include <iomanip.h>
//#include <stdlib.h>
#include <string>
#include <math.h>
//#include <stddef.h>

#define MAXNODES 100
#define MAXARCS  500
#define MAXDESC 50     //Arc descriptor length
#define MAXID 4        //Arc id length
#define debug    0


using namespace std;

struct activity{int num, dur; activity *next;};
struct NODE {
   		int		nodenumber;
		char	nodetype; 		// D = decision, E = chance, P = payoff
		double	emv;
		double	prob;			// probability, for chance nodes
		double	cumprob;		// cumulative probability, for chance nodes checks
		int		prednode;		// predecessor node or NULL
		int		predarc;		// precedessor arc or NULL
		int		fcount;		// number of arc/branches out of node
		int		firstsonarc;		// link to first child arc
		int		bestarc;		// best decision arc for D node
		int		futureDecisions;	// number of decisions beyond this node
		int		level;			// level in tree, distance from root
		int		card;			// cardinality of nodes in subtree
		int		temp;			// temporary label
		};

struct ARC {
   		int		arcnumber;		// unique arc id number
		char	arctype;		// 1 = decision choice, 0 = chance event
		int		fromnode;		// from node id
		int		tonode;			// to node id
		double	prob;			// probability, if type 0
		int		brother;		// link to next brother arc or 0
		char	arcid[MAXID+1];	// arc identifier string
		char	arcDesc[MAXDESC+1];	// Arc descriptor
		};

static NODE dummynode = {0,'?',0.0,0.0,0.0,0,0,0,0,0,0,0};
static ARC  dummyarc  = {0,'?',0,0,0.0,0};
	static string sarc = "+--------->";
static string vtab = "|          ";
static string htab = "           ";
// static string vtab = "|              ";
// static string htab = "               ";
static string indent = "    ";
static string empty = "";
	static char* fmtDnode = "[%2d]";
	static char* fmtEnode = "(%2d)";
	static char* fmtPnode = "{%2d}";
char* logname = "logfil";
ofstream logfil;
string ltab[MAXNODES];

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 inverted(const char *fname);
   void EndNodes();
   void LatestEventTime();
   int  GetArc();
   void Printout();
   void NodeReport();
   void ArcReport();
   void Evaluate();
   void Describe(int, string);
   void DrawTree();
   void DoNode(int,string,string);
   void PutNode(int);
   void OutNodeLabel(int);
   void PutArc(int, string, int);
   void PrintNode(int, string, string, int, int, int);
   void SetLevels(int,int);
   void Driver(int,char**);
private:
   struct event{int count, ee, le; activity *link;} *a;
   int tMax;
   int numNodes;
   int numArcs;
   int root;
   double maxEMV ;     // Set to 1.0 for max, -1.0 for minimize
   NODE	node[MAXNODES+1];
   ARC  arc[MAXARCS+1];
   enum {nil=-1, absent=-2};
   int start; // Start of simulated linked list
              // for nodes without a predecessor
   void SkipRestLine(ifstream &file);
};

void project::PutNode(int i)
// Print node[i]. If payoff, also print payoff and carriage return
	{
	char buf[20];
	if (debug) logfil << endl << "---PutNode " << i << endl << "#";
	switch (node[i].nodetype) {
	case 'D':	OutNodeLabel(i);
				break;
	case 'E':	OutNodeLabel(i);
				break;
	case 'P':	OutNodeLabel(i);
				cout << " " << node[i].emv << endl;
				if (debug) logfil << node[i].emv << endl;
				break;
	}
	if (debug) logfil << "$";
	return;
	}

void project::OutNodeLabel(int i){
	char buf[20];

	switch (node[i].nodetype) {
	case 'D':	sprintf(buf, fmtDnode, i); 
				break;
	case 'E':	sprintf(buf, fmtEnode, i); 
				break;
	case 'P':	sprintf(buf, fmtPnode, i); 
				break;
		}
	cout << buf;
	if (debug) logfil << buf;
	}

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

	if (debug) logfil << endl << "---PutArc(" << a << "%" << tab << "%" << usetab <<  ")" <<endl << "#";
	yesno = '-';
	switch (arc[a].arctype) {
	case 'D':
				if (a != node[arc[a].fromnode].bestarc) yesno = 'x';
	case 'E':	
				sprintf(buf,"+%c--%-4s-->",yesno,arc[a].arcid);
				if (usetab) { cout << tab; if (debug) logfil << tab; }
				cout <<  buf;
				if (debug) logfil << buf;
				cp = tab.c_str();
				break;
	default:	cout << "ERROR: bad arc type: <" << arc[a].arctype << ">" << endl;
	}
	if (debug) logfil << "$";
	return;
	}

void  project::DoNode(int i, string tab1, string tab2)
// Process node[i] and all outbound branches
	{
	int a,j,lvl,t;
	string prefix, postfix;
	
	if (debug) logfil << endl << "***DoNode(" << i << "%" << tab1 << "%" << tab2 << ")" << endl << "!";
	PutNode(i);
	a = node[i].firstsonarc;
	t = 0;
	prefix = tab1+indent;
	postfix = tab1+indent+vtab;
	while (a) {
		PutArc(a,prefix,t);
		DoNode(arc[a].tonode,postfix,postfix);
		a = arc[a].brother;
		postfix = tab1+indent+vtab;
		if (arc[a].brother == 0) postfix = tab1+indent+htab;
		t = 1;
		}
	if (debug) logfil << "@" << endl << "***End DoNode " << i << endl;
	return;
	}

	
void  project::DrawTree()
	{
	SetLevels(root,1);
	cout << endl << "Optimized Decision Tree:" << endl << endl;
	DoNode(root,empty,indent);
	cout << endl;
	}

void  project::SetLevels(int now, int dist)
	{
	node[now].level = dist;
	if (node[now].nodetype == 'P') return;
	now = node[now].firstsonarc;
	while (now) {
		SetLevels(arc[now].tonode,dist+1);
		now = arc[now].brother;
		}
	}

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

void project::ReadProblem(const char *fname)
{  ifstream file(fname, ios::in);
   if (file.fail())
   {  cout << "Cannot open input file.\n";
      exit(1);
   }
   char iflag[5];
   char arcid[10];
   int  ifrom, jto;
   double prob, pay;

   maxEMV = 1.0;  // Set to -1 for minimize

   for (;;)
   {  
      // if (file.fail()) break;
      file >> iflag >> ifrom;
	  if (ifrom > numNodes) numNodes = ifrom;
	  switch (iflag[0])
	  	{
	  	case 'D':	//    Decision arc
		case 'd':
					file >> jto;
	  				if (jto > numNodes) numNodes = jto;
					if (debug) cout << iflag[0] << "  " << ifrom << "  " << jto << endl;
					if (node[jto].prednode > 0) {cout << "ERROR: Duplicate branch into node "<<jto<<endl; exit(-1);}
					else {
	  					++numArcs;
						node[jto].prednode = ifrom;
						node[jto].predarc = numArcs;
						node[ifrom].emv = -maxEMV*99999999.;
						if (node[ifrom].nodetype == 'E'||node[ifrom].nodetype == 'P')
						    {cout << "ERROR: Cannot change the type (E,P) of node " << ifrom << endl; exit(-1);}
						node[ifrom].nodetype = 'D';
						++node[ifrom].fcount;
						arc[numArcs].fromnode = ifrom;
						arc[numArcs].tonode = jto;
						arc[numArcs].arctype = 'D';
						file >> arcid;
						memcpy(arc[numArcs].arcid, arcid, sizeof(char)*MAXID);
						file.getline (arc[numArcs].arcDesc,MAXDESC);
						}
					break;
		case 'E':	//    Event arc
		case 'e':
					file >> jto >> prob;
	  				if (jto > numNodes) numNodes = jto;
					if (debug) cout << iflag[0] << "  " << ifrom << "  " << jto << "  " << prob <<endl;
					if (node[jto].prednode > 0) {cout << "ERROR: Duplicate branch into node "<<jto<<endl; exit(-1);}
					else {
	  					++numArcs;
						node[jto].prednode = ifrom;
						node[jto].predarc = numArcs;
						node[ifrom].emv = 0.0;
						node[ifrom].cumprob += prob;
						if (node[ifrom].nodetype == 'D'||node[ifrom].nodetype == 'P')
						    {cout << "ERROR: Cannot change the type (D,P) of node " << ifrom << endl; exit(-1);}
						node[ifrom].nodetype = 'E';
						++node[ifrom].fcount;
						arc[numArcs].fromnode = ifrom;
						arc[numArcs].tonode = jto;
						arc[numArcs].prob = prob;
						arc[numArcs].arctype = 'E';
						file >> arcid;
						memcpy(arc[numArcs].arcid, arcid, sizeof(char)*MAXID);
						file.getline (arc[numArcs].arcDesc,MAXDESC);
						}
					break;
		case 'P':	//    Payoff arc
		case 'p':
					file >> pay;
	  				if (ifrom > numNodes) numNodes = ifrom;
					if (debug) cout << iflag[0] << "  " << ifrom << "  " << pay << endl;
					node[ifrom].emv = pay;
					node[ifrom].fcount = 0;
					node[ifrom].nodetype = 'P';
      				SkipRestLine(file);
					break;
		default:	cout << "Wrong code" << endl;
					break;
		}
      // SkipRestLine(file);
      if (file.fail()) break;
   }

   file.close();
   cout << numNodes << " nodes and " << numArcs << " arcs" << endl;
   if (numNodes != (numArcs+1)) 
   	{
	cout << "ERROR: For " << numNodes << " nodes and payoffs there should be "<<(numArcs+1)<<" arcs"<<endl;
	exit(-1);
	}
   if (debug) Printout();
}

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) {
		node[i].temp = node[i].fcount;
		switch(node[i].nodetype) {
		  case 'P': {++qlen; queue[qlen] = i; break;}   // Add endpoints to queue
					if (node[i].fcount > 0) {
		  				cout << "ERROR: Payoff nodes cannot have branches, as with node " << i << endl;
						exit(-1);
					   }
		  			break;
		  case 'E': if (fabs(1.0-node[i].cumprob) > 0.001) {   // Check cumulative probabilities at node
		  				cout << "ERROR: Probabilities do not sum to 1 at node " << i << endl;
						exit(-1);
						}
					if (node[i].fcount == 0) {
		  				cout << "ERROR: no branches leave chance node " << i <<  endl;
						exit(-1);
					   }
		  			break;
		    case 'D':
					if (node[i].fcount == 0) {
		  				cout << "ERROR: no branches leave decision node " << i <<  endl;
						exit(-1);
					   }
		  			break;
		  }
		}

	evcount = numNodes;
	while (qlen > 0) {
		evnode = queue[qlen--];
		--evcount;
		evarc  = node[evnode].predarc;
		pred   = node[evnode].prednode;
		--node[pred].temp;
		if (debug) {cout << "Evaluating node " << evnode << "  Q = {";
		    for (i=1; i<= qlen; ++i) cout << queue[i] << " ";
			cout << "}" << endl;
			}
			
		if (pred == 0) break;   // exit at root

		if (arc[evarc].arctype == 'D') {
			if (node[pred].temp <= 0) queue[++qlen] = pred;
			node[pred].futureDecisions += 1+node[evnode].futureDecisions;
			arc[evarc].brother = node[pred].firstsonarc;
			node[pred].firstsonarc = evarc;  // add to chain of child arcs for pred node
			if (node[evnode].emv > node[pred].emv) {
				node[pred].emv = node[evnode].emv;
				node[pred].bestarc = evarc;
				}
			}
		else if (arc[evarc].arctype == 'E') {
			node[pred].emv += arc[evarc].prob * node[evnode].emv;
			arc[evarc].brother = node[pred].firstsonarc;
			node[pred].firstsonarc = evarc;  // add to chain of child arcs for pred node
			node[pred].futureDecisions += node[evnode].futureDecisions;
			if ((node[pred].temp) <= 0) queue[++qlen] = pred;
			}
		else { cout << "Error in type on arc " << i << endl; }
		}

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

void project::Printout(){
   int i;
	NodeReport();
	ArcReport();
	}

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

   cout <<"Node Summary Report (Evaluated and Optimized Tree):"<< endl << endl ;
   // cout << " i  pN  pA  emv type #branch bestarc level" << endl;
   for (i=1; i <=4; ++i) printf(" Node        EMV     ");
   cout << endl;
   for (i=1; i <=4; ++i) printf("----------------     ");
   cout << endl;
   for(i=1;i<=numNodes; ++i) {
   		// cout << i ;
		OutNodeLabel(i);
		sprintf(buf," %-1c%10.3lf     ",node[i].nodetype,node[i].emv);
		cout << buf;
   		//cout << "  " <<  setw(1) << node[i].nodetype;
   		if (debug) cout << "  " << node[i].prednode;
   		if (debug) cout << "  " << node[i].predarc;
   		//cout << "  " << setw(8) << left << setprecision(4) << node[i].emv;
   		if (debug) cout << "  " << node[i].fcount;
   		if (debug) cout << "  " << node[i].bestarc;
		if (debug) cout << "  " << node[i].level;
		//cout << "     ";
		if (i % 4 == 3) cout << endl;
		}
	cout << endl;
}

void project::ArcReport(){
   int i;

   cout << endl << "Input Branch List: "<< endl << endl;
   printf(" Arc  From   To     Prob    Name    Description\n");
   printf("----- ---------   ------    ----    -----------\n");

   for(i=1;i<=numArcs; ++i) {
		printf("%3d %c  %3d  %3d", i, arc[i].arctype, arc[i].fromnode, arc[i].tonode);
		if (arc[i].arctype == 'E') printf("   %-6.4lf",arc[i].prob);
		else printf("         ");
		printf("    %4.4s   %s\n",arc[i].arcid, arc[i].arcDesc);
		}
	}

void project::Describe(int nownode, string tab)
	{
	int a;
	// cout << "<" << nownode << ">" << endl;

	if (node[nownode].futureDecisions == 0) return;

	switch (node[nownode].nodetype) {
	case 'D':	a = node[nownode].bestarc;
				cout << tab;
				cout << "Choose to " << arc[a].arcDesc << " (action from node " ;
				cout << arc[a].fromnode << " to node " << arc[a].tonode << ")" << endl;
				Describe(arc[a].tonode, tab+indent);
				break;
	case 'E':	a = node[nownode].firstsonarc;
				while (a) {
					cout << tab;
					cout << "If event " << arc[a].arcDesc << " (from node " ;
					cout << arc[a].fromnode << " to node " << arc[a].tonode << ") happens," << endl;
					Describe(arc[a].tonode, tab+indent);
					a = arc[a].brother;
					}
				break;
	case 'P':
	default:	break;
	}
	return;
	}


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

	cout << "*** DTREE: DECISION TREE ANALYZER *** " << endl << endl;
   	if (argc != 2) {
	   	cout << "Usage:  dtree inputFilename\n";
	   	exit(1);
   	}
   	if (debug) logfil.open(logname, ios::out);
   	if (debug) logfil << "Begin log file";
   	fname = argv[1];
   	ReadProblem(fname);     // Find range of event numbers
   	Evaluate();
	// Printout();
	ArcReport();
	DrawTree();
	NodeReport();

	cout << endl << "Optimal Strategy:" << endl << endl;
	Describe(root, "   ");
	cout <<endl << "Expected value of optimal strategy is " << node[root].emv << endl;
   	if (debug) logfil.close();
	}

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

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