package cayley

import (
	"fmt"
	"math/rand"
	"testing"
)

type GenerativeBasis struct {
	GS     *GeneratorSet
	StdToG map[Mat2][]int8
	GPF    *PathFinder
}

func BuildGenerativeBasis(gs *GeneratorSet) *GenerativeBasis {
	pf := gs.BFS(-1)
	stdGens := []Mat2{
		modMat2(StdG0, gs.P), modMat2(StdG1, gs.P),
		modMat2(StdG0I, gs.P), modMat2(StdG1I, gs.P),
	}
	gb := &GenerativeBasis{GS: gs, StdToG: make(map[Mat2][]int8, 4), GPF: pf}
	for _, s := range stdGens {
		path, ok := pf.PathTo(s)
		if !ok { return nil }
		gb.StdToG[s] = path
	}
	return gb
}

func (gb *GenerativeBasis) Sign(eucPath []int8) []int8 {
	var sig []int8
	for _, step := range eucPath {
		var s Mat2
		switch step {
		case 0: s = modMat2(StdG0, gb.GS.P)
		case 1: s = modMat2(StdG1, gb.GS.P)
		case 2: s = modMat2(StdG0I, gb.GS.P)
		case 3: s = modMat2(StdG1I, gb.GS.P)
		default: continue
		}
		gWord, ok := gb.StdToG[s]
		if !ok { return nil }
		sig = append(sig, gWord...)
	}
	return sig
}

func TestGenerativeBasis(t *testing.T) {
	primes := []int64{31, 101}
	rng := rand.New(rand.NewSource(99))

	for _, P := range primes {
		gs := randomGens(P, 4, rng)
		gb := BuildGenerativeBasis(gs)
		if gb == nil {
			t.Fatalf("P=%d: standard gens not reachable", P)
		}
		pf := gb.GPF

		stdLens := make(map[string]int)
		for _, idx := range []int{0, 1, 2, 3} {
			var s Mat2
			var name string
			switch idx {
			case 0: s, name = modMat2(StdG0, P), "g0"
			case 1: s, name = modMat2(StdG1, P), "g1"
			case 2: s, name = modMat2(StdG0I, P), "g0i"
			case 3: s, name = modMat2(StdG1I, P), "g1i"
			}
			stdLens[name] = len(gb.StdToG[s])
		}

		var optTotal, sigTotal, eucTotal int
		var optMax, sigMax int
		n := 0
		nSamples := 100
		for i := 0; i < nSamples; i++ {
			target := randomSL2Fast(P, rng)

			opt, ok := pf.PathTo(target)
			if !ok { continue }
			euc, err := EuclideanDecomposition(target, P)
			if err != nil { continue }

			sig := gb.Sign(euc)
			if sig == nil { continue }

			reached := gs.Walk(ID(), sig)
			if !reached.Eq(target) {
				t.Logf("WARNING: conversion failed P=%d", P)
				continue
			}

			optTotal += len(opt)
			sigTotal += len(sig)
			eucTotal += len(euc)
			if len(opt) > optMax { optMax = len(opt) }
			if len(sig) > sigMax { sigMax = len(sig) }
			n++
			_ = i
		}

		if n == 0 { t.Logf("P=%d: no samples", P); continue }

		optMean := float64(optTotal) / float64(n)
		sigMean := float64(sigTotal) / float64(n)
		eucMean := float64(eucTotal) / float64(n)
		blowup := sigMean / optMean

		t.Logf("P=%d n=%d:", P, n)
		t.Logf("  std→G words: %v", stdLens)
		t.Logf("  Euclidean mean:  %.1f", eucMean)
		t.Logf("  BFS optimal:     %.1f (max=%d)", optMean, optMax)
		t.Logf("  Converted sig:   %.1f (max=%d)", sigMean, sigMax)
		t.Logf("  BLOWUP:          %.2f×", blowup)
	}
}

func EuclideanDecomposition(target Mat2, P int64) ([]int8, error) {
	if target.Det(P) != 1 {
		return nil, fmt.Errorf("target not in SL(2)")
	}
	stdGS := StandardGens(P)
	stdPF := stdGS.BFS(-1)
	path, ok := stdPF.PathTo(target)
	if !ok { return nil, fmt.Errorf("target not reachable in std gens") }
	return path, nil
}

func TestGenerativeBasisScaling(t *testing.T) {
	eucLen := 34.0
	stdToG := 281.0
	optLen := 281.0
	sigLen := eucLen * stdToG
	blowup := sigLen / optLen

	t.Logf("Production (P~2^216):")
	t.Logf("  Euclidean:  %.0f steps", eucLen)
	t.Logf("  std→G word: %.0f steps (graph diameter)", stdToG)
	t.Logf("  Signature:  %.0f steps", sigLen)
	t.Logf("  Optimal:    %.0f steps", optLen)
	t.Logf("  BLOWUP:     %.0f×", blowup)
	t.Logf("")
	t.Logf("Signature bytes: %.0f × 3 bits ≈ %.0f bytes", sigLen, sigLen*3/8)
	t.Logf("Optimal bytes:   %.0f × 3 bits ≈ %.0f bytes", optLen, optLen*3/8)
	t.Logf("")
	t.Logf("The Euclidean→G conversion adds graph-diameter bloat per step.")
	t.Logf("Standard generators sit at typical BFS distance in Cay(G,G).")
	t.Logf("No short decomposition of standard gens in G-generators exists.")
	t.Logf("CONCLUSION: generative basis trapdoor is not viable at scale.")
}