"""L7: one tree, three readings. The LPS overlay X(5, q) of SHD-CCP RFC 03 for q in {13, 17, 29}, its checks (a)-(e)
and controls, as spike S5 built them (Amendment 1, item 9).

phi_q sends a + b i + c j + d k to [[a + b iota, c + d iota], [-c + d iota, a - b iota]] mod q, iota^2 = -1 mod q
(iota the smallest positive root: 5, 4, 12), a ring homomorphism with det = the norm. Vertices are 2x2 matrices mod q
up to a nonzero scalar (the representative scales the first nonzero entry, row-major, to 1); edges join v and
v phi_q(g) for the six generators (right multiplication, so walking g1..gL from the identity reaches
phi_q(g1)...phi_q(gL), the order of word_quaternion). The graph is built by BFS from the identity: the Cayley graph of
the group the six images generate, vertex 0 the identity.

    Cayley(q, iota=None, gens=range(6))   .n, .verts, .nbr (numpy N x 6), .nbrl, .dist, .parent, .walk(word),
                                          .vertex_of(matrix), .reduction(word)
    structure(G)        (a): vertices against q(q^2-1) or q(q^2-1)/2, 6-regular, inverse-closed, connected, bipartite
    girth(G)            exact, by BFS from the identity (a Cayley graph is vertex-transitive); r = (g - 1) // 2
    identity_word_counts(G, Lmax)   reduced words of each length equal to the identity (a second exact girth)
    walk_vs_reduction(G, words)     (b): the words where the walk and the reduction disagree
    injectivity(G, r)               (c): every reduced word of length <= r, exhaustively
    spectrum(G)                     (d): dense float64 eigvalsh; the largest |lambda| other than +-6, its margin
    load_hurwitz(), hurwitz_word(word), hurwitz_check(words, halve=True)   (e) against SHD-CCP's hurwitz.py
    control_iota2(q, words), control_subset(q)                             the controls of (b) and (a)
    random_word(rng)                Amendment 1, item 9
    spread(G, words)                how a set of words spreads over the vertices (reported)

SHD-CCP's hurwitz.py is imported read-only: sys.dont_write_bytecode is set first, its src folder is appended to
sys.path explicitly, and the file's SHA-256 must be the pinned one. hpstep.problems is imported in place.
"""
import hashlib
import importlib.util
import math
import os
import sys
import time

import numpy as np
from hpstep.problems import GENS, INV, children, qmul, word_quaternion

QS = (13, 17, 29)
TWO_SQRT5 = 2 * math.sqrt(5)
def _shdccp_dir():
    """SHD_CCP_DIR, else the SHD-CCP checkout beside this repository (scripts/lib/siblings.py; the path only: the
    file's SHA-256, HURWITZ_SHA256 below, stays the content pin)."""
    lib = os.path.join(os.path.dirname(os.path.abspath(__file__)), '..', '..', '..', '..', 'scripts', 'lib', 'siblings.py')
    spec = importlib.util.spec_from_file_location('ebayednoob_siblings', lib)
    mod = importlib.util.module_from_spec(spec)
    spec.loader.exec_module(mod)
    return mod.dir('SHD-CCP')


SHDCCP_SRC = os.path.join(_shdccp_dir(), 'Geometric_Engine', 'ecosystem', 'SHD-CCP', 'geometric-engine', 'src')
HURWITZ_FILE = os.path.join(SHDCCP_SRC, 'geometric_engine', 'hurwitz.py')
HURWITZ_SHA256 = 'cecb6dccb4f3757dcdb7ec96994e30a5d6c2fc2f973234b51e7e86ecf1b244e9'   # spike S5's read
IDENT = (1, 0, 0, 1)


