/* This script is part of radix_info.
   Copyright (C) 2023  Adrien Hopkins

   This program is free software: you can redistribute it and/or modify
   it under the terms of version 3 of the GNU General Public License
   as published by the Free Software Foundation.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program.  If not, see <https://www.gnu.org/licenses/>.
*/

package factors

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

// Run a test with a table of cases
func tableTest[IN comparable, OUT any](t *testing.T, toTest func(IN) OUT,
	cases map[IN]OUT, equal func(OUT, OUT) bool, name string) {
	for input, expected := range cases {
		t.Run(fmt.Sprintf("%v", input), func(t *testing.T) {
			actual := toTest(input)
			if !equal(expected, actual) {
				t.Errorf("%s(%v) = %v, expect %v", name, input, actual, expected)
			}
		})
	}
}

type uintPair struct{ a, b uint }

var primeFactorCases = map[uint]PrimeFactorization{
	0:     PrimeFactorization{map[uint]uint{0: 1}},
	1:     PrimeFactorization{map[uint]uint{}},
	2:     PrimeFactorization{map[uint]uint{2: 1}},
	3:     PrimeFactorization{map[uint]uint{3: 1}},
	4:     PrimeFactorization{map[uint]uint{2: 2}},
	6:     PrimeFactorization{map[uint]uint{2: 1, 3: 1}},
	9:     PrimeFactorization{map[uint]uint{3: 2}},
	10:    PrimeFactorization{map[uint]uint{2: 1, 5: 1}},
	12:    PrimeFactorization{map[uint]uint{2: 2, 3: 1}},
	33:    PrimeFactorization{map[uint]uint{3: 1, 11: 1}},
	60:    PrimeFactorization{map[uint]uint{2: 2, 3: 1, 5: 1}},
	71:    PrimeFactorization{map[uint]uint{71: 1}},
	1024:  PrimeFactorization{map[uint]uint{2: 10}},
	86400: PrimeFactorization{map[uint]uint{2: 7, 3: 3, 5: 2}},
}

func TestPrimeFactorize(t *testing.T) {
	equal := func(a, b PrimeFactorization) bool {
		return mapEquals(a.exponents, b.exponents)
	}
	tableTest(t, PrimeFactorize, primeFactorCases, equal, "PrimeFactorize")
}

var factorCases = map[uint][]uint{
	1:  []uint{1},
	2:  []uint{1, 2},
	4:  []uint{1, 2, 4},
	6:  []uint{1, 2, 3, 6},
	9:  []uint{1, 3, 9},
	10: []uint{1, 2, 5, 10},
	12: []uint{1, 2, 3, 4, 6, 12},
	13: []uint{1, 13},
	15: []uint{1, 3, 5, 15},
	16: []uint{1, 2, 4, 8, 16},
	18: []uint{1, 2, 3, 6, 9, 18},
	30: []uint{1, 2, 3, 5, 6, 10, 15, 30},
	32: []uint{1, 2, 4, 8, 16, 32},
	33: []uint{1, 3, 11, 33},
	60: []uint{1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60},
	71: []uint{1, 71},
}

func TestFactors(t *testing.T) {
	tableTest(t, Factors, factorCases, setEquals[uint], "Factors")
}

var totativeRatioCases = map[uint]float64{
	1: 1.0, 2: 0.5, 3: 2.0 / 3.0, 4: 0.5, 6: 1.0 / 3.0, 7: 6.0 / 7.0, 8: 0.5,
	10: 0.4, 12: 1.0 / 3.0, 14: 3.0 / 7.0, 15: 8.0 / 15.0, 16: 0.5, 20: 0.4,
	24: 1.0 / 3.0, 30: 4.0 / 15.0, 60: 4.0 / 15.0, 71: 70.0 / 71.0,
	120: 4.0 / 15.0,
}

func totativeRatio(n uint) float64 {
	return float64(Totient(n)) / float64(n)
}

func TestTotativeRatio(t *testing.T) {
	tableTest(t, totativeRatio, totativeRatioCases, stdEquals[float64],
		"TotativeRatio")
}

var totientCases = map[uint]uint{
	0: 0, 1: 1, 2: 1, 3: 2, 4: 2, 6: 2, 7: 6, 8: 4, 10: 4, 12: 4,
	14: 6, 15: 8, 16: 8, 20: 8, 24: 8, 30: 8, 60: 16, 71: 70, 120: 32,
}

