1
% Tree -- a macro to make aligned (horizontal) trees in TeX
20
% Nesting is to any level. \leaf is defined as a subtree of one item:
21
% \def\leaf#1{\subtree#1\endsubtree}.
31
% will print item_part2 directly below item_part1 as a single item
32
% as if they were in a \box.
34
% The macro is a 3-pass macro. On the first pass it sets up a data
35
% structure from the \subtree ... \endsubtree definitions. On the second pass
36
% it recursively calculates the width of each level of the tree. On the third
37
% pass it sets up the boxes, glue and rules.
39
% By David Eppstein, TUGboat, vol. 6 (1985), no. 1, pp. 31--35.
40
% Transcribed by Margaret Kromer (peg), Feb., 1986.
43
% At the end of pass 1, the tree is coded as a nested collection of \hboxes
45
\newbox\treebox\newcount\treeboxcnt
46
\def\tree{\message{Begin tree}\treeboxcnt=1\global\setbox\treebox=\boxtree}
47
\def\subtree{\ettext \advance\treeboxcnt by 1 \boxtree}
48
\def\leaf#1{\subtree#1\endsubtree}
49
\def\endsubtree{\ettext \egroup \advance\treeboxcnt-1{}%
50
\ifnum\treeboxcnt=-1 \treeerrora\fi}
51
\def\endtree{\endsubtree \ifnum\treeboxcnt>0 \treeerrorb\fi%
52
\settreesizes \typesettree \message{-- end tree}}
53
% Error messages for unbalanced tree
54
\def\treeerrora{\errhelp=\treeerrorahelp%
55
\errmessage{Unbalanced tree -- too many endsubtrees}}
56
\newhelp\treeerrorahelp{There are more subtrees closed than opened}
57
\def\treeerrorb{\errhelp=\treeerrorbhelp%
58
\errmessage{Unbalanced tree -- not enough endsubtrees}}
59
\newhelp\treeerrorbhelp{Not all the subtrees of the tree are closed.
60
If you continue, you'll get some mysterious secondary errors.}
61
% Set up \vbox containing root of tree
62
\newif\iftreetext\treetextfalse % Whether still aligning text
63
\def\boxtree{\hbox\bgroup % Start outer box of tree or subtree
64
\baselineskip 2.5ex % Narrow line spacing slightly
65
\tabskip 0pt % No spurious glue in alignment
66
\vbox\bgroup % Start inner text \vbox
67
\treetexttrue % Remember for \ettext
68
\let\par\crcr \obeylines % New line breaks without explicit \cr
69
\halign\bgroup##\hfil\cr} % Start alignment with simple template
70
\def\ettext{\iftreetext % Are we still in inner text \vbox?
71
\crcr\egroup \egroup \fi} % Yes, end alignment and box
73
% Recursively calculate widths of tree with \setsizes; keep results in
74
% \treesizes; \treewidth contains total width calculated so far. \treeworkbox
75
% is workspace containing subtree being sized.
77
\def\cons#1#2{\edef#2{\xmark #1#2}} % Add something to start of list
78
\def\car#1{\expandafter\docar#1\docar} % Take first element of list
79
\def\docar\xmark#1\xmark#2\docar{#1} % ..by ignoring rest in expansion
80
\def\cdr#1{\expandafter\docdr#1\docdr#1}% Similarly, drop first element
81
\def\docdr\xmark#1\xmark#2\docdr#3{\def#3{\xmark #2}}
82
\def\xmark{\noexpand\xmark} % List separator expands to self
83
\def\nil{\xmark} % Empty list is just separator
84
\def\settreesizes{\setbox\treeworkbox=\copy\treebox%
85
\global\let\treesizes\nil \setsizes}
86
\newdimen\treewidth % Width of this part of the tree
87
\def\setsizes{\setbox\treeworkbox=\hbox\bgroup% Get a horiz list as a workspace
88
\unhbox\treeworkbox\unskip % Take tree, unpack it into horiz list
89
\inittreewidth % Get old width at this level
90
\sizesubtrees % Recurse through all subtrees
91
\sizelevel % Now set width from remaining \vbox
92
\egroup} % All done, finish our \hbox
93
\def\inittreewidth{\ifx\treesizes\nil % If this is the first at this level
94
\treewidth=0pt % ..then we have no previous max width
95
\else \treewidth=\car\treesizes % Otherwise take old max level width
96
\global\cdr\treesizes % ..and advance level width storage
97
\fi} % ..in preparation for next level.
98
\def\sizesubtrees{\loop % For each box in horiz list (subtree)
99
\setbox\treeworkbox=\lastbox \unskip % ..pull it off list and flush glue
100
\ifhbox\treeworkbox \setsizes % If hbox, it's a subtree - recurse
101
\repeat} % ..and loop; end loop on tree text
103
\ifdim\treewidth<\wd\treeworkbox % If greater than previous maximum
104
\treewidth=\wd\treeworkbox \fi % Then set max to new high
105
\global\cons{\the\treewidth}\treesizes}% In either case, put back on list
107
% Recursively typeset tree with \maketree by adding an \hbox containing
108
% a subtree (in \treebox) to the horizontal list.
109
\newdimen\treeheight % Height of this part of the tree
110
\newif\ifleaf % Tree has no subtrees (is a leaf)
111
\newif\ifbotsub % Bottom subtree of parent
112
\newif\iftopsub % Top subtree of parent
113
\def\typesettree{\medskip\maketree\medskip} % Make whole tree
114
\def\maketree{\hbox{\treewidth=\car\treesizes % Get width at this level
115
\cdr\treesizes % Set up width list for recursion
116
\makesubtreebox\unskip % Set \treebox to text, make subtrees
117
\ifleaf \makeleaf % No subtrees, add glue
118
\else \makeparent \fi}} % Have subtrees, stick them at right
119
{\catcode`@=11 % Be able to use \voidb@x
120
\gdef\makesubtreebox{\unhbox\treebox % Open up tree or subtree
121
\unskip\global\setbox\treebox\lastbox % Pick up very last box
122
\ifvbox\treebox % If we're already at the \vbox
123
\global\leaftrue \let\next\relax % ..then this is a leaf
124
\else \botsubtrue % Otherwise, we have subtrees
125
\setbox\treeworkbox\box\voidb@x % Init stack of processed subs
126
\botsubtrue \let\next\makesubtree % ..and call \maketree on them
127
\fi \next}} % Finish up for whichever it was
128
\def\makesubtree{\setbox1\maketree % Call \maketree on this subtree
129
\unskip\global\setbox\treebox\lastbox % Pick up box before it
130
\treeheight=\ht1 % Get height of subtree we made
131
\advance\treeheight 2ex % Add some room around the edges
132
\ifhbox\treebox \topsubfalse % If picked up box is a \vbox,
133
\else \topsubtrue \fi % ..this is the top, otherwise not
134
\addsubtreebox % Stack subtree with the rest
135
\iftopsub \global\leaffalse % If top, remember not a leaf
136
\let\next\relax \else % ..(after recursion), set return
137
\botsubfalse \let\next\makesubtree % Otherwise, we have more subtrees
138
\fi \next} % Do tail recursion or return
139
\def\addsubtreebox{\setbox\treeworkbox=\vbox{\subtreebox\unvbox\treeworkbox}}
140
\def\subtreebox{\hbox\bgroup % Start \hbox of tree and lines
141
\vbox to \treeheight\bgroup % Start \vbox for vertical rules
142
\ifbotsub \iftopsub \vfil % If both bottom and top subtree
143
\hrule width 0.4pt % ..vertical rule is just a dot
144
\else \treehalfrule \fi \vfil % Bottom gets half-height rule
145
\else \iftopsub \vfil \treehalfrule % Top gets half-height the other way
146
\else \hrule width 0.4pt height \treeheight \fi\fi % Middle, full height
147
\egroup % Finish vertical rule \vbox
148
\treectrbox{\hrule width 1em}\hskip 0.2em\treectrbox{\box1}\egroup}
149
\def\treectrbox#1{\vbox to \treeheight{\vfil #1\vfil}}
150
\def\treehalfrule{\dimen\treeworkbox=\treeheight % Get total height
151
\divide\dimen\treeworkbox 2%
152
\advance\dimen\treeworkbox 0.2pt % Divide by two, add half horiz height
153
\hrule width 0.4pt height \dimen\treeworkbox}% Make a vertical rule that high
154
\def\makeleaf{\box\treebox} % Add leaf box to horiz list
155
\def\makeparent{\ifdim\ht\treebox>%
156
\ht\treeworkbox % If text is higher than subtrees
157
\treeheight=\ht\treebox % ..use that height
158
\else \treeheight=\ht\treeworkbox \fi % Otherwise use height of subtrees
159
\advance\treewidth-\wd\treebox % Take remainder of level width
160
\advance\treewidth 1em % ..after accounting for text and glue
161
\treectrbox{\box\treebox}\hskip 0.2em % Add text, space before connection
162
\treectrbox{\hrule width \treewidth}%
163
\treectrbox{\box\treeworkbox}} % Add \hrule, subs
164
% No idea what \spouse is supposed to do... wasn't included