def __init__(self, NCSymD):
            """
            EXAMPLES::

                sage: w = SymmetricFunctionsNonCommutingVariables(QQ).dual().w()
                sage: TestSuite(w).run()
            """

            def lt_set_part(A, B):
                A = sorted(map(sorted, A))
                B = sorted(map(sorted, B))
                for i in range(len(A)):
                    if A[i] > B[i]:
                        return 1
                    elif A[i] < B[i]:
                        return -1
                return 0

            CombinatorialFreeModule.__init__(
                self,
                NCSymD.base_ring(),
                SetPartitions(),
                prefix="w",
                bracket=False,
                monomial_cmp=lt_set_part,
                category=NCSymDualBases(NCSymD),
            )

    def __init__(self, abstract, prefix, modules, index_set=None):
        """
        INPUT:
         - ``abstract`` -- the abstract character ring
         - ``prefix`` -- a string (e.g. "S", "P")
         - ``modules`` -- a string (e.g. "simple", "projective indecomposable")
         - ``index_set`` -- a list (or iterable) the indexing set for the basis

        By default, the index set is given by the index set for the
        simple modules.

        EXAMPLES::

            sage: G = HTrivialMonoids().Finite().example().character_ring(QQ)

        """
        self._abstract = abstract
        self._modules = modules
        if index_set is None:
            index_set = abstract.base().simple_modules_index_set()
        CombinatorialFreeModule.__init__(self,
                                         abstract.base_ring(), index_set,
                                         prefix = prefix,
                                         category = (abstract.character_ring_category().Realizations(),
                                                     abstract.Realizations()))

    def __init__(self, alg, graded=True):
        r"""
        Initialize ``self``.

        EXAMPLES::

            sage: G = algebras.FSym(QQ).G()
            sage: TestSuite(G).run()  # long time

        Checks for the antipode::

            sage: FSym = algebras.FSym(QQ)
            sage: G = FSym.G()
            sage: for b in G.basis(degree=3):
            ....:     print("%s : %s" % (b, b.antipode()))
            G[123] : -G[1|2|3]
            G[13|2] : -G[13|2]
            G[12|3] : -G[12|3]
            G[1|2|3] : -G[123]

            sage: F = FSym.dual().F()
            sage: for b in F.basis(degree=3):
            ....:     print("%s : %s" % (b, b.antipode()))
            F[123] : -F[1|2|3]
            F[13|2] : -F[13|2]
            F[12|3] : -F[12|3]
            F[1|2|3] : -F[123]
        """
        CombinatorialFreeModule.__init__(self, alg.base_ring(),
                                         StandardTableaux(),
                                         category=FSymBases(alg),
                                         bracket="", prefix=self._prefix)

    def homogeneous_component(self, n):
        """
        Return the `n`-th homogeneous piece of the path algebra.

        INPUT:

        - ``n`` -- integer

        OUTPUT:

        - :class:`CombinatorialFreeModule`, module spanned by the paths
          of length `n` in the quiver

        EXAMPLES::

            sage: P = DiGraph({1:{2:['a'], 3:['b']}, 2:{4:['c']}, 3:{4:['d']}}).path_semigroup()
            sage: A = P.algebra(GF(7))
            sage: A.homogeneous_component(2)
            Free module spanned by [a*c, b*d] over Finite Field of size 7

            sage: D = DiGraph({1: {2: 'a'}, 2: {3: 'b'}, 3: {1: 'c'}})
            sage: P = D.path_semigroup()
            sage: A = P.algebra(ZZ)
            sage: A.homogeneous_component(3)
            Free module spanned by [a*b*c, b*c*a, c*a*b] over Integer Ring

        """
        basis = []
        for v in self._semigroup._quiver:
            basis.extend(self._semigroup.iter_paths_by_length_and_startpoint(n, v))
        M = CombinatorialFreeModule(self._base, basis, prefix='', bracket=False)
        M._name = "Free module spanned by {0}".format(basis)
        return M

    def __init__(self, R, names=None):
        """
        Initialize ``self``.

        TESTS::

            sage: A = algebras.FreeDendriform(QQ, '@'); A
            Free Dendriform algebra on one generator ['@'] over Rational Field
            sage: TestSuite(A).run()

            sage: F = algebras.FreeDendriform(QQ, 'xy')
            sage: TestSuite(F).run() # long time
        """
        if names.cardinality() == 1:
            Trees = BinaryTrees()
            key = BinaryTree._sort_key
        else:
            Trees = LabelledBinaryTrees()
            key = LabelledBinaryTree._sort_key
        # Here one would need LabelledBinaryTrees(names)
        # so that one can restrict the labels to some fixed set
        self._alphabet = names
        cat = Algebras(R).WithBasis().Graded()
        CombinatorialFreeModule.__init__(self, R, Trees,
                                         latex_prefix="",
                                         sorting_key=key,
                                         category=cat)

    def __init__(self, R, names=None):
        """
        Initialize ``self``.

        TESTS::

            sage: A = algebras.FreePreLie(QQ, '@'); A
            Free PreLie algebra on one generator ['@'] over Rational Field
            sage: TestSuite(A).run()

            sage: F = algebras.FreePreLie(QQ, 'xy')
            sage: TestSuite(F).run() # long time

            sage: F = algebras.FreePreLie(QQ, ZZ)
            sage: elts = F.some_elements()[:-1] # Skip the last element
            sage: TestSuite(F).run(some_elements=elts) # long time
        """
        if names.cardinality() == 1:
            Trees = RootedTrees()
        else:
            Trees = LabelledRootedTrees()
        # Here one would need LabelledRootedTrees(names)
        # so that one can restrict the labels to some fixed set

        self._alphabet = names
        cat = MagmaticAlgebras(R).WithBasis().Graded()
        CombinatorialFreeModule.__init__(self, R, Trees,
                                         latex_prefix="",
                                         category=cat)

    def __init__(self, A, category=None):
        """
        Initialize ``self``.

        EXAMPLES::

            sage: A = Algebras(QQ).WithBasis().Filtered().example()
            sage: grA = A.graded_algebra()
            sage: TestSuite(grA).run(elements=[prod(grA.algebra_generators())])
        """
        if A not in ModulesWithBasis(A.base_ring().category()).Filtered():
            raise ValueError("the base algebra must be filtered and with basis")
        self._A = A

        base_ring = A.base_ring()
        base_one = base_ring.one()

        category = A.category().Graded().or_subcategory(category)
        try:
            opts = copy(A.print_options())
            if not opts['prefix'] and not opts['bracket']:
                opts['bracket'] = '('
            opts['prefix'] = opts['prefix'] + 'bar'
        except AttributeError:
            opts = {'prefix': 'Abar'}

        CombinatorialFreeModule.__init__(self, base_ring, A.basis().keys(),
                                         category=category, **opts)

        # Setup the conversion back
        phi = self.module_morphism(diagonal=lambda x: base_one, codomain=A)
        self._A.register_conversion(phi)

    def __init__(self, submodule, category):
        r"""
        Initialize this quotient of a module with basis by a submodule.

        TESTS::

            sage: from sage.modules.with_basis.subquotient import QuotientModuleWithBasis
            sage: X = CombinatorialFreeModule(QQ, range(3), prefix="x"); x = X.basis()
            sage: I = X.submodule( (x[0]-x[1], x[1]-x[2]) )
            sage: Y = QuotientModuleWithBasis(I)
            sage: Y.print_options(prefix='y')
            sage: Y
            Free module generated by {2} over Rational Field
            sage: Y.category()
            Join of Category of finite dimensional modules with basis over Rational Field and Category of vector spaces with basis over Rational Field and Category of quotients of sets
            sage: Y.basis().list()
            [y[2]]
            sage: TestSuite(Y).run()
        """
        self._submodule = submodule
        self._ambient = submodule.ambient()
        embedding = submodule.lift
        indices = embedding.cokernel_basis_indices()
        CombinatorialFreeModule.__init__(self,
                                         submodule.base_ring(), indices,
                                         category=category)

    def __init__(self, cell_complex, degree, cells=None, base_ring=None):
        """
        EXAMPLES::

            sage: T = cubical_complexes.Torus()
            sage: T.n_chains(2, QQ, cochains=True)
            Free module generated by {[1,1] x [0,1] x [1,1] x [0,1],
             [0,0] x [0,1] x [0,1] x [1,1], [0,0] x [0,1] x [1,1] x [0,1],
             [0,0] x [0,1] x [0,0] x [0,1], [0,1] x [1,1] x [0,1] x [0,0],
             [0,1] x [0,0] x [0,0] x [0,1], [1,1] x [0,1] x [0,1] x [0,0],
             [0,1] x [1,1] x [0,0] x [0,1], [0,0] x [0,1] x [0,1] x [0,0],
             [0,1] x [0,0] x [0,1] x [0,0], [0,1] x [0,0] x [1,1] x [0,1],
             [0,1] x [1,1] x [1,1] x [0,1], [0,1] x [0,0] x [0,1] x [1,1],
             [1,1] x [0,1] x [0,0] x [0,1], [1,1] x [0,1] x [0,1] x [1,1],
             [0,1] x [1,1] x [0,1] x [1,1]} over Rational Field
            sage: T.n_chains(2).dimension()
            16

        TESTS::

            sage: T.n_chains(2, cochains=True).base_ring()
            Integer Ring
            sage: T.n_chains(8, cochains=True).dimension()
            0
            sage: T.n_chains(-3, cochains=True).dimension()
            0
        """
        if base_ring is None:
            base_ring = ZZ
        CellComplexReference.__init__(self, cell_complex, degree, cells=cells)
        CombinatorialFreeModule.__init__(
            self, base_ring, self._cells,
            prefix='\\chi',
            bracket=['_', '']
        )

    def __init__(self, base_ring, cartan_type, level, twisted):
        """
        Initialize ``self``.

        EXAMPLES::

            sage: Q = QSystem(QQ, ['A',2])
            sage: TestSuite(Q).run()

            sage: Q = QSystem(QQ, ['E',6,2], twisted=True)
            sage: TestSuite(Q).run()
        """
        self._cartan_type = cartan_type
        self._level = level
        self._twisted = twisted
        indices = tuple(itertools.product(cartan_type.index_set(), [1]))
        basis = IndexedFreeAbelianMonoid(indices, prefix='Q', bracket=False)
        # This is used to do the reductions
        if self._twisted:
            self._cm = cartan_type.classical().cartan_matrix()
        else:
            self._cm = cartan_type.cartan_matrix()
        self._Irev = {ind: pos for pos,ind in enumerate(self._cm.index_set())}
        self._poly = PolynomialRing(ZZ, ['q'+str(i) for i in self._cm.index_set()])

        category = Algebras(base_ring).Commutative().WithBasis()
        CombinatorialFreeModule.__init__(self, base_ring, basis,
                                         prefix='Q', category=category)

    def __init__(self, root_system, base_ring, extended):
        """
        TESTS::

            sage: R = RootSystem(['A',4])
            sage: from sage.combinat.root_system.weight_space import WeightSpace
            sage: Q = WeightSpace(R, QQ); Q
            Weight space over the Rational Field of the Root system of type ['A', 4]
            sage: TestSuite(Q).run()

            sage: WeightSpace(R, QQ, extended = True)
            Traceback (most recent call last):
            ...
            AssertionError: extended weight lattices are only implemented for affine root systems
        """
        basis_keys = root_system.index_set()
        self._extended = extended
        if extended:
            assert root_system.cartan_type().is_affine(), "extended weight lattices are only implemented for affine root systems"
            basis_keys = tuple(basis_keys) + ("delta",)

        self.root_system = root_system
        CombinatorialFreeModule.__init__(self, base_ring,
                                         basis_keys,
                                         prefix = "Lambdacheck" if root_system.dual_side else "Lambda",
                                         latex_prefix = "\\Lambda^\\vee" if root_system.dual_side else "\\Lambda",
                                         category = WeightLatticeRealizations(base_ring))

        if root_system.cartan_type().is_affine() and not extended:
            # For an affine type, register the quotient map from the
            # extended weight lattice/space to the weight lattice/space
            domain = root_system.weight_space(base_ring, extended=True)
            domain.module_morphism(self.fundamental_weight,
                                   codomain = self
                                   ).register_as_coercion()

    def __init__(self, g, basis_key, prefix, **kwds):
        """
        Initialize ``self``.

        TESTS::

            sage: L = lie_algebras.sl(QQ, 2)
            sage: PBW = L.pbw_basis()
            sage: E,F,H = PBW.algebra_generators()
            sage: TestSuite(PBW).run(elements=[E, F, H])
            sage: TestSuite(PBW).run(elements=[E, F, H, E*F + H]) # long time
        """
        if basis_key is not None:
            self._basis_key = basis_key
        else:
            self._basis_key_inverse = None

        R = g.base_ring()
        self._g = g
        monomials = IndexedFreeAbelianMonoid(g.basis().keys(), prefix,
                                             sorting_key=self._monoid_key, **kwds)
        CombinatorialFreeModule.__init__(self, R, monomials,
                                         prefix='', bracket=False, latex_bracket=False,
                                         sorting_key=self._monomial_key,
                                         category=Algebras(R).WithBasis().Filtered())

        def __init__(self, M, prefix='I'):
            """
            Initialize ``self``.

            TESTS::

                sage: L = posets.BooleanLattice(4)
                sage: M = L.moebius_algebra(QQ)
                sage: TestSuite(M.I()).run()
            """
            self._basis_name = "idempotent"
            CombinatorialFreeModule.__init__(self, M.base_ring(),
                                             tuple(M._lattice),
                                             prefix=prefix,
                                             category=MoebiusAlgebraBases(M))

            ## Change of basis:
            E = M.E()
            self.module_morphism(self._to_natural_basis,
                                 codomain=E, category=self.category(),
                                 triangular='lower', unitriangular=True
                                 ).register_as_coercion()

            E.module_morphism(E._to_idempotent_basis,
                              codomain=self, category=self.category(),
                              triangular='lower', unitriangular=True
                              ).register_as_coercion()

    def __init__(self, basis, ambient, unitriangular, category):
        r"""
        Initialization.

        TESTS::

            sage: from sage.modules.with_basis.subquotient import SubmoduleWithBasis
            sage: X = CombinatorialFreeModule(QQ, range(3), prefix="x"); x = X.basis()
            sage: ybas = (x[0]-x[1], x[1]-x[2])
            sage: Y = SubmoduleWithBasis(ybas, X)
            sage: Y.print_options(prefix='y')
            sage: Y.basis().list()
            [y[0], y[1]]
            sage: [ y.lift() for y in Y.basis() ]
            [x[0] - x[1], x[1] - x[2]]
            sage: TestSuite(Y).run()
        """
        import operator

        ring = ambient.base_ring()
        CombinatorialFreeModule.__init__(self, ring, basis.keys(), category=category.Subobjects())
        self._ambient = ambient
        self._basis = basis
        self._unitriangular = unitriangular
        self.lift_on_basis = self._basis.__getitem__

        def __init__(self, alg, prefix="D"):
            r"""
            Initialize ``self``.

            EXAMPLES::

                sage: TestSuite(DescentAlgebra(QQ, 4).D()).run()
            """
            self._prefix = prefix
            self._basis_name = "standard"
            p_set = subsets(range(1, alg._n))
            CombinatorialFreeModule.__init__(self, alg.base_ring(),
                                             map(tuple, p_set),
                                             category=DescentAlgebraBases(alg),
                                             bracket="", prefix=prefix)

            # Change of basis:
            B = alg.B()
            self.module_morphism(self.to_B_basis,
                                 codomain=B, category=self.category()
                                 ).register_as_coercion()

            B.module_morphism(B.to_D_basis,
                              codomain=self, category=self.category()
                              ).register_as_coercion()

            # Coercion to symmetric group algebra
            SGA = SymmetricGroupAlgebra(alg.base_ring(), alg._n)
            self.module_morphism(self.to_symmetric_group_algebra,
                                 codomain=SGA, category=Algebras(alg.base_ring())
                                 ).register_as_coercion()

    def __init__(self, group, base_ring=IntegerRing()):
        r"""
        See :class:`GroupAlgebra` for full documentation.

        EXAMPLES::

            sage: GroupAlgebra(GL(3, GF(7)))
            Group algebra of group "General Linear Group of degree 3 over Finite Field of size 7" over base ring Integer Ring
        """
        from sage.groups.group import Group
        from sage.groups.old import Group as OldGroup
        if not base_ring.is_commutative():
            raise NotImplementedError("Base ring must be commutative")

        if not isinstance(group, (Group, OldGroup)):
            raise TypeError('"%s" is not a group' % group)

        self._group = group
        CombinatorialFreeModule.__init__(self, base_ring, group,
                                         prefix='',
                                         bracket=False,
                                         category=HopfAlgebrasWithBasis(base_ring))

        if not base_ring.has_coerce_map_from(group) :
            ## some matrix groups assume that coercion is only valid to
            ## other matrix groups. This is a workaround
            ## call _element_constructor_ to coerce group elements
            #try :
            self._populate_coercion_lists_(coerce_list=[base_ring, group])
            #except TypeError :
            #    self._populate_coercion_lists_( coerce_list = [base_ring] )
        else :
            self._populate_coercion_lists_(coerce_list=[base_ring])

    def __init__(self, root_system, base_ring, index_set=None):
        """
        EXAMPLES::

            sage: e = RootSystem(['A',3]).ambient_lattice()
            sage: s = e.simple_reflections()

            sage: L = RootSystem(['A',3]).coroot_lattice()
            sage: e.has_coerce_map_from(L)
            True
            sage: e(L.simple_root(1))
            (1, -1, 0, 0)
        """
        self.root_system = root_system
        if index_set is None:
            index_set = tuple(range(0, self.dimension()))
        CombinatorialFreeModule.__init__(self, base_ring,
                                         index_set,
                                         prefix='e',
                                         category = WeightLatticeRealizations(base_ring))
        coroot_lattice = self.root_system.coroot_lattice()
        coroot_lattice.module_morphism(self.simple_coroot, codomain=self).register_as_coercion()

        # FIXME: here for backward compatibility;
        # Should we use dimension everywhere?
        self.n = self.dimension()
        ct = root_system.cartan_type()
        if ct.is_irreducible() and ct.type() == 'E':
            self._v0 = self([0,0,0,0,0, 0,1, 1])
            self._v1 = self([0,0,0,0,0,-2,1,-1])

    def __init__(self, base_ring, n, variable_name, filtration):
        r"""
        Initialize ``self``.

        EXAMPLES::

            sage: Y = Yangian(QQ, 4, filtration='loop')
            sage: TestSuite(Y).run(skip="_test_antipode") # Not implemented
            sage: Y = Yangian(QQ, 4, filtration='natural')
            sage: G = Y.algebra_generators()
            sage: elts = [Y.one(), G[1,2,2], G[1,1,4], G[3,3,1], G[1,2,1]*G[2,1,4]]
            sage: TestSuite(Y).run(elements=elts)  # long time
        """
        self._n = n
        self._filtration = filtration
        category = HopfAlgebrasWithBasis(base_ring).Filtered()
        if filtration == 'natural':
            category = category.Connected()
        self._index_set = tuple(range(1,n+1))
        # The keys for the basis are tuples (l, i, j)
        indices = GeneratorIndexingSet(self._index_set)
        # We note that the generators are non-commutative, but we always sort
        #   them, so they are, in effect, indexed by the free abelian monoid
        basis_keys = IndexedFreeAbelianMonoid(indices, bracket=False,
                                              prefix=variable_name)
        CombinatorialFreeModule.__init__(self, base_ring, basis_keys,
                                         sorting_key=Yangian._term_key,
                                         prefix=variable_name, category=category)

        def __init__(self, QSym):
            r"""
            The dual immaculate basis of the non-commutative symmetric functions. This basis first
            appears in Berg, Bergeron, Saliola, Serrano and Zabrocki's " A lift of the Schur and Hall-Littlewood
            bases to non-commutative symmetric functions".

            EXAMPLES ::

                sage: QSym = QuasiSymmetricFunctions(QQ)
                sage: dI = QSym.dI()
                sage: dI([1,3,2])*dI([1])  # long time (6s on sage.math, 2013)
                dI[1, 1, 3, 2] + dI[2, 3, 2]
                sage: dI([1,3])*dI([1,1])
                dI[1, 1, 1, 3] + dI[1, 1, 4] + dI[1, 2, 3] - dI[1, 3, 2] - dI[1, 4, 1] - dI[1, 5] + dI[2, 3, 1] + dI[2, 4]
                sage: dI([3,1])*dI([2,1])  # long time (7s on sage.math, 2013)
                dI[1, 1, 5] - dI[1, 4, 1, 1] - dI[1, 4, 2] - 2*dI[1, 5, 1] - dI[1, 6] - dI[2, 4, 1] - dI[2, 5] - dI[3, 1, 3] + dI[3, 2, 1, 1] + dI[3, 2, 2] + dI[3, 3, 1] + dI[4, 1, 1, 1] + 2*dI[4, 2, 1] + dI[4, 3] + dI[5, 1, 1] + dI[5, 2]
                sage: F = QSym.F()
                sage: dI(F[1,3,1])
                -dI[1, 1, 1, 2] + dI[1, 1, 2, 1] - dI[1, 2, 2] + dI[1, 3, 1]
                sage: F(dI(F([2,1,3])))
                F[2, 1, 3]
            """
            CombinatorialFreeModule.__init__(self, QSym.base_ring(), Compositions(),
                                             prefix='dI', bracket=False,
                                             category=QSym.Bases())

    def __init__(self, A):
        r"""
        Initialize ``self``.

        EXAMPLES::

            sage: S = SymmetricGroupAlgebra(QQ, 3)
            sage: C = S.cellular_basis()
            sage: TestSuite(C).run()
        """
        self._algebra = A
        I = [(la, s, t) for la in A.cell_poset()
             for s in A.cell_module_indices(la)
             for t in A.cell_module_indices(la)]

        # TODO: Use instead A.category().Realizations() so
        #   operations are defined by coercion?
        cat = Algebras(A.category().base_ring()).FiniteDimensional().WithBasis().Cellular()
        CombinatorialFreeModule.__init__(self, A.base_ring(), I,
                                         prefix='C', bracket=False,
                                         category=cat)

        # Register coercions
        if A._to_cellular_element is not NotImplemented:
            to_cellular = A.module_morphism(A._to_cellular_element, codomain=self,
                                            category=cat)
        if A._from_cellular_index is NotImplemented:
            from_cellular = ~to_cellular
        else:
            from_cellular = self.module_morphism(A._from_cellular_index, codomain=A,
                                                 category=cat)
            if A._to_cellular_element is NotImplemented:
                to_cellular = ~from_cellular
        to_cellular.register_as_coercion()
        from_cellular.register_as_coercion()