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

************************************************
% Plain TeX driver for tree.tex

\def\uncatcodespecials{\catcode`@=12\def\do##1{\catcode`##1=12}\dospecials}
\def\setupverbatim{\tt\obeylines\uncatcodespecials\obeyspaces}
{\obeyspaces\global\let =\ }
\def\beginshowoff{\par\begingroup\setupverbatim\doverbatim}
{\catcode`\!=0 \catcode`\\=12
!obeylines!gdef!doverbatim^^M#1\endshowoff{#1!endgroup!medbreak!filbreak%
!smallskip}}

% see The TeXbook, exercise 22.14
%\input tree.tex
\centerline{\bf TREE TREE}
\bigskip
\tree
  {Tree}
  Uses
  \subtree
    Computer
    Science
    \subtree
      Data
      Structures
      \leaf{Search Tree}
      \leaf{Priority Queue}
    \endsubtree
    \subtree
      Parsing
      \leaf{Parse Tree}
      \leaf{Symbol Table}
    \endsubtree
    \subtree
      Structured
      Programming
    \endsubtree
  \endsubtree
  \subtree
    Genealogy
    \leaf{Ancestors}
    \leaf{Descendants}
  \endsubtree
  \subtree
    Electrical
    Engineering
    \subtree
      Paper
      \leaf{{\it Vitae}}
      \leaf{Announcements}
      \leaf{Proposals}
      \leaf{\TeX{} Samples}
    \endsubtree
  \endsubtree
  \subtree
    Construction
    \leaf{Fences}
    \subtree
      Buildings
      \subtree
        Houses
        \leaf{Human}
        \leaf{Dog}
        \leaf{Bird}
        \leaf{Tree}
      \endsubtree
      \leaf{Barns}
      \leaf{Other}
    \endsubtree
    \leaf{\dots}
  \endsubtree
  \subtree
    Taxonomies
    \leaf{Tree Uses}
  \endsubtree
\endtree

\vskip.5truein
\beginshowoff
% see The TeXbook, exercise 22.14
\input tree.tex
\centerline{TREE TREE}
\bigskip
\tree
  Tree
  Uses
  \subtree
    Computer
    Science
    \subtree
      Data
      Structures
      \leaf{Search Tree}
      \leaf{Priority Queue}
    \endsubtree
    \subtree
      Parsing
      \leaf{Parse Tree}
      \leaf{Symbol Table}
    \endsubtree
    \subtree
      Structured
      Programming
    \endsubtree
  \endsubtree
  \subtree
    Genealogy
    \leaf{Ancestors}
    \leaf{Descendants}
  \endsubtree
  \subtree
    Electrical
    Engineering
    \subtree
      Paper
      \leaf{{\it Vitae}}
      \leaf{Announcements}
      \leaf{Proposals}
      \leaf{\TeX{} Samples}
    \endsubtree
  \endsubtree
  \subtree
    Construction
    \leaf{Fences}
    \subtree
      Buildings
      \subtree
        Houses
        \leaf{Human}
        \leaf{Dog}
        \leaf{Bird}
        \leaf{Tree}
      \endsubtree
      \leaf{Barns}
      \leaf{Other}
    \endsubtree
    \leaf{\dots}
  \endsubtree
  \subtree
    Taxonomies
    \leaf{Tree Uses}
  \endsubtree
\endtree
\endshowoff