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

\begin{MInfo}
  \eng{binary trees}
\end{MInfo}

\MDeclareOption{\Left}{Left}
\MDeclareOption{\Right}{Right}

\begin{MIntro}
  \eng{The library \Mthis{} provides functions for counting,
    generating, and manipulating binary trees.}
\end{MIntro}

\MKeywords{combinatorics, binary trees}

\begin{MDetails}
  \eng{A \emph{binary tree} is either empty, or constructed
    recursively from two trees by attaching them to a common ancestor
    node. Technically, it is a \Mup{combinat::trees} such that
    every node exactly has two operands: the left and the right
    subtree.}

  \eng{A \emph{complete binary tree} is a binary tree where each interior
    node (not a leaf) has non-empty left and right subtrees.}

  \eng{The binary trees of size $n$ are enumerated by the Catalan numbers.
    So they are in bijection with Dyck words.}
\end{MDetails}

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

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

\begin{MParameters}
  \param{list}%
  \eng{A nested list of lists.}
\end{MParameters}

\begin{MDetails}
  \eng{\Mex{\Mthis(list)} creates a new binary tree whose recursive
    structure is encoded by \Mpar{list}. See \Mup{combinat::trees} for
    details on the structure of the list.}
\end{MDetails}

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

\MRelatedDomains{combinat::trees, %combinat::labelledBinaryTrees,
  combinat::decomposableObjects, combinat::dyckWords}

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

\MMethodInherited{size}{combinat::trees}
\MMethodInherited{nops}{combinat::trees}
\MMethodInherited{op}{combinat::trees}
\MMethodInherited{subsop}{combinat::trees}
\MMethodInherited{_index}{combinat::trees}
\MMethodInherited{set_index}{combinat::trees}
\MMethodInherited{expr}{combinat::trees}
\MMethodInherited{print}{combinat::trees}

\begin{MMethodDetails}{isA}
  \infoEng{test if an object is a binary tree}
  \call{\Mtype{any type} bt\Mopt{, \Mtype{nonnegative integer} n}}
  \eng{Returns whether the object \Mpar{bt} is a binary tree.}
  \eng{If the optional argument is present, returns whether \Mpar{bt} is a
   a binary tree of size \Mpar{n}.}
\end{MMethodDetails}

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

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

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

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

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

\MMethodInherited{revert}{combinat::trees}

\begin{MMethodDetails}{branchSlice}
  \infoEng{left or right branch slice of a binary tree}
  \call{\Mtype{binary tree} t\Mopt{, direction}}

  \eng{\Mpar{direction} can be \Mex{Left} or \Mex{Right}. Returns the
    list of the binary trees without left (resp. right) subtrees
    obtained by slicing the left (resp. right) branch of \Mpar{t},
    ordered from top to bottom.}
\end{MMethodDetails}

\begin{MMethodDetails}{toDyckWord}
  \infoEng{Transformation of a tree into a Dyck word}
  \call{\Mtype{binary tree} t}%
  \eng{Returns the Dyck word corresponding to the tree.}
\end{MMethodDetails}

\begin{MMethodDetails}{shuffle}[DocState=alpha]
  \infoEng{shuffle product of two binary trees}
  \call{\Mtype{binary tree} t1, \Mtype{binary tree} t2}
  \eng{Returns the shuffle product of \Mpar{t1} and \Mpar{t2}.}
  %\eng{Reference: ...}
  % ADD A REFERENCE!!!!
\end{MMethodDetails}

%\begin{MMethodDetails}{recursiveRevertRightBranch}[DocState=alpha]
%\end{MMethodDetails}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Examples
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{MExample}{ex-isA}
  \eng{We first define an alias for dummy labels (see
    \Mup{combinat::trees} for explanations on this):}
  \begin{Mexin}
alias(d = combinat::trees::dummyLabel):
  \end{Mexin}
  \begin{Mexout}
  \end{Mexout}
  \eng{We introduce here a binary tree of size 5, and test its type:}
  \begin{Mexin}
bt:=combinat::binaryTrees([d, [d, [d, [d, [], []], []],
                            [d, [], []]], []]);