func TestTotativeCount(t *testing.T) {
	tableTest(t, Totient, totientCases, stdEquals[uint], "Totient")
}

var totativeDigitCases = map[uint32][]uint32{
	0:  []uint32{},
	1:  []uint32{1},
	2:  []uint32{1},
	3:  []uint32{1, 2},
	4:  []uint32{1, 3},
	6:  []uint32{1, 5},
	7:  []uint32{1, 2, 3, 4, 5, 6},
	8:  []uint32{1, 3, 5, 7},
	10: []uint32{1, 3, 7, 9},
	12: []uint32{1, 5, 7, 11},
	14: []uint32{1, 3, 5, 9, 11, 13},
	15: []uint32{1, 2, 4, 7, 8, 11, 13, 14},
	16: []uint32{1, 3, 5, 7, 9, 11, 13, 15},
	20: []uint32{1, 3, 7, 9, 11, 13, 17, 19},
	24: []uint32{1, 5, 7, 11, 13, 17, 19, 23},
	30: []uint32{1, 7, 11, 13, 17, 19, 23, 29},
	60: []uint32{1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59},
	71: []uint32{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
		16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30,
		31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45,
		46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60,
		61, 62, 63, 64, 65, 66, 67, 68, 69, 70},
	120: []uint32{1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59,
		61, 67, 71, 73, 77, 79, 83, 89, 91, 97, 101, 103, 107, 109, 113, 119},
}

func TestTotativeDigits(t *testing.T) {
	tableTest(t, TotativeDigits, totativeDigitCases, sliceEquals[uint32],
		"TotativeDigits")
}

var factorScoreCases = map[uint]float64{
	1:   1.0,
	2:   1.5,
	3:   4.0 / 3.0,
	4:   1.75,
	6:   2.0,
	8:   1.875,
	10:  1.8,
	12:  7.0 / 3.0,
	71:  72.0 / 71.0,
	120: 3.0,
	// number that will use bigScore
	367567200: 62496.0 / 12155.0,
}

func TestFactorScore(t *testing.T) {
	// factors.Score is accurate enough that we can test for exact floats!
	tableTest(t, Score, factorScoreCases, stdEquals[float64], "Score")
}

var basicRankCases = map[uint]string{
	// one test per rank, plus three extra (22, 25, 44) to test that
	// n%3 = 1 vs n%3 = 2 doesn't matter
	2: "D-", 3: "E-", 4: "C~", 5: "F+", 6: "B~", 7: "F-", 8: "C-",
	9: "E~", 10: "D+", 11: "F~", 12: "A-", 14: "D~", 15: "E+", 18: "B-",
	20: "C+", 22: "D-", 24: "A~", 25: "F+", 30: "B+", 44: "C~", 60: "A+",
	// test that it only depends on n%60
	62: "D-", 63: "E-", 64: "C~", 65: "F+", 66: "B~", 67: "F-", 68: "C-",
	69: "E~", 70: "D+", 71: "F~", 72: "A-", 74: "D~", 75: "E+", 78: "B-",
	80: "C+", 82: "D-", 84: "A~", 85: "F+", 90: "B+", 104: "C~", 120: "A+",
	// test that it can extend to 0 and 1 as well
	0: "A+", 1: "F~",
}

func TestBasicRank(t *testing.T) {
	tableTest(t, BasicRank, basicRankCases, stdEquals[string], "BasicRank")
}

var gcdCases = map[struct{ a, b uint32 }]uint32{
	{0, 0}: 0, {1, 1}: 1,
	{0, 1}: 1, {1, 0}: 1,
	{0, 12}: 12, {12, 0}: 12,
	{1, 12}: 1, {12, 1}: 1,
	{6, 10}: 2, {10, 6}: 2,
	{12, 20}: 4, {20, 12}: 4,
	{20, 55}: 5, {55, 20}: 5,
	{60, 120}: 60, {120, 60}: 60,
	{120, 180}: 60, {180, 120}: 60,
}

// a version of gcd() for testing purposes
func gcdTest(c struct{ a, b uint32 }) uint32 {
	return gcd(c.a, c.b)
}

func TestGCD(t *testing.T) {
	tableTest(t, gcdTest, gcdCases, stdEquals[uint32], "gcd")
}

