/****************************************************************/
/* Copyright 1993 : Johns Hopkins University			*/
/*                 Department of Computer Science		*/
/****************************************************************/
/* Contact : murthy@cs.jhu.edu					*/
/****************************************************************/
/* File Name : display.c					*/
/* Author : Sreerama K. Murthy					*/
/* Last modified : October 1993					*/
/* Contains modules : 	main					*/
/*			set_extremes				*/
/*			display_point				*/
/*			display_edge				*/
/*			find_edge				*/
/*			prepare_ps				*/
/*			recursive_draw				*/
/*			finish_ps				*/
/*			make_box				*/
/*			intersection				*/
/*			onedge					*/
/*			correct_side				*/
/*			display_help				*/
/* Uses modules in : 	util.c					*/
/*			oc1.h					*/
/*			load_data.c				*/
/*			classify_util.c				*/
/* Is used by modules in :	None.				*/
/* Remarks       :	This file contains modules to display	*/
/*			datasets and/or decision trees, as 	*/
/*			PostScript(R) files.			*/
/****************************************************************/		

#include "oc1.h"

char *pname;
char point_file[LINESIZE];
int unlabeled=FALSE,no_of_samples,no_of_dimensions=0;
int no_of_categories=0,no_of_coeffs;
struct point **train_points;
struct tree_node *box;
float xmax,xmin,ymax,ymin;
int pminx=72, pmaxx=540, pminy=72, pmaxy = 640;

/************************************************************************/
/* Module name : main							*/ 
/* Functionality :	Accepts & interprets command line options for	*/
/*			the "display" command. Invokes the routines to	*/
/*			read/display data, read/display decision trees.	*/
/* Parameters :	argc,argv : See any C-reference manual.			*/
/* Returns : 	Nothing.						*/
/* Calls modules :	display_help					*/
/*			read_tree (classify_util.c)			*/
/*			error (util.c)					*/
/*			load_points (load_data.c)			*/
/*			prepare_ps					*/
/*			set_extremes					*/
/*			display_point					*/
/*			make_box					*/
/*			recursive_draw					*/
/*			finish_ps					*/
/* Is called by modules :	None.					*/
/************************************************************************/
main(argc,argv)
int argc;
char *argv[];
{
 extern char *optarg;
 extern int optind;
 int c1,i,j;
 int verbose=FALSE;
 int leaf_count(),tree_depth();
 int load_points();
 char decision_tree[LINESIZE];
 char ps_file[LINESIZE];
 char title[LINESIZE];
 struct tree_node *root,*cur_node,*read_tree();
 FILE *psfile, *infile;
 
 strcpy(point_file,"\0");
 strcpy(decision_tree,"\0");
 strcpy(ps_file,"\0");
 strcpy(title,"\0");

 pname = argv[0];
 while ((c1 = getopt (argc, argv, "D:t:T:d:o:vh:x:X:y:Y:")) != EOF)
   switch (c1)
     {
         case 'D':   /*Decision Tree */
                     strcpy(decision_tree,optarg);
                     break;
                     /* A decision tree, when no point_file is specified,
                        is displayed in the unit square. [[0..1],[0..1]] */
         case 't':   /*File containing data points.*/
                     if (strlen(point_file)) display_help();
                     strcpy(point_file,optarg);
                     break;
         case 'T':   /*File containing data points.*/
                     if (strlen(point_file)) display_help();
                     strcpy(point_file,optarg);
                     break;
         case 'd':   no_of_dimensions = atoi (optarg);
                     /* If a decision tree is supplied with the D option,
                        the no_of_dimensions in there override this value. */
                     break;
         case 'o':   /*File into which the postscript output is written.
                       default = stdout */
                     strcpy(ps_file,optarg);
                     break;
         case 'x':   pminx = atoi(optarg); break;
         case 'X':   pmaxx = atoi(optarg); break;
         case 'y':   pminy = atoi(optarg); break;
         case 'Y':   pmaxy = atoi(optarg); break;
         case 'v':   verbose = TRUE;
                     break;
         case 'h':   /*Header (title) of the display.*/
                     strcpy(title,optarg);
                     break;
         default:    display_help();
     }

 if (!strlen(decision_tree) && !strlen(point_file)) display_help();
 if (pmaxx <= pminx || pmaxy <= pminy) display_help();

 /* set title */
 if (!strlen(title)) 
  {
   if (strlen(point_file)) strcat(title,point_file);
   if (strlen(decision_tree))
     { strcat(title,"-"); strcat(title,decision_tree);}
  }

 if (strlen(decision_tree))
  {
    root = read_tree(decision_tree);
    if (verbose) 
     {
       fprintf(stderr,"Decision tree read from %s.\n",decision_tree);
       fprintf(stderr,"Leaf Count = %d, Tree Depth = %d\n",
            leaf_count(root),tree_depth(root));
     }
  }

 if (strlen(point_file))
  {
    if ((infile = fopen(point_file,"r")) == NULL)
      error("Display : Data file can not be opened. ");
    no_of_samples = load_points(infile,&train_points);
    if (verbose)
     { 
      fprintf(stderr,"%d examples loaded from %s.\n", no_of_samples,point_file);
      fprintf(stderr,"#dimensions = %d, #categories = %d\n",no_of_dimensions,
              no_of_categories);
     }
  }

 if (no_of_dimensions != 2) 
   error("DISPLAY : Only planar datasets and decision trees can be displayed. ");

 no_of_coeffs = no_of_dimensions+1;

 if (!strlen(ps_file)) psfile = stdout;
 else if ((psfile = fopen(ps_file,"w")) == NULL)
  {
     fprintf(stderr,"DISPLAY: Output file can not be opened.");
     psfile=stdout;
  }

 prepare_ps(psfile,title);
 set_extremes();

 if (no_of_samples != 0)
    for (i=1;i<=no_of_samples;i++)
         display_point(psfile,train_points[i]);
 
 if (root != NULL)
  {
    make_box();
    recursive_draw(psfile,root);
  }

 finish_ps(psfile);
}

