// Project 2 for CMSC 838P
// Charles B. Cranston xxx-yy-zzzz <zben@ni.umd.edu>
// May 19, 1997

#include "bstring.h"
#include <set.h>
#include <stdio.h>
#include <string.h>
#include "PSOutFile.h"

// This program accepts a general tree in parent-sibling pairs and
//  creates the PostScript to print a diagram of the tree.  If more
//  than one physical page is required, it produces the PostScript
//  to tile the diagram with multiple pieces of paper.

// DEBUG: TESTING NEW PSOUTFILE

const int TOPP = 300;
const int LEFT = 200;

// Define pagesize and printing limits margins for PostScript printer

const int pagewide = 612;	// 72 x 8.5
const int pagehite = 792;	// 72 x 11
const int leftmarg = 18;	// Quarter inch left margin
const int ritemarg = 18;	// Quarter inch right margin
const int toppmarg = 36;	// Half inch top margin
const int bottmarg = 36;	// Half inch bottom margin

// Constants for the tree printing itself

const int leafhite = 20;	// Height for leaf node on paper
const int charwide = 6;		// Avg width of char in points
const char EOL = '\n';


// Construct to iterate through a STL container
// (Inspired by BP's support software for his CMSC430 course)
//     foreach (iterator-name,container-type,containter-name)
// ex: foreach (node,NodeSet,allnodes) { loop-body }

#define foreach(i,t,c) for(t::iterator i=(c).begin();(c).end()!=i;i++)


// -----------------------  TREE NODE UTILITIES  -----------------------
// Data structure for tree nodes.  Each node contains a pointer to
//  its parent node (which is only tested for null/non-null in this
//  program and an STL "set" of the nodes children.  Note that it
//  inherits from the bstring.h string type.

class NodeMem: public string {
public:
	class pnless {			// Functor to compare two NodeMem*s
	public: bool operator() (NodeMem *x, NodeMem *y) const {
			return ( (*x).compare(*y) < 0 );
		}
	};

	typedef NodeMem &Node;			// Usually work with refs
	typedef set<NodeMem *,pnless> NodeSet;	// STL "set" of Nodes

	NodeMem(char * name): string(name), parent(NULL) {}	// Constructor

	// Adding a child puts the child in the parent's set of children
	// and sets the child's parent-pointer to point to the parent.
	addchild(Node child) {
		if ( NULL != (child.parent) )
			cerr << "Duplicate parent!" << EOL;
		child.parent = this;
		children.insert(&child);
	}

	bool isleaf() { return( children.empty() ); }
	
	bool isroot() { return( NULL == parent); }

	Node getbig() { return( *(this->parent) ); }

	// Survey subtree keeping track of max depth and total num nodes
	dumptree(int deep, int &depth, int &total) {
		if ( isleaf() ) {
			if (depth < deep)
				depth = deep;
		} else {
			foreach (nit,NodeSet,this->children)
				(*nit)->dumptree(deep+1,depth,total);
		}
		total++;
	}

	// Write out PostScript to print tree on paper.
	int writeout(PSOutFile &out, int left, int top, int &right) {
		int height;
		int next = left + 16 * charwide;
		if ( isleaf() ) {
			height = leafhite;
			if (right < next)
				right = next;
		} else {
			height = 0;
			int nend = left + charwide*( length() ); // this.length()
			int vmid = 9999;
			int fmid = 9999;
			foreach (nit,NodeSet,this->children) {
				int subhite = (*nit)->writeout(out,
					next+20,top-height,right);
				vmid = top - height - (subhite/2);
				if (9999 == fmid)
					fmid = vmid;
				out.drawline(next,vmid,next+16,vmid);
				height += subhite;
			}
			if (vmid != fmid)
				out.drawline(next,fmid,next,vmid);
			vmid = top - (height/2);
			out.drawline(nend,vmid,next,vmid);
		}
		out.drawname(left,top-(height/2)-3,this);
		return(height);
	}

private:
	NodeMem	*parent;	// Unique big Node
	NodeSet	children;	// Set of little Nodes
};

typedef NodeMem::Node Node;
typedef NodeMem::NodeSet NodeSet;

// Do quick lookup on given name, returns iterator
NodeSet::iterator findnode(NodeSet &set, char *name) {
	string s(name);
	return( set.find((NodeMem *)&s) ); // **UGLY!!!**
}

// Search for Node data structure for a given name.
// If does not already exist then insert new one.
// Uses built-in fast find rather than general find algorithm.
Node getnode(NodeSet &set, char *name) {
	NodeMem *node = new NodeMem(name);
	NodeSet::iterator nit = set.find(node);
	if ( set.end() != nit ) {
		delete node;
		return(**nit);
	} else {
		set.insert(node);
		return(*node);
	}
}

// -----------------------  TREE PRINTING PROGRAM  -----------------------
// Big set of all Nodes used for input lookup.

NodeSet allnodes;

// Read the input data and build the Node sets.
// Data is:  child <tab> parent <newline>
readin(FILE *infile) {
	int numrel = 0;
	char buff[80];

	while ( fgets(buff,80,infile) ) {
		buff[strlen(buff)-1] = 0;	// Kill newline
		char *cp = strchr(buff,'\t');	// Separate names
		*cp++ = 0;
		Node parent = getnode(allnodes,cp);
		Node child  = getnode(allnodes,buff);
		parent.addchild(child);
		numrel++;
	}
	cerr << "readin: " << numrel << " relations "
	     << allnodes.size() << " nodes." << EOL;
}

// The main event
main() {
	FILE *f = fopen("treedata","r");
	readin(f);

	foreach (nit,NodeSet,allnodes) {
		if ( (*nit)->isroot() ) {
			int depth = 0;
			int total = 0;
			(*nit)->dumptree(1,depth,total);
			cerr << **nit << " " << depth << '/' << total << EOL;
		}
	}

	char buff[80];
	PSOutFile out(cout,
	    pagewide,leftmarg,ritemarg,pagehite,toppmarg,bottmarg);

	while ( fgets(buff,80,stdin) ) {
		buff[strlen(buff)-1] = 0;
		NodeSet::iterator nit = findnode(allnodes,buff);
		if ( allnodes.end() == nit ) {
	 		cerr << "main: " << buff << " not found." << EOL;
		} else {
			Node root = **nit;
			cerr << buff << EOL;
			if ( !root.isroot() )
				cerr << "main: big " << root.getbig() << EOL;
			out.beginjob();
			int right = LEFT;
			int hite = root.writeout(out,LEFT+5,TOPP,right);
		//	out.drawrect(LEFT,TOPP-hite,right-LEFT,hite);
		//	out.endjob(LEFT,TOPP-hite,right-LEFT,hite);
			out.endjob();
		}
	}
}

// End of trees.cxx