combinat::binaryTrees::isA(bt);
combinat::binaryTrees::isA(bt,5);
combinat::binaryTrees::isA(bt, 3);
  \end{Mexin}
  \begin{Mexout}
                                o
                               /
                              /\
                             /

                             TRUE

                             TRUE

                             FALSE
  \end{Mexout}
  \eng{There is a strong difference between the binary tree and the list
       used in its construction:}
  \begin{Mexin}
combinat::binaryTrees::isA([d, [d, [d, [d, [], []], []],
                             [d, [], []]], []]);
domtype([d, [d, [d, [d, [], []], []], [d, [], []]], []]);
domtype(bt);
  \end{Mexin}
  \begin{Mexout}
                             FALSE

                           DOM_LIST

                     combinat::binaryTrees
  \end{Mexout}

\end{MExample}

\begin{MExample}{bt-generator}
  \eng{There are $5$ trees of size $3$:}
  \begin{Mexin}
combinat::binaryTrees::count(10);
  \end{Mexin}
  \begin{Mexout}
                             16796
  \end{Mexout}
  \eng{If you want to run through the trees of size $n$, you
    can generate them one by one to save memory:}
  \begin{Mexin}
g := combinat::binaryTrees::generator(3):
g();
g(), g(), g(), g(), g();
  \end{Mexin}
  \begin{Mexout}
                              o
                               \
                                \

                    o ,  o ,  o,   o, FAIL
                     \  / \  /    /
                     /       \   /
  \end{Mexout}
\end{MExample}
%
\begin{MExample}{bt-basic}
  \eng{In this example, we list all the trees on $0$ to $4$ nodes:}
  \begin{Mexin}
for i from 0 to 4 do
  print(combinat::binaryTrees::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 --
    /     /   |
   /     /    |
   \    /    --
  \end{Mexout}
  \eng{We can directly get the sixth tree of size $4$:}
  \begin{Mexin}
combinat::binaryTrees::unrank(6,4);
  \end{Mexin}
  \begin{Mexout}
                              o
                             / \
                                \
  \end{Mexout}
  \eng{We can select a random binary tree by:}
  \begin{Mvin}{test=false}
combinat::binaryTrees::random(10);
  \end{Mvin}
  \begin{Mvout}{test=false}
                                   o
                                  /
                           /
                          /      \
                             /
                            /  \
                              / \
  \end{Mvout}
  \eng{We define a binary tree by hand:}
  \begin{Mexin}
t := combinat::binaryTrees([d, [d, [d, [], [d]], []], [d, [d]]])
  \end{Mexin}
  \begin{Mexout}
                               o
                              / \
                             /  /
                             \
  \end{Mexout}
  \eng{The tree can be converted back into a list of lists. Note that
    the constructor added automatically the missing empty lists:}
  \begin{Mexin}
expr(t)
  \end{Mexin}
  \begin{Mexout}
   [d, [d, [d, [], [d, [], []]], []], [d, [d, [], []], []]]
  \end{Mexout}

  \eng{We can slice the left or the right branch of \Mpar{t}:}
  \begin{Mexin}
combinat::binaryTrees::branchSlice(t, Left)
  \end{Mexin}
  \begin{Mexout}
                        -- o , o, o  --
                        |   \      \  |
                        --  /        --
  \end{Mexout}
  \begin{Mexin}
combinat::binaryTrees::branchSlice(t, Right)
  \end{Mexin}
  \begin{Mexout}
                         --   o,  o --
                         |   /   /   |
                         |  /        |
                         -- \       --
  \end{Mexout}
\end{MExample}

\begin{MExample}{bt-Dyck}
  \eng{Let us start with a binary tree:}
  \begin{Mexin}
combinat::binaryTrees::unrank(12,7);
  \end{Mexin}
  \begin{Mexout}
                             o
                              \
                               \
                                \
                                /
                               /\
  \end{Mexout}
  \eng{We can compute its image under the usual bijection with Dyck words:}
 \begin{Mexin}
combinat::binaryTrees::toDyckWord(
      combinat::binaryTrees::unrank(12,7));
  \end{Mexin}
  \begin{Mexout}
          [1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0]
  \end{Mexout}
\end{MExample}

\MSuperDomain{combinat::trees}

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

%\begin{MBackground}
%\end{MBackground}

\end{Mhelppage}
