"""Fraction-free sparse elimination over Z[t] with bookkeeping of all
polynomials by which we multiply or divide (the 'bad' set)."""
import pickle, sys, time
from flint import fmpz_poly, fmpq_poly, fmpq, fmpz
from system import ERRDIMS
from functools import reduce


def to_fmpq_poly(coeffs):
    return fmpq_poly([fmpq(*map(int, c.split("/"))) if "/" in c else fmpq(int(c)) for c in coeffs])


def qpoly_to_zpoly(q):
    # q: fmpq_poly -> (fmpz_poly primitive-ish, denominator integer)
    den = q.denom()
    return fmpz_poly([int(x) for x in (q * den).coeffs()])


def row_content(row):
    g = None
    for v in row.values():
        g = v if g is None else g.gcd(v)
        if g == 1 or g == -1:
            return fmpz_poly([1])
    return g


def load(path, err_order):
    D = pickle.load(open(path, "rb"))
    rows_raw = D["rows"]
    cols = {}
    for r in rows_raw:
        for c in r:
            if c[0] == "nu" and c not in cols:
                cols[c] = len(cols)
    N = len(cols)
    o = N
    for n in err_order:
        for i in range(ERRDIMS[n]):
            cols[("err", n, i)] = o + i
        o += ERRDIMS[n]
    bad = []
    rows = []
    for r in rows_raw:
        # common denominator
        ents = {cols[c]: (to_fmpq_poly(nu), to_fmpq_poly(de)) for c, (nu, de) in r.items()}
        L = fmpq_poly([1])
        for nu, de in ents.values():
            L = L * de // L.gcd(de) if L.gcd(de) != 0 else L * de
        newr = {}
        for c, (nu, de) in ents.items():
            newr[c] = nu * (L // de)
        # clear rational coeffs
        den = fmpz(1)
        for v in newr.values():
            d = v.denom()
            den = den * d // den.gcd(d)
        zr = {c: fmpz_poly([int(x) for x in (v * den).coeffs()]) for c, v in newr.items()}
        if L.degree() > 0:
            bad.append(qpoly_to_zpoly(L))
        g = row_content(zr)
        if g.degree() > 0:
            bad.append(g)
        if g != 1:
            zr = {c: v // g for c, v in zr.items()}
        rows.append(zr)
    return rows, N, o, cols, bad


def eliminate(rows, verbose=False):
    piv = {}
    bad = []
    t0 = time.time()
    # process sparse rows first
    rows = sorted(rows, key=lambda r: (min(r), len(r)))
    for n, r in enumerate(rows):
        r = dict(r)
        while r:
            c = min(r)
            if c in piv:
                pr = piv[c]
                a = pr[c]
                b = r[c]
                g = a.gcd(b)
                a1, b1 = a // g, b // g
                if a1.degree() > 0:
                    bad.append(a1)
                nr = {}
                keys = set(r) | set(pr)
                for cc in keys:
                    v = a1 * r.get(cc, fmpz_poly([0])) - b1 * pr.get(cc, fmpz_poly([0]))
                    if v != 0:
                        nr[cc] = v
                if nr:
                    cg = row_content(nr)
                    if cg.degree() > 0:
                        bad.append(cg)
                    if cg != 1:
                        nr = {cc: v // cg for cc, v in nr.items()}
                r = nr
            else:
                piv[c] = r
                break
        if verbose and n % 100 == 0:
            print(f"  {n}/{len(rows)} piv {len(piv)} {time.time()-t0:.1f}s", file=sys.stderr)
    return piv, bad


def factor_set(polys):
    fs = {}
    for p in polys:
        c, facs = p.factor()
        for f, e in facs:
            if f.degree() > 0:
                # normalize sign
                if f.coeffs()[-1] < 0:
                    f = -f
                fs[str(f)] = f
    return list(fs.values())