\begin{Mhelppage}{trees}{F.~Hivert and N.~Thiéry}
  [ImplState=stable,TestState=stable,DocState=stable]
\Mproofread{teresa}{10/2003}{proofread}

\begin{MInfo}
  \eng{the domain of trees}
\end{MInfo}

\MDeclareOption{\Left}{Left}
\MDeclareOption{\Right}{Right}
\MDeclareOption{\Prefix}{Prefix}
\MDeclareOption{\Infix}{Infix}
\MDeclareOption{\Postfix}{Postfix}
\MDeclareOption{\RightPrefix}{RightPrefix}
\MDeclareOption{\RightInfix}{RightInfix}
\MDeclareOption{\RightPostfix}{RightPostfix}
\MDeclareOption{\LeftPrefix}{LeftPrefix}
\MDeclareOption{\LeftInfix}{LeftInfix}
\MDeclareOption{\LeftPostfix}{LeftPostfix}

\begin{MIntro}
  \eng{\Mthis{} is the domain of Trees. It provides also functions for
    enumerating, generating, and manipulating trees.}
\end{MIntro}

\MKeywords{combinatorics, trees}

\begin{MDetails}
  \eng{A \emph{tree} either consists of a single node, or is
    recursively constructed from an ordered list of trees by attaching
    them to a common ancestor node.}
  
  \eng{The operands of a tree are its subtrees.}
  
  \eng{Empty trees and subtrees are actually tolerated, so that
    \Mup{combinat::binaryTrees} can inherit from the data structure
    and methods of \Mthis. }
  
  \eng{\begin{sloppypar}
    The nodes of a tree always carry dummy labels, so that
    \Mup{combinat::labelledBinaryTrees} can inherit from
    the data structure and methods of \Mthis. The 0-th operand of a
    tree is the label of its root node.
    \end{sloppypar}}
  
  \eng{For conversions to and from basic \mupad\ expressions, a tree
    is encoded using a nested list of lists. The empty tree is encoded
    as an empty list, while a non-empty tree \Mex{t} is encoded as a
    list whose first operand is the label of the root node of \Mex{t},
    while the other operands encodes respectively the subtrees of
    \Mex{t}. Nodes without labels are emulated by using a dummy
    label; see \Mslot{dummyLabel}.}
  
  \eng{When a function uses a depth walk algorithm, the user can choose in
    which order the node are visited among
    \begin{itemize}
    \item \Prefix=\LeftPrefix,
    \item \RightPrefix,
    \item \Infix=\LeftInfix,
    \item \RightInfix,
    \item \Postfix=\LeftPostfix,
    \item \RightPostfix.
    \end{itemize}
    When no order is specified, the default order is \LeftInfix. The meanings
    of these options are the following: \Left means that the subtrees are
    visited from left to right, and \Right from right to left. \Prefix means
    that the node is visited before its subtrees, \Postfix means it is
    visited after, while \Infix means its is visited exactly after the first
    subtree.}

\end{MDetails}

% -----------------------------------------------------------
%
% -------- construction of Domain elements ----------
%
% -----------------------------------------------------------

\begin{MDomElConst}
  \MCall{list}
\end{MDomElConst}

\begin{MParameters}
  \param{list}%
  \eng{A nested list representing the tree to be created.}
\end{MParameters}

\begin{MDetails}
  \eng{\Mex{\Mthis(list)} creates a new tree whose recursive structure is
    encoded by \Mpar{list} (see the details above). The empty tree is encoded
    as an empty list, while a non-empty tree \Mex{t} is encoded as a list
    whose first operand is the label of the root node of \Mex{t}, while the
    other operands encodes respectively the subtrees of \Mex{t}.}
\end{MDetails}

\begin{MCategories}
\Mex{Cat::DecomposableClass}, \Mup{Cat::CombinatorialClass}
\end{MCategories}

\MRelatedDomains{combinat::binaryTrees, combinat::labelledBinaryTrees,
  combinat::decomposableObjects}

