| 1 |
1026 |
ivang |
% treedef.tex
|
| 2 |
|
|
%
|
| 3 |
|
|
% These definitions for tree macros are taken from "Trees in TeX",
|
| 4 |
|
|
% by David Eppstein, as published in TUGboat 6#1, March 1985.
|
| 5 |
|
|
% David Eppstein's address (as of 15 June 1988) is
|
| 6 |
|
|
% Computer Science Department
|
| 7 |
|
|
% Columbia University
|
| 8 |
|
|
% New York, NY 10027
|
| 9 |
|
|
% Eppstein@cs.Columbia.edu
|
| 10 |
|
|
%
|
| 11 |
|
|
% Tree -- a macro to make aligned (horizontal) trees in TeX
|
| 12 |
|
|
%
|
| 13 |
|
|
% Input is of the form
|
| 14 |
|
|
% \tree
|
| 15 |
|
|
% item
|
| 16 |
|
|
% \subtree
|
| 17 |
|
|
% \leaf{item}
|
| 18 |
|
|
% .
|
| 19 |
|
|
% .
|
| 20 |
|
|
% .
|
| 21 |
|
|
% \endsubtree
|
| 22 |
|
|
% \subtree
|
| 23 |
|
|
% .
|
| 24 |
|
|
% .
|
| 25 |
|
|
% .
|
| 26 |
|
|
% \endsubtree
|
| 27 |
|
|
% \endsubtree
|
| 28 |
|
|
% \endtree
|
| 29 |
|
|
%
|
| 30 |
|
|
% Nesting is to any level. \leaf is defined as a subtree of one item:
|
| 31 |
|
|
% \def\leaf#1{\subtree#1\endsubtree}.
|
| 32 |
|
|
%
|
| 33 |
|
|
% A structure:
|
| 34 |
|
|
% \subtree
|
| 35 |
|
|
% item_part1
|
| 36 |
|
|
% item_part2
|
| 37 |
|
|
% .
|
| 38 |
|
|
% .
|
| 39 |
|
|
% .
|
| 40 |
|
|
%
|
| 41 |
|
|
% will print item_part2 directly below item_part1 as a single item
|
| 42 |
|
|
% as if they were in a \box.
|
| 43 |
|
|
%
|
| 44 |
|
|
% The macro is a 3-pass macro. On the first pass it sets up a data
|
| 45 |
|
|
% structure from the \subtree ... \endsubtree definitions. On the second pass
|
| 46 |
|
|
% it recursively calculates the width of each level of the tree. On the third
|
| 47 |
|
|
% pass it sets up the boxes, glue and rules.
|
| 48 |
|
|
%
|
| 49 |
|
|
% By David Eppstein, TUGboat, vol. 6 (1985), no. 1, pp. 31--35.
|
| 50 |
|
|
% Transcribed by Margaret Kromer (peg), Feb., 1986.
|
| 51 |
|
|
%
|
| 52 |
|
|
% Pass 1
|
| 53 |
|
|
% At the end of pass 1, the tree is coded as a nested collection of \hboxes
|
| 54 |
|
|
% and \vboxes.
|
| 55 |
|
|
\newbox\treebox\newcount\treeboxcnt
|
| 56 |
|
|
\def\tree{\message{Begin tree}\treeboxcnt=1\global\setbox\treebox=\boxtree}
|
| 57 |
|
|
\def\subtree{\ettext \advance\treeboxcnt by 1 \boxtree}
|
| 58 |
|
|
\def\leaf#1{\subtree#1\endsubtree}
|
| 59 |
|
|
\def\endsubtree{\ettext \egroup \advance\treeboxcnt-1{}%
|
| 60 |
|
|
\ifnum\treeboxcnt=-1 \treeerrora\fi}
|
| 61 |
|
|
\def\endtree{\endsubtree \ifnum\treeboxcnt>0 \treeerrorb\fi%
|
| 62 |
|
|
\settreesizes \typesettree \message{-- end tree}}
|
| 63 |
|
|
% Error messages for unbalanced tree
|
| 64 |
|
|
\def\treeerrora{\errhelp=\treeerrorahelp%
|
| 65 |
|
|
\errmessage{Unbalanced tree -- too many endsubtrees}}
|
| 66 |
|
|
\newhelp\treeerrorahelp{There are more subtrees closed than opened}
|
| 67 |
|
|
\def\treeerrorb{\errhelp=\treeerrorbhelp%
|
| 68 |
|
|
\errmessage{Unbalanced tree -- not enough endsubtrees}}
|
| 69 |
|
|
\newhelp\treeerrorbhelp{Not all the subtrees of the tree are closed.
|
| 70 |
|
|
If you continue, you'll get some mysterious secondary errors.}
|
| 71 |
|
|
% Set up \vbox containing root of tree
|
| 72 |
|
|
\newif\iftreetext\treetextfalse % Whether still aligning text
|
| 73 |
|
|
\def\boxtree{\hbox\bgroup % Start outer box of tree or subtree
|
| 74 |
|
|
\baselineskip 2.5ex % Narrow line spacing slightly
|
| 75 |
|
|
\tabskip 0pt % No spurious glue in alignment
|
| 76 |
|
|
\vbox\bgroup % Start inner text \vbox
|
| 77 |
|
|
\treetexttrue % Remember for \ettext
|
| 78 |
|
|
\let\par\crcr \obeylines % New line breaks without explicit \cr
|
| 79 |
|
|
\halign\bgroup##\hfil\cr} % Start alignment with simple template
|
| 80 |
|
|
\def\ettext{\iftreetext % Are we still in inner text \vbox?
|
| 81 |
|
|
\crcr\egroup \egroup \fi} % Yes, end alignment and box
|
| 82 |
|
|
% Pass 2
|
| 83 |
|
|
% Recursively calculate widths of tree with \setsizes; keep results in
|
| 84 |
|
|
% \treesizes; \treewidth contains total width calculated so far. \treeworkbox
|
| 85 |
|
|
% is workspace containing subtree being sized.
|
| 86 |
|
|
\newbox\treeworkbox
|
| 87 |
|
|
\def\cons#1#2{\edef#2{\xmark #1#2}} % Add something to start of list
|
| 88 |
|
|
\def\car#1{\expandafter\docar#1\docar} % Take first element of list
|
| 89 |
|
|
\def\docar\xmark#1\xmark#2\docar{#1} % ..by ignoring rest in expansion
|
| 90 |
|
|
\def\cdr#1{\expandafter\docdr#1\docdr#1}% Similarly, drop first element
|
| 91 |
|
|
\def\docdr\xmark#1\xmark#2\docdr#3{\def#3{\xmark #2}}
|
| 92 |
|
|
\def\xmark{\noexpand\xmark} % List separator expands to self
|
| 93 |
|
|
\def\nil{\xmark} % Empty list is just separator
|
| 94 |
|
|
\def\settreesizes{\setbox\treeworkbox=\copy\treebox%
|
| 95 |
|
|
\global\let\treesizes\nil \setsizes}
|
| 96 |
|
|
\newdimen\treewidth % Width of this part of the tree
|
| 97 |
|
|
\def\setsizes{\setbox\treeworkbox=\hbox\bgroup% Get a horiz list as a workspace
|
| 98 |
|
|
\unhbox\treeworkbox\unskip % Take tree, unpack it into horiz list
|
| 99 |
|
|
\inittreewidth % Get old width at this level
|
| 100 |
|
|
\sizesubtrees % Recurse through all subtrees
|
| 101 |
|
|
\sizelevel % Now set width from remaining \vbox
|
| 102 |
|
|
\egroup} % All done, finish our \hbox
|
| 103 |
|
|
\def\inittreewidth{\ifx\treesizes\nil % If this is the first at this level
|
| 104 |
|
|
\treewidth=0pt % ..then we have no previous max width
|
| 105 |
|
|
\else \treewidth=\car\treesizes % Otherwise take old max level width
|
| 106 |
|
|
\global\cdr\treesizes % ..and advance level width storage
|
| 107 |
|
|
\fi} % ..in preparation for next level.
|
| 108 |
|
|
\def\sizesubtrees{\loop % For each box in horiz list (subtree)
|
| 109 |
|
|
\setbox\treeworkbox=\lastbox \unskip % ..pull it off list and flush glue
|
| 110 |
|
|
\ifhbox\treeworkbox \setsizes % If hbox, it's a subtree - recurse
|
| 111 |
|
|
\repeat} % ..and loop; end loop on tree text
|
| 112 |
|
|
\def\sizelevel{%
|
| 113 |
|
|
\ifdim\treewidth<\wd\treeworkbox % If greater than previous maximum
|
| 114 |
|
|
\treewidth=\wd\treeworkbox \fi % Then set max to new high
|
| 115 |
|
|
\global\cons{\the\treewidth}\treesizes}% In either case, put back on list
|
| 116 |
|
|
% Pass 3
|
| 117 |
|
|
% Recursively typeset tree with \maketree by adding an \hbox containing
|
| 118 |
|
|
% a subtree (in \treebox) to the horizontal list.
|
| 119 |
|
|
\newdimen\treeheight % Height of this part of the tree
|
| 120 |
|
|
\newif\ifleaf % Tree has no subtrees (is a leaf)
|
| 121 |
|
|
\newif\ifbotsub % Bottom subtree of parent
|
| 122 |
|
|
\newif\iftopsub % Top subtree of parent
|
| 123 |
|
|
\def\typesettree{\medskip\maketree\medskip} % Make whole tree
|
| 124 |
|
|
\def\maketree{\hbox{\treewidth=\car\treesizes % Get width at this level
|
| 125 |
|
|
\cdr\treesizes % Set up width list for recursion
|
| 126 |
|
|
\makesubtreebox\unskip % Set \treebox to text, make subtrees
|
| 127 |
|
|
\ifleaf \makeleaf % No subtrees, add glue
|
| 128 |
|
|
\else \makeparent \fi}} % Have subtrees, stick them at right
|
| 129 |
|
|
{\catcode`@=11 % Be able to use \voidb@x
|
| 130 |
|
|
\gdef\makesubtreebox{\unhbox\treebox % Open up tree or subtree
|
| 131 |
|
|
\unskip\global\setbox\treebox\lastbox % Pick up very last box
|
| 132 |
|
|
\ifvbox\treebox % If we're already at the \vbox
|
| 133 |
|
|
\global\leaftrue \let\next\relax % ..then this is a leaf
|
| 134 |
|
|
\else \botsubtrue % Otherwise, we have subtrees
|
| 135 |
|
|
\setbox\treeworkbox\box\voidb@x % Init stack of processed subs
|
| 136 |
|
|
\botsubtrue \let\next\makesubtree % ..and call \maketree on them
|
| 137 |
|
|
\fi \next}} % Finish up for whichever it was
|
| 138 |
|
|
\def\makesubtree{\setbox1\maketree % Call \maketree on this subtree
|
| 139 |
|
|
\unskip\global\setbox\treebox\lastbox % Pick up box before it
|
| 140 |
|
|
\treeheight=\ht1 % Get height of subtree we made
|
| 141 |
|
|
\advance\treeheight 2ex % Add some room around the edges
|
| 142 |
|
|
\ifhbox\treebox \topsubfalse % If picked up box is a \vbox,
|
| 143 |
|
|
\else \topsubtrue \fi % ..this is the top, otherwise not
|
| 144 |
|
|
\addsubtreebox % Stack subtree with the rest
|
| 145 |
|
|
\iftopsub \global\leaffalse % If top, remember not a leaf
|
| 146 |
|
|
\let\next\relax \else % ..(after recursion), set return
|
| 147 |
|
|
\botsubfalse \let\next\makesubtree % Otherwise, we have more subtrees
|
| 148 |
|
|
\fi \next} % Do tail recursion or return
|
| 149 |
|
|
\def\addsubtreebox{\setbox\treeworkbox=\vbox{\subtreebox\unvbox\treeworkbox}}
|
| 150 |
|
|
\def\subtreebox{\hbox\bgroup % Start \hbox of tree and lines
|
| 151 |
|
|
\vbox to \treeheight\bgroup % Start \vbox for vertical rules
|
| 152 |
|
|
\ifbotsub \iftopsub \vfil % If both bottom and top subtree
|
| 153 |
|
|
\hrule width 0.4pt % ..vertical rule is just a dot
|
| 154 |
|
|
\else \treehalfrule \fi \vfil % Bottom gets half-height rule
|
| 155 |
|
|
\else \iftopsub \vfil \treehalfrule % Top gets half-height the other way
|
| 156 |
|
|
\else \hrule width 0.4pt height \treeheight \fi\fi % Middle, full height
|
| 157 |
|
|
\egroup % Finish vertical rule \vbox
|
| 158 |
|
|
\treectrbox{\hrule width 1em}\hskip 0.2em\treectrbox{\box1}\egroup}
|
| 159 |
|
|
\def\treectrbox#1{\vbox to \treeheight{\vfil #1\vfil}}
|
| 160 |
|
|
\def\treehalfrule{\dimen\treeworkbox=\treeheight % Get total height
|
| 161 |
|
|
\divide\dimen\treeworkbox 2%
|
| 162 |
|
|
\advance\dimen\treeworkbox 0.2pt % Divide by two, add half horiz height
|
| 163 |
|
|
\hrule width 0.4pt height \dimen\treeworkbox}% Make a vertical rule that high
|
| 164 |
|
|
\def\makeleaf{\box\treebox} % Add leaf box to horiz list
|
| 165 |
|
|
\def\makeparent{\ifdim\ht\treebox>%
|
| 166 |
|
|
\ht\treeworkbox % If text is higher than subtrees
|
| 167 |
|
|
\treeheight=\ht\treebox % ..use that height
|
| 168 |
|
|
\else \treeheight=\ht\treeworkbox \fi % Otherwise use height of subtrees
|
| 169 |
|
|
\advance\treewidth-\wd\treebox % Take remainder of level width
|
| 170 |
|
|
\advance\treewidth 1em % ..after accounting for text and glue
|
| 171 |
|
|
\treectrbox{\box\treebox}\hskip 0.2em % Add text, space before connection
|
| 172 |
|
|
\treectrbox{\hrule width \treewidth}%
|
| 173 |
|
|
\treectrbox{\box\treeworkbox}} % Add \hrule, subs
|
| 174 |
|
|
|
| 175 |
|
|
************************************************
|
| 176 |
|
|
% Plain TeX driver for tree.tex
|
| 177 |
|
|
|
| 178 |
|
|
\def\uncatcodespecials{\catcode`@=12\def\do##1{\catcode`##1=12}\dospecials}
|
| 179 |
|
|
\def\setupverbatim{\tt\obeylines\uncatcodespecials\obeyspaces}
|
| 180 |
|
|
{\obeyspaces\global\let =\ }
|
| 181 |
|
|
\def\beginshowoff{\par\begingroup\setupverbatim\doverbatim}
|
| 182 |
|
|
{\catcode`\!=0 \catcode`\\=12
|
| 183 |
|
|
!obeylines!gdef!doverbatim^^M#1\endshowoff{#1!endgroup!medbreak!filbreak%
|
| 184 |
|
|
!smallskip}}
|
| 185 |
|
|
|
| 186 |
|
|
% see The TeXbook, exercise 22.14
|
| 187 |
|
|
%\input tree.tex
|
| 188 |
|
|
\centerline{\bf TREE TREE}
|
| 189 |
|
|
\bigskip
|
| 190 |
|
|
\tree
|
| 191 |
|
|
{Tree}
|
| 192 |
|
|
Uses
|
| 193 |
|
|
\subtree
|
| 194 |
|
|
Computer
|
| 195 |
|
|
Science
|
| 196 |
|
|
\subtree
|
| 197 |
|
|
Data
|
| 198 |
|
|
Structures
|
| 199 |
|
|
\leaf{Search Tree}
|
| 200 |
|
|
\leaf{Priority Queue}
|
| 201 |
|
|
\endsubtree
|
| 202 |
|
|
\subtree
|
| 203 |
|
|
Parsing
|
| 204 |
|
|
\leaf{Parse Tree}
|
| 205 |
|
|
\leaf{Symbol Table}
|
| 206 |
|
|
\endsubtree
|
| 207 |
|
|
\subtree
|
| 208 |
|
|
Structured
|
| 209 |
|
|
Programming
|
| 210 |
|
|
\endsubtree
|
| 211 |
|
|
\endsubtree
|
| 212 |
|
|
\subtree
|
| 213 |
|
|
Genealogy
|
| 214 |
|
|
\leaf{Ancestors}
|
| 215 |
|
|
\leaf{Descendants}
|
| 216 |
|
|
\endsubtree
|
| 217 |
|
|
\subtree
|
| 218 |
|
|
Electrical
|
| 219 |
|
|
Engineering
|
| 220 |
|
|
\subtree
|
| 221 |
|
|
Paper
|
| 222 |
|
|
\leaf{{\it Vitae}}
|
| 223 |
|
|
\leaf{Announcements}
|
| 224 |
|
|
\leaf{Proposals}
|
| 225 |
|
|
\leaf{\TeX{} Samples}
|
| 226 |
|
|
\endsubtree
|
| 227 |
|
|
\endsubtree
|
| 228 |
|
|
\subtree
|
| 229 |
|
|
Construction
|
| 230 |
|
|
\leaf{Fences}
|
| 231 |
|
|
\subtree
|
| 232 |
|
|
Buildings
|
| 233 |
|
|
\subtree
|
| 234 |
|
|
Houses
|
| 235 |
|
|
\leaf{Human}
|
| 236 |
|
|
\leaf{Dog}
|
| 237 |
|
|
\leaf{Bird}
|
| 238 |
|
|
\leaf{Tree}
|
| 239 |
|
|
\endsubtree
|
| 240 |
|
|
\leaf{Barns}
|
| 241 |
|
|
\leaf{Other}
|
| 242 |
|
|
\endsubtree
|
| 243 |
|
|
\leaf{\dots}
|
| 244 |
|
|
\endsubtree
|
| 245 |
|
|
\subtree
|
| 246 |
|
|
Taxonomies
|
| 247 |
|
|
\leaf{Tree Uses}
|
| 248 |
|
|
\endsubtree
|
| 249 |
|
|
\endtree
|
| 250 |
|
|
|
| 251 |
|
|
\vskip.5truein
|
| 252 |
|
|
\beginshowoff
|
| 253 |
|
|
% see The TeXbook, exercise 22.14
|
| 254 |
|
|
\input tree.tex
|
| 255 |
|
|
\centerline{TREE TREE}
|
| 256 |
|
|
\bigskip
|
| 257 |
|
|
\tree
|
| 258 |
|
|
Tree
|
| 259 |
|
|
Uses
|
| 260 |
|
|
\subtree
|
| 261 |
|
|
Computer
|
| 262 |
|
|
Science
|
| 263 |
|
|
\subtree
|
| 264 |
|
|
Data
|
| 265 |
|
|
Structures
|
| 266 |
|
|
\leaf{Search Tree}
|
| 267 |
|
|
\leaf{Priority Queue}
|
| 268 |
|
|
\endsubtree
|
| 269 |
|
|
\subtree
|
| 270 |
|
|
Parsing
|
| 271 |
|
|
\leaf{Parse Tree}
|
| 272 |
|
|
\leaf{Symbol Table}
|
| 273 |
|
|
\endsubtree
|
| 274 |
|
|
\subtree
|
| 275 |
|
|
Structured
|
| 276 |
|
|
Programming
|
| 277 |
|
|
\endsubtree
|
| 278 |
|
|
\endsubtree
|
| 279 |
|
|
\subtree
|
| 280 |
|
|
Genealogy
|
| 281 |
|
|
\leaf{Ancestors}
|
| 282 |
|
|
\leaf{Descendants}
|
| 283 |
|
|
\endsubtree
|
| 284 |
|
|
\subtree
|
| 285 |
|
|
Electrical
|
| 286 |
|
|
Engineering
|
| 287 |
|
|
\subtree
|
| 288 |
|
|
Paper
|
| 289 |
|
|
\leaf{{\it Vitae}}
|
| 290 |
|
|
\leaf{Announcements}
|
| 291 |
|
|
\leaf{Proposals}
|
| 292 |
|
|
\leaf{\TeX{} Samples}
|
| 293 |
|
|
\endsubtree
|
| 294 |
|
|
\endsubtree
|
| 295 |
|
|
\subtree
|
| 296 |
|
|
Construction
|
| 297 |
|
|
\leaf{Fences}
|
| 298 |
|
|
\subtree
|
| 299 |
|
|
Buildings
|
| 300 |
|
|
\subtree
|
| 301 |
|
|
Houses
|
| 302 |
|
|
\leaf{Human}
|
| 303 |
|
|
\leaf{Dog}
|
| 304 |
|
|
\leaf{Bird}
|
| 305 |
|
|
\leaf{Tree}
|
| 306 |
|
|
\endsubtree
|
| 307 |
|
|
\leaf{Barns}
|
| 308 |
|
|
\leaf{Other}
|
| 309 |
|
|
\endsubtree
|
| 310 |
|
|
\leaf{\dots}
|
| 311 |
|
|
\endsubtree
|
| 312 |
|
|
\subtree
|
| 313 |
|
|
Taxonomies
|
| 314 |
|
|
\leaf{Tree Uses}
|
| 315 |
|
|
\endsubtree
|
| 316 |
|
|
\endtree
|
| 317 |
|
|
\endshowoff
|