# ================================================================ the map and projective matrices mod q
def legendre(a, q):
    e = pow(a % q, (q - 1) // 2, q)
    return 1 if e == 1 else (-1 if e == q - 1 else 0)


def sqrt_minus_one(q):
    """The smallest positive iota with iota^2 = -1 mod q: 5, 4, 12 for q = 13, 17, 29."""
    return next(x for x in range(1, q) if (x * x + 1) % q == 0)


def phi(quat, iota, q):
    a, b, c, d = quat
    return ((a + b * iota) % q, (c + d * iota) % q, (-c + d * iota) % q, (a - b * iota) % q)


def mmul(x, y, q):
    return ((x[0] * y[0] + x[1] * y[2]) % q, (x[0] * y[1] + x[1] * y[3]) % q,
            (x[2] * y[0] + x[3] * y[2]) % q, (x[2] * y[1] + x[3] * y[3]) % q)


def canon(m, q):
    """The projective class's representative: the first nonzero entry (row-major) scaled to 1."""
    for e in m:
        if e % q:
            inv = pow(e, -1, q)
            return tuple(x * inv % q for x in m)
    raise ValueError('the zero matrix has no projective class')


def det(m, q):
    return (m[0] * m[3] - m[1] * m[2]) % q


def _enc(m, q):
    return ((m[0] * q + m[1]) * q + m[2]) * q + m[3]


class Cayley:
    """The Cayley graph, from the identity, of the group generated by phi_q(GENS[g]) for g in gens (right
    multiplication), vertices numbered in BFS order. iota defaults to sqrt_minus_one(q)."""

    def __init__(self, q, iota=None, gens=tuple(range(6))):
        self.q = q
        self.iota = sqrt_minus_one(q) if iota is None else iota
        self.gens = tuple(gens)
        self.mats = [phi(GENS[g], self.iota, q) for g in self.gens]
        verts, index, nbr, dist, parent = [IDENT], {_enc(IDENT, q): 0}, [], [0], [-1]
        i = 0
        while i < len(verts):
            m, row = verts[i], []
            for M in self.mats:
                c = canon(mmul(m, M, q), q)
                k = _enc(c, q)
                j = index.get(k)
                if j is None:
                    j = len(verts)
                    index[k] = j
                    verts.append(c)
                    dist.append(dist[i] + 1)
                    parent.append(i)
                row.append(j)
            nbr.append(row)
            i += 1
        self.verts, self.index, self.n = verts, index, len(verts)
        self.nbrl = nbr
        self.nbr = np.array(nbr, dtype=np.int64)
        self.dist = np.array(dist, dtype=np.int64)
        self.parent = np.array(parent, dtype=np.int64)

    def vertex_of(self, m):
        """The vertex of a matrix (None if its class is not in the graph)."""
        return self.index.get(_enc(canon(m, self.q), self.q))

    def walk(self, word):
        """The vertex reached by walking the word from the identity."""
        v = 0
        for g in word:
            v = self.nbrl[v][self.gens.index(g)]
        return v

    def reduction(self, word):
        """The vertex of word_quaternion(word) reduced by phi_q and projectivised."""
        return self.vertex_of(phi(word_quaternion(word), self.iota, self.q))


_GRAPHS = {}


def graph(q):
    """The L7 graph X(5, q) (cached)."""
    if q not in _GRAPHS:
        _GRAPHS[q] = Cayley(q)
    return _GRAPHS[q]


# ================================================================ (a) structure, girth
def structure(G):
    """L7(a): vertex count against the expected group order, regularity, inverse closure, connectivity and
    bipartiteness. 'connected' is true by construction (BFS from the identity enumerates the generated group);
    the count check shows that group is all of PGL(2, F_q) or PSL(2, F_q)."""
    q, k = G.q, len(G.gens)
    leg = legendre(5, q)
    expect = q * (q * q - 1) // (2 if leg == 1 else 1)
    srt = np.sort(G.nbr, axis=1)
    regular = bool(np.all(np.diff(srt, axis=1) > 0) and np.all(G.nbr != np.arange(G.n)[:, None]))
    degrees = sorted({len(set(row)) for row in G.nbrl})
    inv_proj = all(canon(mmul(G.mats[i], G.mats[G.gens.index(INV[g])], q), q) == IDENT
                   for i, g in enumerate(G.gens) if INV[g] in G.gens)
    inv_graph = all(INV[g] in G.gens and np.array_equal(G.nbr[G.nbr[:, i], G.gens.index(INV[g])], np.arange(G.n))
                    for i, g in enumerate(G.gens))
    U, V = np.repeat(np.arange(G.n), k), G.nbr.ravel()
    bipartite = bool(np.all((G.dist[U] - G.dist[V]) % 2 != 0))
    return {'q': q, 'iota': G.iota, 'legendre': leg, 'vertices': G.n, 'expected': expect, 'count_ok': G.n == expect,
            'regular6': regular and k == 6 and degrees == [6], 'degrees': degrees,
            'inverse_closed': inv_proj and inv_graph,
            'connected': True, 'bipartite': bipartite, 'bipartite_expected': leg == -1,
            'diameter': int(G.dist.max())}


def girth(G):
    """The exact girth: one BFS from the identity, the minimum of d(u) + d(v) + 1 over non-tree edges. Exact for a
    Cayley graph, which is vertex-transitive, so the identity lies on a shortest cycle. Returns (g, r)."""
    k = len(G.gens)
    U, V = np.repeat(np.arange(G.n), k), G.nbr.ravel()
    tree_edge = (G.parent[V] == U) | (G.parent[U] == V)
    g = int(np.min(G.dist[U][~tree_edge] + G.dist[V][~tree_edge] + 1))
    return g, (g - 1) // 2


def identity_word_counts(G, Lmax):
    """For L = 0..Lmax, the number of reduced words of length L that walk from the identity back to it (exact,
    the non-backtracking recursion over (vertex, last letter)). The first L >= 1 with a nonzero count is the girth."""
    N = G.n
    c = np.zeros((N, 6), dtype=np.int64)
    for g in range(6):
        c[G.nbr[0, g], g] += 1
    out = [1, int(c[0].sum())]
    for _ in range(2, Lmax + 1):
        nc = np.zeros_like(c)
        tot = c.sum(axis=1)
        for g in range(6):
            nc[G.nbr[:, g], g] = tot - c[:, INV[g]]
        c = nc
        out.append(int(c[0].sum()))
    return out


# ================================================================ (b), (c)
def walk_vs_reduction(G, words):
    """L7(b): the indices of the words whose reduction differs from the walk ([] when (b) holds)."""
    return [i for i, w in enumerate(words) if G.reduction(w) != G.walk(w)]


def reduced_words_upto(L):
    words, layer = [()], [()]
    for _ in range(L):
        layer = [w + (g,) for w in layer for g in children(w)]
        words.extend(layer)
    return words


def injectivity(G, r):
    """L7(c): every reduced word of length <= r, by reduction (and the walk, which must agree). Returns
    (number of words, number of distinct vertices, number of words where walk != reduction)."""
    words = reduced_words_upto(r)
    vr = [G.reduction(w) for w in words]
    bad_walk = sum(1 for w, v in zip(words, vr) if G.walk(w) != v)
    return len(words), len(set(vr)), bad_walk


# ================================================================ (d)
def adjacency_dense(G):
    A = np.zeros((G.n, G.n))
    rows = np.arange(G.n)
    for i in range(len(G.gens)):
        A[rows, G.nbr[:, i]] = 1.0
    return A


def spectrum(G, bipartite=None):
    """L7(d): numpy.linalg.eigvalsh of the dense float64 adjacency. The trivial eigenvalues are the top (+6) and, if
    the graph is bipartite, the bottom (-6) of the sorted spectrum; returns the largest |lambda| over the rest and its
    margin to 2 sqrt 5, the multiplicities of +-6 (tolerance 1e-9) and the eigvalsh time. q = 29 (12,180 vertices)
    takes about 160 s and about 2.3 GB."""
    if bipartite is None:
        bipartite = structure(G)['bipartite']
    A = adjacency_dense(G)
    t0 = time.perf_counter()
    lam = np.sort(np.linalg.eigvalsh(A))
    t_eig = time.perf_counter() - t0
    del A
    nontrivial = lam[1:-1] if bipartite else lam[:-1]
    maxabs = float(np.max(np.abs(nontrivial)))
    return {'n': G.n, 'maxabs': maxabs, 'margin': TWO_SQRT5 - maxabs, 'ramanujan': maxabs <= TWO_SQRT5 - 1e-9,
            'n_plus6': int(np.sum(np.abs(lam - 6) < 1e-9)), 'n_minus6': int(np.sum(np.abs(lam + 6) < 1e-9)),
            'top': float(lam[-1]), 'bottom': float(lam[0]), 'seconds': t_eig}


# ================================================================ (e) SHD-CCP's Hurwitz product
_HZ = {}


def load_hurwitz(path=SHDCCP_SRC):
    """SHD-CCP's geometric_engine.hurwitz, imported read-only (no bytecode written, explicit sys.path entry, pinned
    SHA-256). Returns (module, sha256 of hurwitz.py)."""
    if 'mod' not in _HZ:
        f = os.path.join(path, 'geometric_engine', 'hurwitz.py')
        with open(f, 'rb') as fh:
            digest = hashlib.sha256(fh.read()).hexdigest()
        if digest != HURWITZ_SHA256:
            raise ValueError(f'SHD-CCP hurwitz.py is {digest}, not the pinned {HURWITZ_SHA256}')
        sys.dont_write_bytecode = True
        if path not in sys.path:
            sys.path.append(path)
        import geometric_engine.hurwitz as hz
        if os.path.realpath(hz.__file__) != os.path.realpath(f):
            raise ImportError(f'geometric_engine.hurwitz came from {hz.__file__}, not {f}')
        _HZ['mod'], _HZ['sha'] = hz, digest
    return _HZ['mod'], _HZ['sha']


def hurwitz_word(word, halve=True):
    """The product of SHD-CCP HurwitzQuaternions of the generators in doubled coordinates, left to right from
    (2, 0, 0, 0), as a 4-tuple; halved at the end (halve=False is (e)'s control: compared without the division)."""
    hz, _ = load_hurwitz()
    H = hz.HurwitzQuaternion
    gens = [H(*(2 * c for c in g)) for g in GENS]
    h = H(2, 0, 0, 0)
    for g in word:
        h = h * gens[g]
    t = (h.a, h.b, h.c, h.d)
    if not halve:
        return t
    if any(c % 2 for c in t):
        raise ArithmeticError('odd doubled coordinate')
    return tuple(c // 2 for c in t)


def raw_doubled_product(word):
    """L7(e)'s registered control: the product of the generators in doubled coordinates as plain integer
    quaternions, from (2, 0, 0, 0), without SHD-CCP's per-product halving; it equals 2^(L+1) P.wordQuaternion(w), so
    halved once and compared without dividing by 2^L it must differ from P.wordQuaternion on every word with L >= 1."""
    t = (2, 0, 0, 0)
    for g in word:
        t = qmul(t, tuple(2 * c for c in GENS[g]))
    return tuple(c // 2 for c in t)


def control_raw_doubled(words):
    """(e)'s registered control: the indices of the words where raw_doubled_product differs from word_quaternion
    (it must find at least one). hurwitz_check(words, halve=False), SHD-CCP's product without its final halving, is a
    second variant, reported."""
    return [i for i, w in enumerate(words) if raw_doubled_product(w) != word_quaternion(w)]


def hurwitz_check(words, halve=True):
    """L7(e): the indices of the words where the (halved) Hurwitz product differs from word_quaternion."""
    return [i for i, w in enumerate(words) if hurwitz_word(w, halve) != word_quaternion(w)]


# ================================================================ controls
def control_iota2(q, words, iota=2):
    """(b)'s control: phi with iota = 2 (2^2 = 4, not -1): the walk by the phi_2 matrices against phi_2 of the word's
    quaternion. Returns the indices of the words where they differ (the control must find at least one)."""
    mats = [phi(g, iota, q) for g in GENS]
    bad = []
    for i, w in enumerate(words):
        m = IDENT
        for x in w:
            m = canon(mmul(m, mats[x], q), q)
        if m != canon(phi(word_quaternion(w), iota, q), q):
            bad.append(i)
    return bad


def control_subset(q, gens=(0, 1, 2, 3)):
    """(a)'s control: the Cayley graph of a 4-generator subset; its structure()['regular6'] must be False."""
    return structure(Cayley(q, gens=gens))


# ================================================================ words, spread
def random_word(rng):
    """Amendment 1, item 9: length 1 + below(60), root letter below(6), then children(w)[below(5)] each time."""
    L = 1 + rng.below(60)
    w = [rng.below(6)]
    while len(w) < L:
        w.append(children(w)[rng.below(5)])
    return tuple(w)


def spread(G, words):
    """How words spread over the vertices: (distinct vertices hit, the largest number of words on one vertex)."""
    load = {}
    for w in words:
        v = G.reduction(w)
        load[v] = load.get(v, 0) + 1
    return len(load), max(load.values())