% -----------------------------------------------------------
%
% -------- Entries of the Domain --------------------
%
% -----------------------------------------------------------

\begin{MDomEntries}
  \MDomEntry{zero}
  \eng{The empty tree with zero nodes}
  \MDomEntry{one}
  \eng{The tree with one single node}
  \MDomEntry{dummyLabel}
  \eng{The dummy label which is used for unlabelled trees}
\end{MDomEntries}

% -----------------------------------------------------------
%
% --------  Standard methods of the Domain ---------------
%
% -----------------------------------------------------------


\begin{MMethodDetails}{size}
  \infoEng{size of a tree}
  \call{\Mtype{tree} t}
  \eng{Returns the size of \Mpar{t}, that is its number of nodes.}
\end{MMethodDetails}

\begin{MMethodDetails}{count}
  \infoEng{number of trees}
  \call{\Mtype{nonnegative integer} n}
  \eng{Returns the number of trees of size \Mpar{n}.}
\end{MMethodDetails}

\begin{MMethodDetails}{generator}
  \infoEng{generator for trees}
  \call{\Mtype{nonnegative integer} n}
  \eng{Returns a generator for the trees of size \Mpar{n}.}
\end{MMethodDetails}

\begin{MMethodDetails}{list}
  \infoEng{list of the trees}
  \call{\Mtype{nonnegative integer} n}
  \eng{Returns the list of trees of size \Mpar{n}.}
\end{MMethodDetails}

\begin{MMethodDetails}{unrank}
  \infoEng{unranking of a tree}
  \call{\Mtype{nonnegative integer} n, \Mtype{nonnegative integer} i}
  \eng{Returns the i-th tree of size \Mpar{n}.}
\end{MMethodDetails}

\begin{MMethodDetails}{random}
  \infoEng{random tree}
  \call{\Mtype{nonnegative integer} n}
  \eng{Returns a random tree of size \Mpar{n}.}
\end{MMethodDetails}


% -----------------------------------------------------------
%
% --------  Manipulation methods of the Domain ---------------
%
% -----------------------------------------------------------

\MAccessMethods

\begin{MMethodDetails}{nops}
  \infoEng{number of operands of a tree}
  \call{\Mtype{tree} t}%
  \eng{Returns the number of operands of \Mpar{t}, that is its number
    of subtrees.}
\end{MMethodDetails}

\begin{MMethodDetails}{op}
  \infoEng{operands of a tree}
  \call{\Mtype{tree} t}
  \call{\Mtype{tree} t, \Mtype{nonnegative integer} i}
  \call{\Mtype{tree} t, \Mtype{nonnegative range} i..j}
  \call{\Mtype{tree} t, [i1, i2, \Mseq{}]}%
  \eng{Returns a sequence of operands, or the requested operand, or
    FAIL if no corresponding operand exists.}
\end{MMethodDetails}

\begin{MMethodDetails}{subsop}
  \infoEng{replace operands of a tree}
  \call{\Mtype{tree} t, i=new}%
  \eng{Returns a copy of \Mpar{t} in which the \Mpar{i}-th operand is
    replaced by the value \Mpar{new}. It can be used either to change a
    subtree if \Mpar{i}$>0$ or to change the label of the root if \Mpar{i}$=0$.}
  \call{\Mtype{tree} t, i1=new1, i2=new2, \Mseq{}}%
  \eng{Returns a copy of \Mpar{t} with several operands replaced at once.}
\end{MMethodDetails}

\begin{MMethodDetails}{_index}
  \infoEng{indexed access}
  \item t[i]
  \call{\Mtype{tree} t, \Mtype{nonnegative integer} i}%
  \eng{Returns the i-th operand of \Mpar{t} or FAIL if no
    corresponding operand exists.}
\end{MMethodDetails}

