%
% \title{\texttt{trees.sty} -- A Package for Typesetting Trees}
% \author{Manuel Kauers}
% \maketitle
%
% \newenvironment{treeenv}
% {\smallskip\par\noindent\null\hfill}
% {\hfill\null\par\noindent}
%
% \newenvironment{example}
% {\par\goodbreak\medskip
%  \begin{minipage}[c]{.45\textwidth}
%   \def\switch{\end{minipage}\begin{minipage}[c]{.45\textwidth}\hfil}
%   \obeylines
% }{\hfil\end{minipage}\medskip\goodbreak\par}
%
% \MakeShortVerb{\|}
%
% \begin{abstract}
%  This package provides \LaTeX-macros for typesetting trees in a
%  way which makes optimal use of horizontal space.
%  Tree nodes may contain arbitrary material, tree edges are composed
%  of vertical and horizontal lines. 
% \end{abstract}
%
% \tableofcontents
%
% \section{Usage}
%
% \subsection{What the package can do}
%
% \subsubsection*{Trees?}
%
% The purpose of this package is to provide the user with macros that
% allow him/her to typeset trees. 
% A~\emph{tree} is recursive structure which is either a \emph{node}
% or a node together with a set of (sub-)trees. 
% It looks like this:
%
% \begin{treeenv}
%  \tree{Grandfather and Grandmother}{%
%   \tree{Uncle and Aunt}{%
%    \leaf{Cousine}
%   }
%   \tree{Father and Mother}{%
%    \tree{Brother}{%
%     \leaf{Nephew}%
%     \leaf{Niece}%
%    }
%    \tree{Me}{%
%     \tree{Doughter}{%
%      \leaf{Grandson}
%     }
%     \tree{Son}{%
%      \leaf{Granddoughter}%
%     }
%    }
%    \tree{Sister}{%
%     \leaf{Nephew}%
%     \leaf{Niece}%
%    }
%   }
%   \tree{Uncle and Aunt}{%
%    \leaf{Cousine}
%   }
%  }
% \end{treeenv}
%
% \subsubsection*{There are already packages for this purpose}
%
% Yes, but all of the packages that I was aware of at time of
% writing either wasted a lot of space, or they were to difficult to
% use, or they required to use packages which were in conflict with
% other packages I needed. 
% After all, writing packages is kind of sports\dots
%
% This package now aims at being both easy to use and smart in procuding
% nice output. 
% A tree is considered nice if its horizontal expansion is
% small. For instance, most tree packages produce something like
% \begin{treeenv}
%  \tree0{\leaf1\tree{\hbox to 30pt{\hss 2\hss}}{\leaf3\leaf4\leaf5}\leaf6}
% \end{treeenv}%
% because their implementation simply puts subtree next to subtree
% without considering shrinking the space between two neighbours if
% possible. 
% When our package is asked to procuce the tree above, it will produce
% \begin{treeenv}
%  \tree0{\leaf1\tree2{\leaf3\leaf4\leaf5}\leaf6}
% \end{treeenv}%
% which is quite nice according to the above definition of ``nice.''
% In practice, trees tend to become very large, even reasonable trees
% don't fit on one page, that's why we regard the computation of small
% output as an important feature of a tree package. 
%
% The package does not support edges that go directly from one node to
% its parent -- all tree edges are based on vertical lines which are
% centered with respect to the nodes they connect and with horizontal
% parts to connect the vertical parts accordingly.
%
% \subsection{How you get it to do it}
%
% A tree consists of a node and a list of subtrees where a subtree is
% a tree or a single node. In the latter case it is called a leaf.
% That's everything you need to know. Put the |trees.sty| file into a
% directory where \TeX\ will find it, say |\usepackage{trees}| in the
% preamble, and you can continue like this:
%
% \begin{example}
%  |\tree{root}{%|
%  | \leaf{leaf 1}|
%  | \leaf{leaf 2}|
%  | \leaf{leaf 3}|
%  |}|
% \switch
%  \tree{root}{%
%   \leaf{leaf 1}
%   \leaf{leaf 2}
%   \leaf{leaf 3}
%  }
% \end{example}
%
% \begin{macro}{\tree}
% \begin{macro}{\leaf}
% The |\tree| command takes two arguments. The first argument contains
% the root of the tree and the second argument consists of an ordered
% bunch of subtrees which may themselves be trees or leaves. Here,
% |\leaf| is simply defined as |\tree{#1}{}| to save one~|{}|.
%
% Here is an example with a tree of depth~3:
%
% \begin{example}
%  |\tree{$\top$}{%|
%  | \tree{0}{%|
%  |  \tree{0}{%|
%  |   \leaf{0}\leaf{1}}|
%  |  \tree{1}{%|
%  |   \leaf{0}\leaf{1}}}|
%  | \tree{1}{%|
%  |  \tree{0}{%|
%  |   \leaf{0}\leaf{1}}|
%  |  \tree{1}{%|
%  |   \leaf{0}\leaf{1}}}}|
% \switch
%  \tree{$\top$}{%
%   \tree0{\tree0{\leaf0\leaf1}\tree1{\leaf0\leaf1}}
%   \tree1{\tree0{\leaf0\leaf1}\tree1{\leaf0\leaf1}}
%  }
% \end{example}
% 
% The next example shows how different subtrees come close to each
% other. The example also shows that different nodes may change font
% properties like size or shape. In case of different node sizes the
% package will also take care that all nodes of the same level share
% the same ground line. 
% 
% \begin{example}
%  |\tree{\textsc{An Example}}{|
%  | \tree{\large|
%  |     \textbf{a long node}}{|
%  |  \leaf{\footnotesize|
%  |      short node}}|
%  | \tree{\footnotesize|
%  |      short node}{|
%  |  \leaf{\large|
%  |      \textbf{a long node}}}}|\kern-1em
% \switch
%  \tree{\textsc{An Example}}{
%   \tree{\large\bf a long node}{
%   \leaf{\footnotesize short node}}
%   \tree{\footnotesize short node}{
%   \leaf{\large\bf a long node}}
%  }
% \end{example}
% You might complain that the package does more than it should in the
% sense that in the result above the distance between the nodes of the
% same level are too small. 
% Don't worry, things like this are subject to global objects which
% will be discussed in the next section. 
%
% We conclude this section with a last example
%
% \begin{treeenv}
%\tree{0}{
%  \tree{1}{
%    \leaf2
%    \tree3{
%      \leaf4
%      \tree5{
%        \leaf6
%        \leaf7
%        \tree8{
%          \leaf9
%          \leaf{10}
%          \leaf{11}
%          \leaf{12}
%          \leaf{13}
%       }}}
%    \leaf{14}
%    \leaf{15}
%    \leaf{16}}
%  \leaf{17}
%  \tree{18}{
%    \tree{19}{
%      \leaf{20}
%      \tree{21}{
%        \leaf{22}
%        \leaf{23}
%        \leaf{24}}
%      \leaf{25}
%      \tree{26}{
%        \tree{27}{
%         \tree{28}{
%           \leaf{29}
%           \leaf{30}
%           \leaf{31}
%         }
%         \leaf{32}
%         \leaf{33}
%         \tree{34}{
%           \leaf{35}
%           \leaf{36}
%         }
%      }}
%      \leaf{37}}
%    \leaf{38}
%    \leaf{39}} 
%  \leaf{40}  
%  \leaf{41}
%  \tree{42}{
%    \tree{43}{
%      \tree{44}{
%        \leaf{45}
%        \leaf{46}
%        \tree{47}{
%          \tree{48}{
%            \leaf{49}
%        }}
%     }}
%    \leaf{50}
%   }}
% \end{treeenv}
% \end{macro}
% \end{macro}
%
% \subsection{Customisation}
%
% The tree generation depends on certain parameters which can be 
% modified by the user. In the examples of this section, we will 
% assume that |\Tree| is a macro which expands to the following
% definition:
%
% \medskip\par\noindent
% |\tree{\fbox{root}}{%|\\
% |  \tree{left}{%|\\
% |   \leaf{1}\leaf{\fbox{2}}\leaf{3}}|\\
% |  \tree{middle}{\tree{middle}{%|\\
% |    \leaf{\tiny tiny}|\\
% |    \leaf{\small small}|\\
% |    \leaf{\large large}|\\
% |    \leaf{\huge huge}|\\
% |  }}|\\
% |  \tree{right}{%|\\
% |   \leaf{3}\leaf{\fbox{2}}\leaf{1}}}|
% 
% \medskip\par\noindent
% In the normal setting this gives the following tree:
%
% \def\Tree{%
%  \tree{\fbox{root}}{%
%    \tree{left}{\leaf1\leaf{\fbox{2}}\leaf3}
%    \tree{middle}{\tree{middle}{%
%     \leaf{\tiny tiny}\leaf{\small small}\leaf{\large
%     large}\leaf{\huge huge}
%    }}
%    \tree{right}{\leaf3\leaf{\fbox{2}}\leaf1}
%  }
% }
% \def\ttree{\begin{treeenv}\Tree\end{treeenv}}
% \ttree
%
% \def\treeex#1#2#3{%
%   \medskip\par\noindent
%   \begin{treeenv}
%     #1=#2\Tree\hfill
%     #1=#3\Tree
%   \end{treeenv}}
%
% \subsubsection*{The edge width}
% \begin{macro}{\edgewidth}
% The \TeX\ length |\edgewidth| denotes the thickness of the lines
% which are used for drawing the edges. Its default value is~|.3pt|.
%
% \medskip\par\noindent
% |\edgewidth=0pt\Tree|\\
% |\edgewidth=1pt\Tree|
% \treeex\edgewidth{0pt}{1pt}
% \end{macro}
%
% \subsubsection*{The level skip}
% \begin{macro}{\edgeheight} 
% The \TeX\ length |\edgeheight| denotes half of the distance between
% two levels, i.e., the length of the vertical part of an edge which
% connects a node to the horizontal part of an edge. 
% Here the default value is~|3pt|.
%
% \medskip\par\noindent
% |\edgeheight=0pt\Tree|\\
% |\edgeheight=6pt\Tree|
% \treeex\edgeheight{0pt}{6pt}
% \end{macro}
%
% The left example shows that this value only specifies the desired
% length, in fact the minimum length. It might be stretched by the
% package in order to get nodes of different size to the same ground
% line. 
%
% \subsubsection*{The node distance}
% \begin{macro}{\nodeskip}
% The \TeX\ length |\nodeskip| denotes the desired amount of horizontal space
% between to consecutive nodes of the same level (regardless whether
% or not they belong to the same subtree). Again, this is only a
% minimum value which might be stretched locally by the package, if
% necessary. 
% The default value is~|.5em|. 
%
% \medskip\par\noindent
% |\nodeskip=0pt\Tree|\\
% |\nodeskip=1em\Tree|
% \treeex\nodeskip{0pt}{1em}
% \end{macro}
%
% \subsubsection*{The node separation}
% \begin{macro}{\nodesep}
% The |\nodesep| \TeX\ length denotes the distance of the box
% containing a node and the start of the vertical part of the edge
% which eventually connects this note to the others.
% The default here is again~|3pt|, and the package will not adjust
% this value locally as it does with others.
%
% \medskip\par\noindent
% |\nodesep=0pt\Tree|\\
% |\nodesep=6pt\Tree|
% \treeex\nodesep{0pt}{6pt}
% \end{macro}
%
% \subsubsection*{The node fontifier macro}
% \begin{macro}{\node}%
% The |\node| macro implements the template method design pattern. It
% is used by the package to typeset individual nodes. By its
% redefinition, it is for instance possible to define math mode trees
% 
% \medskip\par\noindent
% |\def\mtree#1#2{{\def\node##1{$##1$}\tree{#1}{#2}}}|
% \medskip\par\noindent
% if desired. This allows to omit the math shifts when writing a tree
% whose nodes contain math material. (Note that only the outermost
% |\tree| needs to be changed to |\mtree|.)
%
% \def\mtree#1#2{{\def\node##1{$##1$}\tree{#1}{#2}}}
% \begin{example}
%  |\mtree{x^2}{%|
%  | \leaf{\frac{1}{2}}|
%  | \tree{x^{x^x}}{%|
%  |  \leaf{y_1}\leaf{y_2}}}|
% \switch
%  \mtree{x^2}{\leaf{\frac12}\tree{x^{x^x}}{\leaf{y_1}\leaf{y_2}}}
% \end{example}
% 
% We illustrate the usage of |\node| in the context of our |\Tree|
% example.
%
% \medskip\par\noindent
% |\def\node#1{\textbf{#1}}\Tree|\\
% |\def\node#1{\textit{#1}}\Tree|
% \begin{treeenv}
%  \def\node#1{\textbf{#1}}\Tree\hfill
%  \def\node#1{\textit{#1}}\Tree
% \end{treeenv}
%
% The default definition is
%
% \medskip\par\noindent
% |\def\node#1{#1}|
% \end{macro}
% 
% \subsubsection*{Vertical node orientation}
%
% By default, nodes of the same level are arranged such that they
% share the same base line. This gives by far the nicest result,
% however, you are free to change to a different alignment policy.
% You have the choice to align levels with respect to 
%
% \begin{enumerate}
% \item their base line (by |\baselevels|, this is default),
% \item their vertical center (by |\centerlevels|),
% \item their bottom (by |\floorlevels|), or to
% \item their top (by |\ceillevels|).
% \end{enumerate}
% 
% On the |\Tree| example this looks as follows:
%
% \par\medskip\noindent
% |\baselevels\Tree     \centerlevels\Tree|\\
% |\floorlevels\Tree    \ceillevels\Tree|\\
% \begin{treeenv}
%  \Tree\hfill
%  \centerlevels\Tree\hfill\null\\\null\hfill
%  \floorlevels\Tree\hfill
%  \ceillevels\Tree
% \end{treeenv}
% 
% \subsection{Bug parade}
% 
% No bugs known. 
% If you find one, please let me know: \texttt{manuel@kauers.de}.
%
% \section{Algorithmic Background}
%
% \subsection{Basics}
%
% The typesetting of a tree proceeds in a divide and conquer approach.
% In order to typeset a tree~$t$ which has the root~$r$ and subtrees
% $t_1,\dots,t_n$, first compute recursivley boxed for
% $t_1,\dots,t_n$ and a box containing~$r$. Then put the boxes of
% $t_1,\dots,t_n$ into an |\hbox|~$s$ (with appropriate distances between
% them). From the width of $t_1,t_n$ and $s$ the length of the
% horizontal edge can be computed easily. Taking the leftmost point of
% $s$ as a basis, the horizontal part of the edge to typeset starts at
% width $w(t_1)/2$ and has length $w(s)-(w(t_1)+w(t_2))/2$. 
% The final box containing $t$ will be a vertical box (actually a
% |\vtop|) containing the following elements:
% \begin{enumerate}
% \item A vertical rule which eventually connects $t$ to its parent
% (omitted if $t$ doesn't have a parent)
% \item The root box $r$
% \item A vertical rule connecting $r$ with the horizontal part of the
% edge
% \item the horizontal edge
% \item the subtree array~$s$
% \end{enumerate}
% All elements except for the horizontal edge will be centered, the
% horizontal line will be put as described above. 
%
% This is the natural way to implement a tree algorithm in \TeX, and
% it is also the idea underlying our implementation. 
% However, quite a bit of work is necessary to tune this algorithm
% such that it produces nice results.
% There are essentially two problems: 
% \begin{enumerate}
% \item Nodes of the same level need to be aligned. 
%  Only nodes of the first level of a tree are aligned properly, but
%  two nodes of the same level but different subtrees might be shifted
%  due to the existence of ancestors with different size. 
% \item Superfluous horizontal space between subtrees has to be
%  removed. 
% \end{enumerate}
% The next two sections describe how the package deals with these two
% problems. 
%
% \subsection{Synchronisation of Levels}
%
% This is actually the easier problem. Before we typeset the tree, we
% walk through it to do some measurements. 
% We determine the depth~$d$ of the tree and for each level~$l_i$
% ($i=1,\dots,d$) we measure the maximum height and the maximum depth
% of all the node boxes at level~$l_i$.
% 
% In the second walk through the tree, a counter will keep track of
% the current level, and from the array computed in the first walk, we
% lengthen the vertical parts above and below a node such as to fill
% it to the height/depth of the level. 
%
% \subsection{Removing Superfluous space}
%
% We equip each tree~$t$ of depth~$d$ with two arrays of dimension~$d$
% called \emph{skyline} --- a left one describing the left side of the
% tree and a right one describing its right side. 
% For the skyline, we assume that the tree is enclosed by a rectangle
% of minimum size, and specify that the left [right] skyline vector maps an
% index~$i$ to the distance between the leftmot [rightmost] point of
% the $i$th level of~$t$ to this rectangle. For convenience, we define
% out-of-bounds values to infinity. 
%
% The concept is illustrated in the following example.
%
% \begin{treeenv}
%  \def\ruler#1{\hbox{\llap{\tiny#1}%
%   \rule{.3pt}{1ex}\kern-.3pt
%   \rule[.5ex]{#1}{0.3pt}\kern-.3pt
%   \rule{.3pt}{1ex}}}
%  \vtop{
%   \ruler{52.5pt}\kern6pt
%   \ruler{0pt}\kern6pt
%   \ruler{5.3pt}\kern6pt
%   \ruler{22.1pt}
%  }\kern-57.5pt
%  \edgewidth=.5pt
%  \tree1{
%   \tree{22222}{\leaf{3}\leaf4}
%   \tree{5555}{\leaf{6}\tree{7}{\leaf8\leaf9\leaf0\leaf1\leaf2}\leaf{3}}
%   \tree4{\leaf{555}\tree{66}{\leaf{7777}}\leaf8}
%  }\kern-3pt
%  \def\ruler#1{\hbox{\llap{%
%   \rule{.3pt}{1ex}\kern-.3pt
%   \rule[.5ex]{#1}{0.3pt}\kern-.3pt
%   \rule{.3pt}{1ex}} \tiny#1}}%
%  \vtop{
%   \ruler{52.5pt}\kern6pt
%   \ruler{19pt}\kern6pt
%   \ruler{0pt}\kern6pt
%   \ruler{5.1pt}
%  }
% \end{treeenv}In
%    this example, the left skyline is [52.5pt, 0pt, 5.3pt, 22.1pt]
% and the right skyline is [52.5pt, 19pt, 0pt, 5.1pt].
%
% Given two skylines $s=[s_1,\dots,s_n],s'=[s'_1,\dots,s'_m]$, their
% \emph{distance} $d(s,s')$ is defined by
% \[
%  d(s,s')=\min_{k=1}^{\min\{m,n\}}(s_k+s'_k).
% \]
% Appending a value~$v$ to a skyline~$s$ is defined as usual list
% appending if $v\geq0$. If $v<0$, however, it is defined by first
% \emph{shifting} $s$ by $-v$ and then appending the
% value~$0$. Shifting a skyline~$s$ by $v\geq0$ means adding $v$ to
% each of elements in the array~$s$. 
% 
% The notion of a skyline gives access to the amount of space which we
% might delete when typesetting two consecutive subtrees $t,t'$. If
% $s_l(t)$ is the left skyline of $t$ and $s_r(t')$ is the right
% skyline of~$t'$, then we consider the value $d=d(s_l(t),s_r(t'))$. 
% If it is less than |\nodeskip|, we put |\nodeskip| horizontal space
% between them, otherwise we put $|\nodeskip|-d$ space, where a
% negative result means of course going to the left. 
%
% It remains to compute the skylines of a tree, but this is not too
% difficult. For a leaf there is nothing to do, both skylines are
% [0pt]. 
% Assume the skylines are computed for the subtrees of a tree~$t$, and
% we wish to compute the left skyline of~$t$. The skyline of the
% leftmost subtree is a good starting point. 
% The only nontrivial thing is to be aware of situations like in
% \begin{treeenv}
%  \tree{0}{
%   \leaf{1}
%   \tree{2}{\leaf{333333333333333333333333333}\leaf{4}}
%  }
% \end{treeenv}where
%       the left skyline is also influenced by the other subtrees. 
% This is done by looping over all subtrees $t_1,\dots,t_n$. For each 
% subtree $t_i$ whose depth is higher than the maximum depth among the
% $t_j$ ($j<i$), shift the left skyline of $t_i$ by
% $w(t_1,\dots,t_{i-1})+|\nodeskip|$ (where $w(t_1,\dots,t_{i-1})$ is
% meant to be the width of the partial subtree array including all
% spacings and shrinkings) and overlap it with the left skyline
% of~$t_1$ which means append all overhanging elements. (Note the
% above definition of append in case they are negative.)
% Finally we incorporate the root by appending the value
% $(w(r)-w(s))/2$ where $w(r)$ is the width of the root and $w(s)$ is
% the width of the subtree array. 
% 
% It is easy to see that the usage of horizontal space is minimized by
% this approach. 
%
% \subsection{Wish List}
%
% Two more aspects could be dealt with, and might be incorporated into
% future versions of the package:
%
% \begin{enumerate}
% \item The skyline concept might also be used for vertical shrinking
%   between two consecutive levels. 
%   In the following example, none of the vertical lines between
%   the g/t levels has the desired minimum length |2\edgeheight|.
%   \begin{treeenv}
%    \tree{a}{\tree{\huge g}{\tree{g}{\leaf x}}
%             \tree{t}{\tree{\huge t}{\leaf x}}}
%   \end{treeenv}
% \item It might be that the position of the $i$th subtree in a list
%  of subtrees is not yet uniquely determined by the constraints we
%  have so far. If there is a degree of freedom, such subtrees should
%  be placed centered with respect to their neigbours.
%  \begin{treeenv}
%   \tree{0}{%
%    \tree{1}{\leaf{2}}
%    \leaf 3
%    \tree{4}{\leaf5\leaf6\leaf7\leaf8\leaf9}
%   }\hfill vs.\hfill
%   \tree{0}{%
%    \tree{1}{\leaf{2}}%
%    \kern1pt\null\leaf3
%    \kern-8pt\null\tree{4}{\leaf5\leaf6\leaf7\leaf8\leaf9}
%   }
%  \end{treeenv}
% \item Edge labels would also be nice, although the style of the
% edges makes it difficult to find an appropriate place for them.
% \end{enumerate}
% 
% \section{Implementation}
%
% The layout algorithm described in on the previous pages is of course
% simple enough to be implemented quickly in any higher programming
% language of choice. But to do in in \TeX\ requires some work which
% to describe will be the content of the rest of this document.
%
%    \begin{macrocode}
\ProvidesPackage{trees}[2003/02/24]
\makeatletter
%    \end{macrocode}
%
% As usual, package private control sequences get a prefix. We choose
% the prefix |\tree@|. 
%
% \subsection{Allocation of recources}
%
% Allocation of boxes\dots
%
%    \begin{macrocode}
\newbox\tree@rootbox
\newbox\tree@subtreebox
%    \end{macrocode}
% \dots dimensions\dots
%    \begin{macrocode}
\newdimen\tree@firstnode
\newdimen\tree@lastnode
\newdimen\tree@arraywidth
\newdimen\tree@width
\newdimen\tree@leftoverhang
\newdimen\tree@rightoverhang
\newdimen\tree@oldfirstnode
\newdimen\tree@oldlastnode
\newdimen\tree@oldarraywidth
\newdimen\tree@oldleftoverhang
\newdimen\tree@oldrightoverhang
%    \end{macrocode}
% \dots counters\dots
%    \begin{macrocode}
\newcount\tree@currentlevel
\newcount\tree@nosubtrees
\newcount\tree@oldnosubtrees
\newcount\tree@depth
%    \end{macrocode}
%
% Allocation and definition of public dimensions
%    \begin{macrocode}
\newdimen\edgewidth
\edgewidth=.3pt
\newdimen\edgeheight
\edgeheight=3pt
\newdimen\nodeskip
\nodeskip=.5em
\newdimen\nodesep
\nodesep=3pt
%    \end{macrocode}
%
% \subsection{Tools and Environment}
%
% We need to prepare some infrastructure.
%
% \subsubsection*{Remove spaces}
%
% The |\tree@removespace| macro serves as a ``vacuum cleaner'' for
% spaces which have been put prior to its statement. 
%
%    \begin{macrocode}
\def\tree@removespace{%
 \let\next\empty
 \ifhmode
  \ifdim\lastskip>0pt
   \unskip\let\next\tree@removespace
  \fi
  \ifdim\lastkern>0pt
   \unkern\let\next\tree@removespace
  \fi
 \fi
 \next
}
%    \end{macrocode}
%
% \subsubsection*{Dimensions in Macros}
%
% \begin{macro}{\tree@set}
% \begin{macro}{\tree@value}
% \begin{macro}{\tree@reset}
% We have to deal with quite a number of dimensions when typesetting a
% tree. Since the number of dimension registers is restricted to 256,
% we provide a mechanism to store them in macros.
% Arbitrary text~$t$ can be assigned to variables like~$x$,
% technically there will be a macro |\tree@@|$x$ which expands
% to~$t$. 
%
% The |\tree@set{#1}{#2}| macro sets the value of a variable |#1| to
% the value~|#2|. If the variable has been used before, its value will
% be overriden, otherwise a new variable will be ``allocated.''
% Variable values are global and not affected by grouping.
%
%    \begin{macrocode}
\def\tree@set#1#2{%
 \expandafter\xdef\csname tree@@#1\endcsname{#2}%
}
%    \end{macrocode}
% The |\tree@value{#1}| macro expands to the value which is assigned
% to the variable~|#1|. If nothing has been assigned to~|#1|, an error
% will be raised.
%    \begin{macrocode}
\def\tree@value#1{%
 \expandafter\if\csname tree@@#1\endcsname\relax
  \PackageError
   {trees}%
   {Requesting value of undefined variable #1}%
   {Defining #1=0pt}%
  \tree@set{#1}{0pt}%
 \fi
 \csname tree@@#1\endcsname
}
%    \end{macrocode}
% The |\tree@reset{#1}| macro finally allows to release a variable,
% i.e., forget its content and regard it as undefined. 
%    \begin{macrocode}
\def\tree@reset#1{%
 \expandafter\let\csname tree@@#1\endcsname\undefined
}
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \subsubsection*{Skyline macros}
%
% We now turn to the definition of skyline macros. 
% Skylines will be stored in lists; the dealing with lists implements
% the ideas outlined in the \TeX Book p.~378f.
% We will assume that a skyline list never contains something else but
% dimensions. 
% 
% We need two token registers for temp use.
%    \begin{macrocode}
\toksdef\tree@toksa=0
\toksdef\tree@toksb=2
%    \end{macrocode}
%
% \begin{macro}{\tree@newskyline}
% \begin{macro}{\tree@emptyskyline}
% A constructor for new skyline ``objects.''
% The |\tree@newskyline{#1}| macro creates a new skyline and assigns
% it to |#1| which is assumed to be a control sequence.
% Actually there is no need to use this macro directly, because an
% empty skyline is an empty list, and the empty list is unique. We
% therefore once and for all also provide an empty list in the control
% sequence |\tree@emptyskyline|. 
% 
%    \begin{macrocode}
\def\tree@newskyline#1{\def#1{\\}}
\tree@newskyline\tree@emptyskyline
%    \end{macrocode}
% \end{macro}
% \end{macro}
%
% What follows are macros to maintain skylines.
% \begin{macro}{\tree@append}
% The first thing is to append an item to an existing skyline. 
% |\tree@append| takes a control sequence |#1| containing a
% skyline and a dimension |#2| in the form |\the\counter| or |5pt|. 
% Note that appending a negative length $l<0$ to a skyline is defined
% to append $0$ to the skyline shifted by~$-l$. 
%
%    \begin{macrocode}
\def\tree@append#1#2{%
 \expandafter\ifdim#2<0pt%
  \tree@shift#1{-#2}%
  \tree@append#1{0pt}%
 \else
  \edef\@tempa{\noexpand\\#2}%
  \tree@toksa=\expandafter{\@tempa}%
  \tree@toksb=\expandafter{#1}%
  \edef#1{\the\tree@toksa\the\tree@toksb}%
 \fi
}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\tree@appendRev}
% This version of append is needed by the cover macro to be defined
% below. It behaves appends the new item |#2| to the end of the
% skyline |#1| and doesn't care if |#2| is negative.
%    \begin{macrocode}
\def\tree@appendRev#1#2{%
 \tree@toksa=\expandafter{#2\\}%
 \tree@toksb=\expandafter{#1}%
 \edef#1{\the\tree@toksb\the\tree@toksa}%
}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\tree@shift}
% Given a skyline |#1| and a dimension |#2|, the |\tree@shift| macro
% shifts all items of |#1| by~|#2|. 
%    \begin{macrocode}
\def\tree@shift#1#2{%
 \let\temp@a\\
 \let\temp@b\tree@emptyskyline
 \def\\##1\\{%
  \ifx @##1
    \let\next\empty
  \else
    \@tempdima=##1\relax
    \advance\@tempdima by#2\relax
    \edef\temp@c{\the\@tempdima}%
    \tree@toksa=\expandafter{\temp@c\\}%
    \tree@toksb=\expandafter{\temp@b}%
    \edef\temp@b{\the\tree@toksb\the\tree@toksa}%
    \let\next\\
  \fi
  \next
 }%
 #1@\\%
 \let#1\temp@b
 \let\\\temp@a
}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\tree@separate}
% The |\tree@separate{#1}{#2}| macro separates pops the first item of
% a skyline~|#1| to a dimension register~|#2|.
%    \begin{macrocode}
\def\tree@separate#1#2{%
 \ifx#1\tree@emptyskyline
  #2=5000pt%
 \else
  \expandafter\tree@separate@#1\@#1#2%
 \fi
}
\long\def\tree@separate@\\#1\\#2\@#3#4{%
 #4=#1\def#3{\\#2}%
}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\tree@mindist}
% The |\tree@mindist| macro computes the distance between two skylines
% |#1| and~|#2|. This distance is defined to be the minimum over all
% sums of corresponding items.
% The return value of the macro will be put into the dimension
% register |\@tempdimc|.
%
% First, some initialisation is needed. The actual recursion is
% carried out in the |\tree@mindist@| command.
%    \begin{macrocode}
\def\tree@mindist#1#2{%
 \let\@tempa#1%
 \let\@tempb#2%
 \@tempdimc=5000pt%
 \tree@mindist@
}
\def\tree@mindist@{%
 \let\next\empty
 \ifx\@tempa\tree@emptyskyline\else
  \ifx\@tempb\tree@emptyskyline\else
   \tree@separate\@tempa\@tempdima
   \tree@separate\@tempb\@tempdimb
   \advance\@tempdima\@tempdimb
   \ifdim\@tempdima<\@tempdimc
    \@tempdimc\@tempdima
   \fi
   \let\next\tree@mindist@
  \fi
 \fi
 \next
}
%    \end{macrocode}
% \end{macro}
%
% \begin{macro}{\tree@cover}
% We now turn to the procedure of covering one skyline by another. 
% Let |#1| and |#2| be two skylines, i.e., skyline control
% sequences. The macro will redefine |#1| in the following way. 
% Let $n$ be the length of |#1| and $m$ be the length of~|#2|.
% If $n\leq m$ then |#1| will simply be redefined to~|#2|.
% Otherwise, the $i$th value of the resulting skyline will be equal to
% |#2|$_i$ if this value exists and to |#1|$_i$ otherwise.
% If it afterwards turns out that there are negative entries in the
% resulting skyline, then this skyline will be shifted by the least
% value which makes all entries nonnegative.
%    \begin{macrocode}
\newif\iftree@done
\def\tree@cover#1#2{%
%    \end{macrocode}
% Let |\@tempa|, |\@tempb| be working copies of |#1| and~|#2|,
% respectively. The resulting skyline will be put into |\@tempc|.
%    \begin{macrocode}
 \let\@tempa#1
 \let\@tempb#2
 \let\@tempc\tree@emptyskyline
