%{
/* tree: format trees
* Version 1.1 -- Greg Lee, [email protected], 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: [email protected].
*
* 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"