var mtcCases = map[uint32]uint64{
	2: 0, 3: 0, 4: 2, 5: 10, 6: 8,
	7: 28, 8: 26, 9: 42, 10: 42, 11: 88, 12: 52,
	13: 130, 14: 100, 15: 116, 16: 138, 18: 146,
	20: 190, 24: 252, 28: 416, 30: 380, 32: 618, 36: 598,
	48: 1100, 60: 1496, 64: 2602, 90: 3662, 120: 6080,
	210: 18542, 360: 54362, 840: 270122, 2520: 2363528, 5040: 9409112,
}

func TestMTC(t *testing.T) {
	tableTest(t, MTC, mtcCases, stdEquals[uint64], "MTC")
}

var sanCases = map[uint]bool{
	1: true, 2: true, 4: true, 6: true, 12: true, 24: true, 36: true,
	48: true, 60: true, 120: true, 180: true, 240: true, 360: true,
	720: true, 840: true, 1260: true, 1680: true, 2520: true, 5040: true,
	10080: true, 15120: true, 25200: true, 27720: true, 55440: true,
	3: false, 8: false, 13: false, 18: false, 20: false, 30: false,
	31: false, 72: false, 107: false, 135: false, 144: false, 300: false,
	1728: false, 4000: false, 6912: false, 7560: false,
}

func isSAN(n uint) bool {
	return Type(n) >= Superabundant
}

func TestSAN(t *testing.T) {
	tableTest(t, isSAN, sanCases, stdEquals[bool], "isSAN")
}

var expOrdCases = map[uint]bool{
	0: true, 1: true, 2: true, 4: true, 5: false, 6: true, 8: true, 12: true,
	16: true, 18: false, 20: false, 27: false, 30: true, 36: true, 44: false,
	60: true, 70: false, 90: false, 96: true, 101: false, 120: true, 144: true,
	180: true, 770: false, 900: true, 6912: true, 10010: false,
}

func TestExponentsOrdered(t *testing.T) {
	tableTest(t, exponentsOrdered, expOrdCases, stdEquals[bool],
		"exponentsOrdered")
}

var practicalCases = map[uint]bool{
	1: true, 2: true, 4: true, 6: true, 8: true, 12: true, 16: true,
	18: true, 20: true, 24: true, 28: true, 30: true, 32: true, 36: true,
	48: true, 60: true, 120: true, 180: true, 240: true, 360: true,
	720: true, 840: true, 1260: true, 1680: true, 2520: true, 5040: true,
	10080: true, 15120: true, 25200: true, 27720: true, 55440: true,
	3: false, 10: false, 27: false, 44: false, 45: false, 68: false,
	70: false, 114: false, 121: false, 770: false, 1729: false, 10010: false,
}

func TestPractical(t *testing.T) {
	tableTest(t, practical, practicalCases, stdEquals[bool], "practical")
}

var typeCases = map[uint]CompositenessType{
	2: ColossallyAbundant, 3: None, 4: Superabundant,
	6: ColossallyAbundant, 8: OrderedExponent, 10: None,
	12: ColossallyAbundant, 18: Practical, 20: Practical, 24: Superabundant,
	28: Practical, 30: OrderedExponent, 31: None, 34: None,
	60: ColossallyAbundant, 70: None, 90: Practical, 100: Practical,
	120: ColossallyAbundant, 144: OrderedExponent, 180: Superabundant,
	240: Superabundant, 360: ColossallyAbundant, 720: Superabundant,
	770: None, 900: OrderedExponent, 1680: Superabundant,
	1729: None, 6912: OrderedExponent, 10010: None,
	10080: Superabundant, 15120: Superabundant, 25200: Superabundant,
	27720: Superabundant, 55440: ColossallyAbundant,
}

func TestType(t *testing.T) {
	tableTest(t, Type, typeCases, stdEquals[CompositenessType], "Type")
}