/************************************************************************/
/* Module name : set_extremes						*/ 
/* Functionality : 	Sets the global variables xmin,xmax,ymin and 	*/
/*			ymax as the minimum and maximum values in the	*/
/*			x and y coordinates. These values are 		*/
/*			subsequently used for scaling.			*/
/* Parameters :	None.							*/
/* Returns :	Nothing.						*/
/* Calls modules : None.						*/
/* Is called by modules :	main					*/
/************************************************************************/
set_extremes()
{
  int i;
  float x1,y1,xmargin,ymargin,xrange,yrange;

  if (no_of_samples == 0)
   {
     xmin = pminx;
     xmax = pmaxx;
     ymin = pminy;
     ymax = pmaxy;
     return;
   }

  xmax = xmin = train_points[1]->dimension[1];
  ymax = ymin = train_points[1]->dimension[2];
  
  for (i=1;i<=no_of_samples;i++)
   {
     x1 = train_points[i]->dimension[1];
     y1 = train_points[i]->dimension[2];
     if (xmax < x1) xmax = x1;
     if (xmin > x1) xmin = x1;
     if (ymax < y1) ymax = y1;
     if (ymin > y1) ymin = y1;
   }

  xrange = xmax-xmin;
  yrange = ymax-ymin;
  
  if ((xmargin = xrange * 0.01) == 0) xmargin = 1;
  if ((ymargin = yrange * 0.01) == 0) ymargin = 1;

  xmin -= xmargin; xmax += xmargin;
  ymin -= ymargin; ymax += ymargin;
}

/************************************************************************/
/* Module name :	display_point					*/ 
/* Functionality :	Displays the category number of a data point	*/
/*			at coordinates specified by its two attribute	*/
/*			values.						*/
/* Parameters :	psfile : File to write PostScript(R) output		*/
/*		p      : Pointer to the POINT structure			*/
/* Returns :	Nothing.						*/
/* Calls modules :	None.						*/
/* Is called by modules : main						*/
/* Important Variables used :	translatex, translatey : Inline function*/
/*				calls, defined in oc1.h, to scale 	*/
/*				coordinates.				*/
/************************************************************************/
display_point(psfile,p)
FILE *psfile;
POINT *p;
{
  float x1,y1;

  x1 = translatex(p->dimension[1]);
  y1 = translatey(p->dimension[2]);

  fprintf(psfile,"%f %f moveto (%d) show stroke\n",
              x1,y1,p->category);
}


