1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/exercises/solutions/pgftree.tex Sun Jun 03 20:15:28 2012 +0200
1.3 @@ -0,0 +1,188 @@
1.4 +% pgftree.tex
1.5 +% Version 1.1, 25 Dec 2009
1.6 +
1.7 +% Copyright 2009 by David Chiang
1.8 +
1.9 +% This program is free software; you can redistribute it and/or modify
1.10 +% it under the terms of the GNU General Public License as published by
1.11 +% the Free Software Foundation; either version 2 of the License, or
1.12 +% (at your option) any later version.
1.13 +
1.14 +% This program is distributed in the hope that it will be useful,
1.15 +% but WITHOUT ANY WARRANTY; without even the implied warranty of
1.16 +% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
1.17 +% GNU General Public License for more details.
1.18 +
1.19 +% You should have received a copy of the GNU General Public License along
1.20 +% with this program; if not, write to the Free Software Foundation, Inc.,
1.21 +% 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
1.22 +
1.23 +% New in version 1.1:
1.24 +% - major restructuring to not do arbitrary nesting of subpicture environments
1.25 +% - sideways trees
1.26 +
1.27 +% To do:
1.28 +% - trees with all leaves at same level
1.29 +% - if \nodename does not exist as desired, wrap inside a rectangle node
1.30 +% - don't use pgfsubpic internals
1.31 +
1.32 +\newdimen\levelsep \levelsep=30pt
1.33 +\newdimen\subtreesep \subtreesep=2pt
1.34 +
1.35 +\def\leveldirection{down}
1.36 +\def\siblingdirection{right}
1.37 +
1.38 +% definitions of growing directions
1.39 +\def\pgftree@levelshift{\csname pgftree@levelshift@\leveldirection\endcsname}
1.40 +\def\pgftree@parentanchor{\csname pgftree@parentanchor@\leveldirection\endcsname}
1.41 +\def\pgftree@childanchor{\csname pgftree@childanchor@\leveldirection\endcsname}
1.42 +% these assume that the current subpicture is the child
1.43 +\def\pgftree@presiblingshift{\csname pgftree@presiblingshift@\siblingdirection\endcsname}
1.44 +\def\pgftree@postsiblingshift{\csname pgftree@postsiblingshift@\siblingdirection\endcsname}
1.45 +
1.46 +\def\pgftree@levelshift@down{\pgfpoint{0}{-\levelsep}}
1.47 +\def\pgftree@parentanchor@down{south}
1.48 +\def\pgftree@childanchor@down{north}
1.49 +
1.50 +\def\pgftree@levelshift@up{\pgfpoint{0}{\levelsep}}
1.51 +\def\pgftree@parentanchor@up{north}
1.52 +\def\pgftree@childanchor@up{south}
1.53 +
1.54 +\def\pgftree@levelshift@right{\pgfpoint{\levelsep}{0}}
1.55 +\def\pgftree@parentanchor@right{east}
1.56 +\def\pgftree@childanchor@right{west}
1.57 +
1.58 +\def\pgftree@levelshift@left{\pgfpoint{-\levelsep}{0}}
1.59 +\def\pgftree@parentanchor@left{west}
1.60 +\def\pgftree@childanchor@left{east}
1.61 +
1.62 +\def\pgftree@presiblingshift@right{\pgf@process{\pgf@x-\pgf@subpicminx \advance\pgf@x\subtreesep \pgf@y 0pt}}
1.63 +\def\pgftree@postsiblingshift@right{\pgf@process{\pgf@x\pgf@subpicmaxx \pgf@y 0pt}}
1.64 +
1.65 +\def\pgftree@presiblingshift@left{\pgf@process{\pgf@x-\pgf@subpicmaxx \advance\pgf@x-\subtreesep \pgf@y 0pt}}
1.66 +\def\pgftree@postsiblingshift@left{\pgf@process{\pgf@x\pgf@subpicminx \pgf@y 0pt}}
1.67 +
1.68 +\def\pgftree@presiblingshift@up{\pgf@process{\pgf@x 0pt \pgf@y-\pgf@subpicminy \advance\pgf@y\subtreesep}}
1.69 +\def\pgftree@postsiblingshift@up{\pgf@process{\pgf@x 0pt \pgf@y\pgf@subpicmaxy}}
1.70 +
1.71 +\def\pgftree@presiblingshift@down{\pgf@process{\pgf@x 0pt \pgf@y-\pgf@subpicmaxy \advance\pgf@y-\subtreesep}}
1.72 +\def\pgftree@postsiblingshift@down{\pgf@process{\pgf@x 0pt \pgf@y\pgf@subpicminy}}
1.73 +
1.74 +% for convenience if you are using \pgftree directly
1.75 +\def\drawnode#1{\pgfnode{rectangle}{base}{#1}{\nodename}{\pgfusepath{discard}}}
1.76 +\def\drawedge{%
1.77 +\pgfpathmoveto{\pgfpointanchor{\parentnodename}{\pgftree@parentanchor}}%
1.78 +\pgfpathlineto{\pgfpointanchor{\nodename}{\pgftree@childanchor}}%
1.79 +\pgfusepath{stroke}}
1.80 +
1.81 +% local variables that we need to assign to inside a \pgfforeach
1.82 +\newdimen\pgftree@childx
1.83 +\newdimen\pgftree@savechildx
1.84 +\newdimen\pgftree@childy
1.85 +\newdimen\pgftree@savechildy
1.86 +\newcount\pgftree@childi
1.87 +\newcount\pgftree@savechildi
1.88 +
1.89 +%%% \pgftree{subtree}
1.90 +
1.91 +\def\pgftree#1{%
1.92 +\def\nodename{r}%
1.93 +#1%
1.94 +\pgfplacesubpicture
1.95 +}
1.96 +
1.97 +%%% \pgfsubtree{root}{subtrees}
1.98 +% The first argument draws the root node using PGF/TikZ commands.
1.99 +% The node must be named \nodename.
1.100 +
1.101 +% The second argument is an even-length sequence of tokens.
1.102 +% Token 2n-1 in the sequence draws the nth edge. It should draw an edge from \parentnodename to \nodename.
1.103 +% Token 2n in the sequence draws the nth subtree. Its root must be named \nodename.
1.104 +
1.105 +\pgfnewsubpicture{children}
1.106 +\newdimen\pgftree@lastchildx
1.107 +\newdimen\pgftree@lastchildy
1.108 +
1.109 +\def\pgfsubtree#1#2{%
1.110 +\let\parentnodename\nodename
1.111 +\pgftree@savechildx=\pgftree@childx
1.112 +\pgftree@savechildy=\pgftree@childy
1.113 +\pgftree@savechildi=\pgftree@childi
1.114 +% Build subpicture with all the children and their subtrees
1.115 +{\pgftree@childx=0pt%
1.116 +\pgftree@childy=0pt%
1.117 +\pgftree@childi=0%
1.118 +\process@children #2}%
1.119 +\begin{pgfsubpicture}%
1.120 +% Create node
1.121 +#1%
1.122 +\ifnum\pgftree@childi>0%
1.123 +% Place children
1.124 +% move down \levelsep
1.125 +{\pgftransformshift{\pgftree@levelshift}%
1.126 +% center so that parent is midway between origins of first and last children
1.127 +\pgftransformshift{\pgfpointscale{-0.5}{\pgfqpoint{\the\pgftree@childx}{\the\pgftree@childy}}}%
1.128 +\pgfplacesubpicture}%
1.129 +% Draw the edges
1.130 +{\pgftree@childi=0%
1.131 +\process@edges #2}%
1.132 +\fi
1.133 +\end{pgfsubpicture}%
1.134 +\global\pgftree@childi=\pgftree@savechildi
1.135 +\global\pgftree@childx=\pgftree@savechildx
1.136 +\global\pgftree@childy=\pgftree@savechildy
1.137 +}
1.138 +
1.139 +\def\process@children{%
1.140 +\pgfutil@ifnextchar\egroup
1.141 +{% No more children, step back to origin of last child
1.142 +\global\pgftree@childx\pgftree@lastchildx
1.143 +\global\pgftree@childy\pgftree@lastchildy
1.144 +\global\pgftree@childi\pgftree@childi
1.145 +\ifnum\pgftree@childi>0%
1.146 +\pgfrestoresubpicture{children}% pass children back to caller
1.147 +\fi
1.148 +}%
1.149 +{\@process@children}%
1.150 +}
1.151 +\def\@process@children#1#2{% #1 is the edge, #2 is the child
1.152 +% Build the current child
1.153 +{\edef\nodename{\parentnodename-\the\pgftree@childi}%
1.154 +#2}%
1.155 +\begin{pgfsubpicture}%
1.156 +% Place current child
1.157 +\ifnum\pgftree@childi>0% the first child is always at 0
1.158 +\pgftree@presiblingshift \global\advance\pgftree@childx\pgf@x \global\advance\pgftree@childy\pgf@y
1.159 +\fi
1.160 +{\pgftransformshift{\pgfqpoint{\the\pgftree@childx}{\the\pgftree@childy}}%
1.161 +\pgfplacesubpicture}%
1.162 +\global\pgftree@lastchildx\pgftree@childx
1.163 +\global\pgftree@lastchildy\pgftree@childy
1.164 +\pgftree@postsiblingshift \global\advance\pgftree@childx\pgf@x \global\advance\pgftree@childy\pgf@y
1.165 +% Save the augmented row of children back into "children"
1.166 +\end{pgfsubpicture}
1.167 +\ifnum\pgftree@childi>0%
1.168 +\pgfmergesubpicture{children}
1.169 +\else
1.170 +\pgfsavesubpicture{children}%
1.171 +\fi
1.172 +\advance\pgftree@childi by 1%
1.173 +\process@children
1.174 +}
1.175 +
1.176 +\def\process@edges{%
1.177 +\pgfutil@ifnextchar\egroup
1.178 +{}%
1.179 +{\@process@edges}%
1.180 +}
1.181 +\def\@process@edges#1#2{%
1.182 +\edef\nodename{\parentnodename-\the\pgftree@childi}%
1.183 +#1%
1.184 +\advance\pgftree@childi by 1%
1.185 +\process@edges
1.186 +}
1.187 +
1.188 +\def\subtreeof#1{%
1.189 +% the subpicture which contains a node also contains exactly its subtree
1.190 +\csname pgf@sh@pi@#1\endcsname
1.191 +}