%    pgftree.tex

%    Version 1.1, 25 Dec 2009

%    Copyright 2009 by David Chiang

%    This program is free software; you can redistribute it and/or modify

%    it under the terms of the GNU General Public License as published by

%    the Free Software Foundation; either version 2 of the License, or

%    (at your option) any later version.

%    This program is distributed in the hope that it will be useful,

%    but WITHOUT ANY WARRANTY; without even the implied warranty of

%    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

%    GNU General Public License for more details.

%    You should have received a copy of the GNU General Public License along

%    with this program; if not, write to the Free Software Foundation, Inc.,

%    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.

% New in version 1.1:

% - major restructuring to not do arbitrary nesting of subpicture environments

% - sideways trees

% To do:

% - trees with all leaves at same level

% - if \nodename does not exist as desired, wrap inside a rectangle node

% - don't use pgfsubpic internals

\newdimen\levelsep \levelsep=30pt

\newdimen\subtreesep \subtreesep=2pt

\def\leveldirection{down}

\def\siblingdirection{right}

% definitions of growing directions

\def\pgftree@levelshift{\csname pgftree@levelshift@\leveldirection\endcsname}

\def\pgftree@parentanchor{\csname pgftree@parentanchor@\leveldirection\endcsname}

\def\pgftree@childanchor{\csname pgftree@childanchor@\leveldirection\endcsname}

% these assume that the current subpicture is the child

\def\pgftree@presiblingshift{\csname pgftree@presiblingshift@\siblingdirection\endcsname}

\def\pgftree@postsiblingshift{\csname pgftree@postsiblingshift@\siblingdirection\endcsname}

\def\pgftree@levelshift@down{\pgfpoint{0}{-\levelsep}}

\def\pgftree@parentanchor@down{south}

\def\pgftree@childanchor@down{north}

\def\pgftree@levelshift@up{\pgfpoint{0}{\levelsep}}

\def\pgftree@parentanchor@up{north}

\def\pgftree@childanchor@up{south}

\def\pgftree@levelshift@right{\pgfpoint{\levelsep}{0}}

\def\pgftree@parentanchor@right{east}

\def\pgftree@childanchor@right{west}

\def\pgftree@levelshift@left{\pgfpoint{-\levelsep}{0}}

\def\pgftree@parentanchor@left{west}

\def\pgftree@childanchor@left{east}

\def\pgftree@presiblingshift@right{\pgf@process{\pgf@x-\pgf@subpicminx \advance\pgf@x\subtreesep \pgf@y 0pt}}

\def\pgftree@postsiblingshift@right{\pgf@process{\pgf@x\pgf@subpicmaxx \pgf@y 0pt}}

\def\pgftree@presiblingshift@left{\pgf@process{\pgf@x-\pgf@subpicmaxx \advance\pgf@x-\subtreesep \pgf@y 0pt}}

\def\pgftree@postsiblingshift@left{\pgf@process{\pgf@x\pgf@subpicminx \pgf@y 0pt}}

\def\pgftree@presiblingshift@up{\pgf@process{\pgf@x 0pt \pgf@y-\pgf@subpicminy \advance\pgf@y\subtreesep}}

\def\pgftree@postsiblingshift@up{\pgf@process{\pgf@x 0pt \pgf@y\pgf@subpicmaxy}}

\def\pgftree@presiblingshift@down{\pgf@process{\pgf@x 0pt \pgf@y-\pgf@subpicmaxy \advance\pgf@y-\subtreesep}}

\def\pgftree@postsiblingshift@down{\pgf@process{\pgf@x 0pt \pgf@y\pgf@subpicminy}}

% for convenience if you are using \pgftree directly

\def\drawnode#1{\pgfnode{rectangle}{base}{#1}{\nodename}{\pgfusepath{discard}}}

\def\drawedge{%

\pgfpathmoveto{\pgfpointanchor{\parentnodename}{\pgftree@parentanchor}}%

\pgfpathlineto{\pgfpointanchor{\nodename}{\pgftree@childanchor}}%

\pgfusepath{stroke}}