%    \end{macrocode}
% The |\@tempdimc| dimension is initialized to something ``very
% large.'' It will during the recursion contain the least value of the
% resulting skyline, at the end its minimum. Its sign will indicate if
% a shift is necessary.
%    \begin{macrocode}
 \@tempdimc=5000pt
%    \end{macrocode}
% As long as neither |\@tempa| nor |\@tempb| are empty\dots
%    \begin{macrocode}
 \tree@donefalse
 \loop
  \ifx\@tempa\tree@emptyskyline
   \ifx\@tempb\tree@emptyskyline
%    \end{macrocode}
% Base case: Set the ``done'' flag to true to exit the loop and assign
% the computed skyline to~|#1|.
%    \begin{macrocode}
    \let#1\@tempc
    \tree@donetrue
   \else
%    \end{macrocode}
% Append the first item of |\@tempb| to the back of |\@tempc|, update
% the minimum, if necessary.
%    \begin{macrocode}
    \tree@separate\@tempb\@tempdimb
    \ifdim\@tempdimb<\@tempdimc
     \@tempdimc=\@tempdimb
    \fi
    \tree@appendRev\@tempc{\the\@tempdimb}%
   \fi
  \else
   \ifx\@tempb\tree@emptyskyline
%    \end{macrocode}
% Now, |\@tempa| has more entries but |\@tempb| is already empty. We
% have to append the first item of |\@tempa| to the back of |\@tempc|
% and to eventually update the minimum.
%    \begin{macrocode}
    \tree@separate\@tempa\@tempdima
    \ifdim\@tempdima<\@tempdimc
     \@tempdimc=\@tempdima
    \fi
    \tree@appendRev\@tempc{\the\@tempdima}%
   \else