\begin{MMethodDetails}{set_index}
  \infoEng{indexed assignment}
  \item t[i] := new
  \call{\Mtype{tree} t, \Mtype{nonnegative integer} i, new}%
  \eng{Sets the \Mpar{i}-th operand of \Mpar{t} to \Mpar{new}.
    Returns \Mpar{new} in the first form, and the modified \Mpar{t} in
    the second form. }
\end{MMethodDetails}

% -----------------------------------------------------------
%
% -------- Conversion methods of the Domain ---------------
%
% -----------------------------------------------------------

\MConvMethods

\begin{MMethodDetails}{convert}
  \infoEng{conversion of an list into a tree}
  \call{\Mtype{list} l}%
  \eng{Returns the tree whose structure is encoded in the list
    \Mpar{l}. Convert is called by the constructor an behaves identically.}
\end{MMethodDetails}

\begin{MMethodDetails}{expr}
  \infoEng{conversion of a tree into an expression}
  \call{\Mtype{tree} t}%
  \eng{Returns a list which encodes the structure of \Mpar{t}, and can
    be fed back into the constructor. Thus \Mex{convert(expr(t))} is always
    equal to \Mex{t}, when \Mex{t} is a tree.}
\end{MMethodDetails}

\begin{MMethodDetails}{print}
  \infoEng{pretty printing of a tree}
  \call{\Mtype{tree} t}%
  \eng{Returns a \Mup{output::asciiArt} representation of \Mpar{t}
    suitable for basic 2D pretty printing. The labels are not printed.}
\end{MMethodDetails}


% -----------------------------------------------------------
%
% -------- technical methods of the Domains ---------------
%
% -----------------------------------------------------------

\MTechMethods

\begin{MMethodDetails}{revert}
  \infoEng{reverse of a tree}
  \call{\Mtype{tree} t}
  
  \eng{Returns the reverse tree of \Mpar{t} obtained by reverting the
    order of the subtrees of \Mpar{t}, and reverting those recursively.}
\end{MMethodDetails}

\begin{MMethodDetails}{shape}
  \infoEng{shape of a tree}
  \call{\Mtype{labelled tree} t}
  \eng{Returns the shape of a labelled tree, that is the unlabelled
    tree obtained by removing all labels.}
\end{MMethodDetails}

\begin{MMethodDetails}{toWord}
  \infoEng{word from a tree} \call{\Mtype{tree} t, \Mtype{order} p}
  \eng{Returns the list of the labels of a tree by reading in a depth walk the
    nodes of the tree in a specified order. This order can be:
    LeftPrefix=Prefix, RightPrefix, LeftPostfix=Postfix, RightPostfix,
    LeftInfix=Infix, RightInfix. The defaut order is Prefix.}
\end{MMethodDetails}

\begin{MMethodDetails}{fromShapeAndWord}
  \infoEng{filling of a tree}
  \call{\Mtype{tree} t, \Mtype{word} w, \Mtype{order} p}
  \eng{Label the node of the tree \Mpar{t} with the element of the word
  \Mpar{w}. This returns the tree of the same shape as t, which reading over order p
  gives w back. The length of the word \Mpar{w} must be equal to the number of
  nodes of \Mpar{t}.}
\end{MMethodDetails}

\begin{MMethodDetails}{toPoset}
  \infoEng{converting a tree into a partially ordered set.}
  \call{\Mtype{tree} t}%
  \eng{Returns the partially ordered set encoded by the structure of
    \Mpar{t}, that is return an element of
    \Mup[Graph,firstpage]{Graph}, whose vertices are the nodes of the
    tree and whose edges are the branches of the tree. This can only
    be done if the labels of the nodes of the tree are distinct.}
\end{MMethodDetails}

% -----------------------------------------------------------
%
% -------- Examples ---------------
%
% -----------------------------------------------------------

\begin{MExample}{ex-basic}
  \eng{One computes the list all the trees on $0$ to $5$ nodes writing:}
  \begin{Mexin}
for i from 0 to 5 do 
  print(combinat::trees::list(i))
