summaryrefslogtreecommitdiff
path: root/graphics/pictex/tree.sty
blob: 6e91652a0e35bfe05849fee52ff521ecce16040d (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
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
% Binary tree drawing in LaTeX using the PiCTeX macros.
%
% Edward M. Reingold (reingold@cs.uiuc.edu)
% Nachum Dershowitz (nachum@cs.uiuc.edu)
%
\typeout{Binary Tree Macros.  Released 18 Jan 1991; modified 2 Apr 1992.}
%
% These macros are in the public domain.  You may use them and copy them at
% will, provided you retain the authorship information.
%
%
% USAGE: \tree[optional root symbol]{left subtree}{right subtree}
%
% For example,
%
%     \tree[X]
%        {\setdots\tree[Z]
%           {\setsolid\tree[Y]{a}{}}
%           {\setsolid\tree{c}{d}}}
%        {\tree
%           {\tree{}{f}}
%           {\tree{g}{h}}}
%
% The root symbol and leaves can be anything you can construct in LaTeX
% or PiCTeX.  The trees constructed can be used in any context in LaTeX
% or PiCTeX.  That is, you can have, say, tables of trees of equations.
%
%
% WARNING: Do not use the tilde (~) as the first character in any subtree!
%
%
% PARAMETERS: Feel free to change the following tree drawing parameters;
%             these parameters can be reset even in the middle of a tree.
%
\newdimen\subtreesep \subtreesep=10pt   % Distance between nonempty subtrees
\newdimen\levelsep   \levelsep=30pt     % Distance between successive levels
\def\nodesymbol{$\bullet$}              % Default symbol for an internal node
%                          Tree edges connecting to the default node symbol
%                          will go to it's center.  Other tree edges will be
%                          chopped off at a node's bounding box.
%
%
% Here's an example that changes the parameters in the middle of the tree:
%
%     \subtreesep=15pt\levelsep=40pt
%     \tree[\fbox{\subtreesep=5pt\levelsep=13pt\tree[o]{a}{a}}]
%        {b}{b}
%
%
% You can get triangular subtrees by using \triangle which has the format 
%
%      \triangle[optional apex label]{width}{height}
%
% For example,
%
%      \tree{\triangle[A]{2\subtreesep}{2\levelsep}}
%           {\tree{\triangle{\subtreesep}{\levelsep}}
%                 {\tree{\fbox{}}
%                       {\fbox{}}}}
%
%
% Don't fiddle with the stuff that follows; it's fairly delicate.
%
% Working variables
%
\catcode`@=11%
\newdimen\halfsubtreesep % half the subtree separation
%
\newdimen\leftwd         % width of left subtree
\newdimen\rightwd        % width of right subtree
%
\newcount\rootbullet     % flag indicating if root is the default bullet
\newdimen\rootwd         % width of root
\newdimen\rootht         % height of root
\newdimen\rootdp         % depth of root
%
\newcount\leftrootbullet % flag indicating if left root is the default bullet
\newdimen\leftrootht     % height of left subtree's root
\newdimen\leftrootwd     % width of left subtree's root
\newcount\rightrootbullet% flag indicating if right root is the default bullet
\newdimen\rightrootht    % height of right subtree's root
\newdimen\rightrootwd    % width of right subtree's root
%
\newdimen\@@root           % distance of root midpointfrom left edge of tree
\newdimen\leftroot       % distance of root midpoint of left subtree
                         % from left edge of tree
\newdimen\rightroot      % distance of root midpoint of right subtree
                         % from left edge of tree
%
\newcount\leafnode       % flag indicating if subtree just placed is a leaf
%
\newdimen\rootxpos       % x-cooordinate of the root midpoint
\newdimen\leftrootpos    % position of the root of the left subtree
\newdimen\rightrootpos   % position of the root of the right subtree
\newdimen\leftpos        % position of the NE corner of the left subtree
\newdimen\rightpos       % position of the NW corner of the right subtree
%
\newbox\rootnode         % the root node, as placed
\newbox\leftsubtree      % the left subtree, as placed
\newbox\rightsubtree     % the right subtree, as placed
%
\newdimen\xa             % (\xa,\ya) = coordinates of the point on the root
\newdimen\ya             % node at which to connect the line to a child
\newdimen\xb             % (\xb,\yb) = coordinates of the point on the child
\newdimen\yb             % at which to connect the line to the parent
%
\let\ifnextchar=\@ifnextchar%
\def\tree{\ignorespaces%
\def\tree{\ifnextchar[{\treey}{\treex}}%
%
\setdimensionmode%
\setlinear%
%
\@ifnextchar[{\treey}{\treex}%
}%
%
\long\def\treex#1#2{\itree{#1}{#2}{\nodesymbol}}  % use default node symbol
\long\def\treey[#1]#2#3{\itree{#2}{#3}{#1}}       % use specified node symbol
%
\long\def\itree#1#2#3{\ignorespaces  % #1=left, #2=right, #3=root
%
\halfsubtreesep=\subtreesep     % Do this calculation for each node so its...
\divide\halfsubtreesep by 2     % ...value can vary throughout the tree
%
\ignorespaces%
%
% Recursively draw nonempty left subtree
%
\ifx ~#1~\ignorespaces%
 \else%
   \leafnode=1  % Assume left subtree is a leaf
   \setbox\leftsubtree=\hbox{#1}\ignorespaces
   \leftwd=\wd\leftsubtree%
   \leftroot=\@@root%
   \leftrootbullet=\rootbullet%
   \leftrootht=\rootht%
   \leftrootwd=\rootwd%
   \ifnum \leafnode=1%
      \leftroot=\leftwd%
      \divide\leftroot by 2%
      \leftrootbullet=0%
      \leftrootht=\ht\leftsubtree%
      \advance\leftrootht by \dp\leftsubtree%
      \leftrootwd=\leftwd%
   \fi%
\fi%
%
% Recursively draw nonempty right subtree
%
\ifx ~#2~\ignorespaces%
 \else%
   \leafnode=1  % Assume right subtree is a leaf
   \setbox\rightsubtree=\hbox{#2}\ignorespaces%
   \rightwd=\wd\rightsubtree%
   \rightroot=\@@root%
   \rightrootbullet=\rootbullet%
   \rightrootht=\rootht%
   \rightrootwd=\rootwd%
   \ifnum \leafnode=1%
      \rightroot=\rightwd%
      \divide\rightroot by 2%
      \rightrootbullet=0%
      \rightrootht=\ht\rightsubtree%
      \advance\rightrootht by \dp\rightsubtree%
      \rightrootwd=\rightwd%
   \fi%
\fi%
%
% In the case of empty subtrees, give artificial values for those empty
% trees so that the later calculations are done properly.
%
\ifx ~#1#2~\ignorespaces        %  Both subtrees empty
   \rightroot=0pt%
   \leftroot=-\halfsubtreesep%
   \leftwd=-\halfsubtreesep%
\else\ifx ~#1~\ignorespaces     %  Left subtree empty, right subtree not empty
   \leftroot=\rightroot%
   \advance\leftroot by -\subtreesep%
   \leftwd=-\subtreesep%
\else\ifx ~#2~\ignorespaces     %  Right subtree empty, left subtree not empty
   \rightroot=\leftroot%
   \advance\rightroot by -\leftwd%
\fi\fi\fi%
%
% With the subtrees done, now do the root node
%
\setbox\rootnode=\hbox{\setcoordinatemode #3}\ignorespaces%
\global\rootwd=\wd\rootnode%
\global\rootht=\ht\rootnode%
\global\advance\rootht by \dp\rootnode%
\ifx \nodesymbol#3\ignorespaces%
    \global\rootbullet=1%
  \else\ignorespaces%
    \global\rootbullet=0%
\fi%
%
% Find distance of the root midpoint from left edge of the tree
%
\global\@@root=\leftroot%
\global\advance\@@root by \rightroot%
\global\advance\@@root by \leftwd%
\global\advance\@@root by \subtreesep%
\ifdim \@@root<\rootwd \global\@@root=\rootwd \fi%
\global\divide\@@root by 2%
%
% Indicate this root and all its ancestors are not a leaves
%
\global\leafnode=0%
%
% Find positions of the root and those of the roots of the subtrees
%
\leftrootpos=\leftroot%
\advance\leftrootpos by -\leftwd%
\advance\leftrootpos by -\halfsubtreesep%
%
\rightrootpos=\rightroot%
\advance\rightrootpos by \halfsubtreesep%
%
\rootxpos=\leftrootpos%
\advance\rootxpos by \rightrootpos%
\divide\rootxpos by 2%
%
\leftpos=0pt%
\advance\leftpos by \leftrootht%
\divide\leftpos by 2%
%
\rightpos=0pt%
\advance\rightpos by \rightrootht%
\divide\rightpos by 2%
%
% Now the root is a box of width \rootwd and total height \rootht, centered
% at (\rootxpos,\levelsep); the root of the left subtree is a box of
% width \leftrootwd and total height \leftrootht, centered at
% (\leftrootpos,0); the root of the right subtree is a box of width
% \rightrootwd and total height \rightrootht, centered at (\rightrootpos,0).
%
%
\beginpicture
%
\put {\box\rootnode} at {\rootxpos} {\levelsep}     % Draw the root
%
\ifx ~#1~\else                                      % Draw the left subtree
   \put {\box\leftsubtree} [rt] at {-\halfsubtreesep} {\leftpos}
   \xa=\rootxpos%
   \ya=\levelsep%
   \ifnum\rootbullet=0%
      \chop{\rootxpos}{\levelsep}{-\rootwd}{\rootht}{\leftrootpos}{0}%
           {\xa}{\ya}%
   \fi%
   \xb=\leftrootpos%
   \yb=0pt%
   \ifnum\leftrootbullet=0%
      \chop{\leftrootpos}{0}{\leftrootwd}{-\leftrootht}{\rootxpos}{\levelsep}%
           {\xb}{\yb}%
   \fi%
   \plot {\xa} {\ya}  {\xb} {\yb} /%
\fi%
%
\ifx ~#2~\else                                      % Draw the right subtree
   \put {\box\rightsubtree} [lt] at {\halfsubtreesep} {\rightpos}
   \xa=\rootxpos%
   \ya=\levelsep%
   \ifnum\rootbullet=0%
      \chop{\rootxpos}{\levelsep}{\rootwd}{\rootht}{\rightrootpos}{0}%
           {\xa}{\ya}%
   \fi%
   \xb=\rightrootpos%
   \yb=0pt%
   \ifnum\rightrootbullet=0%
      \chop{\rightrootpos}{0}{-\rightrootwd}{-\rightrootht}{\rootxpos}%
           {\levelsep}{\xb}{\yb}%
   \fi
   \plot {\xa} {\ya}  {\xb} {\yb} /%
\fi%
%
% Draw the bottom of the triangle, when appropriate.
%
\ifx#1. \ifx#2. \plot {\leftrootpos} {0pt} {\rightrootpos} {0pt} / \fi\fi%
%
\endpicture%
}%
%
\long\def\triangle{\ifnextchar[{\triangley}{\trianglex}}%
\long\def\trianglex#1#2{\itriangle{#1}{#2}{}}       % use empty apex symbol
\long\def\triangley[#1]#2#3{\itriangle{#2}{#3}{#1}} % use specified apex symbol
\long\def\itriangle#1#2#3{%  A triangle #1 wide and #2 high, #3 at apex
   \subtreesep=#1%
   \levelsep=#2%
   \tree[#3]{.}{.}%
}%
%
\newcount\@@x%  Scratch counters used in the computations of \chop
\newcount\@@y%  to find the location on the border of a node's bounding
\newcount\@@a%  box at which to attach a line aimed at a target point
\newcount\@@b%  from the center of the box.
\newcount\@@c%
\newcount\@@d%  It would be better to do all these calculation in dimen's
\newcount\@@e%  instead of counters, but so many dimen's are used above
\newcount\@@f%  that to do so would make running out of dimen's very probable.
\newcount\@@g%  
\newcount\@@h%  Forgive us for not explaining the following computations;
\newcount\@@l%  they're based on elementary analytical geometry.
%
\def\chop#1#2#3#4#5#6#7#8{\ignorespaces%
                          % (#1,#2) = coordinates of center of bounding box
                          % #3 x #4 = width x height of bounding box
                          % (#5,#6) = coordinates of target point
                          % (#7,#8) = coordinates of computed intersection
                          %           point
%
\@@a=#1\divide \@@a by 10000%  Scale down to prevent arithmetic overflow.
\@@b=#2\divide \@@b by 10000%
\@@c=#3\divide \@@c by 10000%
\@@d=#4\divide \@@d by 10000%
\@@e=#5\divide \@@e by 10000%
\@@f=#6\divide \@@f by 10000%
%
\@@l=-\@@f\advance\@@l by \@@b%
%%
\@@y=-\@@d%
\divide \@@y by 2%
\advance\@@y by \@@b%
%%
\@@g=\@@c%
\divide \@@g by 2%
\advance\@@g by \@@a%
%%
\@@x=-\@@a%
\advance\@@x by \@@e%
\multiply\@@x by \@@d%
\divide\@@x by \@@l%
\divide\@@x by 2%
\advance \@@x by \@@a%
%%
\count255=-\@@a%
\advance\count255 by \@@e%
\multiply\count255 by 2%
\@@h=-\@@c%
\multiply \@@h by \@@l%
\divide \@@h by \count255%
\advance \@@h by \@@b%
%
\ifnum #5>#1%
   \ifnum\@@x>\@@g\else\@@g=\@@x\@@h=\@@y\fi%
\else%
   \ifnum\@@x<\@@g\else\@@g=\@@x\@@h=\@@y\fi%
\fi%
\multiply\@@g by 10000%  Scale back up
\multiply\@@h by 10000%
\global#7=\@@g sp%
\global#8=\@@h sp%
}%
\catcode`@=12%