/************************************************************************/
/* Module name : recursive_draw						*/
/* Functionality :	Recursively draws a node of the decision tree.	*/
/*			ie., Determines the edge corresponding to the	*/
/*			hyperplane at the current node, displays it,	*/
/*			and recurses on the left and right children.	*/
/* Parameters :	psfile : File to write PostScript(R) output		*/
/*		cur_node : Pointer to anode in the decision tree.	*/
/* Returns :	Nothing.						*/
/* Calls modules :	find_edge					*/
/*			display_edge					*/
/*			recursive_draw					*/
/* Is called by modules :	main					*/
/*				recursive_draw				*/
/************************************************************************/
recursive_draw(psfile,cur_node)
struct tree_node *cur_node;
FILE *psfile;
{
  EDGE l,find_edge();

  if (cur_node == NULL) return;

  l = find_edge(cur_node);
  if (cur_node->parent == NULL)
    display_edge(psfile,l, "Root");
  else
    display_edge(psfile,l, cur_node->label);

  recursive_draw(psfile,cur_node->left);
  recursive_draw(psfile,cur_node->right); 

}


/************************************************************************/
/* Module name : prepare_ps						*/
/* Functionality :	Prepares the PostScript(R) file. i.e., draws	*/
/*			a bounding box, displays the title of the 	*/
/*			box, if any; sets the initial font etc.		*/
/* Parameters :	psfile : File to write PostScript(R) output		*/
/*		title  : Character string title for the display.	*/
/* Returns :	Nothing.						*/
/* Calls modules :	None.						*/
/* Is called by modules :	main					*/
/* Important Variables used :	pmaxx,pminx,pmaxy,pminy : coordinates	*/
/*				of the bounding box. Also used in 	*/
/*				scaling. 				*/
/************************************************************************/
prepare_ps (psfile,title)
char *title;
FILE *psfile;
{
  fprintf (psfile, "%%!\ngsave\n");
  fprintf (psfile, "0.5 setlinewidth\n");
 
  fprintf(psfile,"%d %d moveto %d %d lineto stroke\n", pminx,pminy,pmaxx,pminy);
  fprintf(psfile,"%d %d moveto %d %d lineto stroke\n", pmaxx,pminy,pmaxx,pmaxy);
  fprintf(psfile,"%d %d moveto %d %d lineto stroke\n", pmaxx,pmaxy,pminx,pmaxy);
  fprintf(psfile,"%d %d moveto %d %d lineto stroke\n", pminx,pmaxy,pminx,pminy);
  fprintf (psfile,"/Helvetica findfont 7 scalefont setfont\n");
  fprintf(psfile,"%d %d moveto (%s) show stroke\n",
          pminx+10,pmaxy,title);
}

/************************************************************************/
/* Module name :	finish_ps					*/ 
/* Functionality :	Completes the PostScript(R) file, and closes it.*/
/* Parameters :	psfile : File to write PostScript(R) output		*/
/* Returns :	Nothing.						*/
/* Calls modules :	None.						*/
/* Is called by modules :	main					*/
/************************************************************************/
finish_ps (psfile)
FILE *psfile;
{
    int i;

    fprintf (psfile, "showpage\ngrestore\n");
    fclose (psfile);
}

/************************************************************************/
/* Module name :	find_edge					*/ 
/* Functionality :	Determines the edge (defined by two end points)	*/
/*			corresponding to the hyperplane at the current	*/
/*			node of the decision tree. 			*/
/* Parameters :	cur_node: Node of the decision tree under consideration	*/
/* Returns :	an EDGE structure					*/
/* Calls modules :	intersection					*/
/*			onedge						*/
/*			correct_side					*/
/*			error (util.c)					*/
/* Is called by modules :	recursive_draw				*/
/* Important Variables used :	box : Root of a tree of four nodes, 	*/
/*				each representing an edge of the 	*/
/*				bounding box. 				*/ 
/*				first, second : Boolean variables to	*/
/*				record whether the first (second) end	*/
/*				point of the edge has been found.	*/
/* Remarks :	Two main principles used in finding the edge 		*/
/*		corresponding to a hyperplane are			*/
/*		1. A valid endpoint is formed when the current hyperplane*/
/*		   intersects the hyperplanes at one of its ancestors	*/
/*		   or the bounding box.					*/
/*		2. A valid end point lies on the "correct" side of each	*/
/*		   of the hyperplanes on the path from the root to the	*/
/*		   current node's parent.				*/ 
/*		An underlying assumption is that the decision tree is 	*/
/*		being traversed in pre-order.				*/
/************************************************************************/
EDGE find_edge(cur_node)
struct tree_node *cur_node;
{
 EDGE l;
 struct endpoint p,intersection();
 struct tree_node *cur_ancestor;
 int onedge(),correct_side(),first=FALSE,second = FALSE;