%    \end{macrocode}
% At this point, both |\@tempa| and |\@tempb| have more
% elements. We have to append the first item of |\@tempb| to the back
% of |\@tempc| and again to update the minimum if necessary.
%    \begin{macrocode}
    \tree@separate\@tempb\@tempdimb
    \ifdim\@tempdimb<\@tempdimc
     \@tempdimc=\@tempdimb
    \fi
    \tree@appendRev\@tempc{\the\@tempdimb}%
%    \end{macrocode}
% The first item of |\@tempa| has to be skipped to keep synchronized.
%    \begin{macrocode}
    \tree@separate\@tempa\@tempdima
   \fi
  \fi
 \iftree@done\else\repeat
%    \end{macrocode}
% This completes the loop over the elements. 
% Shift the result if its smallest entry is negative.
%    \begin{macrocode}
 \ifdim\@tempdimc<0pt
  \tree@shift#1{-\@tempdimc}%
 \fi
}
%    \end{macrocode}
% \end{macro}
%
% \subsection{Public customisation}
%
% \begin{macro}{\node}
% \begin{macro}{\leaf}
% \begin{macro}{\baselevels}
% \begin{macro}{\centerlevels}
% \begin{macro}{\ceillevels}
% \begin{macro}{\floorlevels}
% We define the macros for customisation. There is not much to say
% about them.
%    \begin{macrocode}
\def\node#1{#1}%
\def\leaf#1{\tree{#1}{}}%
\def\baselevels{%
 \let\tree@setrootbox@pre\tree@baserootbox@pre
 \let\tree@setrootbox@post\tree@baserootbox@post
}
\def\centerlevels{%
 \let\tree@setrootbox@pre\tree@centerrootbox@pre
 \let\tree@setrootbox@post\tree@centerrootbox@post
}
\def\ceillevels{%
 \let\tree@setrootbox@pre\tree@ceilrootbox@pre
 \let\tree@setrootbox@post\tree@ceilrootbox@post
}
\def\floorlevels{%
 \let\tree@setrootbox@pre\tree@floorrootbox@pre
 \let\tree@setrootbox@post\tree@floorrootbox@post
}
%    \end{macrocode}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
% \end{macro}
%
% \subsection{Tree Typesetting}
%
% \begin{macro}{\tree}
% It is time to get to the heart of the package. 
% 
%    \begin{macrocode}
\def\tree#1#2{{%
%    \end{macrocode}
% Initialize dimensions and counters
%    \begin{macrocode}
 \baselineskip=0pt
 \global\tree@depth=-1
 \global\tree@currentlevel=0
