1% Modifications to tree.tex by D. Roegel, for desc-tex2 2% ----------------------------------------------------- 3% 4% (compare with the original file to see changes) 5% 6% 16 January 1995 D. Roegel (roegel@loria.fr) 7% 8% There are now six kinds of \subtree nodes: 9% 10% These nodes are boxes which are marked through a distinct 11% very small depth. This correspond to a dirty trick 12% mentionned in Appendix D of the TeXbook. 13% 14% \subtree{normal} (depth 0sp) 15% 16% \subtree{unframed;rules:right} (depth 5sp) 17% 18% \subtree{unframed;rules:left,right} (depth 1sp) 19% 20% \subtree{unframed;rules:left} (depth 3sp) 21% 22% \subtree{framed;rules:right} (depth 2sp) 23% 24% \subtree{unframed;norules} (depth 4sp) 25% 26% Case ``unframed;rules:left'' is normally never needed 27% and remains for historical reasons. 28% 29% 30% Note that 1sp is very small since 65536x72.27sp=2.54cm 31% 32% ----------------------------------------------------------------------- 33% Old documentation 34% 35% Tree -- a macro to make aligned (horizontal) trees in TeX 36% 37% Input is of the form 38% \tree 39% item 40% \subtree 41% \leaf{item} 42% . 43% . 44% . 45% \endsubtree 46% \subtree 47% . 48% . 49% . 50% \endsubtree 51% \endsubtree 52% \endtree 53% 54% Nesting is to any level. \leaf is defined as a subtree of one item: 55% \def\leaf#1{\subtree#1\endsubtree}. 56% 57% A structure: 58% \subtree 59% item_part1 60% item_part2 61% . 62% . 63% . 64% 65% will print item_part2 directly below item_part1 as a single item 66% as if they were in a \box. 67% 68% The macro is a 3-pass macro. On the first pass it sets up a data 69% structure from the \subtree ... \endsubtree definitions. On the second pass 70% it recursively calculates the width of each level of the tree. On the third 71% pass it sets up the boxes, glue and rules. 72% 73% By David Eppstein, TUGboat, vol. 6 (1985), no. 1, pp. 31--35. 74% Transcribed by Margaret Kromer (peg), Feb., 1986. 75% 76% Pass 1 77% At the end of pass 1, the tree is coded as a nested collection of \hboxes 78% and \vboxes. 79\newbox\treebox\newcount\treeboxcnt 80%---------------------------------------------------------------------------- 81% Some new things: 82\def\ifequal#1#2{\def\first{#1}\def\second{#2}\ifx\first\second} 83\newif\ifdontframe 84\dontframefalse 85\newif\ifnolinkleft 86\nolinkleftfalse 87\newif\ifnolinkright 88\nolinkrightfalse 89\newif\ifnothing 90\nothingfalse 91\newif\ifrootandsecondfam 92\rootandsecondfamfalse 93\def\framesep{1mm} 94\def\framerule{0.4pt} 95\def\frameseprule{3.24pt} 96%---------------------------------------------------------------------------- 97\def\tree#1{\message{Begin tree}\treeboxcnt=1\global\setbox\treebox=\boxtree{#1}} 98\def\subtree#1{\ettext \advance\treeboxcnt by 1 \boxtree{#1}} 99\def\leaf#1{\subtree{n}#1\endsubtree} 100\def\endsubtree{\ettext \egroup \advance\treeboxcnt-1{}% 101 \ifnum\treeboxcnt=-1 \treeerrora\fi} 102\def\endtree{\endsubtree \ifnum\treeboxcnt>0 \treeerrorb\fi% 103 \settreesizes \typesettree\message{-- end tree}} 104% Error messages for unbalanced tree 105\def\treeerrora{\errhelp=\treeerrorahelp% 106 \errmessage{Unbalanced tree -- too many endsubtrees}} 107\newhelp\treeerrorahelp{There are more subtrees closed than opened} 108\def\treeerrorb{\errhelp=\treeerrorbhelp% 109 \errmessage{Unbalanced tree -- not enough endsubtrees}} 110\newhelp\treeerrorbhelp{Not all the subtrees of the tree are closed. 111If you continue, you'll get some mysterious secondary errors.} 112% Set up \vbox containing root of tree 113\newif\iftreetext\treetextfalse % Whether still aligning text 114\def\boxtree#1{\hbox\bgroup % Start outer box of tree or subtree 115 \baselineskip 2.5ex % Narrow line spacing slightly 116 \tabskip 0pt % No spurious glue in alignment 117 %\kern\framerule 118 %\kern\framesep 119 \vbox\bgroup % Start inner text \vbox 120 \kern\framerule 121 \kern\framesep 122% Some new things: 123 \ifequal{#1}{unframed;rules:left,right}\dontframetrue\fi 124 \ifequal{#1}{framed;rules:right}\nolinklefttrue\fi 125 \ifequal{#1}{unframed;rules:left}\nolinkrighttrue\fi 126 \ifequal{#1}{unframed;norules}\nothingtrue\fi 127 \ifequal{#1}{unframed;rules:right}\rootandsecondfamtrue\fi 128 \treetexttrue % Remember for \ettext 129 \let\par\crcr \obeylines % New line breaks without explicit \cr 130 \halign\bgroup##\hfil\cr} % Start alignment with simple template 131\def\ettext{\iftreetext % Are we still in inner text \vbox? 132 \crcr\egroup 133% Some new things: 134 \kern\framesep 135 \kern\framerule 136 % various depths are added when some flags are set: 137 \ifdontframe\hrule height0ptwidth0ptdepth1sp\fi 138 \dontframefalse 139 \ifnolinkleft\hrule height0ptwidth0ptdepth2sp\fi 140 \nolinkleftfalse 141 \ifnolinkright\hrule height0ptwidth0ptdepth3sp\fi 142 \nolinkrightfalse 143 \ifnothing\hrule height0ptwidth0ptdepth4sp\fi 144 \nothingfalse 145 \ifrootandsecondfam\hrule height0ptwidth0ptdepth5sp\fi 146 \rootandsecondfamfalse 147 \egroup 148 \hskip\frameseprule\relax 149 %\hskip\framerule\relax 150 \fi} % Yes, end alignment and box 151% Pass 2 152% Recursively calculate widths of tree with \setsizes; keep results in 153% \treesizes; \treewidth contains total width calculated so far. \treeworkbox 154% is workspace containing subtree being sized. 155\newbox\treeworkbox 156\def\cons#1#2{\edef#2{\xmark #1#2}} % Add something to start of list 157\def\car#1{\expandafter\docar#1\docar} % Take first element of list 158\def\docar\xmark#1\xmark#2\docar{#1} % ..by ignoring rest in expansion 159\def\cdr#1{\expandafter\docdr#1\docdr#1}% Similarly, drop first element 160\def\docdr\xmark#1\xmark#2\docdr#3{\def#3{\xmark #2}} 161\def\xmark{\noexpand\xmark} % List separator expands to self 162\def\nil{\xmark} % Empty list is just separator 163\def\settreesizes{\setbox\treeworkbox=\copy\treebox% 164 \global\let\treesizes\nil \setsizes} 165\newdimen\treewidth % Width of this part of the tree 166\def\setsizes{\setbox\treeworkbox=\hbox\bgroup% Get a horiz list as a workspace 167 \unhbox\treeworkbox\unskip % Take tree, unpack it into horiz list 168 \inittreewidth % Get old width at this level 169 \sizesubtrees % Recurse through all subtrees 170 \sizelevel % Now set width from remaining \vbox 171 \egroup} % All done, finish our \hbox 172\def\inittreewidth{\ifx\treesizes\nil % If this is the first at this level 173 \treewidth=0pt % ..then we have no previous max width 174 \else \treewidth=\car\treesizes % Otherwise take old max level width 175 \global\cdr\treesizes % ..and advance level width storage 176 \fi} % ..in preparation for next level. 177\def\sizesubtrees{\loop % For each box in horiz list (subtree) 178 \setbox\treeworkbox=\lastbox \unskip % ..pull it off list and flush glue 179 \ifhbox\treeworkbox \setsizes % If hbox, it's a subtree - recurse 180 \repeat} % ..and loop; end loop on tree text 181\def\sizelevel{% 182 \ifdim\treewidth<\wd\treeworkbox % If greater than previous maximum 183 \treewidth=\wd\treeworkbox \fi % Then set max to new high 184 \global\cons{\the\treewidth}\treesizes}% In either case, put back on list 185% Pass 3 186% Recursively typeset tree with \maketree by adding an \hbox containing 187% a subtree (in \treebox) to the horizontal list. 188\newdimen\treeheight % Height of this part of the tree 189\newif\ifleaf % Tree has no subtrees (is a leaf) 190\newif\ifbotsub % Bottom subtree of parent 191\newif\iftopsub % Top subtree of parent 192\def\typesettree{\medskip\maketree\medskip} % Make whole tree 193\def\maketree{\hbox{\treewidth=\car\treesizes % Get width at this level 194 \cdr\treesizes % Set up width list for recursion 195 \makesubtreebox\unskip % Set \treebox to text, make subtrees 196 \ifleaf \makeleaf % No subtrees, add glue 197 \else \makeparent\fi}} % Have subtrees, stick them at right 198{\catcode`@=11 % Be able to use \voidb@x 199\gdef\makesubtreebox{\unhbox\treebox % Open up tree or subtree 200 \unskip\global\setbox\treebox\lastbox % Pick up very last box 201 \ifvbox\treebox % If we're already at the \vbox 202 \global\leaftrue \let\next\relax % ..then this is a leaf 203 \else \botsubtrue % Otherwise, we have subtrees 204 \setbox\treeworkbox\box\voidb@x % Init stack of processed subs 205 \botsubtrue \let\next\makesubtree % ..and call \maketree on them 206 \fi \next}} % Finish up for whichever it was 207\def\makesubtree{\setbox1\maketree % Call \maketree on this subtree 208 \unskip\global\setbox\treebox\lastbox % Pick up box before it 209 \treeheight=\ht1 % Get height of subtree we made 210 \advance\treeheight 2ex % Add some room around the edges 211 \ifhbox\treebox \topsubfalse % If picked up box is a \vbox, 212 \else \topsubtrue \fi % ..this is the top, otherwise not 213 \addsubtreebox % Stack subtree with the rest 214 \iftopsub \global\leaffalse % If top, remember not a leaf 215 \let\next\relax \else % ..(after recursion), set return 216 \botsubfalse \let\next\makesubtree % Otherwise, we have more subtrees 217 \fi \next} % Do tail recursion or return 218\def\addsubtreebox{% 219 \setbox\treeworkbox=\vbox{\subtreebox\unvbox\treeworkbox}} 220\def\subtreebox{\hbox\bgroup % Start \hbox of tree and lines 221 \ifdim\dp1=2sp\def\norules{1}% 222 \else\def\norules{0}% 223 \fi 224 \vbox to \treeheight\bgroup % Start \vbox for vertical rules 225 \ifbotsub \iftopsub \vfil % If both bottom and top subtree 226 \if\norules1% 227 \hrule height0pt width 0.4pt 228 \else 229 \hrule width 0.4pt % ..vertical rule is just a dot 230 \fi 231 \else \treehalfrule{\norules}\fi \vfil % Bottom gets half-height rule 232 \else \iftopsub 233 \vfil \treehalfrule{\norules}% Top gets half-height the other way 234 \else \if\norules1\hrule width 0.4pt height 0pt\kern\treeheight 235 \else 236 \hrule width 0.4pt height \treeheight 237 \fi 238 \fi\fi % Middle, full height 239 \egroup % Finish vertical rule \vbox 240 %\treectrbox{\hrule width 1em}\hskip 0.2em\treectrbox{\box1}\egroup} 241% Some new things: 242 \if\norules1% 243 \treectrbox{\hrule width 1em height0pt}% 244 \else 245 \treectrbox{\hrule width 1em}% 246 \fi 247 \treectrbox{\box1 248 % this rule enforces the depth to be 0pt, 249 % and avoids transmission of this depth 250 % towards the left 251 \hrule width0ptheight0ptdepth0pt 252 }\egroup} 253\def\treectrbox#1{{\setbox0=\vbox{#1}% 254 \ifdim\dp0=2sp 255 \gdef\newdp{2}% 256 \else 257 \gdef\newdp{0}% 258 \fi 259 \ifdim\dp0=1sp\gdef\newdp{1}\fi 260 \vbox to \treeheight{\vfil\box0\vfil 261 \hrule width0ptheight0ptdepth\newdp sp}}} 262\def\treehalfrule#1{\dimen\treeworkbox=\treeheight % Get total height 263 \divide\dimen\treeworkbox 2% 264 \advance\dimen\treeworkbox 0.2pt % Divide by two, add half horiz height 265 \if#11\hrule width 0.4pt height 0pt\kern\dimen\treeworkbox 266 \else \hrule width 0.4pt height \dimen\treeworkbox 267 \fi 268 }% Make a vertical rule that high 269% Some new things: 270% The frame is partly put *inside* the box, since we do not want 271% to change the dimensions of the resulting box (see \ettext) 272\def\ifdepth#1#2#3{\ifdim\dp\treebox=#1sp\gdef\newdp{#2}\gdef\newdpl{#3}\fi} 273\def\noframedtreebox#1{\hbox{\kern\framerule\kern\framesep 274 \vbox{\kern\framerule\kern\framesep 275 \box\treebox 276 \kern\framerule\kern\framesep 277 #1}% 278 \kern\framerule\kern\framesep}} 279\def\makeleaf{\gdef\newdpl{0}\gdef\newdp{0}% 280 \ifdepth{2}{2}{0}% 281 \ifdepth{1}{1}{1}% 282 \ifdepth{3}{1}{3}% 283 \ifdepth{4}{2}{3}% 284 \ifdepth{5}{2}{3}% 285 \ifdim\dp\treebox=1sp 286 \noframedtreebox{}% 287 \else 288 \if\newdpl3 289 \ifdim\dp\treebox=5sp\gdef\newdpl{0}\fi 290 \noframedtreebox{\hrule height0ptwidth0ptdepth\newdp sp}% 291 \else 292 \vbox{\hrule 293 \hbox{\vrule\kern\framesep 294 \vbox{%\kern\framesep 295 \box\treebox 296 %\kern\framesep 297 }% 298 \kern\framesep 299 \vrule 300 }% 301 \hrule 302 \hrule height0ptwidth0ptdepth\newdp sp 303 }% 304 \fi 305 \fi 306 }% % Add leaf box to horiz list 307% This is an alternative definition giving braces: 308%\def\makeleaf{\vbox{\hbox{$\left\{\vcenter{\box\treebox}\right.$}\kern0pt}}% 309%\def\makeleaf{\box\treebox}% original definition 310\def\makeparent{\ifdim\ht\treebox>% 311 \ht\treeworkbox % If text is higher than subtrees 312 \treeheight=\ht\treebox % ..use that height 313 \else \treeheight=\ht\treeworkbox \fi % Otherwise use height of subtrees 314 \advance\treewidth-\wd\treebox % Take remainder of level width 315 \advance\treewidth 1em % ..after accounting for text and glue 316 %\treectrbox{\box\treebox}\hskip 0.2em % Add text, space before connection 317 \treectrbox{\makeleaf}%\hskip 0.2em 318 \if\newdpl3% 319 \treectrbox{\hrule height 0pt width \treewidth}% 320 \else 321 \treectrbox{\hrule height 0.4pt width \treewidth}% 322 \fi 323 \treectrbox{\box\treeworkbox}} % Add \hrule, subs 324 325 326 327 328