 cur_ancestor = cur_node;
 while (cur_ancestor->parent != NULL) cur_ancestor = cur_ancestor->parent;
 cur_ancestor->parent = box;
 
 cur_ancestor = cur_node->parent;

 while (cur_ancestor != NULL)
  {
   p = intersection(cur_node->coefficients,cur_ancestor->coefficients);

   if ( p.x != HUGE && p.y != HUGE 
        && onedge(p,cur_ancestor->edge)
        && correct_side(p,cur_node))
    {
     if (first == FALSE)
      {
       l.from = p;
       first = TRUE;
       cur_ancestor = cur_ancestor->parent;
       continue;
      }

     if (second == FALSE)
      {
       second = TRUE;
       l.to = p;
       cur_ancestor = cur_ancestor->parent;
       break;
      } 

    
    }
   else
    cur_ancestor = cur_ancestor->parent;
  }
 
 if (first == FALSE || second == FALSE) 
  {
   if (no_of_samples == 0)
    {
     fprintf(stderr,"Can't draw the decision tree in the Unit Square.\n");
     fprintf(stderr,"Try normalizing. \n");
     error("GET_EDGE");
    }
   else
     error("GET_EDGE : Decision tree can't be drawn. Try normalizing.");
  }

 cur_ancestor = cur_node;
 while (cur_ancestor->parent != box) cur_ancestor = cur_ancestor->parent;
 cur_ancestor->parent = NULL; 

 cur_node->edge = l;
 return(l);
}

/************************************************************************/
/* Module name : make_box						*/ 
/* Functionality :	Creates four hypothetical decision tree nodes	*/
/*			to contain the left, right, bottom and top	*/
/*			edges of the bounding box, and links them up	*/
/*			as a 4-level tree. Sets the global variable	*/
/*			"box" to point to the root of this tree.	*/
/* Parameters :	None.							*/
/* Returns :	Nothing.						*/
/* Calls modules :	None.						*/
/* Is called by modules :	main					*/
/* Remarks :	The "box" tree comes handy while trying to find the	*/
/*		the end points of the edge representing a hyperplane,	*/
/*		in the "find_edge" module.				*/
/************************************************************************/
make_box()
{
 struct tree_node *left,*right,*top,*bottom;

 left = (struct tree_node *)malloc(sizeof(struct tree_node));
 left->coefficients = vector(1,no_of_coeffs);
 left->coefficients[1]=1; 
 left->coefficients[2]=0; 
 left->coefficients[3]=-1.0*xmin;

 top = (struct tree_node *)malloc(sizeof(struct tree_node));
 top->coefficients = vector(1,no_of_coeffs);
 top->coefficients[1]=0; 
 top->coefficients[2]=1; 
 top->coefficients[3]=-1.0*ymax;

 right = (struct tree_node *)malloc(sizeof(struct tree_node));
 right->coefficients = vector(1,no_of_coeffs);
 right->coefficients[1]=1; 
 right->coefficients[2]=0; 
 right->coefficients[3]=-1.0*xmax;

 bottom = (struct tree_node *)malloc(sizeof(struct tree_node));
 bottom->coefficients = vector(1,no_of_coeffs);
 bottom->coefficients[1]=0; 
 bottom->coefficients[2]=1; 
 bottom->coefficients[3]=-1.0*ymin;

 (left->edge).from.x = (bottom->edge).to.x   = xmin; 
 (left->edge).from.y = (bottom->edge).to.y   = ymin;
 (left->edge).to.x   = (top->edge).from.x    = xmin;
 (left->edge).to.y   = (top->edge).from.y    = ymax; 
 (top->edge).to.x    = (right->edge).from.x  = xmax;
 (top->edge).to.y    = (right->edge).from.y  = ymax;
 (right->edge).to.x  = (bottom->edge).from.x = xmax;
 (right->edge).to.y  = (bottom->edge).from.y = ymin;

 bottom->parent = right;
 right->parent = top;
 top->parent = left;
 left->parent = NULL;

 box = bottom;
}

