1 | % 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 |
---|