// ====== DIGIT MAP TESTS ======
var (
	zt = zeroType                      // 00 - zero
	ot = oneType                       // 0R - one
	ft = DigitType{1, Regular}         // 1R - factors
	rt = DigitType{2, Regular}         // 2R - regulars (index 2)
	wt = DigitType{0, Omega}           // 0ω - omega neighbours
	at = DigitType{0, Alpha}           // 0α - alpha neighbours
	nt = DigitType{0, Pseudoneighbour} // 0N - neighbour-like
	pt = DigitType{0, Opaque}          // 0P - opaque totatives
)
var digitMapCases = map[uint][]DigitType{
	0: []DigitType{},
	1: []DigitType{zt},
	2: []DigitType{zt, ot},
	3: []DigitType{zt, ot, wt},
	4: []DigitType{zt, ot, ft, wt},
	5: []DigitType{zt, ot, wt, at, wt},
	6: []DigitType{zt, ot, ft, ft, rt, wt},
	8: []DigitType{zt, ot, ft, at, ft, pt, DigitType{1, Alpha}, wt},
	10: []DigitType{zt, ot, ft, wt, rt, ft, DigitType{1, Omega}, pt,
		DigitType{3, Regular}, wt},
	11: []DigitType{zt, ot, wt, at, at, wt, at, pt, nt, pt, wt},
	12: []DigitType{zt, ot, ft, ft, ft, pt, ft, pt, rt, rt,
		DigitType{1, Opaque}, wt},
	16: []DigitType{zt, ot, ft, wt, ft, wt, DigitType{1, Omega}, pt,
		ft, pt, DigitType{1, Omega}, pt, DigitType{1, Omega},
		pt, DigitType{1, Opaque}, wt},
	17: []DigitType{zt, ot, wt, at, wt, pt, at, pt, wt, at,
		pt, pt, nt, pt, pt, pt, wt},
	19: []DigitType{zt, ot, wt, wt, at, at, wt, pt, nt, wt,
		at, pt, nt, pt, pt, nt, pt, pt, wt},
	22: []DigitType{zt, ot, ft, wt, rt, pt, DigitType{1, Omega}, wt,
		DigitType{3, Regular}, pt, DigitType{1, Opaque}, ft,
		DigitType{2, Omega}, pt, DigitType{1, Omega}, pt,
		DigitType{4, Regular}, pt, DigitType{1, Opaque}, pt,
		DigitType{2, Opaque}, wt},
	24: []DigitType{zt, ot, ft, ft, ft, at, ft, pt, ft, rt,
		DigitType{1, Alpha}, pt, ft, pt, DigitType{1, Opaque},
		DigitType{1, Alpha}, rt, pt, rt, pt, DigitType{1, Alpha},
		DigitType{1, Opaque}, DigitType{1, Opaque}, wt},
}

func TestDigitMap(t *testing.T) {
	tableTest(t, DigitMap, digitMapCases, sliceEquals[DigitType], "DigitMap")
}

// ensures GetDigitType(d, r) == DigitMap(r)[d];
// does not ensure it has the correct value (that's TestDigitMap's job)
func TestGetDigitType(t *testing.T) {
	for radix := range digitMapCases {
		digitMap := DigitMap(radix)
		for digit := range digitMap {
			actual := GetDigitType(uint(digit), radix)
			if actual != digitMap[digit] {
				t.Logf("GetDigitType(%d, %d) = %d", digit, radix, actual)
				t.Errorf("GetDigitType(%d, %d) != DigitMap(%d)[%d]",
					digit, radix, radix, digit)
			}
		}
	}
}

// A few test cases related to radix zero
func TestGetDigitTypeMisc(t *testing.T) {
	t.Run("GetDigitType(0, 0)", func(t *testing.T) {
		if GetDigitType(0, 0) != ft {
			t.Errorf("GetDigitType(0, 0) = %s, expected 1R", GetDigitType(0, 0))
		}
	})
	t.Run("GetDigitType(1, 0)", func(t *testing.T) {
		if GetDigitType(1, 0) != ot {
			t.Errorf("GetDigitType(1, 0) = %s, expected 0R", GetDigitType(1, 0))
		}
	})
	t.Run("GetDigitType(2, 0)", func(t *testing.T) {
		if GetDigitType(2, 0) != pt {
			t.Errorf("GetDigitType(2, 0) = %s, expected 0P", GetDigitType(2, 0))
		}
	})
}