/************************************************************************/
/* Module name :	display_edge					*/ 
/* Functionality :	Displays an edge, with an optional character	*/
/*			label.						*/
/* Parameters :	psfile : File to write PostScript(R) output		*/
/*		e      : Pointer to the EDGE structure			*/
/*		label  : Character label to be displayed at the centre 	*/
/*			 of the edge.					*/
/* Returns :	Nothing.						*/
/* Calls modules :	None.						*/
/* Is called by modules : recursive_draw				*/
/* Important Variables used :	translatex, translatey : Inline function*/
/*				calls, defined in oc1.h, to scale 	*/
/*				coordinates.				*/
/************************************************************************/
display_edge (psfile, e, label)
FILE *psfile;
EDGE e;
char *label;
{
    int i;
    struct endpoint p1, p2;
    double x,y;
    double angle;

    p1 = e.from;
    p2 = e.to;
    y = (double)(p2.y - p1.y);
    x = (double)(p2.x - p1.x);
    angle = atan2pi (y,x) * 180;
    if (angle > 90) angle -= 180;
    if (angle < -90) angle += 180;
    fprintf (psfile, "%f %f moveto %f %f lineto stroke\n",
	     translatex (p1.x),
	     translatey (p1.y),
	     translatex (p2.x),
	     translatey (p2.y)
	    );
    if (strlen(label))
    {
        for (i=1;i<=strlen(label);i++) label[i-1] = toupper(label[i-1]);

        fprintf (psfile,"/Helvetica findfont 12 scalefont setfont\n");
	fprintf (psfile, "gsave %f %f moveto %f ",
		 translatex ((p1.x + p2.x)/2),
		 translatey ((p1.y + p2.y)/2),
		 angle);
        fprintf (psfile, "rotate 0 1 rmoveto (%s) show stroke grestore\n",
                 label);
        fprintf (psfile,"/Helvetica findfont 7 scalefont setfont\n");
    }
}


/************************************************************************/
/* Module name : intersection						*/ 
/* Functionality :	Computes the intersection point of two 		*/
/*			hyperplanes.					*/
/* Parameters :	c1,c2 : two coefficient arrays, each of length 3.	*/
/* Returns :	the intersection point, stored in an "endpoint" struct.	*/
/*		(HUGE,HUGE) if there is no intersection.		*/
/* Calls modules :	None.						*/
/* Is called by modules :	find_edge				*/
/************************************************************************/
struct endpoint intersection(c1,c2)
float *c1,*c2;
{
 float denom;
 struct endpoint p;
 

 denom = c2[2] * c1[1] - c2[1] * c1[2];
 if (!denom)
   {
     p.x = HUGE;
     p.y = HUGE;
     return(p);
    }

 p.x = (c2[3] * c1[2] - c2[2] * c1[3]) / denom;
 p.y = (c2[1] * c1[3] - c2[3] * c1[1]) / denom;
 return(p);
 

}

/************************************************************************/
/* Module name : onedge							*/ 
/* Functionality :	Checks if a point lies on an edge.		*/
/* Parameters :	p : pointer to a POINT structure.			*/
/*		e : pointer to an EDGE structure.			*/
/* Returns :	1: if p lies on e					*/
/*		0: otherwise.						*/
/* Calls modules :	None.						*/
/* Is called by modules : find_edge					*/
/************************************************************************/
int onedge(p,e)
struct endpoint p;
EDGE e;
{
 struct endpoint p1,p2;

 p1=e.from;
 p2=e.to;

 if (((p1.x >= p.x && p2.x <= p.x) ||
      (p1.x <= p.x && p2.x >= p.x)) &&
      ((p1.y >= p.y && p2.y <= p.y) ||
      (p1.y <= p.y && p2.y >= p.y))) return(TRUE);
 return(FALSE);
}

