summaryrefslogtreecommitdiff
path: root/graphics/tree/tree.l
diff options
context:
space:
mode:
Diffstat (limited to 'graphics/tree/tree.l')
-rw-r--r--graphics/tree/tree.l1735
1 files changed, 1735 insertions, 0 deletions
diff --git a/graphics/tree/tree.l b/graphics/tree/tree.l
new file mode 100644
index 0000000000..289debbf83
--- /dev/null
+++ b/graphics/tree/tree.l
@@ -0,0 +1,1735 @@
+%{
+/* tree: format trees
+ * Version 1.1 -- Greg Lee, lee@uhccux.uhcc.hawaii.edu, June 24, 1990
+ *
+ * This program is free and in the public domain. Please keep future
+ * versions in the public domain.
+ *
+ * The inspiration for and predecessor to `tree' was a program by
+ * Chris Barker, of the Linguistics Board at University of California,
+ * Santa Cruz, email: barker@ling.ucsc.edu.
+ *
+ * A pattern matching function yylex() is built, which finds tree
+ * definitions in a text; yylex() is called recursively to build
+ * a tree structure in memory; a sequence of formatting operations
+ * is carried out (see printtree()); then the formatted tree is
+ * displayed by tty() or, for TeX code, the function tex().
+ */
+#include <ctype.h>
+
+#define TRUE 1
+#define FALSE 0
+
+/* When formatting for TeX, multiply column widths by this to get better
+ * positioning:
+ */
+#define COLMUL 8
+
+/* The c_ values are from the command line; the real values are taken
+ * from them or from options given after the \tree command.
+ */
+ int tex_opt, c_tex_opt = FALSE; /* generate TeX code? */
+ int utex_opt, c_utex_opt = FALSE;/* generate TeX code with PS? */
+ int gap_opt, c_gap_opt = 2; /* space between subtrees */
+ int black_opt, c_black_opt = 0; /* black triangles */
+ int debug_opt = FALSE; /* tracing? */
+ int quiet_opt, c_quiet_opt = FALSE; /* no warnings */
+ int verbose_opt, c_verbose_opt = FALSE; /* show tex commands? */
+ int lexical_opt, c_lexical_opt = FALSE; /* no lines */
+ int T_opt, c_T_opt = FALSE;
+ int O_opt, c_O_opt = FALSE;
+ int I_opt, c_I_opt = FALSE;
+ int F_opt, c_F_opt = FALSE;
+ int E_opt, c_E_opt = FALSE;
+ int R_opt, c_R_opt = FALSE;
+
+/* count columns before \tree command encountered */
+ int indent = 0;
+/* count caps in name to compensate for extra width */
+ int capscount = 0;
+/* keep track of recursion in yylex() calls to assign nodes to rows */
+ int level = 0;
+ int maxlevel = 0;
+/* source line (not useful now -- need some error checking) */
+ int linenumber = 1;
+
+/* types of nodes */
+#define HBAR 1 /* horizontal bar */
+#define VBAR 2 /* vertical bar */
+#define OBAR 4 /* horizontal overbar */
+#define NODENAME 8 /* named node */
+
+#define NAMEROOM 20000 /* how much to malloc for node names */
+char *buf, *bufp; /* for buffer storing node names */
+
+/* A node has a:
+ * row, from row 1, telling how far from the top of the tree it is;
+ * col, from col 0, how far from the left;
+ * mid, its horizontal mid point, used for vertical alignment;
+ * l, its width in columns;
+ * treeid, an identifying number;
+ * type, whether its a name or a bar of some sort;
+ * attrib, a list of 26 values of attributes bestowed by \<cap>s;
+ * n, pointer to its name if it has one;
+ * and a bunch of pointers to contiguous nodes in the tree.
+ *
+ * Attributes `S' and `U' are used internally; must change this if
+ * there are to be \S or \U commands.
+ */
+typedef struct list {
+ int row, col, mid, l, treeid, type;
+ char attrib[26];
+ char *n;
+ struct list *daughter;
+ struct list *sister;
+ struct list *mother;
+ struct list *right;
+ struct list *left;
+} LIST, *TREE;
+
+/* next number for treeid */
+int treenum = 1;
+
+TREE newnode();
+
+/* global reference by yylex() */
+TREE tree;
+
+#define ERROR(message) fprintf(stderr,"Tree: %s (line %d).\n", \
+ message, linenumber)
+
+/* Next is code for flex to build the yylex() function. There are three
+ * states the pattern matcher can be in:
+ * T, if it's matching text after the \tree command that defines
+ * a tree;
+ * N, if it's echoing text that is not in the scope of a \tree command;
+ * C, if it's discarding comments within the definition of a tree.
+ */
+%}
+
+%s T N C
+
+%%
+<N>\n {
+ indent = 0;
+ linenumber++;
+ ECHO;
+}
+<N>\t {
+ indent++;
+ while (indent % 8) indent++;
+ ECHO;
+}
+<N>. {
+ indent++;
+ ECHO;
+}
+<N>\\tree[ \t\n]*(-([tuvqLTOIFER]+|[bg][0-9]+)[ \t\n]*)*\([ \t\n]* {
+ TREE root;
+
+ setoptions(yytext + 5);
+ level++;
+ if (level > maxlevel) maxlevel = level;
+ root = newnode(level,bufp);
+ tree = root;
+/* do a whole tree: in state T analyze the tree definition
+ * and build the tree; format and display, and resume echoing
+ * text until the next tree definition is found.
+ */
+ BEGIN(T);
+ yylex();
+ printtree(root);
+ maxlevel = 0;
+ BEGIN(N);
+}
+<N>\\tree {
+ if (!quiet_opt) ERROR("ill-formed \\tree command ignored");
+ ECHO;
+}
+<T,C>\([ \t\n]* {
+ TREE node;
+
+ notenewlines(yytext);
+ level++;
+ if (level > maxlevel) maxlevel = level;
+ addchar('\0'); /* terminate last node name */
+ capscount = 0; /* no caps in next name yet */
+ node = newnode(level,bufp);
+/* nodes at same level of embedding are connected together as
+ * sisters; but if current level is greater than that of
+ * the node that was just being made, this next node must be
+ * a daughter of that node.
+ */
+ if (tree->row < level) tree->daughter = node;
+ else tree->sister = node;
+ tree = node;
+ BEGIN(T);
+ yylex();
+ tree = node;
+}
+<T,C>\) {
+ level--;
+ addchar('\0');
+ capscount = 0;
+/* discard text now until the beginning of the next node
+ */
+ BEGIN(C);
+/* this is a return from a yylex() invocation called from yylex().
+ */
+ return;
+}
+<T>[ \t\n]+\\% {
+ notenewlines(yytext);
+ addchar(' ');
+ if (tex_opt || verbose_opt) {
+ addchar('\\');
+ tree->l++;
+ }
+ addchar('%');
+ tree->l += 2;
+}
+<T>\\[%#\&\$] {
+ if (tex_opt || verbose_opt) {
+ addchar('\\');
+ tree->l++;
+ }
+ addchar(yytext[1]);
+ tree->l++;
+}
+<T,C>%.*\n {
+ notenewlines(yytext);
+}
+<T,C>[ \t\n]*%.*\n[ \t\n]*/[\)\(] {
+ notenewlines(yytext);
+}
+<T>\\[MDB][0-9][ \t\n]+ {
+ giveval(tree, yytext[1], yytext[2]);
+}
+<T>\\[MDB][0-9]/[^A-Za-z] {
+ giveval(tree, yytext[1], yytext[2]);
+}
+<T>\\[A-Z][ \t\n]+ {
+ give(tree, yytext[1]);
+}
+<T>\\[A-Z]/[^A-Za-z] {
+ give(tree, yytext[1]);
+}
+<T>\\[ )(\\] {
+ addchar(yytext[1]);
+ tree->l++;
+}
+<T>(\\[`'"^~=.])|(\$[_^]) {
+ if (tex_opt || verbose_opt) {
+ addchar(yytext[0]);
+ addchar(yytext[1]);
+ if (verbose_opt) tree->l += 2;
+ }
+}
+<T>[\${}] {
+ if (tex_opt || verbose_opt) {
+ addchar(yytext[0]);
+ if (verbose_opt) tree->l++;
+ }
+}
+<T>[A-HJ-Z] {
+ addchar(yytext[0]);
+ tree->l++;
+ if (tex_opt && ++capscount > 3) {
+ tree->l++;
+ capscount = 0;
+ }
+}
+<T>. {
+ addchar(yytext[0]);
+ tree->l++;
+}
+<T>\\tree[ \t\n]* {
+ if (!quiet_opt) ERROR("\\tree command found inside tree");
+ notenewlines(yytext);
+ if (tex_opt || verbose_opt) {
+ int i;
+ for (i = 0; i < yyleng; i++) {
+ addchar(yytext[i]);
+ if (verbose_opt) tree->l++;
+ }
+ }
+}
+<T>\\[A-Za-z]+[ \t\n]* {
+ notenewlines(yytext);
+ if (tex_opt || verbose_opt) {
+ int i;
+ for (i = 0; i < yyleng; i++) {
+ addchar(yytext[i]);
+ if (verbose_opt) tree->l++;
+ }
+ }
+}
+
+<T>[ \t\n]+/[\)\(] {
+ notenewlines(yytext);
+}
+<T>[ \t\n]+ {
+ notenewlines(yytext);
+ if (tree->l) {
+ addchar(' ');
+ tree->l++;
+ }
+}
+<C>[^ \t\n\(\)]+ {
+ if (!quiet_opt) ERROR("word after node name ignored");
+}
+<C>. ;
+<C>\n linenumber++;
+
+%%
+
+/* count newlines in string; update linecount; issue warning if
+ * blank line
+ */
+notenewlines(s)
+char *s;
+{ int warn = 0;
+ while (*s) {
+ if (*s == '\n') {
+ if (warn && !quiet_opt)
+ ERROR("blank line within tree");
+ else warn++;
+ linenumber++;
+ }
+ else if (*s != ' ' && *s != '\t') warn = 0;
+ s++;
+ }
+}
+
+/* Called for every \tree in input. Resets option values from defaults
+ * established on command line.
+ */
+setoptions(s)
+char *s;
+{ int c, gap = -1;
+
+ tex_opt = c_tex_opt;
+ utex_opt = c_utex_opt;
+ gap_opt = c_gap_opt;
+ black_opt = c_black_opt;
+ verbose_opt = c_verbose_opt;
+ quiet_opt = c_quiet_opt;
+ lexical_opt = c_lexical_opt;
+ T_opt = c_T_opt;
+ O_opt = c_O_opt;
+ I_opt = c_I_opt;
+ F_opt = c_F_opt;
+ E_opt = c_E_opt;
+ R_opt = c_R_opt;
+
+ while (c = *s++)
+ switch (c) {
+ case 't': tex_opt = TRUE; utex_opt = FALSE; break;
+ case 'u': utex_opt = TRUE; tex_opt = TRUE; break;
+ case 'g': gap = gap_opt = atoi(s); break;
+ case 'b': black_opt = atoi(s); break;
+ case 'v': verbose_opt = TRUE; break;
+ case 'q': quiet_opt = TRUE; break;
+ case 'L': lexical_opt = TRUE; break;
+ case 'T': T_opt = TRUE; break;
+ case 'O': O_opt = TRUE; break;
+ case 'I': I_opt = TRUE; break;
+ case 'F': F_opt = TRUE; break;
+ case 'E': E_opt = TRUE; break;
+ case 'R': R_opt = TRUE; break;
+ case '\n': linenumber++; break;
+ }
+ if (gap >= 0 && tex_opt) gap_opt *= COLMUL;
+}
+
+
+extern char *optarg; /* from getopt */
+extern int optind;
+
+main(argc, argv)
+int argc;
+char *argv[];
+{ int c;
+ char *progname = NULL, *basename();
+
+ if ( (bufp = buf = (char *)malloc(NAMEROOM)) == 0 ) {
+ fprintf(stderr, "can't get memory space\n");
+ exit(1);
+ }
+
+ progname = basename (argv[0]);
+ while ((c = getopt (argc, argv, "hg:tub:vLTOIFERdq")) != EOF)
+ switch (c) {
+ case 'g': c_gap_opt = max(0, atoi(optarg)); break;
+ case 't': c_tex_opt = TRUE; break;
+ case 'u': c_utex_opt = TRUE; c_tex_opt = TRUE; break;
+ case 'b': c_black_opt = max(0, atoi(optarg)); break;
+ case 'v': c_verbose_opt = TRUE; break;
+ case 'd': debug_opt = TRUE; break;
+ case 'q': c_quiet_opt = TRUE; break;
+ case 'L': c_lexical_opt = TRUE; break;
+ case 'T': c_T_opt = TRUE; break;
+ case 'O': c_O_opt = TRUE; break;
+ case 'I': c_I_opt = TRUE; break;
+ case 'F': c_F_opt = TRUE; break;
+ case 'E': c_E_opt = TRUE; break;
+ case 'R': c_R_opt = TRUE; break;
+ case 'h':
+ default:
+ fprintf(stderr, "Usage: %s [options] [files]\n", progname);
+ fprintf(stderr, "options = -gnum\t(gap between subtrees)\n");
+ fprintf(stderr, " -h\t(print this information)\n");
+ fprintf(stderr, " -t\t(TeX code)\n");
+ fprintf(stderr, " -u\t(TeX code w. diagonals)\n");
+ fprintf(stderr, " -bnum\t(black triangles)\n");
+ fprintf(stderr, " -v\t(show TeX commands)\n");
+ fprintf(stderr, " -q\t(quiet)\n");
+ fprintf(stderr, " -L\t(lexical)\n");
+ fprintf(stderr, " -T\t(triangles)\n");
+ fprintf(stderr, " -O\t(omit lines)\n");
+ fprintf(stderr, " -I\t(invert)\n");
+ fprintf(stderr, " -F\t(flatten)\n");
+ fprintf(stderr, " -E\t(even)\n");
+ fprintf(stderr, " -R\t(relational)\n");
+ exit(1);
+ }
+
+ /* doubled column values for tex code */
+ if (c_tex_opt) c_gap_opt *= COLMUL;
+
+ BEGIN(N);
+
+ if (optind >= argc) {
+ (void) yylex ();
+ }
+ else for (; (optind < argc); optind++) {
+ if (yyin == NULL) yyin = stdin;
+ if (freopen (argv[optind], "r", stdin) != NULL) {
+#ifdef FLEX_SCANNER
+ /* to get flex to look at > 1 file */
+ yy_init = 1;
+#endif
+ (void) yylex ();
+ if (level) {
+ fprintf(stderr,"Unbalanced parens in file: %s\n",
+ argv[optind]);
+ exit(1);
+ }
+ }
+ else {
+ (void) fprintf (stderr,
+ "Couldn't open file: %s\n", argv[optind]);
+ exit (1);
+ }
+ }
+ if (level) {
+ fprintf(stderr,"Unbalanced parens.\n");
+ exit(1);
+ }
+}
+
+
+char *basename (s)
+char *s;
+{
+ char *p, *strrchr();
+
+ if (p = strrchr(s, '/'))
+ return(++p);
+ else return(s);
+}
+
+max(a, b)
+int a, b;
+{
+ return ((a > b) ? a : b);
+}
+
+TREE newnode(row, n)
+int row;
+char *n;
+{ TREE temp;
+ int i;
+
+ temp = (TREE) malloc (sizeof (LIST));
+ if (!temp) {
+ ERROR("out of memory");
+ exit(1);
+ }
+ temp->daughter = NULL;
+ temp->sister = NULL;
+ temp->mother = NULL;
+ temp->right = NULL;
+ temp->left = NULL;
+ temp->n = n;
+ temp->l = 0;
+ temp->row = row;
+ temp->col = 0;
+ temp->mid = 0;
+ temp->treeid = treenum++;
+ temp->type = NODENAME;
+ for (i = 0; i < 26; i++) temp->attrib[i] = '\0';
+ if (lexical_opt) give(temp,'L');
+ if (T_opt) give(temp,'T');
+ if (O_opt) give(temp,'O');
+ if (R_opt) give(temp,'R');
+ return (temp);
+}
+
+/* append one node name character in buffer; this is called only
+ * from within yylex().
+ */
+addchar(c)
+char c;
+{
+ *bufp++ = c;
+}
+
+/* after yylex() has built an in-memory tree structure, printtee()
+ * formats and displays it.
+ */
+printtree(root)
+TREE root;
+{ TREE over;
+
+ addbars(root, 0); /* put in VBARs and HBARs */
+ flatbars(root, maxlevel); /* interpret \E and \F commands */
+ rectify(root); /* `left' links for row/col order */
+ addlinks(root); /* miscellaneous initialization */
+ over = newnode(0, NULL); /* preliminary to calling align: */
+ over->daughter = root; /* new node is needed for the */
+ root->mother = root->left = over; /* case of an inverted root */
+ if (I_opt) {
+ /* for side-by-side trees, interpret -I option as meaning that
+ * each tree should be inverted individually
+ */
+ if (root->l) give(root,'I');
+ else if (root->daughter) {
+ TREE node = root->daughter;
+ if (node->type == HBAR) node = node->daughter;
+ if (node->type == VBAR)
+ while (node && node->type == VBAR) {
+ give(node->daughter,'I');
+ node = node->sister;
+ }
+ else while (node) {
+ give(node,'I');
+ node = node->sister;
+ }
+ }
+ }
+ align(root); /* assign column values for */
+ /* vertical alignment */
+ root = over->daughter; /* root will be a different node */
+ /* if it was just inverted */
+ free(over);
+ if (debug_opt) {
+ fprintf(stderr,"\n\n\t------ROOT------\n");
+ debugprint(root);
+ }
+ if (!root->l) { /* remove empty top nodes to get */
+ /* side-by-side trees */
+ TREE old;
+ if (root->daughter) {
+ old = root;
+ root = root->daughter;
+ free(old);
+ }
+ if (root->type == HBAR && root->daughter) {
+ TREE node;
+ old = root;
+ root = root->daughter;
+ free(old);
+ /* mothers of roots are made NULL to block the middle
+ * vertical of an HBAR for tty output
+ */
+ if (root->type == VBAR && root->daughter) {
+ for (node = root; node; node = node->sister)
+ if (node->daughter) node->daughter->mother = NULL;
+ old = root;
+ root = root->daughter;
+ free(old);
+ }
+ }
+ else if (root->type == VBAR && root->daughter) {
+ old = root;
+ root = root->daughter;
+ free(old);
+ }
+ root->mother = NULL;
+ }
+ if (tex_opt) tex(root); /* now display */
+ else tty(root);
+ bufp = buf; /* can reuse name buffer for next tree */
+ freenodes(root);
+}
+
+freenodes(tree)
+TREE tree;
+{ TREE next;
+
+ while (tree) {
+ next = tree->right;
+ free(tree);
+ tree = next;
+ }
+}
+
+
+/* b is from the value given for the -b option */
+int b;
+/* these are the characters used to draw screen trees; the arrays
+ * are indexed by variable b above
+ */
+char tf[] = "_-:|::|-|*"; /* triangle fill */
+char itf[] = "~-:|::|-|*"; /* inverted triangle fill */
+char vb[] = "||:|::||||"; /* vertical bar */
+char lhb[] = "_-.|:._<//"; /* left part of horizontal bar */
+char rhb[] = "_-.|:._>\\\\"; /* right part of horizontal bar */
+char ilhb[] = "~-\"|:\"^<\\\\";/* left of inverted horizontal bar */
+char irhb[] = "~-\"|:\"^>//"; /* right of inverted horizontal bar */
+char lvb[] = "_-.|://<//"; /* left of vertical centerpiece */
+char mvb[] = " +:|: "; /* middle of vertical centerpiece */
+char rvb[] = "_+.|:\\\\>\\\\";/* right of vertical centerpiece */
+char lcb[] = " |:|://///"; /* vertical for left sister */
+char rcb[] = " |:|:\\\\\\\\\\";/* vertical for right sister */
+char lchb[] = "_+ |: "; /* left corner of horizontal bar */
+char rchb[] = "_+ |: "; /* right corner of horizontal bar */
+char ilchb[] = "_+ |: "; /* left corner of inv'd horizontal bar */
+char irchb[] = "_+ |: "; /* right corner of inv'd horizontal bar */
+
+
+/* display tree for screen */
+tty(root)
+TREE root;
+{ TREE node;
+ int row = root->row, col = 0, i;
+
+ if (debug_opt) {
+ putchar('\n');
+ for (col = 0; col < indent; col++) putchar(' ');
+ col = 0;
+ }
+
+ /* display each node, left-to-right and top-to-bottom */
+ for (node = root; node; node = node->right) {
+
+ /* boldness is from \B command or -b option */
+ if (b = has(node,'B')) {
+ if (b == '+') b = 9;
+ else if (isdigit(b)) b -= '0';
+ else b = 0; /* presumably impossible */
+ }
+ else for (b = black_opt; b > 10; b /= 10) ;
+
+ /* newline and indentation */
+ if (node->row > row) {
+ while (node->row > row) { putchar('\n'); row++; }
+ for (col = 0; col < indent; col++) putchar(' ');
+ col = 0;
+ }
+
+ /* spacing between nodes */
+ for ( ; node->col > col; col++) putchar(' ');
+
+ /* disconnect illegitimate sisters created by inversion */
+ if (node->sister && node->sister->mother != node->mother)
+ node->sister = NULL;
+
+ /* display a node in a way appropriate to its type */
+ switch (node->type) {
+ case NODENAME:
+ if (has(node,'P')) /* space over phantom node */
+ for (i = 0; i < node->l; i++) putchar(' ');
+ else printf("%s", node->n);
+ break;
+ case VBAR:
+ /* join all verticals at the base of a triangle */
+ if (has(node,'T') && !has(node,'O')) {
+ char hbar = tf[b];
+ /* no vertical if this is not the first or
+ * only sister
+ */
+ if (has(node,'S') != 'f'
+ && has(node,'S') != 'o') {
+ for (i = 0; i < node->l; i++)
+ putchar(' ');
+ break;
+ }
+ /* use special fill character for base of
+ * inverted triangle
+ */
+ if (node->mother && node->mother->type == OBAR)
+ hbar = itf[b];
+ /* make left edge of base */
+ putchar(vb[b]);
+ /* when only one node at base, length of base
+ * is length of node
+ */
+ if (has(node,'S') == 'o')
+ for (i = 2; i < node->l; i++)
+ putchar(hbar);
+ /* but when there are several nodes at the
+ * base, the base goes from the first to the
+ * last sister
+ */
+ else {
+ while (node->sister
+ && node->mother == node->sister->mother
+ && has(node,'S') != 'l'
+ && node->sister->type == VBAR)
+ node = node->sister;
+ for ( ; node->col > col+1; col++)
+ putchar(hbar);
+ col++;
+ }
+ /* make the right edge of the base */
+ putchar(vb[b]);
+ break;
+ } /* end of code for triangle bases */
+
+ /* space over omitted or phantom lines */
+ if (has(node,'O') || has(node,'P')) putchar(' ');
+ /* possibly do a bold vertical */
+ else if (!blackvbar(node))
+ /* do a plain vertical */
+ putchar(vb[b]);
+ break;
+
+ case HBAR:
+ /* possibly do a bold hbar */
+ if (node->l >= 4 && blackhbar(node)) break;
+ /* otherwise, make the left side, */
+ for (i = 0; i < node->mid; i++) putchar(lhb[b]);
+ /* ... then the middle */
+ if (node->mother) putchar(vb[b]);
+ else putchar(lhb[b]);
+ /* ... then the right side */
+ for (i = 0; i < node->l - node->mid - 1; i++)
+ putchar(rhb[b]);
+ break;
+
+ case OBAR:
+ /* similar to hbar, above */
+ if (node->l >= 4 && blackobar(node)) break;
+ for (i = 0; i < node->mid; i++) putchar(ilhb[b]);
+ if (node->mother && node->right) putchar(vb[b]);
+ else putchar(ilhb[b]);
+ for (i = 0; i < node->l - node->mid - 1; i++)
+ putchar(irhb[b]);
+ break;
+ } /* end of switch */
+
+ col += node->l;
+
+ } /* end of loop to display each node */
+}
+
+
+/* draw horizontal bar with corners missing and a centerpiece */
+blackhbar(node)
+TREE node;
+{ int i, lless;
+
+ /* don't do it if no boldness requested or a \Head has forced
+ * the "midpoint" of the hbar to one end
+ */
+ if (!b || !node->mid || node->mid +1 >= node->l) return(FALSE);
+
+ /* make the center of the bar a little to the left, usually,
+ * for even-length bars, so the two parts of the centerpiece
+ * tend to come under the middle two characters of the name above
+ */
+ lless = (node->l % 2 && b < 8) ? 2 : 1;
+
+ /* the left corner */
+ putchar(lchb[b]);
+
+ /* the left segment before the centerpiece */
+ for (i = lless; i < node->mid; i++) putchar(lhb[b]);
+
+ /* lower levels of bolding look better with a one-char
+ * centerpiece
+ */
+ if (b < 3) {
+ if (lless == 2) putchar(lhb[b]);
+ putchar(mvb[b]);
+ putchar(rhb[b]);
+ }
+ else {
+ /* the two-char centerpiece */
+ putchar(lvb[b]);
+ if (lless == 2) putchar(mvb[b]);
+ putchar(rvb[b]);
+ }
+
+ /* now the right segment before the corner */
+ for (i = 3; i < node->l - node->mid; i++)
+ putchar(rhb[b]);
+
+ /* finally the right corner */
+ putchar(rchb[b]);
+
+ /* yes, we did one */
+ return(TRUE);
+}
+
+/* as above, but for inverted trees */
+blackobar(node)
+TREE node;
+{ int i, lless;
+
+ if (!b || !node->mid || node->mid +1 >= node->l) return(FALSE);
+
+ lless = (node->l % 2 && b < 8) ? 2 : 1;
+ putchar(ilchb[b]);
+ for (i = lless; i < node->mid; i++) putchar(ilhb[b]);
+ if (b < 3) {
+ if (lless == 2) putchar(ilhb[b]);
+ putchar(mvb[b]);
+ putchar(irhb[b]);
+ }
+ else {
+ if (b == 7) putchar(lvb[b]);
+ else putchar(rvb[b]);
+ if (lless == 2) putchar(mvb[b]);
+ if (b == 7) putchar(rvb[b]);
+ else putchar(lvb[b]);
+ }
+ for (i = 3; i < node->l - node->mid; i++)
+ putchar(irhb[b]);
+ putchar(irchb[b]);
+ return(TRUE);
+}
+
+/* draw corner sisters appropriate to horizontal above them */
+blackvbar(node)
+TREE node;
+{
+ /* don't do it when no boldness was asked for, or there is
+ * no node name above, or the hbar above was too short to
+ * be made bold
+ */
+ if (!b || !node->mother || node->mother->l < 4)
+ return(FALSE);
+ /* mark heads */
+ if (b >= 5 && has(node,'H')) {
+ putchar('*');
+ return(TRUE);
+ }
+ /* if it's the first sister, use a corner char */
+ if (has(node,'S') == 'f') {
+ if (node->mother->type == HBAR) {
+ putchar(lcb[b]);
+ return(TRUE);
+ }
+ if (node->mother->type == OBAR) {
+ putchar(rcb[b]);
+ return(TRUE);
+ }
+ }
+ /* likewise if its the last sister, but use the other corner char */
+ else if (has(node,'S') == 'l') {
+ if (node->mother->type == HBAR) {
+ putchar(rcb[b]);
+ return(TRUE);
+ }
+ if (node->mother->type == OBAR) {
+ putchar(lcb[b]);
+ return(TRUE);
+ }
+ }
+ return(FALSE);
+}
+
+/* take care of spacing between daughters of a branching node, and
+ * figure width of the sisters; called by align()
+ */
+sisterbal(tree)
+TREE tree;
+{
+ TREE temp, first, last, head = NULL;
+ int hblen, rlen, bestspace, space, numdaughters = 1, leeway;
+ int join = FALSE;
+
+ /* figure which sisters are to be covered by the bar; mark them
+ * for convenience later in display routines
+ */
+ for (first = tree->daughter; has(first,'O') && first->sister;
+ first = first->sister);
+ for (last = first; last->sister; last = last->sister);
+ while (has(last,'O') && last != first) last = last->left;
+ giveval(first,'S','f');
+ giveval(last,'S','l');
+
+ /* look for heads and nodes that came from the bottom of inverted
+ * subtrees -- we must not try to balance the latter
+ */
+ for (temp = first; temp != last; temp = temp->sister) {
+ numdaughters++ ;
+ if (has(temp, 'H')) head = temp;
+ if (has(temp->sister, 'H')) head = temp->sister;
+ if (has(temp, 'I') == 2) join = TRUE;
+ if (has(temp->sister, 'I') == 2) join = TRUE;
+ }
+
+ /* first approximation to the length of the bar */
+ hblen = (last->col + last->l) - first->col;
+ rlen = (last->col + last->mid + 1/*COLMUL*/) - (first->col + first->mid);
+
+ /* first, try to adjust in a way that does not require
+ * widening the bar
+ */
+ if (numdaughters > 2) bestspace = rlen / (numdaughters - 1);
+ else bestspace = 0;
+ if (!join) for (temp = first; temp != last; temp = temp->sister) {
+ space = temp->sister->col + temp->sister->mid
+ - (temp->col + temp->mid);
+ leeway = rightroom(temp) - gap_opt;
+ if (temp == first && numdaughters == 2) leeway /= 2;
+ if (space > bestspace && leeway > 0) {
+ space -= bestspace;
+ if (space > leeway) space = leeway;
+ moveright(temp, space);
+ if (temp == first) {
+ hblen = (last->col + last->l)
+ - tree->daughter->col;
+ rlen = (last->col + last->mid + 1/*COLMUL*/)
+ - (first->col + first->mid);
+ bestspace = rlen / (numdaughters - 1);
+ }
+ }
+ }
+ bestspace = 0;
+
+ /* then look for the widest space between adjacent sisters, and
+ * widen the space between others to match
+ */
+ if (!join) for (temp = first; temp != last; temp = temp->sister) {
+ if ((space = temp->sister->col + temp->sister->mid
+ - (temp->col + temp->mid)) > bestspace)
+ bestspace = space;
+ }
+ if (!join) for (temp = first; temp != last; temp = temp->sister) {
+ if ((space = temp->sister->col + temp->sister->mid
+ - (temp->col + temp->mid)) < bestspace)
+ moveright(temp->sister, bestspace - space);
+ }
+
+ /* triangles with a single node at their bases are a special case */
+ if (last == first && last->daughter) {
+ hblen = last->daughter->l;
+ last->l = last->daughter->l;
+ last->col = last->daughter->col;
+ giveval(last,'S','o');
+ }
+ /* revise hbar length and fill in lengths */
+ else hblen = (last->col + last->l) - first->col;
+ tree->l = hblen;
+ if (head) tree->mid = head->col + head->mid - first->col;
+ else tree->mid = (hblen - 1) / 2;
+/* ( arguably, when slanty lines will be drawn, the length of the
+ * hbar should be a little less -- must try this some day )
+ */
+
+ /* if the left edge of the hbar is to the right of the left
+ * edge of the first sister, align all the sisters now
+ */
+ if ((space = tree->col - first->col) > 0) {
+ for (temp = tree->daughter; temp; temp = temp->sister)
+ moveright(temp, space);
+ return(0);
+ }
+ /* otherwise, tell align() to move the hbar to the right */
+ return(space);
+}
+
+/* assign col values to nodes for appropriate vertical alignments;
+ * also call for inversion of trees with \Is
+ */
+align(tree)
+TREE tree;
+{ int diff, thisrow;
+ TREE offspring, invert();
+
+ if (tree) {
+ /* the vbar of a relational node has already been aligned */
+ if (has(tree,'R') && tree->type == VBAR) return;
+
+ /* every node has to go at least far enough to the right to
+ * avoid bumping into the node on the left (if any)
+ */
+ if (tree->left && tree->left->row == tree->row)
+ tree->col = tree->left->col + tree->left->l + gap_opt;
+ else tree->col = 0;
+
+ /* force relational nodes to align on the vbar, by artifically
+ * considering the vbar to be at the "midpoint" of the node
+ */
+ if (has(tree,'R') && tree->type == NODENAME && tree->sister) {
+ tree->sister->col = tree->col + tree->l + gap_opt/4;
+ tree->mid = tree->sister->col + tree->sister->mid - tree->col;
+ }
+
+ /* for non-terminal nodes, align the lower parts of the tree
+ * (cyclically), and calculate the displacement required to
+ * line this tree up above its offspring
+ */
+ if (offspring = tree->daughter) {
+ align(offspring);
+ offspring = tree->daughter; /* may have different tree if inverted*/
+ diff = 0;
+ if (tree->type == HBAR) {
+ /* do not change alignment of the top (formerly bottom)
+ * parts of an inverted subtree, since they are already
+ * properly aligned with nodes below them; but the whole
+ * subtree can be moved by its top left node
+ */
+ if (has(tree,'I') == 1) diff = tree->col - offspring->col;
+ else diff = sisterbal(tree);
+ }
+ /* the case of sisters which are not under an hbar can arise
+ * through use of \L; we center the tree over them
+ */
+ else if (has(offspring,'I') != 2 && has(offspring,'I') != 3
+ && offspring->sister && !has(offspring->sister,'R')) {
+ TREE temp, first, last;
+ for (first = offspring; has(first,'O') && first->sister;
+ first = first->sister);
+ for (last = first; last->sister; last = last->sister);
+ if (last == first) first = offspring;
+ else while (has(last,'O') && last != first) last = last->left;
+ for (temp = first; ; temp = temp->sister) {
+ if (has(temp,'H')) first = last = temp;
+ if (temp == last) break;
+ }
+ diff = tree->col + tree->mid
+ - (first->col + first->mid
+ + last->col + last->mid)/2;
+ }
+ /* here the tree has a single daughter; line up the midpoints */
+ else {
+ /* this propagates a mark up the tree that tells the
+ * sisterbal() routine not to change the alignment of
+ * an empty node that has been attached to part of an
+ * inverted tree, because that would undo the work we
+ * did in attaching it
+ */
+ if (has(offspring,'I') == 2) giveval(tree,'I',2);
+ diff = tree->col + tree->mid
+ - (offspring->col + offspring->mid);
+ }
+
+ /* now actually do the alignment by moving either the tree
+ * or the offspring to the right, whichever is required
+ */
+ if (diff > 0) {
+ moveright(offspring, diff);
+ /* move the bar at the right of a relational node along
+ * with the node
+ */
+ if (has(offspring->sister,'R')
+ && offspring->sister->type == VBAR)
+ offspring->sister->col += diff;
+ /* this is a duplication of effort, I think, but it does
+ * have to be done here
+ */
+ else align(offspring->sister);
+ }
+ else if (diff < 0) {
+ tree->col -= diff;
+ if (has(tree->sister,'R')) tree->sister->col -= diff;
+ }
+ }
+
+ /* in the case of a terminal node, there is ordinarily nothing
+ * to do, but it may be possible to align empty nodes with parts of
+ * an inverted subtree beneath them
+ */
+ else if (tree->type == VBAR) { /* a terminal vbar is an "empty node" */
+ /* An inverted subtree is connected to the rest by its upper left
+ * corner, which as been conveniently marked with an I-attribute
+ * value of 3. We are going work our way to the left along the
+ * current row looking for such a corner, then if we find one,
+ * go down one row to the top row of the inverted subtree and
+ * work our way right an equal number of nodes to find a node to
+ * align with. After the corner, nodes in this top row have been
+ * marked with an I-attribute value of 2, so we can tell when
+ * the search has failed.
+ */
+ TREE node = tree, invh = NULL;
+ int bcount = 1;
+ /* first work our way left: */
+ while (node->left && node->left->row == node->row) {
+ if (debug_opt)
+ printf("\nAL: at #%d going left to #%d.",
+ node->treeid,node->left->treeid);
+ if (has(node->left->daughter,'I') == 3) {
+ invh = node->left->daughter;
+ break;
+ }
+ else {
+ node = node->left;
+ bcount++;
+ }
+ }
+ /* then right an equal distance along top of inverted tree */
+ while (bcount && invh && has(invh->sister,'I') == 2) {
+ if (debug_opt)
+ printf("\nAL: at #%d going right to #%d.",
+ invh->treeid,invh->sister->treeid);
+ invh = invh->sister;
+ bcount--;
+ }
+ /* have we found one? yes, if we're still in the inverted
+ * tree and the node is not to the left of us (we can't
+ * move this tree node to the left -- only to the right)
+ */
+ if (has(invh,'I') == 2 && tree->col + tree->mid <= invh->col + invh->mid) {
+ if (debug_opt)
+ printf("\naligning #%d over #%d.\n",
+ tree->treeid,invh->treeid);
+ /* do the alignment */
+ tree->col = invh->col + invh->mid - tree->mid;
+ /* mark as not subject to balancing by sisterbal() */
+ giveval(tree,'I',2);
+ }
+ } /* end alignment of terminal node */
+
+ /* if inversion was requested, do it */
+ if (has(tree,'I') == '+')
+ tree = invert(tree);
+
+ /* recurse left-to-right */
+ align(tree->sister);
+ }
+}
+
+/* do inversion of a tree; much global info in the tree has to be
+ * kept correct, so this is hard; the actual inversion is done
+ * by inv(); invert() is called by align() just above
+ */
+TREE invert(tree)
+TREE tree;
+{ TREE mother, sister, node, inv();
+
+ /* make all nodes in each row sisters; makes inversion easier,
+ * and makes it possible later to move the inverted tree around from
+ * above
+ */
+ makelbranch(tree);
+ /* save these links for later reattachment */
+ mother = tree->mother;
+ sister = tree->sister;
+ tree->sister = NULL;
+ tree = inv(tree, NULL);
+ /* in the special case where a tree has VBARs at the top
+ * after inversion, put an HBAR over the VBARs
+ */
+ if (tree->sister && mother && mother->type == VBAR
+ && tree->type == VBAR && tree->sister->type == VBAR
+ && (!mother->mother || mother->mother->type != HBAR)) {
+ TREE last;
+ for (last = tree->sister;
+ last->sister && last->sister->type == VBAR;
+ last = last->sister)
+ last->mother = mother;
+ last->mother = mother;
+ mother->type = HBAR;
+ giveval(mother,'I',1);
+ mother->l = last->col + last->l - tree->col;
+ mother->mid = (mother->l - 1)/2;
+ }
+ /* otherwise mark the top row so align() can tell that these
+ * nodes are at the top of an inverted tree and can find the
+ * top left corner
+ */
+ else if (mother && !(mother->type == VBAR && has(mother,'O'))) {
+ for (node = tree; node; node = node->sister)
+ giveval(node,'I',2);
+ giveval(tree,'I',3);
+ }
+ /* it's possible that inversion has caused parts of the inverted
+ * tree to bump against things to the left; now check for this
+ * and, to preserve internal alignment, when necessary move the
+ * entire subtree to the right
+ */
+ for (node = tree; node; node = node->daughter) {
+ TREE temp;
+ int room;
+ if (node->left && node->left->row == node->row)
+ if ((room = node->left->col + node->left->l + gap_opt
+ - node->col) > 0)
+ for (temp = tree; temp; temp = temp->sister)
+ moveright(temp, room);
+ }
+ /* if this corner of the tree is a vbar, should a line be drawn
+ * to an hbar above, or an obar below? maybe both -- I really
+ * don't know
+ */
+ tree->mother = mother; /* ?? */
+
+ /* in -L trees, following not quite right */
+ if (mother) {
+ mother->daughter = tree;
+ }
+ /* reattach former sister to rightmost sister of top */
+ while (tree->sister) tree = tree->sister;
+ tree->sister = sister;
+
+ return(tree);
+}
+
+/* see how much a tree could be moved to the right without coming
+ * too close to anything following; called by sisterbal()
+ */
+rightroom(west)
+TREE west;
+{ int mingap = 10000, gap;
+ TREE node, south = NULL;
+
+ if (west) south = west->daughter;
+ else return(0);
+ while (west) {
+ if (west->right && west->row == west->right->row) {
+ gap = west->right->col - west->col - west->l;
+ if (gap < mingap) mingap = gap;
+ }
+ node = south;
+ south = west = NULL;
+ while (node) {
+ west = node;
+ if (node->daughter) south = node->daughter;
+ node = node->sister;
+ }
+ }
+ return(mingap);
+}
+
+/* move a tree right by increasing col values */
+moveright(tree, amount)
+TREE tree;
+int amount;
+{
+ while (tree) {
+ tree->col += amount;
+ if (tree = tree->daughter) {
+ TREE sis;
+ sis = tree->sister;
+ while (sis) {
+ moveright(sis, amount);
+ sis = sis->sister;
+ }
+ }
+ }
+}
+
+/* flip a tree organized as a stack of linked sets of sisters, keeping
+ * left and right links correct; gah!; called by invert()
+ */
+TREE inv(tree,rest)
+TREE tree, rest;
+{ TREE temp, node, right, left, last, lastd;
+ int row;
+
+ if (tree) {
+ temp = tree->daughter;
+ tree->daughter = rest;
+
+ for (node = tree; node; node = node->sister) {
+ if (node->type == HBAR) node->type = OBAR;
+ else if (node->type == OBAR) node->type = HBAR;
+ else if (node->type == VBAR) {
+ /* this is so texvbar() can tell when to invert
+ * arrows when bold verticals have been requested
+ */
+ if (has(node,'U') == 'i') giveval(node,'U','u');
+ else giveval(node,'U','i');
+ }
+ }
+
+ row = tree->row;
+ for (last = tree; last->sister; last = last->sister) ;
+ right = last->right;
+ left = tree->left;
+ node = tree;
+ while (node && node->daughter) {
+ for (last = node; ;) {
+ last->row = node->daughter->row;
+ if (!last->sister) break;
+ last = last->sister;
+ }
+ for (lastd = node->daughter; lastd->sister;
+ lastd = lastd->sister) ;
+ if (lastd->right) last->right = lastd->right;
+ else last->right = node->daughter;
+ if (node->daughter->left)
+ node->left = node->daughter->left;
+ last->right->left = last;
+ if (node->left) node->left->right = node;
+ node = node->daughter;
+ }
+ if (left) node->left = left;
+ else node->left = last;
+ for (last = node; ;) {
+ last->row = row;
+ if (!last->sister) break;
+ last = last->sister;
+ }
+ last->right = right;
+ if (right) right->left = last;
+ if (left) left->right = node;
+
+ if (debug_opt) { fprintf(stderr,"\n\nCalled inv():\n");
+ debugprint(tree); }
+ return(inv(temp,tree));
+ }
+ else return(rest);
+}
+
+/* convert a tree to left-branching; this is a preliminary to inverting a tree;
+ * called by invert()
+ */
+makelbranch(tree)
+TREE tree;
+{ TREE node, east, west, south, last;
+
+ east = west = tree;
+ while (tree) {
+ for (node = east, last = south = NULL; ; node = node->right) {
+ if (node->daughter) {
+ last = node->daughter;
+ if (!south) south = node->daughter;
+ node->daughter = NULL;
+ }
+ if (node == west) break;
+ else node->sister = node->right;
+ }
+ if (west->right == south) west->right = NULL;
+ if (south && south->left == west) south->left = NULL;
+ while (last && last->sister) last = last->sister;
+ west = last;
+ east->daughter = south;
+ tree = east = south;
+ }
+}
+
+/* initialize some links to contiguous nodes, and also lengths and
+ * mid column values
+ */
+addlinks(tree)
+TREE tree;
+{
+ while (tree) {
+ if (tex_opt) tree->l *= COLMUL;
+ tree->mid = (tree->l - 1) / 2;
+ if (tree->right) tree->right->left = tree;
+ if (tree->daughter) tree->daughter->mother = tree;
+ if (tree->sister) tree->sister->mother = tree->mother;
+ tree = tree->right;
+ }
+}
+
+/* for debugging */
+printnode(node)
+TREE node;
+{ int i;
+
+ if (!node) {
+ fprintf(stderr,"NIL");
+ return;
+ }
+ if (node->type == VBAR)
+ fprintf(stderr,"#%d | at %d/%d", node->treeid,
+ node->col, node->row);
+ else if (node->type == HBAR)
+ fprintf(stderr,"#%d _|_ at %d/%d", node->treeid,
+ node->col, node->row);
+ else if (node->type == OBAR)
+ fprintf(stderr,"#%d ^|^ at %d/%d", node->treeid,
+ node->col, node->row);
+ else fprintf(stderr,"#%d=%s at %d/%d", node->treeid, node->n,
+ node->col, node->row);
+ fprintf(stderr,"[");
+ for (i = 0; i < 26; i++) {
+ char c;
+ if ((c = node->attrib[i]) == '+')
+ fprintf(stderr,"%c", 'A'+i);
+ else if (c)
+ fprintf(stderr,"%c=%d", 'A'+i, c);
+ }
+ fprintf(stderr,"]");
+}
+
+/* for debugging */
+debugprint(tree)
+TREE tree;
+{
+ if (tree) {
+ debugprint(tree->daughter);
+ printnode(tree);
+ if (tree->daughter) {
+ fprintf(stderr," DAUGHTER:");
+ printnode(tree->daughter);
+ }
+ if (tree->sister) {
+ fprintf(stderr," SISTER:");
+ printnode(tree->sister);
+ }
+ fprintf(stderr,"\n ");
+ if (tree->mother) {
+ fprintf(stderr," MOM:");
+ printnode(tree->mother);
+ }
+ if (tree->left) {
+ fprintf(stderr," LEFT:");
+ printnode(tree->left);
+ }
+ if (tree->right) {
+ fprintf(stderr," RIGHT:");
+ printnode(tree->right);
+ }
+ fprintf(stderr,"\n");
+ debugprint(tree->sister);
+ }
+}
+
+/* create new VBAR or HBAR node; called by addbars() */
+TREE newbar(model, row, bartype)
+TREE model;
+int row, bartype;
+{ TREE temp;
+ int i;
+
+ temp = newnode(row, NULL);
+ temp->type = bartype;
+ temp->l = 1;
+ for (i = 0; i < 26; i++) temp->attrib[i] = model->attrib[i];
+
+ /* bars get the following attributes only when above empty
+ * nodes (and that is done in addbars() when a NODENAME is
+ * removed)
+ */
+ giveval(temp,'F',0);
+ giveval(temp,'I',0);
+ giveval(temp,'R',0);
+
+ return(temp);
+}
+
+/* test node for value of attribute */
+has(tree, attrib)
+TREE tree;
+char attrib;
+{
+ if (tree && attrib >= 'A' && attrib <= 'Z')
+ return(tree->attrib[attrib - 'A']);
+ else return(0);
+}
+
+/* give value of attribute to node */
+giveval(tree, attrib, val)
+TREE tree;
+char attrib, val;
+{ int prev;
+
+ if (tree && attrib >= 'A' && attrib <= 'Z') {
+ prev = tree->attrib[attrib - 'A'];
+ tree->attrib[attrib - 'A'] = val;
+ return(prev);
+ }
+ else return(0);
+}
+
+/* give `+' value of attribute to node */
+give(tree, attrib)
+TREE tree;
+char attrib;
+{
+ return(giveval(tree, attrib, '+'));
+}
+
+/* stick in VBARs above name nodes, and HBARs under branching nodes;
+ * also remove empty name nodes
+ */
+addbars(tree, addrows)
+TREE tree;
+int addrows;
+{ TREE kin, mother, node, temp;
+ int numsisters;
+
+ if (tree) {
+ /* account for new rows created above by adding bars */
+ tree->row += addrows;
+ /* I don't think maxlevel is used now, but may as well
+ * keep it up to date
+ */
+ if (tree->row > maxlevel) maxlevel = tree->row;
+ /* add no bars directly under node with \L */
+ if (has(tree,'L')) {
+ /* for -F option, propagate F attribute up from a
+ * terminal to dominating \L nodes
+ */
+ if (F_opt && tree->daughter
+ && !has(tree->daughter->daughter,'F')) {
+ give(tree,'F'); /* work up through higher \L nodes */
+ giveval(tree->daughter,'F',0);
+ }
+ /* save reference for following business with R nodes */
+ node = tree;
+ /* go down and add bars to lower parts of tree */
+ tree = tree->daughter;
+ while (tree) {
+ addbars(tree, addrows);
+ tree = tree->sister;
+ }
+ /* for -R, propagate absence of R attribute up from
+ * terminals to dominating \L nodes
+ */
+ if (R_opt && !has(node->daughter,'R'))
+ giveval(node,'R',0);
+ }
+ /* no \L command, so unless this is a terminal, we do want to
+ * add bars under it -- either just a vbar, or for branching
+ * nodes, an hbar and under that a vbar for each sister
+ */
+ else if (tree->daughter) {
+ kin = mother = tree;
+ tree = tree->daughter;
+ /* nodes with \O will not be covered by an hbar, so count
+ * the sisters that will be covered, to decide whether
+ * this should appear as a branching node
+ */
+ for (node = tree, numsisters = 0; node; node = node->sister)
+ if (!has(node,'O')) numsisters++;
+ /* for tty output, a triangle base needs 3 characters,
+ * and for triangles over single daughter nodes, the name
+ * may be too short
+ */
+ if (!tex_opt && numsisters < 2 && tree->l < 3)
+ giveval(kin,'T',0);
+ /* triangles over single daughters do need an hbar, but
+ * otherwise unless there are at least 2 sisters to cover,
+ * no hbar is needed
+ */
+ if (numsisters > 1 || (has(kin,'T')
+ /* need at least one node at base */
+ && numsisters
+ /* a vbar cannot serve as a good base */
+ && tree->l
+ /* would get odd results over inverted tree */
+ && !has(tree,'I')
+ )
+ ) {
+ /* auto-evening for all branching nodes */
+ if (E_opt) give(kin,'E');
+ /* make the hbar and attach it */
+ temp = newbar(kin, tree->row + addrows, HBAR);
+ temp->mother = mother;
+ mother = temp;
+ temp->daughter = tree;
+ kin->daughter = temp;
+ /* shift lower parts of tree down one row */
+ addrows++;
+ kin = temp;
+ }
+ /* now add a vbar above the daughter and each sister */
+ while (tree) {
+ temp = newbar(tree, tree->row + addrows, VBAR);
+ /* whether a vbar is part of a triangle is determined
+ * by node above, not the one below it, and similarly
+ * for bolding and \M labels
+ */
+ giveval(temp,'T',0);
+ giveval(temp,'B',has(mother,'B'));
+ giveval(temp,'M',0);
+ if (mother->type == NODENAME)
+ giveval(temp,'M',has(mother,'M'));
+ if (has(mother,'T') && mother->type == HBAR && !has(temp,'O')) give(temp,'T');
+
+ /* attach the new bar */
+ temp->mother = mother;
+ if (tree == kin->daughter) kin->daughter = temp;
+ else kin->sister = temp;
+ /* finish attachment and work down the tree if this
+ * is a non-empty node
+ */
+ if (tree->l) {
+ temp->daughter = tree;
+ tree->mother = temp;
+ addbars(tree, addrows+1);
+ }
+ /* but if it is an empty node, discard it after copying
+ * attributes that we wouldn't want to lose
+ */
+ else {
+ addbars(tree, addrows);
+ temp->daughter = tree->daughter;
+ if (tree->daughter) tree->daughter->mother = temp;
+ if (has(tree,'F')) give(temp,'F');
+ if (has(tree,'I')) give(temp,'I');
+ giveval(temp,'M',has(tree,'M'));
+ free(tree);
+ }
+ /* make the single-noded base of a triangle wide enough
+ * to cover the name below it, and cause the apex of
+ * such a triangle to be moved downward together with
+ * its base in case there is flattening
+ */
+ if (has(temp,'T') && numsisters == 1) {
+ temp->l = tree->l;
+ if (has(tree,'F')) {
+ give(kin,'F');
+ giveval(tree,'F',0);
+ }
+ }
+ /* vbar takes over any link to sister at right */
+ kin = temp;
+ temp = tree->sister;
+ tree->sister = NULL;
+
+ /* add vertical to the right of relational node */
+ if (has(tree,'R') && tree->type == NODENAME && tree->l
+ && (!has(tree,'L') || has(tree->daughter,'R'))) {
+ TREE rtemp;
+ rtemp = newbar(tree, tree->row, VBAR);
+ give(rtemp,'R');
+ giveval(rtemp,'T',0);
+ giveval(rtemp,'O',0);
+ tree->sister = rtemp;
+ }
+ /* now loop to add vbar to sister, if any */
+ tree = temp;
+ }
+ }
+ /* here it's a terminal node; do flatten it if -F option,
+ * but don't automatically display it as relational for -R opt.
+ */
+ else {
+ if (F_opt) give(tree,'F');
+ if (R_opt) giveval(tree,'R',0);
+ }
+ } /* if (tree) */
+}
+
+/* find lowest node in tree, ignoring inverted subtrees */
+howlow(tree)
+TREE tree;
+{ int row, low = 0;
+
+ while (tree) {
+ if (tree->row > low) low = tree->row;
+ tree = tree->daughter;
+ if (tree && (row = howlow(tree->sister)) > low) low = row;
+ if (tree && tree->type == NODENAME && has(tree,'I')) break;
+ }
+ return(low);
+}
+
+/* increase row numbers */
+movedown(tree, amount)
+TREE tree;
+int amount;
+{
+ while (tree) {
+ tree->row += amount;
+ movedown(tree->sister, amount);
+ tree = tree->daughter;
+ }
+}
+
+/* add VBARs to bring \F'd constituents downward */
+flatbars(tree, bottom)
+TREE tree;
+int bottom;
+{ TREE node, temp, next;
+ int far = bottom;
+
+ if (tree) {
+ if ( (tree->type == NODENAME || (tree->type == HBAR
+ && tree->mother && tree->mother->type == VBAR) )
+ && has(tree,'E') )
+ bottom = howlow(tree);
+ if (!(node = tree->daughter)) {
+ temp = tree->left;
+ if (temp && temp->sister == tree) {
+ node = tree;
+ tree = temp;
+ }
+ }
+ while (node) {
+ next = node->sister;
+ if (next) next->left = node;
+ if (node->daughter) {
+ if (has(node,'F')) far -= howlow(node) - node->row;
+ else flatbars(node, bottom);
+ }
+ if (has(node,'F')) {
+ if (node->type == VBAR) far--;
+ while (node->row < far) {
+ temp = newbar(node, node->row, VBAR);
+ temp->daughter = node;
+ if (has(node,'R') && node->sister) node->sister->row++;
+ else {
+ temp->sister = node->sister;
+ node->sister = NULL;
+ }
+ node->row++;
+ if (node == tree->sister && next) next->left = temp;
+ if (node == tree->daughter) tree->daughter = temp;
+ else if (node == tree->sister) tree->sister = temp;
+ /*else ERROR("flatbars");*/
+ if (!tree->sister) giveval(tree,'T',0);
+ if (node->type == VBAR && has(node,'T'))
+ giveval(node,'T',0);
+ else giveval(temp,'T',0);
+ node->mother = temp; /* ?? */
+ tree = temp;
+ }
+ if (node->daughter) {
+ movedown(node->daughter, node->row + 1
+ - node->daughter->row);
+ }
+ } /* end if (has(node,'F')) */
+ tree = node;
+ node = next;
+ } /* end if (node) */
+ } /* end if (tree) */
+}
+
+/* initialize `left' links in one row of tree; called by rectify() */
+TREE rectifyrow(prev, root, row)
+TREE prev, root;
+int row;
+{ TREE node = root, last = NULL, temp;
+
+ if (node && node->row <= row) {
+ if (node->row == row) {
+ prev->right = node;
+ if (debug_opt) {
+ fprintf(stderr,"\nLINK OF ");
+ printnode(prev);
+ fprintf(stderr," TO ");
+ printnode(node);
+ }
+ last = prev = node;
+ }
+ else if (temp = rectifyrow(prev, node->daughter, row))
+ last = prev = temp;
+ if (temp = rectifyrow(prev, node->sister, row))
+ last = prev = temp;
+ }
+ return(last);
+}
+
+/* initialize `left' links so can traverse tree in row-column order */
+rectify(root)
+TREE root;
+{ TREE node = root;
+ int row;
+
+ for (row = 2; node = rectifyrow(node, root, row); row++) ;
+}
+
+/* all TeX code in is tex.c */
+#include "tex.c"