package cayley

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

func TestFullBench251(t *testing.T) {
	if testing.Short() {
		t.Skip("P=251 BFS takes ~2min")
	}
	P := int64(251)
	rng := rand.New(rand.NewSource(42))
	volume := P * (P*P - 1)

	// === BFS: graph statistics ===
	t.Logf("=== P=%d |G|=%d ===", P, volume)
	start := time.Now()
	gs := randomGens(P, 4, rng)
	pf := gs.BFS(-1)
	bfsTime := time.Since(start)
	t.Logf("Obfuscated BFS: %s, %d vertices, diam=%d, mean=%.1f",
		bfsTime.Round(time.Millisecond), pf.Reachable(),
		pf.MaxDist(), pf.DistStatsMean())

	// === Standard generator BFS ===
	stdGS := StandardGens(P)
	start = time.Now()
	stdPF := stdGS.BFS(-1)
	stdTime := time.Since(start)
	t.Logf("Standard BFS:   %s, diam=%d, mean=%.1f",
		stdTime.Round(time.Millisecond), stdPF.MaxDist(), stdPF.DistStatsMean())

	// === Generative basis ===
	gb := BuildGenerativeBasis(gs)
	if gb == nil {
		t.Fatal("standard gens not reachable")
	}
	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])
	}
	t.Logf("std→G words:  %v (avg=%.1f)", stdLens, avgMap(stdLens))

	// === Blowup: sample 20 targets, reusing precomputed BFS ===
	var eucT, sigT, optT int
	n := 0
	for i := 0; i < 20; i++ {
		target := randomSL2Fast(P, rng)
		euc, ok := stdPF.PathTo(target)
		if !ok { continue }
		opt, ok := pf.PathTo(target)
		if !ok { continue }
		sig := gb.Sign(euc)
		if sig == nil { continue }
		if !gs.Walk(ID(), sig).Eq(target) { continue }
		eucT += len(euc); sigT += len(sig); optT += len(opt); n++
	}
	if n > 0 {
		t.Logf("Blowup n=%d:", n)
		t.Logf("  Euclidean:     %.1f", float64(eucT)/float64(n))
		t.Logf("  Converted sig: %.1f", float64(sigT)/float64(n))
		t.Logf("  BFS optimal:   %.1f", float64(optT)/float64(n))
		t.Logf("  Euc→sig blowup: %.1f×", float64(sigT)/float64(eucT))
		t.Logf("  Sig→opt blowup: %.1f×", float64(sigT)/float64(optT))
	}

	// === Security ===
	diam := pf.MaxDist()
	mim := math.Pow(4.0, float64(diam)/2.0)
	t.Logf("Security: diam=%d MIM≈2^%.0f", diam, math.Log2(mim))
}

func avgMap(m map[string]int) float64 {
	var s int
	for _, v := range m { s += v }
	return float64(s) / float64(len(m))
}