end_for
  \end{Mexin}
  \begin{Mexout}
                              []

                              [o]

                               o
                              [|]

                         --  o , o --
                         |  / \  |  |
                         --      | --

                  --  o ,  o ,  o ,  o , o --
                  |  /|\  / \  / \   |   |  |
                  |         |  |    / \  |  |
                  --                     | --

--   o  ,  o ,  o ,  o  ,  o ,  o ,  o ,   o ,  o ,  o ,  o ,
|  // \\  /|\  /|\  / \   / \  /|\  / \   / \  / \   |    |
|           |   |     /\    |  |    | |  /\    |    /|\  / \
|                           |                  |           |
--

    o ,  o , o --
    |    |   |  |
   / \   |   |  |
   |    / \  |  |
             | --
  \end{Mexout}
  \eng{If one wants to run through the trees of a given size, one can generate
the trees one by one to save memory:}
  \begin{Mexin}
g:=combinat::trees::generator(4):
g(); g(); g(); g(); g(); g();
  \end{Mexin}
  \begin{Mexout}
                               o
                              /|\

                               o
                              / \
                                |

                               o
                              / \
                              |

                               o
                               |
                              / \

                               o
                               |
                               |
                               |

                             FAIL
  \end{Mexout}
  \eng{If one wants direct access to the i-th tree of size n, it is possible
in the following way:}
  \begin{Mexin}
combinat::trees::unrank(2,4);
  \end{Mexin}
  \begin{Mexout}
                               o
                              / \
                                |
  \end{Mexout}
  \eng{To make statistics on general trees or to test some conjectures on the
shapes of trees with a large number of nodes, one can use:}
  \begin{Mexin}
combinat::trees::random(91)
  \end{Mexin}
  \begin{Mexout}
              o
             /|   \
             | // |         \                    \
             |   / \     /      \
            / \  | |/////\\\\\/    \
            |    |    | |          |
            |           |          |
                                   |
                              /         \
                               /  /           \ \
                                //\   \         |
                                 | /// \    \\ / \
                                   |   |     | |
                                    /     \   / \
                                     /    |  \|
                                      /  / \\
                                      |  |
                                         |
                                         |
                                       / | \
                                      /|\| |
                                          /|\
  \end{Mexout}
\end{MExample}

\begin{MExample}{ex-struct}
  \eng{The structure of a tree is encoded as a list of lists. Nodes
    without label are emulated using a dummy label. To shorten the
    notations, we define an alias for this dummy label:}
  \begin{Mexin}
alias(d = combinat::trees::dummyLabel):
  \end{Mexin}
  \begin{Mexout}
  \end{Mexout}
  \eng{Now, to construct a tree from a list, one can use both:}
  \begin{Mexin}
combinat::trees([d,[d],[d,[d],[d]]]);
combinat::trees::new([d,[d],[d,[d],[d]]]);
combinat::trees::convert([d,[d],[d,[d],[d]]])
  \end{Mexin}
  \begin{Mexout}
                              o
                             / \
                               /\

                              o
                             / \
                               /\

                              o
                             / \
                               /\
  \end{Mexout}
  \eng{To recover the list-format of a tree from its drawing, one uses:}
  \begin{Mexin}
combinat::trees::expr(%)
  \end{Mexin}
  \begin{Mexout}
                    [d, [d], [d, [d], [d]]]
  \end{Mexout}
\end{MExample}

\begin{MExample}{ex-sizenopsop}
  \eng{Let us compute some simple statistics on a given tree:}
  \begin{Mexin}
treetmp:=combinat::trees([d, [d, [d]], [d, [d], [d], [d]]])
  \end{Mexin}
  \begin{Mexout}
                              o
                             / \
                             |/|\
  \end{Mexout}
  \eng{The size, number of operands and operands are respectively:}
  \begin{Mexin}
