"""Exact roster and primitive odd shapes reconstructed from modular symbols.
Reuse source: NumberDB T696 generate.py, SHA256
de34dd03ca07e1eebe7af6ec731422362a8291b84204844f8a0ed76bd75e435a.
No website writes. All embeddings ordered exactly before rational filtering.
"""
import sys,json
from functools import lru_cache
from math import comb,gcd,lcm
import numberdb.sage as numberdb
from sage.modular.modsym.modsym import ModularSymbols
from sage.rings.rational_field import QQ
from sage.rings.integer_ring import ZZ
from sage.rings.infinity import infinity
from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing
from sage.rings.polynomial import laurent_polynomial_ring  # matrix dispatch
from sage.rings.qqbar import AA, _init_qqbar
_init_qqbar()
QX=PolynomialRing(QQ,'X')
ZX=PolynomialRing(ZZ,'X')
X=QX.gen()

def selected_spaces():
    return [(1,k) for k in range(4,27,2)]+[(N,12) for N in range(2,11)]

def primitive(p):
    p=QX(p)
    if not p: raise ValueError('A zero parity part has no primitive normalization')
    den=lcm(*(int(c.denominator()) for c in p.list()))
    q=ZX([ZZ(c*den) for c in p.list()])
    content=gcd(*(int(c) for c in q.list()))
    if q.leading_coefficient()<0: content=-content
    return ZX([c//content for c in q.list()])

@lru_cache(None)
def space_data(N,k):
    M=ModularSymbols(N,k,sign=-1)
    C=M.cuspidal_subspace()
    S=C.new_subspace()
    B=max(2,int(M.sturm_bound()))
    rows=[]
    for A in S.decomposition():
        q=A.q_eigenform(B+1,names='a')
        K=q.base_ring()
        assert q[0]==0 and q[1]==1
        d=int(A.dimension())
        assert d==int(K.degree())
        embeddings=[lambda a:AA(a)] if d==1 else K.embeddings(AA)
        assert len(embeddings)==d
        for emb in embeddings:
            cs=tuple(emb(q[n]) for n in range(B+1))
            rows.append({'factor':A,'q':q,'field_degree':d,'sort':cs,
                         'embedding':emb})
    rows.sort(key=lambda r:r['sort'][2:])
    assert len(rows)==S.dimension()
    assert all(rows[j-1]['sort']!=rows[j]['sort'] for j in range(1,len(rows)))
    for i,r in enumerate(rows,1):
        r.update(N=N,k=k,i=i,sturm_bound=B)
    return M,C,S,rows

@lru_cache(None)
def exact_polynomial(N,k,i):
    M,C,S,rows=space_data(N,k)
    r=rows[i-1]
    assert r['field_degree']==1
    pm=r['factor'].rational_period_mapping()
    assert pm.codomain().dimension()==1
    w=k-2
    moments=[QQ(pm(M.modular_symbol([j,0,infinity]))[0]) for j in range(w+1)]
    assert all(moments[j]==0 for j in range(0,w+1,2))
    p=sum(ZZ(comb(w,j))*moments[j]*X**(w-j) for j in range(1,w+1,2))
    return primitive(p)

def roster():
    for N,k in selected_spaces():
        for r in space_data(N,k)[3]:
            yield r