% local variables that we need to assign to inside a \pgfforeach

\newdimen\pgftree@childx

\newdimen\pgftree@savechildx

\newdimen\pgftree@childy

\newdimen\pgftree@savechildy

\newcount\pgftree@childi

\newcount\pgftree@savechildi

%%% \pgftree{subtree}

\def\pgftree#1{%

\def\nodename{r}%

#1%

\pgfplacesubpicture

}

%%% \pgfsubtree{root}{subtrees}

% The first argument draws the root node using PGF/TikZ commands.

% The node must be named \nodename.

% The second argument is an even-length sequence of tokens.

% Token 2n-1 in the sequence draws the nth edge. It should draw an edge from \parentnodename to \nodename.

% Token 2n in the sequence draws the nth subtree. Its root must be named \nodename.

\pgfnewsubpicture{children}

\newdimen\pgftree@lastchildx

\newdimen\pgftree@lastchildy

\def\pgfsubtree#1#2{%

\let\parentnodename\nodename

\pgftree@savechildx=\pgftree@childx

\pgftree@savechildy=\pgftree@childy

\pgftree@savechildi=\pgftree@childi

% Build subpicture with all the children and their subtrees

{\pgftree@childx=0pt%

\pgftree@childy=0pt%

\pgftree@childi=0%

\process@children #2}%

\begin{pgfsubpicture}%

% Create node

#1%

\ifnum\pgftree@childi>0%

% Place children

% move down \levelsep

{\pgftransformshift{\pgftree@levelshift}%

% center so that parent is midway between origins of first and last children

\pgftransformshift{\pgfpointscale{-0.5}{\pgfqpoint{\the\pgftree@childx}{\the\pgftree@childy}}}%

\pgfplacesubpicture}%

% Draw the edges

{\pgftree@childi=0%

\process@edges #2}%

\fi

\end{pgfsubpicture}%

\global\pgftree@childi=\pgftree@savechildi

\global\pgftree@childx=\pgftree@savechildx

\global\pgftree@childy=\pgftree@savechildy

}

\def\process@children{%

\pgfutil@ifnextchar\egroup

{% No more children, step back to origin of last child

\global\pgftree@childx\pgftree@lastchildx

\global\pgftree@childy\pgftree@lastchildy

\global\pgftree@childi\pgftree@childi

\ifnum\pgftree@childi>0%

\pgfrestoresubpicture{children}% pass children back to caller

\fi

}%

{\@process@children}%

}

\def\@process@children#1#2{% #1 is the edge, #2 is the child

% Build the current child

{\edef\nodename{\parentnodename-\the\pgftree@childi}%

#2}%

\begin{pgfsubpicture}%

% Place current child

\ifnum\pgftree@childi>0% the first child is always at 0

\pgftree@presiblingshift \global\advance\pgftree@childx\pgf@x \global\advance\pgftree@childy\pgf@y

\fi

{\pgftransformshift{\pgfqpoint{\the\pgftree@childx}{\the\pgftree@childy}}%

\pgfplacesubpicture}%

\global\pgftree@lastchildx\pgftree@childx

\global\pgftree@lastchildy\pgftree@childy

\pgftree@postsiblingshift \global\advance\pgftree@childx\pgf@x \global\advance\pgftree@childy\pgf@y

% Save the augmented row of children back into "children"

\end{pgfsubpicture}

\ifnum\pgftree@childi>0%

\pgfmergesubpicture{children}

\else

\pgfsavesubpicture{children}%

\fi

\advance\pgftree@childi by 1%

\process@children

}

\def\process@edges{%

\pgfutil@ifnextchar\egroup

{}%

{\@process@edges}%

}

\def\@process@edges#1#2{%

\edef\nodename{\parentnodename-\the\pgftree@childi}%

#1%

\advance\pgftree@childi by 1%

\process@edges

}

\def\subtreeof#1{%

% the subpicture which contains a node also contains exactly its subtree

\csname pgf@sh@pi@#1\endcsname

}