summaryrefslogtreecommitdiff
path: root/graphics/pictex/tree.sty
diff options
context:
space:
mode:
authorNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
committerNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
commite0c6872cf40896c7be36b11dcc744620f10adf1d (patch)
tree60335e10d2f4354b0674ec22d7b53f0f8abee672 /graphics/pictex/tree.sty
Initial commit
Diffstat (limited to 'graphics/pictex/tree.sty')
-rw-r--r--graphics/pictex/tree.sty353
1 files changed, 353 insertions, 0 deletions
diff --git a/graphics/pictex/tree.sty b/graphics/pictex/tree.sty
new file mode 100644
index 0000000000..6e91652a0e
--- /dev/null
+++ b/graphics/pictex/tree.sty
@@ -0,0 +1,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%