summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorFrédéric Chapoton <chapoton@math.univ-lyon1.fr>2017-06-02 09:46:17 +0200
committerFrédéric Chapoton <chapoton@math.univ-lyon1.fr>2017-06-02 09:46:17 +0200
commit6c73e55002ac7b46e3363e86edbd04ff3d7f643a (patch)
tree86d221ecde72ac46380919ca6db52eb9930da9a0
parentUpdated SageMath version to 8.0.beta9 (diff)
parenttrac 13987 lazy import of mary trees (diff)
Merge branch 'public/combinat/13987-mary-trees' in 8.0.b9
-rw-r--r--src/sage/combinat/all.py10
-rw-r--r--src/sage/combinat/mary_tree.py950
2 files changed, 958 insertions, 2 deletions
diff --git a/src/sage/combinat/all.py b/src/sage/combinat/all.py
index c6bee3f..347fee5 100644
--- a/src/sage/combinat/all.py
+++ b/src/sage/combinat/all.py
@@ -119,10 +119,16 @@ from .parking_functions import ParkingFunctions, ParkingFunction
# Trees and Tamari interval posets
from .ordered_tree import (OrderedTree, OrderedTrees,
LabelledOrderedTree, LabelledOrderedTrees)
+
+lazy_import('sage.combinat.mary_tree', ['MAryTree', 'MAryTrees',
+ 'LabelledMAryTree',
+ 'LabelledMAryTrees'])
+
from .binary_tree import (BinaryTree, BinaryTrees,
- LabelledBinaryTree, LabelledBinaryTrees)
+ LabelledBinaryTree, LabelledBinaryTrees)
-lazy_import('sage.combinat.interval_posets', ['TamariIntervalPoset', 'TamariIntervalPosets'])
+lazy_import('sage.combinat.interval_posets', ['TamariIntervalPoset',
+ 'TamariIntervalPosets'])
from .rooted_tree import (RootedTree, RootedTrees,
LabelledRootedTree, LabelledRootedTrees)
diff --git a/src/sage/combinat/mary_tree.py b/src/sage/combinat/mary_tree.py
new file mode 100644
index 00000000..42e4ba5
--- /dev/null
+++ b/src/sage/combinat/mary_tree.py
@@ -0,0 +1,950 @@
+r"""
+`m`-ary trees
+
+This module deals with `m`-ary trees as mathematical (in particular immmutable)
+objects.
+
+This is different from rooted trees as we want to fix the number of subtrees.
+"""
+#*****************************************************************************
+# Copyright (C) 2010 Florent Hivert <Florent.Hivert@univ-rouen.fr>,
+#
+# Distributed under the terms of the GNU General Public License (GPL)
+# as published by the Free Software Foundation; either version 2 of
+# the License, or (at your option) any later version.
+# http://www.gnu.org/licenses/
+#*****************************************************************************
+from six import add_metaclass
+
+from sage.structure.list_clone import ClonableArray
+from sage.combinat.abstract_tree import (AbstractClonableTree,
+ AbstractLabelledClonableTree)
+from sage.combinat.ordered_tree import LabelledOrderedTrees
+from sage.rings.integer import Integer
+from sage.misc.inherit_comparison import InheritComparisonClasscallMetaclass
+from sage.misc.classcall_metaclass import ClasscallMetaclass
+from sage.misc.lazy_attribute import lazy_attribute
+from sage.categories.finite_enumerated_sets import FiniteEnumeratedSets
+from sage.structure.parent import Parent
+from sage.structure.unique_representation import UniqueRepresentation
+from sage.arith.all import binomial
+from sage.sets.non_negative_integers import NonNegativeIntegers
+from sage.sets.disjoint_union_enumerated_sets import DisjointUnionEnumeratedSets
+from sage.sets.family import Family
+from sage.misc.cachefunc import cached_method
+
+
+@add_metaclass(InheritComparisonClasscallMetaclass)
+class MAryTree(AbstractClonableTree, ClonableArray):
+ r"""
+ The class of `m`-ary trees
+
+ INPUT:
+
+ - `m` -- the arity
+
+ - ``children`` -- ``None`` (default) or a list, tuple or iterable of
+ length `m` of `m`-ary trees or convertible objects.
+
+ - ``check`` -- (default to ``True``) whether check for `m`-arity should be
+ performed or not.
+
+ EXAMPLES::
+
+ sage: MAryTree(3)
+ .
+ sage: MAryTree(3, [])
+ [., ., .]
+ sage: MAryTree(3, [None, [], None])
+ [., [., ., .], .]
+ sage: MAryTree(3, [[], None, None])
+ [[., ., .], ., .]
+ sage: MAryTree(3, [[], None])
+ Traceback (most recent call last):
+ ...
+ TypeError: This is not a 3-ary tree
+ """
+ @staticmethod
+ def __classcall_private__(cls, *args, **opts):
+ r"""
+ Ensure that `m`-ary trees created by the enumerated sets and directly
+ are the same and that they are instances of :class:`MAryTree`
+
+ TESTS::
+
+ sage: from sage.combinat.mary_tree import MAryTrees_all
+ sage: issubclass(MAryTrees_all(3).element_class, MAryTree)
+ True
+ sage: t0 = MAryTree(3, [[], None, []])
+ sage: t0.parent()
+ 3-ary trees
+ sage: type(t0)
+ <class 'sage.combinat.mary_tree.MAryTrees_all_with_category.element_class'>
+ sage: t1 = MAryTrees(3)([[], None, []])
+ sage: t1.parent() is t0.parent()
+ True
+ sage: t1 = MAryTrees(3, 3)([[], None, []])
+ sage: t1.parent() is t0.parent()
+ True
+ sage: type(t1) is type(t0)
+ True
+ """
+ m = args[0]
+ parent = cls._auto_parent(m)
+ args = args[1:]
+ return parent.element_class(parent, *args, **opts)
+
+ @staticmethod
+ def _auto_parent(m):
+ """
+ The automatic parent of the element of this class depending of
+ the arity
+
+ When calling the constructor of an element of this class, one needs a