"""Hom(G, Z_n) computed from the GEOMETRIC model (ops + lattice + t).

This route does not rely on the named generators generating G -- which for
three of the 68 entries (g11 pg, g131 p4m, g134 p4g) they do not (see
cx_report_gens.py).  A homomorphism is stored as

    phi = (u0, u1, ct, c[0..N-1])

with  phi(I, lambda, 0) = u . lambda,  phi(t) = ct,  phi(op_i) = c_i,
and   phi(M, v, tau) = c_i + u . lambda + ct * k   after reduce().
"""
import itertools
import cx_geom as X


def gen_subset(G):
    """A small generating subset of the finite quotient Q = G/(Lambda + Zt)."""
    N = len(G.ops)
    have = {G.id_i}
    gens = []
    for a in range(N):
        if a in have:
            continue
        gens.append(a)
        cur = set(have) | {a}
        while True:
            new = set(cur)
            for x in cur:
                for g in gens:
                    new.add(G.tab[x][g][0])
                    new.add(G.tab[g][x][0])
            if new == cur:
                break
            cur = new
        have = cur
        if len(have) == N:
            break
    return gens


def homs(G, n, ct_choices=None):
    N = len(G.ops)
    us = [u for u in itertools.product(range(n), repeat=2)
          if all(tuple(x % n for x in X.mv(X.mT(M), u)) == u for M in G.mats)]
    cts = list(range(n)) if G.with_time else [0]
    if ct_choices is not None:
        cts = [x for x in cts if x in ct_choices]
    gq = gen_subset(G)
    out = []
    for u in us:
        for ct in cts:
            for vals in itertools.product(range(n), repeat=len(gq)):
                c = [None]*N
                c[G.id_i] = 0
                ok = True
                for g, v in zip(gq, vals):
                    if c[g] is not None and c[g] != v % n:
                        ok = False
                        break
                    c[g] = v % n
                if not ok:
                    continue
                changed = True
                while changed and ok:
                    changed = False
                    for a in range(N):
                        if c[a] is None:
                            continue
                        for g in gq:
                            k, lam, kt = G.tab[a][g]
                            val = (c[a] + c[g] - u[0]*lam[0] - u[1]*lam[1]
                                   - ct*kt) % n
                            if c[k] is None:
                                c[k] = val
                                changed = True
                            elif c[k] != val:
                                ok = False
                                break
                        if not ok:
                            break
                if not ok or any(x is None for x in c):
                    continue
                for a in range(N):
                    for b in range(N):
                        k, lam, kt = G.tab[a][b]
                        if (c[a]+c[b]-u[0]*lam[0]-u[1]*lam[1]-ct*kt-c[k]) % n:
                            ok = False
                            break
                    if not ok:
                        break
                if ok:
                    out.append((u[0], u[1], ct, tuple(c)))
    out = sorted(set(out))
    return out


def onto(G, phi, n):
    """Image of phi is all of Z_n?  Generated by u, ct and the c_i."""
    u0, u1, ct, c = phi
    g = n
    for x in (u0, u1, ct) + tuple(c):
        g = X.gcd(g, x)
    return g == 1