def _product_coroot_root(self, i, j):
        r"""
        Return the product `\alpha^{\vee}_i \alpha_j`.

        EXAMPLES::

            sage: k = QQ['c,t']
            sage: R = algebras.RationalCherednik(['A',3], k.gen(0), k.gen(1))
            sage: R._product_coroot_root(1, 1)
            ((1, 2*t), (s1*s2*s3*s2*s1, 1/2*c), (s2*s3*s2, 1/2*c),
             (s1*s2*s1, 1/2*c), (s1, 2*c), (s3, 0), (s2, 1/2*c))
            sage: R._product_coroot_root(1, 2)
            ((1, -t), (s1*s2*s3*s2*s1, 0), (s2*s3*s2, -1/2*c),
             (s1*s2*s1, 1/2*c), (s1, -c), (s3, 0), (s2, -c))
            sage: R._product_coroot_root(1, 3)
            ((1, 0), (s1*s2*s3*s2*s1, 1/2*c), (s2*s3*s2, -1/2*c),
             (s1*s2*s1, -1/2*c), (s1, 0), (s3, 0), (s2, 1/2*c))
        """
        Q = RootSystem(self._cartan_type).root_lattice()
        ac = Q.simple_coroot(i)
        al = Q.simple_root(j)

        R = self.base_ring()
        terms = [( self._weyl.one(), self._t * R(ac.scalar(al)) )]
        for s in self._reflections:
            # p[0] is the root, p[1] is the coroot, p[2] the value c_s
            pr, pc, c = self._reflections[s]
            terms.append(( s, c * R(ac.scalar(pr) * pc.scalar(al)
                                    / pc.scalar(pr)) ))
        return tuple(terms)

    def weight_in_root_lattice(self):
        r"""
        Return the weight of ``self`` as an element of the root lattice.

        EXAMPLES::

            sage: M = crystals.infinity.NakajimaMonomials(['F',4])
            sage: m = M.module_generators[0].f_string([3,3,1,2,4])
            sage: m.weight_in_root_lattice()
            -alpha[1] - alpha[2] - 2*alpha[3] - alpha[4]

            sage: M = crystals.infinity.NakajimaMonomials(['B',3,1])
            sage: mg = M.module_generators[0]
            sage: m = mg.f_string([1,3,2,0,1,2,3,0,0,1])
            sage: m.weight_in_root_lattice()
            -3*alpha[0] - 3*alpha[1] - 2*alpha[2] - 2*alpha[3]

            sage: M = crystals.infinity.NakajimaMonomials(['C',3,1])
            sage: m = M.module_generators[0].f_string([3,0,1,2,0])
            sage: m.weight_in_root_lattice()
            -2*alpha[0] - alpha[1] - alpha[2] - alpha[3]
        """
        Q = RootSystem(self.parent().cartan_type()).root_lattice()
        al = Q.simple_roots()
        return Q.sum(e*al[k[0]] for k,e in six.iteritems(self._A))

    def __classcall_private__(cls, starting_weight, cartan_type = None, starting_weight_parent = None):
        """
        Classcall to mend the input.

        Internally, the
        :class:`~sage.combinat.crystals.littlemann_path.CrystalOfLSPaths` code
        works with a ``starting_weight`` that is in the weight space associated
        to the crystal. The user can, however, also input a ``cartan_type``
        and the coefficients of the fundamental weights as
        ``starting_weight``. This code transforms the input into the right
        format (also necessary for UniqueRepresentation).

        TESTS::

            sage: crystals.LSPaths(['A',2,1],[-1,0,1])
            The crystal of LS paths of type ['A', 2, 1] and weight -Lambda[0] + Lambda[2]

            sage: R = RootSystem(['B',2,1])
            sage: La = R.weight_space(extended=True).basis()
            sage: C = crystals.LSPaths(['B',2,1],[0,0,1])
            sage: B = crystals.LSPaths(La[2])
            sage: B is C
            True
        """
        if cartan_type is not None:
            cartan_type, starting_weight = CartanType(starting_weight), cartan_type
            if cartan_type.is_affine():
                extended = True
            else:
                extended = False

            R = RootSystem(cartan_type)
            P = R.weight_space(extended = extended)
            Lambda = P.basis()
            offset = R.index_set()[Integer(0)]
            starting_weight = P.sum(starting_weight[j-offset]*Lambda[j] for j in R.index_set())
        if starting_weight_parent is None:
            starting_weight_parent = starting_weight.parent()
        else:
            # Both the weight and the parent of the weight are passed as arguments of init to be able
            # to distinguish between crystals with the extended and non-extended weight lattice!
            if starting_weight.parent() != starting_weight_parent:
                raise ValueError("The passed parent is not equal to parent of the inputted weight!")

        return super(CrystalOfLSPaths, cls).__classcall__(cls, starting_weight, starting_weight_parent = starting_weight_parent)

    def maximal_elements(self):
        r"""
        Return the maximal elements of ``self`` with respect to Bruhat order.

        The current implementation is via a conjectural type-free
        formula. Use maximal_elements_combinatorial() for proven
        type-specific implementations. To compare type-free and
        type-specific (combinatorial) implementations, use method
        :meth:`_test_maximal_elements`.

        EXAMPLES::

            sage: W = WeylGroup(['A',4,1])
            sage: PF = W.pieri_factors()
            sage: sorted([w.reduced_word() for w in PF.maximal_elements()], key=str)
            [[0, 4, 3, 2], [1, 0, 4, 3], [2, 1, 0, 4], [3, 2, 1, 0], [4, 3, 2, 1]]

            sage: W = WeylGroup(RootSystem(["C",3,1]).weight_space())
            sage: PF = W.pieri_factors()
            sage: sorted([w.reduced_word() for w in PF.maximal_elements()], key=str)
            [[0, 1, 2, 3, 2, 1], [1, 0, 1, 2, 3, 2], [1, 2, 3, 2, 1, 0],
             [2, 1, 0, 1, 2, 3], [2, 3, 2, 1, 0, 1], [3, 2, 1, 0, 1, 2]]

            sage: W = WeylGroup(RootSystem(["B",3,1]).weight_space())
            sage: PF = W.pieri_factors()
            sage: sorted([w.reduced_word() for w in PF.maximal_elements()], key=str)
            [[0, 2, 3, 2, 0], [1, 0, 2, 3, 2], [1, 2, 3, 2, 1],
             [2, 1, 0, 2, 3], [2, 3, 2, 1, 0], [3, 2, 1, 0, 2]]

            sage: W = WeylGroup(['D',4,1])
            sage: PF = W.pieri_factors()
            sage: sorted([w.reduced_word() for w in PF.maximal_elements()], key=str)
            [[0, 2, 4, 3, 2, 0], [1, 0, 2, 4, 3, 2], [1, 2, 4, 3, 2, 1],
             [2, 1, 0, 2, 4, 3], [2, 4, 3, 2, 1, 0], [3, 2, 1, 0, 2, 3],
             [4, 2, 1, 0, 2, 4], [4, 3, 2, 1, 0, 2]]
        """
        ct = self.W.cartan_type()
        s = ct.translation_factors()[1]
        R = RootSystem(ct).weight_space()
        Lambda = R.fundamental_weights()
        orbit = [R.reduced_word_of_translation(x)
                 for x in (s*(Lambda[1]-Lambda[1].level()*Lambda[0]))._orbit_iter()]
        return [self.W.from_reduced_word(x) for x in orbit]

    def weight_in_root_lattice(self):
        r"""
        Return the weight of ``self`` as an element of the root lattice.

        EXAMPLES::

            sage: M = crystals.infinity.NakajimaMonomials(['F',4])
            sage: m = M.module_generators[0].f_string([3,3,1,2,4])
            sage: m.weight_in_root_lattice()
            -alpha[1] - alpha[2] - 2*alpha[3] - alpha[4]

            sage: M = crystals.infinity.NakajimaMonomials(['B',3,1])
            sage: mg = M.module_generators[0]
            sage: m = mg.f_string([1,3,2,0,1,2,3,0,0,1])
            sage: m.weight_in_root_lattice()
            -3*alpha[0] - 3*alpha[1] - 2*alpha[2] - 2*alpha[3]
        """
        Q = RootSystem(self.parent().cartan_type()).root_lattice()
        alpha = Q.simple_roots()
        path = self.to_highest_weight()
        return Q(sum(-alpha[j] for j in path[1]))

    def __classcall_private__(cls, crystals, weight):
        """
        Normalize input to ensure a unique representation.

        EXAMPLES::

            sage: B = crystals.KirillovReshetikhin(['A',2,1], 1,1)
            sage: L = RootSystem(['A',2,1]).weight_lattice()
            sage: C = crystals.KyotoPathModel(B, L.fundamental_weight(0))
            sage: C2 = crystals.KyotoPathModel((B,), L.fundamental_weight(0))
            sage: C3 = crystals.KyotoPathModel([B], L.fundamental_weight(0))
            sage: C is C2 and C2 is C3
            True

            sage: L = RootSystem(['A',2,1]).weight_space()
            sage: C = KyotoPathModel(B, L.fundamental_weight(0))
            Traceback (most recent call last):
            ...
            ValueError: Lambda[0] is not in the weight lattice
        """
        if isinstance(crystals, list):
            crystals = tuple(crystals)
        elif not isinstance(crystals, tuple):
            crystals = (crystals,)

        if any(not B.is_perfect() for B in crystals):
            raise ValueError("all crystals must be perfect")
        level = crystals[0].level()
        if any(B.level() != level for B in crystals[1:]):
            raise ValueError("all crystals must have the same level")
        ct = crystals[0].cartan_type()
        P = RootSystem(ct).weight_lattice()
        if weight.parent() is not P:
            raise ValueError("{} is not in the weight lattice".format(weight))
        if sum( ct.dual().c()[i] * weight.scalar(h) for i,h in
                enumerate(P.simple_coroots()) ) != level:
            raise ValueError( "{} is not a level {} weight".format(weight, level) )

        return super(KyotoPathModel, cls).__classcall__(cls, crystals, weight)

    def __classcall_private__(cls, starting_weight, cartan_type = None):
        """
        Classcall to mend the input.

        Internally, the CrystalOfLSPaths code works with a ``starting_weight`` that
        is in the ``weight_space`` associated to the crystal. The user can, however,
        also input a ``cartan_type`` and the coefficients of the fundamental weights
        as ``starting_weight``. This code transforms the input into the right
        format (also necessary for UniqueRepresentation).

        TESTS::

            sage: CrystalOfLSPaths(['A',2,1],[-1,0,1])
            The crystal of LS paths of type ['A', 2, 1] and weight -Lambda[0] + Lambda[2]

            sage: R = RootSystem(['B',2,1])
            sage: La = R.weight_space().basis()
            sage: C = CrystalOfLSPaths(['B',2,1],[0,0,1])
            sage: B = CrystalOfLSPaths(La[2])
            sage: B is C
            True
        """
        if cartan_type is not None:
            cartan_type, starting_weight = CartanType(starting_weight), cartan_type
            if cartan_type.is_affine():
                extended = True
            else:
                extended = False

            R = RootSystem(cartan_type)
            P = R.weight_space(extended = extended)
            Lambda = P.basis()
            offset = R.index_set()[Integer(0)]
            starting_weight = P.sum(starting_weight[j-offset]*Lambda[j] for j in R.index_set())

        return super(CrystalOfLSPaths, cls).__classcall__(cls, starting_weight)

    def __init__(self, cartan_type, starting_weight):
        """
        EXAMPLES::

            sage: C = CrystalOfLSPaths(['A',2,1],[-1,0,1]); C
            The crystal of LS paths of type ['A', 2, 1] and weight (-1, 0, 1)
            sage: C.R
            Root system of type ['A', 2, 1]
            sage: C.weight
            -Lambda[0] + Lambda[2]
            sage: C.weight.parent()
            Extended weight space over the Rational Field of the Root system of type ['A', 2, 1]
            sage: C.module_generators
            [(-Lambda[0] + Lambda[2],)]
        """
        self._cartan_type = CartanType(cartan_type)
        self.R = RootSystem(cartan_type)

        self._name = "The crystal of LS paths of type %s and weight %s"%(cartan_type,starting_weight)

        if self._cartan_type.is_affine():
            self.extended = True
            if all(i>=0 for i in starting_weight):
                Parent.__init__(self, category = HighestWeightCrystals())
            else:
                Parent.__init__(self, category = Crystals())
        else:
            self.extended = False
            Parent.__init__(self, category = FiniteCrystals())

        Lambda = self.R.weight_space(extended = self.extended).basis()
        offset = self.R.index_set()[Integer(0)]

        zero_weight = self.R.weight_space(extended = self.extended).zero()
        self.weight = sum([zero_weight]+[starting_weight[j-offset]*Lambda[j] for j in self.R.index_set()])

        if self.weight == zero_weight:
            initial_element = self(tuple([]))
        else:
            initial_element = self(tuple([self.weight]))
        self.module_generators = [initial_element]

    def __init__(self, cartan_type, highest_weight):
        """
        EXAMPLES::

            sage: C = ClassicalCrystalOfAlcovePaths(['A',3],[1,0,0])
            sage: C.list()
            [[], [0], [0, 1], [0, 1, 2]]
            sage: TestSuite(C).run()
        """
        Parent.__init__(self, category = ClassicalCrystals())
        self._cartan_type = CartanType(cartan_type)
        self._name = "The crystal of alcove paths for type %s"%cartan_type
        self.chain_cache = {}
        self.endweight_cache = {}

        self.R = RootSystem(cartan_type)
        alpha = self.R.root_space().simple_roots()
        Lambda = self.R.weight_space().basis()

        self.positive_roots = sorted(self.R.root_space().positive_roots());

        self.weight = Lambda[Integer(1)] - Lambda[Integer(1)]
        offset = self.R.index_set()[Integer(0)]
        for j in self.R.index_set():
            self.weight = self.weight + highest_weight[j-offset]*Lambda[j]

        self.initial_element = self([])

        self.initial_element.chain = self.get_initial_chain(self.weight)
        rho = (Integer(1)/Integer(2))*sum(self.positive_roots)
        self.initial_element.endweight = rho

        self.chain_cache[ str([]) ] = self.initial_element.chain
        self.endweight_cache[ str([]) ] = self.initial_element.endweight

        self.module_generators = [self.initial_element]

        self._list = super(ClassicalCrystalOfAlcovePaths, self).list()
        self._digraph = super(ClassicalCrystalOfAlcovePaths, self).digraph()
        self._digraph_closure = self.digraph().transitive_closure()

    def __init__(self, ct, c, t, base_ring, prefix):
        r"""
        Initialize ``self``.

        EXAMPLES::

            sage: k = QQ['c,t']
            sage: R = algebras.RationalCherednik(['A',2], k.gen(0), k.gen(1))
            sage: TestSuite(R).run()  # long time
        """
        self._c = c
        self._t = t
        self._cartan_type = ct
        self._weyl = RootSystem(ct).root_lattice().weyl_group(prefix=prefix[1])
        self._hd = IndexedFreeAbelianMonoid(ct.index_set(), prefix=prefix[0],
                                            bracket=False)
        self._h = IndexedFreeAbelianMonoid(ct.index_set(), prefix=prefix[2],
                                           bracket=False)
        indices = DisjointUnionEnumeratedSets([self._hd, self._weyl, self._h])
        CombinatorialFreeModule.__init__(self, base_ring, indices,
                                         category=Algebras(base_ring).WithBasis().Graded(),
                                         sorting_key=self._genkey)

