From e0c6872cf40896c7be36b11dcc744620f10adf1d Mon Sep 17 00:00:00 2001 From: Norbert Preining Date: Mon, 2 Sep 2019 13:46:59 +0900 Subject: Initial commit --- info/digests/tugboat/tb0tree.tex | 423 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 423 insertions(+) create mode 100644 info/digests/tugboat/tb0tree.tex (limited to 'info/digests/tugboat/tb0tree.tex') diff --git a/info/digests/tugboat/tb0tree.tex b/info/digests/tugboat/tb0tree.tex new file mode 100644 index 0000000000..51ebdf8c51 --- /dev/null +++ b/info/digests/tugboat/tb0tree.tex @@ -0,0 +1,423 @@ +% tb11eppstein.tex + +\Title Trees in \TeX +\\David Eppstein +\endx + +% This paper was 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 + +% First the tree macro definitions. + +\input treedef + +% Now the paper itself + +{\obeyspaces\gdef {\ifvmode\indent\fi\space}} +{\catcode `|=0 \catcode`\\=12 |gdef|vbarg#1\endvb{#1|endgroup|medskip}} +\def\makeother#1{\catcode`#112\relax} +\def\vb{\medskip \begingroup \verb \obeylines \obeyspaces \tt \vbarg} +\def\verb{\let\do\makeother \dospecials} +\catcode`\*=\active +\def*{\begingroup\verb\tt\dostar} +\def\dostar#1*{#1\endgroup} + +% \centerline{\bf Trees in \TeX} +% \centerline{David Eppstein; February 6, 1985} + +\beginsection Introduction + +There are many possible uses for trees in typeset text. The following +taxonomy illustrates some of them. + +\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 + Taxonomies + \leaf{Tree Uses} + \endsubtree +\endtree + +Unfortunately \TeX\ provides no easy way to typeset such trees. +One possible method is given in exercise 22.14 of the \TeX book: using +\TeX's alignment primitives by hand. This method becomes very clumsy as the +trees grow, however. A more general technique is to write a set of tree +construction macros; that is the approach taken in this paper. The +taxonomy above was typeset with the following input: + +\vb +\tree + Tree + Uses + + \subtree + Computer + Science + + \subtree + Data + Structures + + \leaf{Search Tree} + \leaf{Priority Queue} + \endsubtree + ... + \endsubtree + ... +\endtree +\endvb + +It turns out that \TeX's alignment primitives are not very well suited to +automatic generation of trees. The left edges of the trees at each +level can easily be made to line up, but it is difficult to center +lines of text for the root of a tree in vertical relation to its subtrees. +Instead, the macros described here construct trees from boxes and +glue, doing the alignment themselves. This is not quite as simple as +it sounds---it would be incorrect to set subtrees independently of +each other, because then the edges would not line up. For instance, +in the taxonomy above, the text ``Search Tree'' should line up +with ``Parse Tree''. A one-pass algorithm would set the former +somewhat to the right of the latter. + +To solve this problem, the macros described here set a tree using +three passes. First, a data structure is built up from the tree +definition. Second, that data structure is used to calculate the +width of each level of the tree, so that the subtrees can be aligned with each +other. Finally, the data structure and the calculated list of widths +are used to set the system of boxes, glue, and rules that make up the tree. + +\beginsection Pass 1: Internal storage of the tree structure + +There are several possible ways to store the structure defined by the +tree macros. Since we want to remember already-set text (the words at +the roots of each tree of subtree) we will use a nested structure of boxes. +Each subtree is stored in an *\hbox*, so that pieces of it can be pulled +off easily using *\lastbox* and *\unskip*. To distinguish it from +another subtree, the text at the root of a subtree is stored in a *\vbox*. +To make this clearer, let us return to our original taxonomy. +We shall ignore for the moment +the details inside the text *\vbox*es, and the glue between boxes. +After the first pass, the tree as a whole would look like the +following set of boxes: + +\vb +\hbox{\vbox{Tree Uses} + \hbox{\vbox{Computer Science} + \hbox{\vbox{Data Structures} + \hbox{\vbox{Search Tree}} + \hbox{\vbox{Priority Queue}}} + ...} + ...} +\endvb + +Now we can begin defining the tree macros. We start defining a tree +with the *\tree* macro; this merely sets up the assignment of the +boxed tree structure into a box called *\treebox*. Starting a subtree +is similar, but there is no assignment; also, if it is the first +*\subtree* of its tree or subtree, we must stop making the *\vbox* +containing the root text. A leaf is merely a subtree without any +sub-subtrees. + +\vb +\newbox\treebox +\def\tree{\global\setbox\treebox=\boxtree} +\def\subtree{\ettext \boxtree} +\def\leaf#1{\subtree#1\endsubtree} +\endvb + +Finishing a subtree merely involves first making sure the root text is +complete, and second +completing the box that was started in the expansion of *\subtree*. +Finishing a whole tree involves both of those steps, but then after the +box is completed the remaining two passes must be run. + +\vb +\def\endsubtree{\ettext \egroup} +\def\endtree{\endsubtree \settreesizes \typesettree} +\endvb + + +Now all that remains to be defined of the first pass is the construction +of the *\vbox* containing the root text. The difficulty here is +convincing \TeX\ to make the *\vbox* only as wide as the widest line +of text, rather than the width of the entire page. One solution is to +put the text in an *\halign*, with *\crcr* implicit at the end of each line. +The *\iftreetext* test is used to tell whether we are still inside the +*\halign* and *\vbox*, so that *\ettext* can tell whether it should do +anything. It is globally false, but within the *\vbox* it gets set to true. + +\vb +\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 +\endvb + +\beginsection Pass 2: Calculation of widths at each level + +Here we calculate a list of the dimensions of each level of the tree; +that is, the widths of the widest *\vbox* at each level. +To do this, we need to be able to maintain lists of things. Since these +are dimensions rather than boxes of text it will be most convenient to +use macros like the ones given on page 378 of the \TeX book. However, +it turns out that we need to set our lists both locally to some +grouping and also globally. Therefore, we will use a stripped down +version of those list macros that can handle the *\global* flag. +To implement this feature, we have to lose some others; the chief losses +are that the contents of the lists will be macro-expanded by various of +the list manipulation macros, and that we can't use redefinitions of *\\* +to perform some operation on the whole list. + +To initialize a control sequence to the empty list, we do *\let\csname\nil*. +Then to add an element to the start of the list we do *\cons{tokens}\csname*, +and to remove that element we do *\cdr\csname*. Both *\cons* and *\cdr* +can be prefixed with *\global*. The first element on the list can be +expanded into the token stream by doing *\car\csname*. There is no +error checking, so giving *\car* or *\cdr* the empty list will cause +mysterious errors later on. Because of the macro expansion performed +by *\cons* and *\cdr*, the token used to separate list elements +expands to itself, and unlike the \TeX book macros cannot be redefined +to do anything useful. + +\vb +\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 a separator. +\endvb + +We calculate the level widths by calling *\setsizes* on the tree; it +will in turn call itself recursively for each of its subtrees. The +tree being sized will be in *\box0*, which is used as scratch in this +macro, and the list of widths already found for this level and below +will be in *\treesizes* (initially *\nil*). When the macro exits, +*\treesizes* will be updated with the widths found in the various +levels of the given tree or subtree. A new *\dimen*, *\treewidth*, is +used within the macro to remember the previous maximum width at the +level of the tree's root. + +\vb +\def\settreesizes{\setbox0=\copy\treebox \global\let\treesizes\nil \setsizes} +\newdimen\treewidth % Width of this part of the tree. +\def\setsizes{\setbox0=\hbox\bgroup % Get a horiz list as a workspace. + \unhbox0\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. +\endvb + +The first thing *\setsizes* does is to find out what the previous +maximum at this level was, and store it in *\treewidth*. If +*\treesizes* is *\nil*, we haven't seen anything this deep in the tree +before, so the previous size is zero. Otherwise, it is *\car\treesizes*, +and we also do *\cdr\treesizes* to prepare for later recursive calls +to *\setsizes*. + +\vb +\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. +\endvb + +At this point, we have a horizontal list (the *\hbox* in *\setsizes*) +containing the *\vbox* for the text at the root of this subtree, +followed by the *\hbox*es for all of its sub-subtrees. We loop pulling boxes +from the end of the list with *\lastbox* until we find the text *\vbox*, +calling *\setsizes* recursively for each *\hbox* we come across. + +\vb +\def\sizesubtrees{\loop % For each box in horiz list (subtree) + \setbox0=\lastbox \unskip % ..pull it off list and flush glue. + \ifhbox0 \setsizes % If hbox, it's a subtree - recurse + \repeat} % ..and loop; end loop on tree text. +\endvb + +Now all that remains to do in this call to *\setsizes* is to update +*\treewidth* if the text box, which can be found in *\box0*, is wider +than the previous maximum. Then we add the (possibly updated) value +of *\treewidth* as a text string back onto the head of *\treesizes*. + +\vb +\def\sizelevel{\ifdim\treewidth<\wd0 % If greater than previous maximum + \treewidth=\wd0 \fi % Then set max to new high + \global\cons{\the\treewidth}\treesizes}% In either case, put back on list +\endvb + +\beginsection Pass 3: Typesetting the tree + +We are now ready to begin actual construction of the tree. This is +done by calling *\maketree*, which like *\setsizes* calls itself +recursively for all subtrees. It adds an *\hbox* containing the given +subtree (which it finds in *\treebox*) to the current horizontal list; +thus the outer call to *\maketree* sends the whole tree into \TeX's +output stream. + +\vb +\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 with spacing. +\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. +\endvb + +After *\maketree* sets *\treewidth* from *\treesizes*, it calls +*\makesubtreebox*. This opens up the horizontal list describing this +level of the tree, and checks whether it has subtrees. If not, +*\ifleaf* is set to true; otherwise it is set to false, and *\box0* +is set to contain a *\vbox* of them with their connecting rules, +except for the horizontal rule leading from the tree text to the +subtrees. In any case *\treebox* is set to the *\vbox* containing the +tree text. + +\vb + +{\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. + \setbox0\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. +\endvb + +If this tree or subtree itself has subtrees, we need to put them and +their connections in *\box0* for *\makesubtreebox*. We come here with +the bottom subtree in *\treebox*, the remaining list of subtrees in +the current horizontal list, and the already processed subtrees +stacked in *\box0*. The *\ifbotsub* test will be true for the first +call, that is, the bottom subtree. Here we process the subtree in +*\treebox*. If this is the top subtree, we return; otherwise we tail +recurse to process the remaining subtrees. We use *\box1* as +another scratch variable; this is safe because the *\hbox* in *\maketree* +puts us inside a group, and also because we are not changing the output list. + +\penalty-200 %%%%%%%%%%%%%%%%%%%% added for TUGboat + +\vb + +\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. +\endvb + +Each subtree in the list is processed and stacked in *\box0*; this is +done by *\addsubtreebox*, which calls *\subtreebox* to add connecting +rules to the subtree in *\box1*, and appends to that the old contents +of *\box0*. The vertical connecting rules in the tree are made with +tall narrow *\hrule*s rather than a more simple calls to *\vrule*, +because they are made inside a *\vbox*. + +\vb +\def\addsubtreebox{\setbox0=\vbox{\subtreebox\unvbox0}} +\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} +\endvb + +The last line of the definition of *\subtreebox* calls *\treectrbox* +twice: once for the horizontal connecting rule, and once for the +subtree box itself. This macro centers its argument in a *\vbox* the +height of this subtree and surrounding space. We also define here +*\treehalfrule*, the macro called to make an *\hrule* half the height +of the subtree (with half the height of the horizontal connection +added to make the corners come out square). + +\vb +\def\treectrbox#1{\vbox to \treeheight{\vfil #1\vfil}} +\def\treehalfrule{\dimen0=\treeheight % Get total height. + \divide\dimen0 2\advance\dimen0 0.2pt % Divide by two, add half horiz height. + \hrule width 0.4pt height \dimen0} % Make a vertical rule that high. +\endvb + +That completes *\makesubtree*. If this subtree has no sub-subtrees +under it, *\maketree* will now run *\makeleaf*; this merely adds the +tree text to the *\hbox* opened in *\maketree*. Otherwise we call +*\makeparent* to attach the sub-subtrees and connecting rules to the +text at the root of the subtree. + +\vb +\def\makeleaf{\box\treebox} % Add leaf box to horiz list. +\def\makeparent{\ifdim\ht\treebox>\ht0 % If text is higher than subtrees + \treeheight=\ht\treebox % ..use that height. + \else \treeheight=\ht0 \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{\box0}} % Add \hrule, subs. +\endvb + +% restore * to type ordinary +\catcode`\*=12 + +\endinput +%\bye -- cgit v1.2.3