From a3035e710219b198c2c191e161a8ec3ac677e0e6 Mon Sep 17 00:00:00 2001
From: Joel Sherrill <joel.sherrill@OARcorp.com>
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/treedef.tex')

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