class CrystalOfLSPaths(UniqueRepresentation, Parent):
    r"""
    Crystal graph of LS paths generated from the straight-line path to a given weight.

    INPUT:

    - ``cartan_type`` -- the Cartan type of a finite or affine root system
    - ``starting_weight`` -- a weight given as a list of coefficients of the fundamental weights

    The crystal class of piecewise linear paths in the weight space,
    generated from a straight-line path from the origin to a given
    element of the weight lattice.

    OUTPUT: - a tuple of weights defining the directions of the piecewise linear segments

    EXAMPLES::

        sage: C = CrystalOfLSPaths(['A',2,1],[-1,0,1]); C
        The crystal of LS paths of type ['A', 2, 1] and weight (-1, 0, 1)
        sage: c = C.module_generators[0]; c
        (-Lambda[0] + Lambda[2],)
        sage: [c.f(i) for i in C.index_set()]
        [None, None, (Lambda[1] - Lambda[2],)]

        sage: R = C.R; R
        Root system of type ['A', 2, 1]
        sage: Lambda = R.weight_space().basis(); Lambda
        Finite family {0: Lambda[0], 1: Lambda[1], 2: Lambda[2]}
        sage: b=C(tuple([-Lambda[0]+Lambda[2]]))
        sage: b==c
        True
        sage: b.f(2)
        (Lambda[1] - Lambda[2],)

    For classical highest weight crystals we can also compare the results with the tableaux implementation::

        sage: C = CrystalOfLSPaths(['A',2],[1,1])
        sage: list(set(C.list()))
        [(-Lambda[1] - Lambda[2],), (-Lambda[1] + 1/2*Lambda[2], Lambda[1] - 1/2*Lambda[2]), (-Lambda[1] + 2*Lambda[2],),
        (1/2*Lambda[1] - Lambda[2], -1/2*Lambda[1] + Lambda[2]), (Lambda[1] - 2*Lambda[2],), (-2*Lambda[1] + Lambda[2],),
        (2*Lambda[1] - Lambda[2],), (Lambda[1] + Lambda[2],)]
        sage: C.cardinality()
        8
        sage: B = CrystalOfTableaux(['A',2],shape=[2,1])
        sage: B.cardinality()
        8
        sage: B.digraph().is_isomorphic(C.digraph())
        True

    TESTS::

        sage: C = CrystalOfLSPaths(['A',2,1],[-1,0,1])
        sage: TestSuite(C).run(skip=['_test_elements', '_test_elements_eq', '_test_enumerated_set_contains', '_test_some_elements'])
        sage: C = CrystalOfLSPaths(['E',6],[1,0,0,0,0,0])
        sage: TestSuite(C).run()

    REFERENCES::

        .. [L] P. Littelmann, Paths and root operators in representation theory. Ann. of Math. (2) 142 (1995), no. 3, 499-525.
    """

    @staticmethod
    def __classcall__(cls, cartan_type, starting_weight):
        """
        cartan_type and starting_weight are lists, which are mutable. The class
        UniqueRepresentation requires immutable inputs. The following code
        fixes this problem.

        TESTS::

            sage: CrystalOfLSPaths.__classcall__(CrystalOfLSPaths,['A',2,1],[-1,0,1])
            The crystal of LS paths of type ['A', 2, 1] and weight (-1, 0, 1)
        """
        cartan_type = CartanType(cartan_type)
        starting_weight = tuple(starting_weight)
        return super(CrystalOfLSPaths, cls).__classcall__(cls, cartan_type, starting_weight)

    def __init__(self, cartan_type, starting_weight):
        """
        EXAMPLES::

            sage: C = CrystalOfLSPaths(['A',2,1],[-1,0,1]); C
            The crystal of LS paths of type ['A', 2, 1] and weight (-1, 0, 1)
            sage: C.R
            Root system of type ['A', 2, 1]
            sage: C.weight
            -Lambda[0] + Lambda[2]
            sage: C.weight.parent()
            Extended weight space over the Rational Field of the Root system of type ['A', 2, 1]
            sage: C.module_generators
            [(-Lambda[0] + Lambda[2],)]
        """
        self._cartan_type = CartanType(cartan_type)
        self.R = RootSystem(cartan_type)

        self._name = "The crystal of LS paths of type %s and weight %s"%(cartan_type,starting_weight)

        if self._cartan_type.is_affine():
            self.extended = True
            if all(i>=0 for i in starting_weight):
