From a3035e710219b198c2c191e161a8ec3ac677e0e6 Mon Sep 17 00:00:00 2001 From: Joel Sherrill Date: Tue, 27 May 1997 12:40:10 +0000 Subject: base RTEMS documentation --- doc/common/treedef.tex | 317 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 317 insertions(+) create mode 100644 doc/common/treedef.tex (limited to 'doc/common') diff --git a/doc/common/treedef.tex b/doc/common/treedef.tex new file mode 100644 index 0000000000..26eda0c28c --- /dev/null +++ b/doc/common/treedef.tex @@ -0,0 +1,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 -- cgit v1.2.3