/************************************************************************/
/* Module name : correct_side						*/ 
/* Functionality :	Checks if a point lies on the "correct" side of	*/
/*			the hyperplanes at all nodes on the path from	*/
/*			the root of the decision tree to the parent of	*/
/*			the node under consideration. 			*/
/*			ie., the following should hold recursively: if 	*/
/*			"cur_node" is the right child of "cur_node->	*/
/*			parent", then the point should lie on the right	*/
/*			side of the hyperplane at "cur_node->parent".	*/
/*			Same for the left child.			*/
/*			This test makes sure that we draw each hyperplane*/
/*			in the appropriate region.			*/
/* Parameters :	p : pointer to an "endpoint" structure.			*/
/*		    Is an intersection point of the hyperplane at	*/
/*		    cur_node with that at one of its ancestors, or with	*/
/*		    the bounding box.					*/
/*		cur_node : Decision tree node under consideration.	*/
/* Returns :	1: If p is on the correct side of all of cur_node's	*/
/*		   ancestors.						*/
/*		0: otherwise.						*/
/* Calls modules :	None.						*/
/* Is called by modules : find_edge					*/
/* Important Variables used : TOLERANCE : A very small positive number	*/
/*			      defined in oc1.h, needed to compensate	*/
/*			      for peculiarities in floating point	*/
/*			      arithmetic on Unix.			*/
/* Remarks : This assumes that the decision tree is displayed in a	*/
/*	     pre-order traversal.					*/
/************************************************************************/
int correct_side(p,cur_node)
struct endpoint p;
struct tree_node *cur_node;
{
  float sum;
  struct tree_node *node,*parent;

  node = cur_node;

  while ((parent = node->parent) != box)
   {
    sum = 0;

    sum =   parent->coefficients[1] * p.x
          + parent->coefficients[2] * p.y
          + parent->coefficients[3];

    if ((sum <= TOLERANCE && sum >= -1.0 * TOLERANCE) || 
        (node == parent->left && sum < 0) ||
        (node == parent->right && sum > 0))
       node = parent; 
    else break;
   }

  if (parent == box) return (TRUE);
  else return(FALSE);
}

/************************************************************************/
/* Module name : display_help						*/ 
/* Functionality :	Displays the command line options for the	*/
/*			"display" command.				*/
/* Parameters :	None.							*/
/* Returns :	Nothing.						*/
/* Calls modules :	None.						*/
/* Is called by modules :	main					*/
/************************************************************************/
display_help()
{
 fprintf (stderr,"\n\nUsage : display -D:t:o:d:vT:x:X:y:Y:");
 fprintf (stderr,"\nOptions :");
 fprintf (stderr,"\n	-D<File containing the Decision tree>");
 fprintf (stderr,"\n	  (Default: None)");
 fprintf (stderr,"\n	-t or -T <File containing the data points>");
 fprintf (stderr,"\n	  (Default: None)");
 fprintf (stderr,"\n	-o<file to write the PostScript(R) output>");
 fprintf (stderr,"\n	  (Default=stdout)"); 
 fprintf (stderr,"\n	-d<#dimensions> (Default=2)");
 fprintf (stderr,"\n	-v : Verbose (Default=FALSE)");
 fprintf (stderr,"\n	-h<header (title) for the display>");
 fprintf (stderr,"\n	  (Default=<datafile>-<decision tree file>)");
 fprintf (stderr,"\n	-x<minimum x coord for the display>");
 fprintf (stderr,"\n	  (Default=72)");
 fprintf (stderr,"\n	-X<maximum x coord for the display>");
 fprintf (stderr,"\n	  (Default=540)");
 fprintf (stderr,"\n	-y<minimum y coord for the display>");
 fprintf (stderr,"\n	  (Default=72)");
 fprintf (stderr,"\n	-Y<maximum y coord for the display>");
 fprintf (stderr,"\n	  (Default=640)");
 fprintf (stderr,"\n\n");
 exit(0);
 

}

/************************************************************************/
/************************************************************************/