package cayley

import (
	"fmt"
	"math"
	"testing"
	"time"
)

func TestBFSCost(t *testing.T) {
	primes := []int64{11, 31, 101}
	for _, P := range primes {
		gs := StandardGens(P)
		volume := P * (P*P - 1)

		start := time.Now()
		pf := gs.BFS(-1)
		elapsed := time.Since(start)

		// Estimate memory: Dist map + Parent map + Edge map.
		// Each Mat2 = 4 int64 = 32 bytes. Each Path/node = ~diam * 1 byte.
		// Rough: 3 maps × (32B key + 8B value overhead) × N
		memKB := float64(len(pf.Dist)) * 80.0 / 1024.0

		opsPerSec := float64(volume) / elapsed.Seconds()
		microsPerOp := elapsed.Microseconds() / int64(volume)

		t.Logf("P=%2d |G|=%9d  time=%8s  speed=%.0f v/s  μs/v=%d  mem≈%d KB  diam=%d",
			P, volume, elapsed.Round(time.Microsecond), opsPerSec, microsPerOp,
			int(memKB), pf.MaxDist())
	}
}

func TestBFSCostExtrapolation(t *testing.T) {
	// Extrapolate from small primes.
	// BFS time = O(|G|) = O(P^3).
	// At P=101: 1M vertices, ~4s.
	// At P=2^216: ops/s stays roughly constant (~250K vertices/s).
	// Time = (2^216)^3 / 250K seconds.

	opsPerSec := 250000.0 // from P=101 measurement (1M / 4s)

	for _, Pbits := range []int{10, 20, 30, 40, 60, 80, 100} {
		P := math.Pow(2, float64(Pbits))
		volume := P * P * P
		seconds := volume / opsPerSec
		//years := seconds / 31536000.0

		memBytes := volume * 80.0 // 80 bytes per vertex (map overhead)
		memGB := memBytes / 1e9

		t.Logf("P=2^%d  |G|≈2^%.0f  time=%s  mem=%s",
			Pbits, math.Log2(volume),
			formatDuration(seconds),
			formatMem(memGB))
	}
}

func formatDuration(secs float64) string {
	if secs < 60 { return fmt.Sprintf("%.0fs", secs) }
	if secs < 3600 { return fmt.Sprintf("%.0fm", secs/60) }
	if secs < 86400 { return fmt.Sprintf("%.0fh", secs/3600) }
	if secs < 31536000 { return fmt.Sprintf("%.0fd", secs/86400) }
	return fmt.Sprintf("%.0fy", secs/31536000)
}

func formatMem(gb float64) string {
	if gb < 1 { return fmt.Sprintf("%.0fMB", gb*1000) }
	if gb < 1000 { return fmt.Sprintf("%.0fGB", gb) }
	if gb < 1e6 { return fmt.Sprintf("%.0fTB", gb/1000) }
	return fmt.Sprintf("%.0fPB", gb/1e6)
}