from sage.libs.singular.letterplace import temporary_MPolynomialRing_from_letterplace_ring
from sage.libs.singular.function import singular_function
from sage.algebras.free_algebra import FreeAlgebra
from sage.libs.singular.function import lib, singular_function
from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing

def iter_free_monomial(monomial, gens):
    for (index, exponent) in monomial:
        for i in xrange(exponent):
            yield gens[index]

def freegb(ideal, deg_bound):
    """
    sage: F.<x,y,z> = FreeAlgebra(QQ, 3); F
    Free Algebra on 3 generators (x, y, z) over Rational Field
    sage: l=[2*x*z*x+y*x*y, 3*x*y+x*z]
    sage: freegb(l, 10)
    [3*y*x*z^7*y + y*x*z^8, 3*y*x*z^6*y + y*x*z^7, y*x*z^6*x*z + 314928*y^2*x*z^2*x^5, 3*y*x*z^5*y + y*x*z^6, y*x*z^5*x*z - 17496*y^2*x*z^2*x^4, 3*y*x*z^4*y + y*x*z^5, y*x*z^4*x*z + 972*y^2*x*z^2*x^3, 3*y*x*z^4*x^2*z*y + y*x*z^4*x^2*z^2, 3*y*x*z^3*y + y*x*z^4, y*x*z^3*x*z - 54*y^2*x*z^2*x^2, 3*y*x*z^3*x^2*z^2*y + y*x*z^3*x^2*z^3, 3*y*x*z^3*x^2*z*y + y*x*z^3*x^2*z^2, 3*y*x*z^3*x^3*z*y + y*x*z^3*x^3*z^2, 3*y*x*z^2*y + y*x*z^3, y*x*z^2*x*z + 3*y^2*x*z^2*x, 3*y*x*z^2*x^2*z^3*y + y*x*z^2*x^2*z^4, 3*y*x*z^2*x^2*z^2*y + y*x*z^2*x^2*z^3, y*x*z^2*x^2*z^2*x*z + 3*y^2*x*z^2*x^2*z^2*x, 3*y*x*z^2*x^2*z*y + y*x*z^2*x^2*z^2, 3*y*x*z^2*x^3*z^2*y + y*x*z^2*x^3*z^3, 3*y*x*z^2*x^3*z*y + y*x*z^2*x^3*z^2, 3*y*x*z^2*x^4*z*y + y*x*z^2*x^4*z^2, 3*y*x*z*y + y*x*z^2, x*z*y^6*x*z - 7776*y*x*z^2*x^6, x*z*y^5*x*z - 1296*y*x*z^2*x^5, x*z*y^4*x*z - 216*y*x*z^2*x^4, x*z*y^3*x*z - 36*y*x*z^2*x^3, x*z*y^2*x*z - 6*y*x*z^2*x^2, x*z*y*x*z - y*x*z^2*x, 6*x*z*x - y*x*z, 3*x*y + x*z]
    """
    lib("freegb.lib")
    free_algebra=ideal[0].parent()
    base_ring = free_algebra.base_ring()
    gens = free_algebra.gens()
    variable_names = [str(g) for g in gens]
    pre_letter_place_ring=PolynomialRing(base_ring, variable_names)
    make_letter_place_ring = singular_function("makeLetterplaceRing")
    ring_wrap = make_letter_place_ring(10, ring=pre_letter_place_ring)
    
    (to_letter_place, from_letter_place) = \
        temporary_MPolynomialRing_from_letterplace_ring(ring_wrap, 
        base_ring, gens,  deg_bound
        )
    
    singular_ring = iter(from_letter_place.keys()).next().parent()
    
    polynomial_list=[]
    for p in ideal:
        sum_p = 0
        for term in p:
            (coef, monomial) = term
            m = 1
            for (i,v) in enumerate(iter_free_monomial(monomial, gens)):
                m=m*to_letter_place[v][i]
            m=m*coef
            sum_p = sum_p+m
        polynomial_list.append(sum_p)
    
    
    free_gbasis=singular_function("freeGBasis")
    from sage.libs.singular.option import LibSingularOptions
    libsingular_options = LibSingularOptions()
    bck = int(libsingular_options)
    #letter place needs these options
    libsingular_options['redTail'] = True
    libsingular_options['redSB'] = True
    libsingular_options(bck)
    
    singular_system=singular_function("system")
    gb = singular_system("freegb",
        singular_ring.ideal(polynomial_list), 
        deg_bound, 
        len(gens))

    result = []
    def sort_key(index_generator_tuple):
        return index_generator_tuple[0]
    for p in gb:
        sum_p=free_algebra(0)
        for (coef, monomial) in p:
            m=free_algebra(1)
            index_generator_list=[]
            for v in monomial.variables():
                #there exist no exponent > 1 in the result freegb 
                (index, alg_gen) = from_letter_place[v]
                index_generator_list.append((index, alg_gen))
            index_generator_list = sorted(index_generator_list, key=sort_key)
            
            for (index, alg_gen) in index_generator_list:
                m = m * alg_gen
            m=coef * m
            sum_p = sum_p + m
        result.append(sum_p)
    return result