sawine@11: %    pgftree.tex
sawine@11: %    Version 1.1, 25 Dec 2009
sawine@11: 
sawine@11: %    Copyright 2009 by David Chiang
sawine@11: 
sawine@11: %    This program is free software; you can redistribute it and/or modify
sawine@11: %    it under the terms of the GNU General Public License as published by
sawine@11: %    the Free Software Foundation; either version 2 of the License, or
sawine@11: %    (at your option) any later version.
sawine@11: 
sawine@11: %    This program is distributed in the hope that it will be useful,
sawine@11: %    but WITHOUT ANY WARRANTY; without even the implied warranty of
sawine@11: %    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
sawine@11: %    GNU General Public License for more details.
sawine@11: 
sawine@11: %    You should have received a copy of the GNU General Public License along
sawine@11: %    with this program; if not, write to the Free Software Foundation, Inc.,
sawine@11: %    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
sawine@11: 
sawine@11: % New in version 1.1:
sawine@11: % - major restructuring to not do arbitrary nesting of subpicture environments
sawine@11: % - sideways trees
sawine@11: 
sawine@11: % To do:
sawine@11: % - trees with all leaves at same level
sawine@11: % - if \nodename does not exist as desired, wrap inside a rectangle node
sawine@11: % - don't use pgfsubpic internals
sawine@11: 
sawine@11: \newdimen\levelsep \levelsep=30pt
sawine@11: \newdimen\subtreesep \subtreesep=2pt
sawine@11: 
sawine@11: \def\leveldirection{down}
sawine@11: \def\siblingdirection{right}
sawine@11: 
sawine@11: % definitions of growing directions
sawine@11: \def\pgftree@levelshift{\csname pgftree@levelshift@\leveldirection\endcsname}
sawine@11: \def\pgftree@parentanchor{\csname pgftree@parentanchor@\leveldirection\endcsname}
sawine@11: \def\pgftree@childanchor{\csname pgftree@childanchor@\leveldirection\endcsname}
sawine@11: % these assume that the current subpicture is the child
sawine@11: \def\pgftree@presiblingshift{\csname pgftree@presiblingshift@\siblingdirection\endcsname}
sawine@11: \def\pgftree@postsiblingshift{\csname pgftree@postsiblingshift@\siblingdirection\endcsname}
sawine@11: 
sawine@11: \def\pgftree@levelshift@down{\pgfpoint{0}{-\levelsep}}
sawine@11: \def\pgftree@parentanchor@down{south}
sawine@11: \def\pgftree@childanchor@down{north}
sawine@11: 
sawine@11: \def\pgftree@levelshift@up{\pgfpoint{0}{\levelsep}}
sawine@11: \def\pgftree@parentanchor@up{north}
sawine@11: \def\pgftree@childanchor@up{south}
sawine@11: 
sawine@11: \def\pgftree@levelshift@right{\pgfpoint{\levelsep}{0}}
sawine@11: \def\pgftree@parentanchor@right{east}
sawine@11: \def\pgftree@childanchor@right{west}
sawine@11: 
sawine@11: \def\pgftree@levelshift@left{\pgfpoint{-\levelsep}{0}}
sawine@11: \def\pgftree@parentanchor@left{west}
sawine@11: \def\pgftree@childanchor@left{east}
sawine@11: 
sawine@11: \def\pgftree@presiblingshift@right{\pgf@process{\pgf@x-\pgf@subpicminx \advance\pgf@x\subtreesep \pgf@y 0pt}}
sawine@11: \def\pgftree@postsiblingshift@right{\pgf@process{\pgf@x\pgf@subpicmaxx \pgf@y 0pt}}
sawine@11: 
sawine@11: \def\pgftree@presiblingshift@left{\pgf@process{\pgf@x-\pgf@subpicmaxx \advance\pgf@x-\subtreesep \pgf@y 0pt}}
sawine@11: \def\pgftree@postsiblingshift@left{\pgf@process{\pgf@x\pgf@subpicminx \pgf@y 0pt}}
sawine@11: 
sawine@11: \def\pgftree@presiblingshift@up{\pgf@process{\pgf@x 0pt \pgf@y-\pgf@subpicminy \advance\pgf@y\subtreesep}}
sawine@11: \def\pgftree@postsiblingshift@up{\pgf@process{\pgf@x 0pt \pgf@y\pgf@subpicmaxy}}
sawine@11: 
sawine@11: \def\pgftree@presiblingshift@down{\pgf@process{\pgf@x 0pt \pgf@y-\pgf@subpicmaxy \advance\pgf@y-\subtreesep}}
sawine@11: \def\pgftree@postsiblingshift@down{\pgf@process{\pgf@x 0pt \pgf@y\pgf@subpicminy}}
sawine@11: 
sawine@11: % for convenience if you are using \pgftree directly
sawine@11: \def\drawnode#1{\pgfnode{rectangle}{base}{#1}{\nodename}{\pgfusepath{discard}}}
sawine@11: \def\drawedge{%
sawine@11: \pgfpathmoveto{\pgfpointanchor{\parentnodename}{\pgftree@parentanchor}}%
sawine@11: \pgfpathlineto{\pgfpointanchor{\nodename}{\pgftree@childanchor}}%
sawine@11: \pgfusepath{stroke}}
sawine@11: 
sawine@11: % local variables that we need to assign to inside a \pgfforeach
sawine@11: \newdimen\pgftree@childx
sawine@11: \newdimen\pgftree@savechildx
sawine@11: \newdimen\pgftree@childy
sawine@11: \newdimen\pgftree@savechildy
sawine@11: \newcount\pgftree@childi
sawine@11: \newcount\pgftree@savechildi
sawine@11: 
sawine@11: %%% \pgftree{subtree}
sawine@11: 
sawine@11: \def\pgftree#1{%
sawine@11: \def\nodename{r}%
sawine@11: #1%
sawine@11: \pgfplacesubpicture
sawine@11: }
sawine@11: 
sawine@11: %%% \pgfsubtree{root}{subtrees}
sawine@11: % The first argument draws the root node using PGF/TikZ commands.
sawine@11: % The node must be named \nodename.
sawine@11: 
sawine@11: % The second argument is an even-length sequence of tokens.
sawine@11: % Token 2n-1 in the sequence draws the nth edge. It should draw an edge from \parentnodename to \nodename.
sawine@11: % Token 2n in the sequence draws the nth subtree. Its root must be named \nodename.
sawine@11: 
sawine@11: \pgfnewsubpicture{children}
sawine@11: \newdimen\pgftree@lastchildx
sawine@11: \newdimen\pgftree@lastchildy
sawine@11: 
sawine@11: \def\pgfsubtree#1#2{%
sawine@11: \let\parentnodename\nodename
sawine@11: \pgftree@savechildx=\pgftree@childx
sawine@11: \pgftree@savechildy=\pgftree@childy
sawine@11: \pgftree@savechildi=\pgftree@childi
sawine@11: % Build subpicture with all the children and their subtrees
sawine@11: {\pgftree@childx=0pt%
sawine@11: \pgftree@childy=0pt%
sawine@11: \pgftree@childi=0%
sawine@11: \process@children #2}%
sawine@11: \begin{pgfsubpicture}%
sawine@11: % Create node
sawine@11: #1%
sawine@11: \ifnum\pgftree@childi>0%
sawine@11: % Place children
sawine@11: % move down \levelsep
sawine@11: {\pgftransformshift{\pgftree@levelshift}%
sawine@11: % center so that parent is midway between origins of first and last children
sawine@11: \pgftransformshift{\pgfpointscale{-0.5}{\pgfqpoint{\the\pgftree@childx}{\the\pgftree@childy}}}%
sawine@11: \pgfplacesubpicture}%
sawine@11: % Draw the edges
sawine@11: {\pgftree@childi=0%
sawine@11: \process@edges #2}%
sawine@11: \fi
sawine@11: \end{pgfsubpicture}%
sawine@11: \global\pgftree@childi=\pgftree@savechildi
sawine@11: \global\pgftree@childx=\pgftree@savechildx
sawine@11: \global\pgftree@childy=\pgftree@savechildy
sawine@11: }
sawine@11: 
sawine@11: \def\process@children{%
sawine@11: \pgfutil@ifnextchar\egroup
sawine@11: {% No more children, step back to origin of last child
sawine@11: \global\pgftree@childx\pgftree@lastchildx
sawine@11: \global\pgftree@childy\pgftree@lastchildy
sawine@11: \global\pgftree@childi\pgftree@childi
sawine@11: \ifnum\pgftree@childi>0%
sawine@11: \pgfrestoresubpicture{children}% pass children back to caller
sawine@11: \fi
sawine@11: }%
sawine@11: {\@process@children}%
sawine@11: }
sawine@11: \def\@process@children#1#2{% #1 is the edge, #2 is the child
sawine@11: % Build the current child
sawine@11: {\edef\nodename{\parentnodename-\the\pgftree@childi}%
sawine@11: #2}%
sawine@11: \begin{pgfsubpicture}%
sawine@11: % Place current child
sawine@11: \ifnum\pgftree@childi>0% the first child is always at 0
sawine@11: \pgftree@presiblingshift \global\advance\pgftree@childx\pgf@x \global\advance\pgftree@childy\pgf@y
sawine@11: \fi
sawine@11: {\pgftransformshift{\pgfqpoint{\the\pgftree@childx}{\the\pgftree@childy}}%
sawine@11: \pgfplacesubpicture}%
sawine@11: \global\pgftree@lastchildx\pgftree@childx
sawine@11: \global\pgftree@lastchildy\pgftree@childy
sawine@11: \pgftree@postsiblingshift \global\advance\pgftree@childx\pgf@x \global\advance\pgftree@childy\pgf@y
sawine@11: % Save the augmented row of children back into "children"
sawine@11: \end{pgfsubpicture}
sawine@11: \ifnum\pgftree@childi>0%
sawine@11: \pgfmergesubpicture{children}
sawine@11: \else
sawine@11: \pgfsavesubpicture{children}%
sawine@11: \fi
sawine@11: \advance\pgftree@childi by 1%
sawine@11: \process@children
sawine@11: }
sawine@11: 
sawine@11: \def\process@edges{%
sawine@11: \pgfutil@ifnextchar\egroup
sawine@11: {}%
sawine@11: {\@process@edges}%
sawine@11: }
sawine@11: \def\@process@edges#1#2{%
sawine@11: \edef\nodename{\parentnodename-\the\pgftree@childi}%
sawine@11: #1%
sawine@11: \advance\pgftree@childi by 1%
sawine@11: \process@edges
sawine@11: }
sawine@11: 
sawine@11: \def\subtreeof#1{%
sawine@11: % the subpicture which contains a node also contains exactly its subtree
sawine@11: \csname pgf@sh@pi@#1\endcsname
sawine@11: }