diff options
author | Karl Berry <karl@freefriends.org> | 2006-01-12 23:46:03 +0000 |
---|---|---|
committer | Karl Berry <karl@freefriends.org> | 2006-01-12 23:46:03 +0000 |
commit | 873660d1a83ece926fe7206288dda9c36b349c1b (patch) | |
tree | a48f77125c309a355b5d0eb58d6b24446abe9d62 /Master/texmf-dist/tex/generic/pictex/tree.sty | |
parent | 2939242967231097459df0fc3150fabc2f639111 (diff) |
generic 1
git-svn-id: svn://tug.org/texlive/trunk@613 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Master/texmf-dist/tex/generic/pictex/tree.sty')
-rw-r--r-- | Master/texmf-dist/tex/generic/pictex/tree.sty | 353 |
1 files changed, 353 insertions, 0 deletions
diff --git a/Master/texmf-dist/tex/generic/pictex/tree.sty b/Master/texmf-dist/tex/generic/pictex/tree.sty new file mode 100644 index 00000000000..6e91652a0e3 --- /dev/null +++ b/Master/texmf-dist/tex/generic/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% |