var splitCases = map[uintPair]uintPair{
	// digit, radix, regular part, totative part
	uintPair{0, 0}:    uintPair{0, 1},
	uintPair{0, 1}:    uintPair{1, 0},
	uintPair{0, 2}:    uintPair{1, 0},
	uintPair{0, 12}:   uintPair{1, 0},
	uintPair{1, 0}:    uintPair{1, 1},
	uintPair{20, 0}:   uintPair{1, 20},
	uintPair{360, 0}:  uintPair{1, 360},
	uintPair{1, 1}:    uintPair{1, 1},
	uintPair{12, 1}:   uintPair{1, 12},
	uintPair{87, 1}:   uintPair{1, 87},
	uintPair{120, 1}:  uintPair{1, 120},
	uintPair{1, 2}:    uintPair{1, 1},
	uintPair{1, 3}:    uintPair{1, 1},
	uintPair{1, 7}:    uintPair{1, 1},
	uintPair{1, 12}:   uintPair{1, 1},
	uintPair{1, 39}:   uintPair{1, 1},
	uintPair{1, 2948}: uintPair{1, 1},
	uintPair{5, 6}:    uintPair{1, 5},
	uintPair{10, 6}:   uintPair{2, 5},
	uintPair{12, 6}:   uintPair{12, 1},
	uintPair{15, 6}:   uintPair{3, 5},
	uintPair{35, 6}:   uintPair{1, 35},
	uintPair{56, 6}:   uintPair{8, 7},
	uintPair{5, 12}:   uintPair{1, 5},
	uintPair{10, 12}:  uintPair{2, 5},
	uintPair{12, 12}:  uintPair{12, 1},
	uintPair{15, 12}:  uintPair{3, 5},
	uintPair{35, 12}:  uintPair{1, 35},
	uintPair{56, 12}:  uintPair{8, 7},
	uintPair{12, 7}:   uintPair{1, 12},
	uintPair{56, 7}:   uintPair{7, 8},
	uintPair{70, 10}:  uintPair{10, 7},
}

// testing version of Split
func splitTest(a uintPair) uintPair {
	regular, totative := Split(a.a, a.b)
	return uintPair{regular, totative}
}

func TestSplit(t *testing.T) {
	tableTest(t, splitTest, splitCases, stdEquals[uintPair], "Split")
}

var primeRegularComplexityCases = map[uint]map[uint]float64{
	2:   {2: 1},
	3:   {3: 1},
	4:   {2: 1},
	6:   {2: 3, 3: 2},
	10:  {2: 5, 5: 2},
	12:  {2: math.Sqrt(3), 3: 4},
	20:  {2: math.Sqrt(5), 5: 4},
	24:  {2: math.Cbrt(3), 3: 8},
	36:  {2: 3, 3: 2},
	40:  {2: math.Cbrt(5), 5: 8},
	60:  {2: math.Sqrt(15), 3: 20, 5: 12},
	120: {2: math.Cbrt(15), 3: 40, 5: 24},
	360: {2: math.Cbrt(45), 3: math.Sqrt(40), 5: 72},
}

func TestPrimeRegularComplexity(t *testing.T) {
	// Use approxEquals instead of == due to differences between
	// math.Sqrt/math.Cbrt and math.Pow.
	// The different digits are never shown to the user, so no big deal.
	tableTest(t, PrimeRegularComplexities, primeRegularComplexityCases,
		mapApproxEquals[uint], "PrimeRegularComplexities")
}

// to be used as the equal paramater for tableTest
func stdEquals[T comparable](a, b T) bool { return a == b }

func mapEquals[K, V comparable](a, b map[K]V) bool {
	for k, av := range a {
		bv, ok := b[k]
		if !ok || bv != av {
			return false
		}
	}
	for k, bv := range b {
		av, ok := a[k]
		if !ok || bv != av {
			return false
		}
	}
	return true
}

func approxEquals(a, b, epsilon float64) bool {
	return math.Abs(a-b) <= epsilon*math.Max(math.Abs(a), math.Abs(b))
}

func mapApproxEquals[K comparable](a, b map[K]float64) bool {
	for k, av := range a {
		bv, ok := b[k]
		if !ok || !approxEquals(av, bv, 1e-15) {
			return false
		}
	}
	for k, bv := range b {
		av, ok := a[k]
		if !ok || !approxEquals(av, bv, 1e-15) {
			return false
		}
	}
	return true
}

func setEquals[E comparable](a, b []E) bool {
	// use maps to simulate sets
	// aSet[a] == true means set contains a, false means not
	aSet := make(map[E]bool)
	bSet := make(map[E]bool)
	for _, i := range a {
		aSet[i] = true
	}
	for _, j := range b {
		bSet[j] = true
	}
	return mapEquals(aSet, bSet)
}

func sliceEquals[E comparable](a, b []E) bool {
	if len(a) != len(b) {
		return false
	}

	for i := 0; i < len(a); i++ {
		if a[i] != b[i] {
			return false
		}
	}

	return true
}