combinat::trees::size(treetmp);
combinat::trees::nops(treetmp); 
combinat::trees::op(treetmp)
  \end{Mexin}
  \begin{Mexout}
                               7

                               2

                            o,  o
                            |  /|\
  \end{Mexout}

\end{MExample}

\begin{MExample}{ex-subs}
  \eng{Change the shape of a tree:}
  \begin{Mexin}
treetmp  := combinat::trees([d, [d, [d]], [d, [d], [d], [d]]]);
treetmp2 := combinat::trees::subsop(treetmp,
            1=combinat::trees([d,[d],[d]]));
treetmp2[1]
  \end{Mexin}
  \begin{Mexout}
                              o
                             / \
                             |/|\

                               o
                              / \
                             /\/|\

                               o
                              / \
  \end{Mexout}
  \eng{Change the shape of the tree using another way:}
  \begin{Mexin}
treetmp3:=treetmp; treetmp3[1]:=combinat::trees([d,[d],[d]]);
bool(treetmp2=treetmp3)
  \end{Mexin}
  \begin{Mexout}
                              o
                             / \
                             |/|\

                               o
                              / \

                             TRUE
  \end{Mexout}
\end{MExample}

\begin{MExample}{ex-revert}
  \eng{To recursively revert the subtrees of a tree (making the mirror image
of this tree), one uses:}
  \begin{Mexin}
tree:=combinat::trees([d, [d], [d, [d], [d, [d], [d], [d, [d]]], [d]]]);
combinat::trees::revert(tree)
  \end{Mexin}
  \begin{Mexout}
                             o
                            /  \
                             / | \
                              /|\
                                |

                               o
                              /  \
                            / | \
                             /|\
                             |
  \end{Mexout}
\end{MExample}

\begin{MExample}{ex-readings}
  \eng{To compute a special reading of a tree, one can use:}
  \begin{Mexin}
valtree:=combinat::trees([6,[3,[1,[],[2]],[5,[4],[]]],[8,[7],[10,[9]]]]);
combinat::trees::toWord(valtree,Infix);          
combinat::trees::toWord(valtree,RightPostfix);
  \end{Mexin}
  \begin{Mexout}
                              6
                            /   \
                            3   8
                           /  \/ \
                           1  57 10
                            \/   |
                            24   9

                [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

                [9, 10, 7, 8, 4, 5, 2, 1, 3, 6]
  \end{Mexout}
\end{MExample}

\begin{MExample}{ex-affnodes}
  \eng{To associate with each node of a given tree a value, thanks to a
  following order, one uses:}
  \begin{Mexin}
valtree := combinat::trees([d,[d,[d,[],[d]],[d,[d],[]]],
           [d,[d],[d,[d]]]]);
valb := combinat::trees::fromShapeAndWord(valtree,
        [8,4,1,7,9,5,3,10,2,6],Postfix);
combinat::trees::toWord(valb,Postfix);
  \end{Mexin}
  \begin{Mexout}
                               o
                              / \
                             /\ /\
                             \/  |

                              6
                            /   \
                            9   2
                           /  \/ \
                           4  75 10
                            \/   |
                            81   3

                [8, 4, 1, 7, 9, 5, 3, 10, 2, 6]
  \end{Mexout}
\end{MExample}

\begin{MBackground}
  \eng{Unlike most combinatorial domains \Mthis{} is not a facade domains.}
  
  \eng{Empty trees and subtrees are actually tolerated, so that
    \Mup{combinat::binaryTrees} can inherit from the data structure
    and methods of \Mthis{}. }
  
  \eng{The nodes of a tree always carry dummy labels, so that
    \Mex{combinat::labelledTrees} (in construction) can inherit from
    the data structure and methods of \Mthis. The 0-th operand of a
    tree is the label of its root node. }
\end{MBackground}

\MSuperDomain{combinat::trees}

\begin{MAxioms}
  \Mup{Ax::normalRep}
  \Mup{Ax::canonicalRep}
\end{MAxioms}

\end{Mhelppage}
