/*  File   : tree2tex.c
    Author : Richard A. O'Keefe
    Updated: %G%
    Purpose: Take "Newick" trees and plot them using LaTeX.

    Requires:
	the "qtree" package for LaTeX.  If you don't already have it,
	you can find qtree.sty at
	http://www.ling.upenn.edu/advice/latex/qtree/

    Method:
	cc -o tree2tex tree2tex.c
	yourprog <characters.dat >yourprog.tree
	./tree2tex <yourprog.tree >yourprog.tex
	latex yourprog.tex
	dvips -o yourprog.ps yourprog.dvi

    Beware:
	(1) The tree is printed in landscape mode so as to fit more nodes
	    in, but even so, 30 is about the practical limit.
	(2) qtree.sty was developed for linguistic trees, not phylogenies,
	    so it can't handle trees more than 20 levels deep.
	In short, this is a quick hack for COSC348 assignment 3, NOT a
	general solution.  For a general solution, look up 'graphviz',
	'daVinci', 'Phylodendron' and others.
*/
#include <stdio.h>
#include <stdlib.h>

typedef struct Node *Tree;
struct Node {
    struct Node *left, *right;
    int datum;
    int label;
};

static Tree read_tree(void) {
    int c;
    Tree t = malloc(sizeof *t);

    if (t == 0) abort();
    c = getchar();
    if (c == '(') {
	Tree x, y;

	x = read_tree();
	c = getchar();
	if (c != ',') abort();
	y = read_tree();
	c = getchar();
	if (c != ')') abort();
	
	if (x->datum <= y->datum) {
	    t->left = x, t->right = y, t->datum = x->datum;
	} else {
	    t->left = y, t->right = x, t->datum = y->datum;
	}
    } else {
	int n = 0;

	while ('0' <= c && c <= '9') {
	    n = n*10 + (c-'0');
	    c = getchar();
	}
	ungetc(c, stdin);
	t->left = t->right = 0;
	t->datum = n;
    }
    return t;
}

static void print_tree(Tree t) {
    if (t->left == 0) {
	printf(" %d", t->datum);
    } else {
	printf(" [");
	print_tree(t->left);
	print_tree(t->right);
	printf(" ]");
    }
}

int main(void) {
    Tree t = read_tree();

    printf("\\documentclass{article}\n");
    printf("\\usepackage{qtree}\n");
    printf("\\usepackage{lscape}\n");
    printf("\\begin{document}\n");
    printf("\\begin{landscape}\n");
    printf("\\hskip -1.0in\n");
    printf("\\Tree");
    print_tree(t);
    printf("\n");
    printf("\\end{landscape}\n");
    printf("\\end{document}\n");
    return 0;
}