#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

#define DEBUG 0
#define eps 1.0e-10

#define STRLEN 256
#define LINELEN 2560
#define MAXNOVARS 1000
#define MAXCHILD 25

  /* 
     This program accepts a number of options:

     WARNING!: This code has not been thoroughly tested.  If you find
               an error, please email us: caruana@cs.cmu.edu
  */

int show_probs;
int node_count = 0;

struct trel { struct trel *parent, *children[MAXCHILD], *left_sibling, *right_sibling;
              int no_children, depth, node_number;
              double prob0, prob1;
	      double count0, count1;
	      char varname[STRLEN], test[STRLEN], testval[STRLEN];
	    };
	    
struct trel *new_trel ()
{
  int i;
  struct trel *temp;

  temp = (struct trel *) malloc(sizeof(struct trel));
  if (temp == NULL)
    {
      printf("Error! ran out of memory on tree allocation.\n");
      exit(-1);
    }
  temp->parent = NULL;
  for (i=0; i<MAXCHILD; i++)
    temp->children[i] = NULL;
  temp->left_sibling = NULL;
  temp->right_sibling = NULL;
  temp->no_children = 0;
  temp->depth = -1;
  temp->prob0 = -1.0;
  temp->prob1 = -1.0;
  temp->count0 = 0;
  temp->count1 = 0;
  strcpy(temp->varname, "");
  strcpy(temp->test, "");
  strcpy(temp->testval, "");
  temp->node_number = node_count;
  /*if (DEBUG) printf("Initialized node %d\n", node_count);*/
  node_count++;
  return(temp);
}
	    

void print_tree (struct trel *tree)
{
    int i;
    
    if (tree != NULL)
	{
           printf("node %4d depth %4d %s %s %s %5.3lf\n", 
		  tree->node_number, tree->depth, tree->varname, tree->test, tree->testval, tree->prob1); 
	   fflush(stdout);
           for (i=0; i < tree->no_children; i++)
             print_tree(tree->children[i]);
	}
	
}


void dot_tree (struct trel *tree)
{
    int i;
    if (tree != NULL)
      {
        if (tree->no_children == 0)
	  {
	    printf("n%d [shape=box,label=\"p(csec)=%4.2lf\\n[%3.1lf,%3.1lf]\"]\n", 
		   tree->node_number, tree->prob1, tree->count0, tree->count1);
 	    if (tree->depth != 0)
	      printf("n%d -> n%d [label=\"%s %s\"]\n", tree->parent->node_number, tree->node_number, tree->test, tree->testval);
	  }
      	else
	  {
	    printf("n%d [shape=ellipse,label=\"%s\\n[%3.1lf,%3.1lf]\"]\n", 
		   tree->node_number, tree->children[0]->varname, tree->count0, tree->count1);
	    if (tree->depth != 0)
 	      printf("n%d -> n%d [label=\"%s %s\"]\n", tree->parent->node_number, tree->node_number, tree->test, tree->testval);
	    for (i=0; i<tree->no_children; i++)
	      dot_tree(tree->children[i]);
	  }
      }
      
}



struct trel *read_tree()
{
  int  i, n, nlines;
  int  depth;
  char line[LINELEN];
  char word[STRLEN];
  char **ap, *argv[MAXNOVARS], *inputstring;
  struct trel *root, *prev, *current, *lsib;
  
  nlines = 0;
  root = new_trel();
  root->depth = 0;
  gets(line);
  inputstring = line;  
  if (DEBUG) printf("%s\n", line);
  n = 0;
    for (ap = argv; (*ap = strsep(&inputstring, " \t:+()")) != NULL;)
      if (**ap != '\0')
	{
	  ++ap;
	  n++;
	}
  if (DEBUG) printf("%s,%s,%s,%s\n", argv[1], argv[2], argv[4], argv[5]);
  if (n > 1) root->count0 = atof(argv[1]);
  if (n > 2) root->count1 = atof(argv[2]);
  if (n > 4) root->prob0 = atof(argv[4]);
  if (n > 5) root->prob1 = atof(argv[5]);
  prev = root;
  
  while (gets(line))
  {
    if (DEBUG) printf("%s\n", line);
    inputstring = line;
    nlines++;
    n = 0;
    for (ap = argv; (*ap = strsep(&inputstring, " \t:+()")) != NULL;)
      if (**ap != '\0')
	{
	  ++ap;
	  n++;
	}
    for (i=0; i<n && strcmp(argv[i],"|") == 0; i++);
    depth = i+1;
    current = new_trel();
    current->depth = depth;
    if (DEBUG) printf("%d %d %d %s %s %s\n", n, i, depth, argv[i], argv[i+1], argv[i+2]); fflush(stdout);
    if (n > i  ) strcpy(current->varname, argv[i]);
    if (n > i+1) strcpy(current->test,    argv[i+1]);
    if (n > i+2) strcpy(current->testval, argv[i+2]);
    if (n > i+4) current->count0 = atof(argv[i+4]);
    if (n > i+5) current->count1 = atof(argv[i+5]);
    if (n > i+7) current->prob0 = atof(argv[i+8]);
    if (n > i+8) current->prob1 = atof(argv[i+8]);
    if (depth == prev->depth)
	{
	    /* sibling to previous node */
	    if (DEBUG) printf("Sibling to previous node\n"); fflush(stdout);
	    current->left_sibling = prev;
	    prev->right_sibling = current;
	    current->parent = prev->parent;
	    prev->parent->children[prev->parent->no_children] = current;
	    prev->parent->no_children++;
	}
    else if (depth == (prev->depth+1))
	{
	    /* first child of previous node */
	    if (DEBUG) printf("First child to previous node\n"); fflush(stdout);
	    prev->children[prev->no_children] = current;
	    prev->no_children++;
	    current->parent = prev;
	}
    else 
	{
	    /* find current node's left sibling */
	    if (DEBUG) printf("Finding current node's left sibling\n"); fflush(stdout);
	    for(lsib = prev->parent; lsib->depth != depth; lsib = lsib->parent);
	    lsib->right_sibling = current;
	    current->left_sibling = lsib;
	    current->parent = lsib->parent;
	    lsib->parent->children[lsib->parent->no_children] = current;
	    lsib->parent->no_children++;
	    current->depth = depth;
	}
    if (DEBUG) print_tree(current);
    prev = current;
  }
  return(root);
}


void read_options(argc, argv)
     int  argc;
     int  **argv;
{
  int arg, taken;
  
  show_probs = 0;
  arg = 1;
  while ( arg < argc )
    {
      taken = 0;
      if (!strcmp((char *)argv[arg], "-probs"))
	{
	  /*arg++; ptreenc = atoi((char *)argv[arg]);*/
	  show_probs = 1;
	  taken = 1;
	}
      if (!taken)
	{
	  printf("\nWarning!: Unrecognized program option %s\n", argv[arg]);
	}
      arg++;
    }
}

main (argc, argv)
     int  argc;
     int  **argv;

{
  struct trel * input_tree;

  read_options(argc, argv);
  input_tree = read_tree();
  if (DEBUG) print_tree(input_tree);

  printf("digraph csection {\n");
  printf("size = \"8.0,10.0\";\n");
  printf("page = \"8.5,11.0\";\n");
  printf("nodesep = 0.25;\n");
  printf("height = 0.25\n");
  printf("rankdir = TB;\n");
  printf("fontsize = 12;\n");
  printf("fontname = \"Helvetica\";\n");
  printf("orientation = landscape;\n");
  dot_tree(input_tree);
  printf("}\n");
}