#.........这里部分代码省略.........

        def energy_function(self):
            r"""
            Return the energy function of ``self``.

            The energy function `D(\pi)` of the level zero LS path `\pi \in \mathbb{B}_\mathrm{cl}(\lambda)`
            requires a series of definitions; for simplicity the root system is assumed to be untwisted affine.

            The LS path `\pi` is a piecewise linear map from the unit interval `[0,1]` to the weight lattice.
            It is specified by "times" `0=\sigma_0<\sigma_1<\dotsm<\sigma_s=1` and "direction vectors"
            `x_u \lambda` where `x_u \in W/W_J` for `1\le u\le s`, and `W_J` is the
            stabilizer of `\lambda` in the finite Weyl group `W`. Precisely,

            .. MATH::

                \pi(t)=\sum_{u'=1}^{u-1} (\sigma_{u'}-\sigma_{u'-1})x_{u'}\lambda+(t-\sigma_{u-1})x_{u}\lambda

            for `1\le u\le s` and `\sigma_{u-1} \le t \le \sigma_{u}`.

            For any `x,y\in W/W_J` let

            .. MATH::

                d: x= w_{0} \stackrel{\beta_{1}}{\leftarrow}
                w_{1} \stackrel{\beta_{2}}{\leftarrow} \cdots
                \stackrel{\beta_{n}}{\leftarrow} w_{n}=y

            be a shortest directed path in the parabolic quantum Bruhat graph. Define

            .. MATH::

                \mathrm{wt}(d):=\sum_{\substack{1\le k\le n \\  \ell(w_{k-1})<\ell(w_k)}}
                \beta_{k}^{\vee}

            It can be shown that `\mathrm{wt}(d)` depends only on `x,y`;
            call its value `\mathrm{wt}(x,y)`. The energy function `D(\pi)` is defined by

            .. MATH::

                D(\pi)=-\sum_{u=1}^{s-1} (1-\sigma_{u}) \langle \lambda,\mathrm{wt}(x_u,x_{u+1}) \rangle

            For more information, see [LNSSS2013]_.

            REFERENCES:

            .. [LNSSS2013] C. Lenart, S. Naito, D. Sagaki, A. Schilling, M. Shimozono,
               A uniform model for Kirillov-Reshetikhin crystals. Extended abstract.
               DMTCS proc, to appear ( {{{:arXiv:`1211.6019`}}} )

            .. NOTE::

                In the dual-of-untwisted case the parabolic quantum Bruhat graph that is used is obtained by
                exchanging the roles of roots and coroots. Moreover, in the computation of the
                pairing the short roots must be doubled (or tripled for type `G`). This factor
                is determined by the translation factor of the corresponding root.
                Type `BC` is viewed as untwisted type, whereas the dual of `BC` is viewed as twisted.
                Except for the untwisted cases, these formulas are currently still conjectural.

            EXAMPLES::

                sage: R = RootSystem(['C',3,1])
                sage: La = R.weight_space().basis()
                sage: LS = CrystalOfProjectedLevelZeroLSPaths(La[1]+La[3])
                sage: b = LS.module_generators[0]
                sage: c = b.f(1).f(3).f(2)
                sage: c.energy_function()
                0
                sage: c=b.e(0)
                sage: c.energy_function()
                1

                sage: R = RootSystem(['A',2,1])
                sage: La = R.weight_space().basis()
                sage: LS = CrystalOfProjectedLevelZeroLSPaths(2*La[1])
                sage: b = LS.module_generators[0]
                sage: c = b.e(0)
                sage: c.energy_function()
                1
                sage: [c.energy_function() for c in sorted(LS.list())]
                [0, 1, 0, 0, 0, 1, 0, 1, 0]

            The next test checks that the energy function is constant on classically connected components::

                sage: R = RootSystem(['A',2,1])
                sage: La = R.weight_space().basis()
                sage: LS = CrystalOfProjectedLevelZeroLSPaths(2*La[1]+La[2])
                sage: G = LS.digraph(index_set=[1,2])
                sage: C = G.connected_components()
                sage: [all(c[0].energy_function()==a.energy_function() for a in c) for c in C]
                [True, True, True, True]

                sage: R = RootSystem(['D',4,2])
                sage: La = R.weight_space().basis()
                sage: LS = CrystalOfProjectedLevelZeroLSPaths(La[2])
                sage: J = R.cartan_type().classical().index_set()
                sage: hw = [x for x in LS if x.is_highest_weight(J)]
                sage: [(x.weight(), x.energy_function()) for x in hw]
                [(-2*Lambda[0] + Lambda[2], 0), (-2*Lambda[0] + Lambda[1], 1), (0, 2)]
                sage: G = LS.digraph(index_set=J)
                sage: C = G.connected_components()
                sage: [all(c[0].energy_function()==a.energy_function() for a in c) for c in C]
#.........这里部分代码省略.........

#.........这里部分代码省略.........
        .. [LP2008]  C. Lenart and A. Postnikov. A combinatorial model for crystals of Kac-Moody algebras. Trans. Amer. Math. Soc.  360  (2008), 4349-4381. 
    """

    @staticmethod
    def __classcall__(cls, cartan_type, highest_weight):
        """
        cartan_type and heighest_weight are lists, which are mutable, this
        causes a problem for class UniqueRepresentation, the following code
        fixes this problem.

        EXAMPLES::
            sage: ClassicalCrystalOfAlcovePaths.__classcall__(ClassicalCrystalOfAlcovePaths,['A',3],[0,1,0])
            <class 'sage.combinat.crystals.alcove_path.ClassicalCrystalOfAlcovePaths_with_category'>
        """
        cartan_type = CartanType(cartan_type)
        highest_weight = tuple(highest_weight)
        return super(ClassicalCrystalOfAlcovePaths, cls).__classcall__(cls, cartan_type, highest_weight)

    def __init__(self, cartan_type, highest_weight):
        """
        EXAMPLES::

            sage: C = ClassicalCrystalOfAlcovePaths(['A',3],[1,0,0])
            sage: C.list()
            [[], [0], [0, 1], [0, 1, 2]]
            sage: TestSuite(C).run()
        """
        Parent.__init__(self, category = ClassicalCrystals())
        self._cartan_type = CartanType(cartan_type)
        self._name = "The crystal of alcove paths for type %s"%cartan_type
        self.chain_cache = {}
        self.endweight_cache = {}

        self.R = RootSystem(cartan_type)
        alpha = self.R.root_space().simple_roots()
        Lambda = self.R.weight_space().basis()

        self.positive_roots = sorted(self.R.root_space().positive_roots());

        self.weight = Lambda[Integer(1)] - Lambda[Integer(1)]
        offset = self.R.index_set()[Integer(0)]
        for j in self.R.index_set():
            self.weight = self.weight + highest_weight[j-offset]*Lambda[j]

        self.initial_element = self([])

        self.initial_element.chain = self.get_initial_chain(self.weight)
        rho = (Integer(1)/Integer(2))*sum(self.positive_roots)
        self.initial_element.endweight = rho

        self.chain_cache[ str([]) ] = self.initial_element.chain
        self.endweight_cache[ str([]) ] = self.initial_element.endweight

        self.module_generators = [self.initial_element]

        self._list = super(ClassicalCrystalOfAlcovePaths, self).list()
        self._digraph = super(ClassicalCrystalOfAlcovePaths, self).digraph()
        self._digraph_closure = self.digraph().transitive_closure()

    def get_initial_chain(self, highest_weight):
        """
        Called internally by __init__() to construct the chain of roots
        associated to the highest weight element.

        EXAMPLES::
            sage: C = ClassicalCrystalOfAlcovePaths(['A',3],[0,1,0])

    def one_dimensional_configuration_sum(self, q = None, group_components = True):
        r"""
        Compute the one-dimensional configuration sum.

        INPUT:

        - ``q`` -- (default: ``None``) a variable or ``None``; if ``None``,
          a variable ``q`` is set in the code
        - ``group_components`` -- (default: ``True``) boolean; if ``True``,
          then the terms are grouped by classical component

        The one-dimensional configuration sum is the sum of the weights of all elements in the crystal
        weighted by the energy function. For untwisted types it uses the parabolic quantum Bruhat graph, see [LNSSS2013]_.
        In the dual-of-untwisted case, the parabolic quantum Bruhat graph is defined by
        exchanging the roles of roots and coroots (which is still conjectural at this point).

        EXAMPLES::

            sage: R = RootSystem(['A',2,1])
            sage: La = R.weight_space().basis()
            sage: LS = crystals.ProjectedLevelZeroLSPaths(2*La[1])
            sage: LS.one_dimensional_configuration_sum() # long time
            B[-2*Lambda[1] + 2*Lambda[2]] + (q+1)*B[-Lambda[1]]
            + (q+1)*B[Lambda[1] - Lambda[2]] + B[2*Lambda[1]] + B[-2*Lambda[2]] + (q+1)*B[Lambda[2]]
            sage: R.<t> = ZZ[]
            sage: LS.one_dimensional_configuration_sum(t, False) # long time
            B[-2*Lambda[1] + 2*Lambda[2]] + (t+1)*B[-Lambda[1]] + (t+1)*B[Lambda[1] - Lambda[2]]
            + B[2*Lambda[1]] + B[-2*Lambda[2]] + (t+1)*B[Lambda[2]]

        TESTS::

            sage: R = RootSystem(['B',3,1])
            sage: La = R.weight_space().basis()
            sage: LS = crystals.ProjectedLevelZeroLSPaths(La[1]+La[2])
            sage: LS.one_dimensional_configuration_sum() == LS.one_dimensional_configuration_sum(group_components=False) # long time
            True
            sage: K1 = crystals.KirillovReshetikhin(['B',3,1],1,1)
            sage: K2 = crystals.KirillovReshetikhin(['B',3,1],2,1)
            sage: T = crystals.TensorProduct(K2,K1)
            sage: T.one_dimensional_configuration_sum() == LS.one_dimensional_configuration_sum() # long time
            True

            sage: R = RootSystem(['D',4,2])
            sage: La = R.weight_space().basis()
            sage: LS = crystals.ProjectedLevelZeroLSPaths(La[1]+La[2])
            sage: K1 = crystals.KirillovReshetikhin(['D',4,2],1,1)
            sage: K2 = crystals.KirillovReshetikhin(['D',4,2],2,1)
            sage: T = crystals.TensorProduct(K2,K1)
            sage: T.one_dimensional_configuration_sum() == LS.one_dimensional_configuration_sum() # long time
            True

            sage: R = RootSystem(['A',5,2])
            sage: La = R.weight_space().basis()
            sage: LS = crystals.ProjectedLevelZeroLSPaths(3*La[1])
            sage: K1 = crystals.KirillovReshetikhin(['A',5,2],1,1)
            sage: T = crystals.TensorProduct(K1,K1,K1)
            sage: T.one_dimensional_configuration_sum() == LS.one_dimensional_configuration_sum() # long time
            True
        """
        if q is None:
            from sage.rings.all import QQ
            q = QQ['q'].gens()[0]
        #P0 = self.weight_lattice_realization().classical()
        P0 = RootSystem(self.cartan_type().classical()).weight_lattice()
        B = P0.algebra(q.parent())
        def weight(x):
            w = x.weight()
            return P0.sum(int(c)*P0.basis()[i] for i,c in w if i in P0.index_set())
        if group_components:
            G = self.digraph(index_set = self.cartan_type().classical().index_set())
            C = G.connected_components()
            return sum(q**(c[0].energy_function())*B.sum(B(weight(b)) for b in c) for c in C)
        return B.sum(q**(b.energy_function())*B(weight(b)) for b in self)

    def __init__(self, cartan_type, prefix, finite=True):
        r"""

        EXAMPLES::

            sage: from sage.combinat.root_system.fundamental_group import FundamentalGroupOfExtendedAffineWeylGroup
            sage: F = FundamentalGroupOfExtendedAffineWeylGroup(['A',3,1])
            sage: F in Groups().Commutative().Finite()
            True
            sage: TestSuite(F).run()
        """
        def leading_support(beta):
            r"""
            Given a dictionary with one key, return this key
            """
            supp = beta.support()
            assert len(supp) == 1
            return supp[0]

        self._cartan_type = cartan_type
        self._prefix = prefix
        special_node = cartan_type.special_node()
        self._special_nodes = cartan_type.special_nodes()

        # initialize dictionaries with the entries for the distinguished special node
        # dictionary of inverse elements
        inverse_dict = {}
        inverse_dict[special_node] = special_node
        # dictionary for the action of special automorphisms by permutations of the affine Dynkin nodes
        auto_dict = {}
        for i in cartan_type.index_set():
            auto_dict[special_node,i] = i
        # dictionary for the finite Weyl component of the special automorphisms
        reduced_words_dict = {}
        reduced_words_dict[0] = tuple([])

        if cartan_type.dual().is_untwisted_affine():
            # this combines the computations for an untwisted affine type and its affine dual
            cartan_type = cartan_type.dual()
        if cartan_type.is_untwisted_affine():
            cartan_type_classical = cartan_type.classical()
            I = [i for i in cartan_type_classical.index_set()]
            Q = RootSystem(cartan_type_classical).root_lattice()
            alpha = Q.simple_roots()
            omega = RootSystem(cartan_type_classical).weight_lattice().fundamental_weights()
            W = Q.weyl_group(prefix="s")
            for i in self._special_nodes:
                if i == special_node:
                    continue
                antidominant_weight, reduced_word = omega[i].to_dominant_chamber(reduced_word=True, positive=False)
                reduced_words_dict[i] = tuple(reduced_word)
                w0i = W.from_reduced_word(reduced_word)
                idual = leading_support(-antidominant_weight)
                inverse_dict[i] = idual
                auto_dict[i,special_node] = i
                for j in I:
                    if j == idual:
                        auto_dict[i,j] = special_node
                    else:
                        auto_dict[i,j] = leading_support(w0i.action(alpha[j]))

        self._action = Family(self._special_nodes, lambda i: Family(cartan_type.index_set(), lambda j: auto_dict[i,j]))
        self._dual_node = Family(self._special_nodes, inverse_dict.__getitem__)
        self._reduced_words = Family(self._special_nodes, reduced_words_dict.__getitem__)

        if finite:
            cat = Category.join((Groups().Commutative().Finite(),EnumeratedSets()))
        else:
            cat = Groups().Commutative().Infinite()
        Parent.__init__(self, category = cat)

    def product_on_basis(self, left, right):
        r"""
        Return ``left`` multiplied by ``right`` in ``self``.

        EXAMPLES::

            sage: R = algebras.RationalCherednik(['A',2], 1, 1, QQ)
            sage: a2 = R.algebra_generators()['a2']
            sage: ac1 = R.algebra_generators()['ac1']
            sage: a2 * ac1  # indirect doctest
            a2*ac1
            sage: ac1 * a2
            -I + a2*ac1 - s1 - s2 + 1/2*s1*s2*s1
            sage: x = R.an_element()
            sage: [y * x for y in R.some_elements()]
            [0,
             3*ac1 + 2*s1 + a1,
             9*ac1^2 + 10*I + 6*a1*ac1 + 6*s1 + 3/2*s2 + 3/2*s1*s2*s1 + a1^2,
             3*a1*ac1 + 2*a1*s1 + a1^2,
             3*a2*ac1 + 2*a2*s1 + a1*a2,
             3*s1*ac1 + 2*I - a1*s1,
             3*s2*ac1 + 2*s2*s1 + a1*s2 + a2*s2,
             3*ac1^2 - 2*s1*ac1 + 2*I + a1*ac1 + 2*s1 + 1/2*s2 + 1/2*s1*s2*s1,
             3*ac1*ac2 + 2*s1*ac1 + 2*s1*ac2 - I + a1*ac2 - s1 - s2 + 1/2*s1*s2*s1]
            sage: [x * y for y in R.some_elements()]
            [0,
             3*ac1 + 2*s1 + a1,
             9*ac1^2 + 10*I + 6*a1*ac1 + 6*s1 + 3/2*s2 + 3/2*s1*s2*s1 + a1^2,
             6*I + 3*a1*ac1 + 6*s1 + 3/2*s2 + 3/2*s1*s2*s1 - 2*a1*s1 + a1^2,
             -3*I + 3*a2*ac1 - 3*s1 - 3*s2 + 3/2*s1*s2*s1 + 2*a1*s1 + 2*a2*s1 + a1*a2,
             -3*s1*ac1 + 2*I + a1*s1,
             3*s2*ac1 + 3*s2*ac2 + 2*s1*s2 + a1*s2,
             3*ac1^2 + 2*s1*ac1 + a1*ac1,
             3*ac1*ac2 + 2*s1*ac2 + a1*ac2]
        """
        # Make copies of the internal dictionaries
        dl = dict(left[2]._monomial)
        dr = dict(right[0]._monomial)

        # If there is nothing to commute
        if not dl and not dr:
            return self.monomial((left[0], left[1] * right[1], right[2]))

        R = self.base_ring()
        I = self._cartan_type.index_set()
        P = PolynomialRing(R, 'x', len(I))
        G = P.gens()
        gens_dict = {a:G[i] for i,a in enumerate(I)}
        Q = RootSystem(self._cartan_type).root_lattice()
        alpha = Q.simple_roots()
        alphacheck = Q.simple_coroots()

        def commute_w_hd(w, al): # al is given as a dictionary
            ret = P.one()
            for k in al:
                x = sum(c * gens_dict[i] for i,c in alpha[k].weyl_action(w))
                ret *= x**al[k]
            ret = ret.dict()
            for k in ret:
                yield (self._hd({I[i]: e for i,e in enumerate(k) if e != 0}), ret[k])

        # Do Lac Ra if they are both non-trivial
        if dl and dr:
            il = dl.keys()[0]
            ir = dr.keys()[0]

            # Compute the commutator
            terms = self._product_coroot_root(il, ir)

            # remove the generator from the elements
            dl[il] -= 1
            if dl[il] == 0:
                del dl[il]
            dr[ir] -= 1
            if dr[ir] == 0:
                del dr[ir]

            # We now commute right roots past the left reflections: s Ra = Ra' s
            cur = self._from_dict({ (hd, s*right[1], right[2]): c * cc
                                    for s,c in terms
                                    for hd, cc in commute_w_hd(s, dr) })
            cur = self.monomial( (left[0], left[1], self._h(dl)) ) * cur

            # Add back in the commuted h and hd elements
            rem = self.monomial( (left[0], left[1], self._h(dl)) )
            rem = rem * self.monomial( (self._hd({ir:1}), self._weyl.one(),
                                        self._h({il:1})) )
            rem = rem * self.monomial( (self._hd(dr), right[1], right[2]) )

            return cur + rem

        if dl:
            # We have La Ls Lac Rs Rac,
            #   so we must commute Lac Rs = Rs Lac'
            #   and obtain La (Ls Rs) (Lac' Rac)
            ret = P.one()
            for k in dl:
                x = sum(c * gens_dict[i]
                        for i,c in alphacheck[k].weyl_action(right[1].reduced_word(),
                                                             inverse=True))
#.........这里部分代码省略.........

#.........这里部分代码省略.........

        # Normalize the parameter c
        if isinstance(c, (tuple, list)):
            if ct.is_simply_laced():
                if len(c) != 1:
                    raise ValueError("1 parameter c_s must be given for simply-laced types")
                c = (base_ring(c[0]),)
            else:
                if len(c) != 2:
                    raise ValueError("2 parameters c_s must be given for non-simply-laced types")
                c = (base_ring(c[0]), base_ring(c[1]))
        else:
            c = base_ring(c)
            if ct.is_simply_laced():
                c = (c,)
            else:
                c = (c, c)

        return super(RationalCherednikAlgebra, cls).__classcall__(cls, ct, c, t, base_ring, tuple(prefix))

    def __init__(self, ct, c, t, base_ring, prefix):
        r"""
        Initialize ``self``.

        EXAMPLES::

            sage: k = QQ['c,t']
            sage: R = algebras.RationalCherednik(['A',2], k.gen(0), k.gen(1))
            sage: TestSuite(R).run()  # long time
        """
        self._c = c
        self._t = t
        self._cartan_type = ct
        self._weyl = RootSystem(ct).root_lattice().weyl_group(prefix=prefix[1])
        self._hd = IndexedFreeAbelianMonoid(ct.index_set(), prefix=prefix[0],
                                            bracket=False)
        self._h = IndexedFreeAbelianMonoid(ct.index_set(), prefix=prefix[2],
                                           bracket=False)
        indices = DisjointUnionEnumeratedSets([self._hd, self._weyl, self._h])
        CombinatorialFreeModule.__init__(self, base_ring, indices,
                                         category=Algebras(base_ring).WithBasis().Graded(),
                                         sorting_key=self._genkey)

    def _genkey(self, t):
        """
        Construct a key for comparison for a term indexed by ``t``.

        The key we create is the tuple in the following order:

        - overall degree
        - length of the Weyl group element
        - the Weyl group element
        - the element of `\mathfrak{h}`
        - the element of `\mathfrak{h}^*`

        E