%    \end{macrocode}
% We walk through the tree twice. For the first time, we redefine
% |\tree| to |\tree@measurenodes| (defined below) which measures the
% level heights and counts the depth of the tree.
% This measurement is done within an |\hbox| to avoid that something
% ``falls down'' and is typeset. The |\hbox| should be empty
% afterwards, anyway it will be thrown away.
%    \begin{macrocode}
 \let\tree\tree@measurenodes
 \setbox\tree@rootbox=\hbox{\tree{#1}{#2}}% 
%    \end{macrocode}
% Now, typeset the tree.
% This is done in the second walk through the tree, this time carried
% out by a |\@tree| macro to be defined below. 
% We have to do some initialisations and to take special care about
% the different treatment of the root. (Note that this code is only
% executed on the uppermost level.)
%    \begin{macrocode}
 \global\tree@currentlevel=0
 \tree@newskyline\tree@rightskyline
 \tree@newskyline\tree@leftskyline
 \let\tree\@tree
 \let\ifroot\iftrue
 \tree{#1}{#2}%
%    \end{macrocode}
% Finally, we release all the allocated dimensions and are done.
%    \begin{macrocode}
 \tree@currentlevel=0
 \loop
  \tree@reset{\the\tree@currentlevel}%
  \advance\tree@currentlevel by 1
 \ifnum\tree@currentlevel<\tree@depth\repeat
}} % matches \def\tree
%    \end{macrocode}
% \end{macro}
% \begin{macro}{\tree@measurenodes}
% The purpose of this macro is to set up the data that is needed to
% typeset the tree, i.e., the number of levels (the depth) and for
% each depths the height and depth, determined by the highest and
% deepest node in it. It is assumed that the |\tree@currentlevel|
% counter is set to~|0| the |\tree@depth| is~|-1| and the variables
% |lht0|,\dots, |lht|$d-1$, |ldp0|,\dots,|ldp|$d-1$ are undefined or
% defined to~|0pt|.
% Afterwards, |lht|$i$ will contain the height of level $i$ where
% levels are counted from top to bottom, and where the root has
% level~$0$.
% The tree depth will reside in the |\tree@depth| counter register,
% the value will be defined to it globally.
%    \begin{macrocode}
\def\tree@measurenodes#1#2{%
%    \end{macrocode}
% Typeset the root of \emph{this} tree into a box register.
%    \begin{macrocode}
 \setbox\tree@rootbox=\hbox{\node{#1}}%
%    \end{macrocode}
% If the current level is more than the tree depth, we have
% encountered a level on which we have not yet been. We will increase 
% the depth counter accordingly and set the height and depth values of
% this new level to the respective dimensions of the |#1| box.
%    \begin{macrocode}
 \ifnum\tree@currentlevel>\tree@depth
  \global\tree@depth=\tree@currentlevel
  \tree@set{lht\the\tree@currentlevel}{\the\ht\tree@rootbox}%
  \tree@set{ldp\the\tree@currentlevel}{\the\dp\tree@rootbox}%
 \else
%    \end{macrocode}
% Otherwise we have been here and we only have to update the level
% height and level depth if the respective values for |#1| is more
% than it was for the nodes of this level which we have already seen.
%    \begin{macrocode}
  \expandafter\ifdim\tree@value{lht\the\tree@currentlevel}
                   <\ht\tree@rootbox
   \tree@set{lht\the\tree@currentlevel}{\the\ht\tree@rootbox}%
  \fi
  \expandafter\ifdim\tree@value{ldp\the\tree@currentlevel}
                   <\dp\tree@rootbox
   \tree@set{ldp\the\tree@currentlevel}{\the\dp\tree@rootbox}%
  \fi
 \fi
%    \end{macrocode}
% Recursion step: We increase the current level by~1 and call call
% recursively the measurement of the subtrees if there are some. We
% increase the currentlevel aferwards when we come back.
%    \begin{macrocode}
 \advance\tree@currentlevel by 1
 #2
 \advance\tree@currentlevel by -1
} % matches \def\tree@measurenodes
%    \end{macrocode}
% \end{macro}
% 
% The alignment of the elements of a level is goverend by macros which
% insert the vertical pieces of the edges below and above the nodes.
% There are four |\tree@..rootbox@pre| commands for the above parts
% and four |\tree@..rootbox@post| commands, namely one where |..| is
% one of |base|, |center|, |ceil|, or |floor|. 
% The tree typesetting macro uses none of them directly, but it uses
% |\tree@setrootbox@pre| and |\tree@setrootbox@post| which are by
% default defined to be the alignment at the common baseline. 
% The user can change the alignment policy by use of the commands
% |\baselevels|, |\centerlevels|, |\floorlevels|, |\ceillevels| which
% simply redefine |\tree@setrootbox@pre| and |\tree@setrootbox@post|
% accordingly. 
%
% The environment which calls the stretching macros establishes some
% information in registers. When a |\tree@..rootbox@..| command is
% called, it can be assumed that |\@tempdima| contains the height of
% the current level and |\@tempdimb| contains the depth of the current
% level. 
% Further it can be assumed that no assignments will be done between
% the call of |..@pre| and |..@post|, also the |\@tempdima| and
% |\@tempdimb| values remain changed in |..@post| if |..@pre| changes
% them. 
%
% First the base line oriented alignment
%    \begin{macrocode}
\def\tree@baserootbox@pre{%
 \advance\@tempdima by-\ht\tree@rootbox\relax
 \ifdim\@tempdima>0pt
  \nointerlineskip
  \@tempdimc\@tempdima
  \hbox to\tree@width{\hss\rule\edgewidth\@tempdimc\hss}%
 \fi
 \@tempdima\dp\tree@rootbox\relax
}
\def\tree@baserootbox@post{%
 \advance\@tempdimb by-\@tempdima
 \ifdim\@tempdimb>0pt
  \nointerlineskip
  \@tempdimc\@tempdimb
  \hbox to\tree@width{\hss\rule\edgewidth\@tempdimc\hss}%
 \fi
}
%    \end{macrocode}
% Now the floor alignment.
%    \begin{macrocode}
\def\tree@floorrootbox@pre{%
 \advance\@tempdima\@tempdimb
 \advance\@tempdima-\ht\tree@rootbox
 \advance\@tempdima-\dp\tree@rootbox
 \ifdim\@tempdima>0pt
  \nointerlineskip
  \@tempdimc\@tempdima
  \hbox to\tree@width{\hss\rule\edgewidth\@tempdimc\hss}%
 \fi
}
\def\tree@floorrootbox@post{}
%    \end{macrocode}
% Now the ceiling alignment.
%    \begin{macrocode}
\def\tree@ceilrootbox@pre{%
 \advance\@tempdima\@tempdimb
 \advance\@tempdima-\ht\tree@rootbox
 \advance\@tempdima-\dp\tree@rootbox
}
\def\tree@ceilrootbox@post{%
 \ifdim\@tempdima>0pt
  \nointerlineskip
  \@tempdimc\@tempdima
  \hbox to\tree@width{\hss\rule\edgewidth\@tempdimc\hss}%
 \fi
}
%    \end{macrocode}
% And finally the centered alignment.
%    \begin{macrocode}
\def\tree@centerrootbox@pre{%
 \advance\@tempdima\@tempdimb
 \advance\@tempdima-\ht\tree@rootbox
 \advance\@tempdima-\dp\tree@rootbox
 \@tempdimc.5\@tempdima
 \ifdim\@tempdimc>0pt
   \nointerlineskip 
   \hbox to\tree@width{\hss\rule\edgewidth\@tempdimc\hss}%
 \fi
}
\def\tree@centerrootbox@post{%
 \ifdim\@tempdimc>0pt
   \nointerlineskip 
   \hbox to\tree@width{\hss\rule\edgewidth\@tempdimc\hss}%
 \fi
}
%    \end{macrocode}
%
% We define the default to base line oriented alignment.
%
%    \begin{macrocode}
\let\tree@setrootbox@pre\tree@baserootbox@pre
\let\tree@setrootbox@post\tree@baserootbox@post
%    \end{macrocode}
% 
% Now we will turn to the definition of |\@tree| which does the actual
% typesetting after the tree cells have been measured. 
% Skylines are computed on the fly, and the horizontal shrinking is
% done accordingly. 
% In the general situation, we have already arranged subtrees
% $t_1,\dots,t_{i-1}$ of a list of subtrees and got by a recursive
% call a box containing the subtrees $t_{i,1},\dots,t_{i,m}$ of the
% subtree~$t_i$. 
% When computing the amount of horizontal space which might be removed 
% the situation of the variables is according to the following drawing.
%
% \medskip
% \setbox42=\hbox{$\langle$}
% \setbox43=\hbox{\kern\wd42\kern-1.5pt$\rangle$}
% \def\zack{\nointerlineskip\copy42\nointerlineskip\copy43}
% \def\sline#1#2{\vbox{#1\hbox to0pt{\hss\kern2\wd42 #2\hss}}}
% \def\triag{%
%  \begin{picture}(30,45)(0,0)
%   \put(0,0){\line(1,3){15}}
%   \put(0,0){\line(1,0){30}}
%   \put(30,0){\line(-1,3){15}}
%  \end{picture}%
% }
% \def\Triag{%
%  \begin{picture}(40,60)(0,0)
%   \put(0,0){\line(1,3){20}}
%   \put(0,0){\line(1,0){40}}
%   \put(40,0){\line(-1,3){20}}
%  \end{picture}%
% }
% \setbox46=\hbox{\tree{$r_i$}{%
%   \leaf{\triag}\leaf{\triag}\kern30pt\null\leaf{\triag}
%  }}
% \setbox46=\hbox{\raise60pt\box46}%
% \leavevmode\noindent\null\kern-5pt\tree{$r$}{%
%  \leaf{\Triag}\kern26pt\null\leaf{\Triag}\kern31pt\null
%  \leaf{\copy46}
% }
% \\[-85pt]
% \null\kern10pt
% \hbox{\sline{\zack\zack\zack}{old left}}\kern21pt
% \raise30pt\hbox{$t_1$\kern27pt$\cdots$\kern22pt$t_{i-1}$}\kern12pt
% \hbox{\sline{\zack\zack\zack}{old right}}\kern33pt
% \sline{\zack\zack}{left}\kern9pt
% \raise23pt\hbox{$t_{i,1}$\kern29pt
%                 $t_{i,2}$\kern22pt
%                 $\cdots$\kern22pt
%                 $t_{i,m}$}\kern6pt
% \sline{\zack\zack}{right}
% \bigskip
% 
% In a first step, the root of $t_i$ is incorporated into
% |\tree@leftskyline| and |\tree@rightskyline|. This is nothing more
% than appending the appropriate length which depends on the root
% width and the subtree array width to each of them. 
%
% Next, the distance between |\tree@oldrightskyline|, i.e., the left
% shape of the already put $t_1,\dots,t_{i+1}$, and
% |\tree@leftskyline|, i.e., the shape of the just obtained
% subtree~$t_i$, yields the minimum distance between 
% corresponding nodes of $t_1,\dots,t_{i-1}$ and~$t_i$. If this
% distance is more than desired, i.e., more than |\nodeskip|,
% $t_i$~can be moved to the left by an according value.
%
% The last step is to update the two ``old'' skylines
% |\tree@oldleftskyline| and 
% |\tree@oldrightskyline| such that they are fit to incorporate the
% next subtree~$t_{i+1}$. 
%
%    \begin{macrocode}
\def\@tree#1#2{%
%    \end{macrocode}
% The whole thing is intended to work recursively, so we have to save
% global variables in private ones in order to be able to restore them
% afterwards. 
%    \begin{macrocode}
  \tree@oldnosubtrees=\tree@nosubtrees
  \tree@oldfirstnode=\tree@firstnode
  \tree@oldlastnode=\tree@lastnode
  \tree@oldarraywidth=\tree@arraywidth
  \tree@oldleftoverhang=\tree@leftoverhang
  \tree@oldrightoverhang=\tree@rightoverhang
  \let\tree@oldleftskyline\tree@leftskyline
  \let\tree@oldrightskyline\tree@rightskyline
%    \end{macrocode}
% We typeset the node and put it into the root box register. 
%    \begin{macrocode}
  \setbox\tree@rootbox=\hbox{\node{#1}}%
%    \end{macrocode}
% After the appropriate initialisation, we typeset the subtrees
% recursively and put the result into the |\tree@subtreebox| box
% register. 
%    \begin{macrocode}
  \global\tree@nosubtrees=0%
  \global\tree@firstnode=-1pt%
  \global\tree@arraywidth=0pt%
  \global\tree@leftoverhang=0pt%
  \global\tree@rightoverhang=0pt%
  \let\tree@leftskyline\tree@emptyskyline
  \let\tree@rightskyline\tree@emptyskyline
%    \end{macrocode}
% Here we are typesetting the subtree array. First we go some distance
% to the left to make up for the corresponding going to the right of
% the first subtree in the list. The |\tree@arraywidth| will always
% contain the ``current'' length of the subtree |\hbox|. The level is
% increased by one, we are not any more in the root, and call the
% subtree generation recursively. The recursive call is hidden in |#2|
% which in general consists of |\tree| calls. 
% At the end, superfluous horizontal space of the list will be
% removed. 
%    \begin{macrocode}
  \setbox\tree@subtreebox=\hbox{{%
      \global\tree@arraywidth=-\nodeskip
      \kern-\nodeskip
      \advance\tree@currentlevel by 1
      \let\ifroot\iffalse
      #2\tree@removespace}}%
%    \end{macrocode}
% In the recursion, the left and the right skylines of the subtree
% have been constructed. 
% Also, there are two lengths
% |\tree@leftoverhang| and |\tree@rightoverhang| which denote how much
% the subtree box overhangs to the left/right side, i.e., if parts of the
% subtree array range outside the |\hbox|, how far do they do this to
% the left and to the right.
% Left and right overhang are illustrated in the following examples for
% the subtrees with root~2.
%
% \begin{treeenv}
%  \vtop{\kern7.5pt\hbox{\tiny left overhang\strut}\nointerlineskip
%          \hbox{\kern38pt\rule\edgewidth{5pt}\rule[2.5pt]{10pt}\edgewidth
%              \rule\edgewidth{5pt}}}
%  \kern-21pt
%  \begingroup
%  \edgewidth.5pt
%  \tree0{\leaf1\tree2{\leaf3\leaf4\leaf5\leaf6\leaf7}\leaf8}
%  \qquad\qquad
%  \tree0{\tree1{\leaf3\leaf4\leaf5\leaf6\leaf7}\leaf2}
%  \endgroup
%  \kern-14.5pt
%  \vtop{\kern7.5pt\hbox{\kern7pt\tiny right overhang\strut}\nointerlineskip
%          \hbox{\rule\edgewidth{5pt}\rule[2.5pt]{9.5pt}\edgewidth
%              \rule\edgewidth{5pt}}}
% \end{treeenv}
% 
% According to this information, we have to fill the respective amount
% of space into the box. 
% After that the subtrees box will have the correct dimensions.
%    \begin{macrocode}
  \setbox\tree@subtreebox=\hbox{%
    \null\kern\tree@leftoverhang
    \unhbox\tree@subtreebox
    }%
%    \end{macrocode}
% We need to know the width of the first and the last subtree in the
% procuded array for determining the start and end point of the
% horizontal part of the edge.
% This information is provided after the recursive descend in the
% registers |\tree@firstnode| and |\tree@lastnode|. 
% In the case of overhangs, these lengths have to be adjusted
% according to the overhanging parts.
%    \begin{macrocode}
  \advance\tree@firstnode2\tree@leftoverhang
  \advance\tree@lastnode2\tree@rightoverhang
%    \end{macrocode}
% The old overhang values are restored for the recursive ascend.
%    \begin{macrocode}
  \global\tree@leftoverhang=\tree@oldleftoverhang
  \global\tree@rightoverhang=\tree@oldrightoverhang
%    \end{macrocode}
% Determine the overall width of this tree which is the
% maximum of the node's and the subtree's widths.
%    \begin{macrocode}
  \tree@width=\wd\tree@rootbox
  \ifdim\tree@width<\wd\tree@subtreebox
    \tree@width=\wd\tree@subtreebox
  \fi
%    \end{macrocode}
% |\tree@leftskyline| and |\tree@rightskyline| are the left and right
% skylines of the subtreearray just produced. Extend them
% by the value for this root which is 
% \[
% \tfrac12(|\wd\tree@subtreebox| - |\wd\tree@rootbox|)
% \]
%    \begin{macrocode}
  \@tempdimc=.5\wd\tree@subtreebox
  \advance\@tempdimc-.5\wd\tree@rootbox
  \tree@append\tree@leftskyline{\the\@tempdimc}%
  \tree@append\tree@rightskyline{\the\@tempdimc}%
%    \end{macrocode}
% Insert space between the previous subtree and \emph{this} subtree. 
% The space to insert now is the desired amount of space
% minus the distance between the two skylines and minus the
% space which might be already there.
% The |\null| box prevents the kerning from being removed. 
%    \begin{macrocode}
  \tree@removespace
  \kern\nodeskip
  \null
%    \end{macrocode}
% The left and right skyline need to be updated in order to take
% deeper subtrees of the array into account as well. 
% For some reason, |\tree@shift| introduces space which we have to remove
% afterwards: insert |\null| not to remove the intended space, and
% a |\tree@removespace| behind all the space introducing commands\dots
%    \begin{macrocode}
  \tree@mindist\tree@oldrightskyline\tree@leftskyline
  \tree@removespace
  \ifdim\@tempdimc<5000pt
   \kern-\@tempdimc
   \advance\tree@oldarraywidth-\@tempdimc
  \else
   \@tempdimc=0pt
  \fi
%    \end{macrocode}
% If the old array width is negative, borrow some space from |\leftoverhang|
%    \begin{macrocode}
  \ifdim\tree@oldarraywidth<-\nodeskip
   \global\advance\tree@leftoverhang-\tree@oldarraywidth
   \global\advance\tree@leftoverhang-\nodeskip
   \tree@oldarraywidth=-\nodeskip
  \fi
%    \end{macrocode}
% If the move to the left is more than the subtree is wide,
% add their difference to |\rightoverhang|.
%    \begin{macrocode}
  \global\tree@rightoverhang0pt
  \ifdim\@tempdimc>\tree@width
   \global\tree@rightoverhang\@tempdimc
   \global\advance\tree@rightoverhang-\tree@width
   \global\advance\tree@rightoverhang-\nodeskip
  \else
  \fi
  \null
  \@tempdimb=-\@tempdimc
  \advance\@tempdimb\nodeskip
  \advance\@tempdimb\tree@width
  \tree@shift\tree@oldrightskyline\@tempdimb
  \tree@cover\tree@oldrightskyline\tree@rightskyline
  \let\tree@rightskyline\tree@oldrightskyline
%    \end{macrocode}
% same with the left skyline
%    \begin{macrocode}
  \tree@shift\tree@leftskyline\tree@oldarraywidth
  \tree@cover\tree@leftskyline\tree@oldleftskyline
  \let\tree@oldleftskyline\tree@leftskyline
  \tree@removespace
%    \end{macrocode}
% Typeset node, subtrees and the edges between them.
% distinguish between leaf and no-leaf.
%    \begin{macrocode}
  \ifdim\wd\tree@subtreebox>0pt%
    \vtop{%
%    \end{macrocode}
% Typeset the vertical edge above the node, if the node is not
% the root of the entire tree.
%    \begin{macrocode}
      \ifroot\else
        \nointerlineskip
        \hbox to\tree@width{\hss\rule\edgewidth\edgeheight\hss}%
      \fi
%    \end{macrocode}
% Typeset the node itself, surrounded by |..@pre| and |..@post|
% commands to align them. Also put space where needed.
%    \begin{macrocode}
      \expandafter\@tempdima
                  \tree@value{lht\the\tree@currentlevel}%
      \expandafter\@tempdimb
                  \tree@value{ldp\the\tree@currentlevel}%
      \tree@setrootbox@pre
      \ifroot\else
       \kern\nodesep
      \fi
      \nointerlineskip
      \hbox to\tree@width{\hss\unhbox\tree@rootbox\hss}%
      \nointerlineskip
      \kern\nodesep
      \tree@setrootbox@post
%    \end{macrocode}
% If there is more than one subtree, typeset the horizontal
% part of the edge, otherwise, insert some vertical line which
% is by |\edgewidth| higher to keep consistence.
%    \begin{macrocode}
      \ifnum\tree@nosubtrees>1
        \nointerlineskip
        \hbox to\tree@width{\hss\rule\edgewidth\edgeheight\hss}%
        \@tempdimc=\wd\tree@subtreebox
        \advance\@tempdimc-.5\tree@firstnode
        \advance\@tempdimc-.5\tree@lastnode
        \advance\@tempdimc\edgewidth
        \nointerlineskip
        \hbox{%
          \kern.5\tree@width
          \kern-.5\wd\tree@subtreebox
          \kern.5\tree@firstnode
          \kern-.5\edgewidth
          \rule\@tempdimc\edgewidth}%
      \else
        \@tempdimc=\edgeheight
        \advance\@tempdimc\edgewidth
        \nointerlineskip
        \hbox to\tree@width{\hss\rule\edgewidth\@tempdimc\hss}%
      \fi
%    \end{macrocode}
% Now put the subtrees.
%    \begin{macrocode}
      \nointerlineskip
      \hbox to\tree@width{\hss\unhbox\tree@subtreebox\hss}%
    }%
  \else
%    \end{macrocode}
% Now we are in the case of a leaf. This is similar and easier.
%    \begin{macrocode}
    \vtop{%
      \nointerlineskip
      \hbox to\tree@width{\hss\rule\edgewidth\edgeheight\hss}%
      \expandafter\@tempdima
                  \tree@value{lht\the\tree@currentlevel}%
      \expandafter\@tempdimb
                  \tree@value{ldp\the\tree@currentlevel}%
      \tree@setrootbox@pre
      \ifroot\else
       \kern\nodesep
      \fi
      \nointerlineskip
      \hbox to\tree@width{\hss\unhbox\tree@rootbox\hss}%
%    \end{macrocode}
% Put some space below the tree
%    \begin{macrocode}
      \nointerlineskip
      \hbox to\tree@width{\null\mathstrut\hfill\null}%
    }%
  \fi
%    \end{macrocode}
% Essentially, we are done. It remains to restore variables, and to
% put some horizontal space. 
%    \begin{macrocode}
  \global\tree@nosubtrees=\tree@oldnosubtrees
  \global\advance\tree@nosubtrees by 1
  \global\tree@firstnode=\tree@oldfirstnode
  \global\tree@arraywidth\tree@oldarraywidth
  \global\advance\tree@arraywidth\nodeskip
  \global\advance\tree@arraywidth\tree@width
  \global\let\tree@leftskyline\tree@oldleftskyline
  \global\let\tree@rightskyline\tree@oldrightskyline
  \ifdim\tree@firstnode<0pt
   \global\tree@firstnode\tree@width
  \fi
  \global\tree@lastnode\tree@width
  \tree@removespace
  \kern\tree@rightoverhang
  \null
} % matches \def\@tree
%    \end{macrocode}
% That's it.

%\fboxrule0pt
%\fboxsep-\fboxrule