package prosediff

import (
	"math/rand"
	"testing"

	"github.com/stretchr/testify/assert"
	"github.com/stretchr/testify/require"
)

func TestDiffIntsScripts(t *testing.T) {
	tests := []struct {
		name string
		a, b []int
		want []edit
	}{
		{"both empty", nil, nil, nil},
		{"identical", []int{1, 2, 3}, []int{1, 2, 3}, []edit{{OpEqual, 3}}},
		{"all inserted", nil, []int{1, 2}, []edit{{OpInsert, 2}}},
		{"all deleted", []int{1, 2}, nil, []edit{{OpDelete, 2}}},
		{"middle replaced", []int{1, 2, 3}, []int{1, 9, 3},
			[]edit{{OpEqual, 1}, {OpDelete, 1}, {OpInsert, 1}, {OpEqual, 1}}},
		{"suffix appended", []int{1, 2}, []int{1, 2, 3}, []edit{{OpEqual, 2}, {OpInsert, 1}}},
		{"prefix removed", []int{0, 1, 2}, []int{1, 2}, []edit{{OpDelete, 1}, {OpEqual, 2}}},
		{"nothing in common", []int{1, 2}, []int{3, 4},
			[]edit{{OpDelete, 2}, {OpInsert, 2}}},
	}
	for _, tc := range tests {
		t.Run(tc.name, func(t *testing.T) {
			got := diffInts(tc.a, tc.b)
			assert.Equal(t, tc.want, got)
			assertScriptApplies(t, tc.a, tc.b, got)
		})
	}
}

// TestDiffIntsMinimalRandom is the real correctness check: on random inputs
// the script must both reconstruct b from a and keep exactly as many elements
// equal as the longest common subsequence.
func TestDiffIntsMinimalRandom(t *testing.T) {
	rng := rand.New(rand.NewSource(1))
	for iter := 0; iter < 400; iter++ {
		a := randSeq(rng, rng.Intn(14), 5)
		b := randSeq(rng, rng.Intn(14), 5)
		script := diffInts(a, b)
		assertScriptApplies(t, a, b, script)
		require.Equal(t, lcsLen(a, b), commonCount(script),
			"non-minimal script for a=%v b=%v: %v", a, b, script)
		for i := 1; i < len(script); i++ {
			require.NotEqual(t, script[i-1].op, script[i].op, "runs not coalesced: %v", script)
		}
	}
}

func TestRatio(t *testing.T) {
	assert.Equal(t, 1.0, ratio(nil, nil))
	assert.Equal(t, 1.0, ratio([]int{1, 2}, []int{1, 2}))
	assert.Equal(t, 0.0, ratio([]int{1, 2}, []int{3, 4}))
	assert.Equal(t, 0.5, ratio([]int{1, 2}, []int{1, 3}))
}

func randSeq(rng *rand.Rand, n, alphabet int) []int {
	if n == 0 {
		return nil
	}
	out := make([]int, n)
	for i := range out {
		out[i] = rng.Intn(alphabet)
	}
	return out
}

func assertScriptApplies(t *testing.T, a, b []int, script []edit) {
	t.Helper()
	var gotA, gotB []int
	i, j := 0, 0
	for _, e := range script {
		switch e.op {
		case OpEqual:
			require.LessOrEqual(t, i+e.n, len(a))
			require.LessOrEqual(t, j+e.n, len(b))
			for n := 0; n < e.n; n++ {
				require.Equal(t, a[i+n], b[j+n], "equal run over differing elements")
			}
			gotA = append(gotA, a[i:i+e.n]...)
			gotB = append(gotB, b[j:j+e.n]...)
			i += e.n
			j += e.n
		case OpDelete:
			gotA = append(gotA, a[i:i+e.n]...)
			i += e.n
		case OpInsert:
			gotB = append(gotB, b[j:j+e.n]...)
			j += e.n
		}
	}
	require.Equal(t, len(a), i)
	require.Equal(t, len(b), j)
	require.Equal(t, a, sliceOrNil(gotA))
	require.Equal(t, b, sliceOrNil(gotB))
}

func sliceOrNil(s []int) []int {
	if len(s) == 0 {
		return nil
	}
	return s
}

// lcsLen is the textbook O(nm) LCS, used only as the oracle.
func lcsLen(a, b []int) int {
	dp := make([][]int, len(a)+1)
	for i := range dp {
		dp[i] = make([]int, len(b)+1)
	}
	for i := 1; i <= len(a); i++ {
		for j := 1; j <= len(b); j++ {
			if a[i-1] == b[j-1] {
				dp[i][j] = dp[i-1][j-1] + 1
				continue
			}
			dp[i][j] = max(dp[i-1][j], dp[i][j-1])
		}
	}
	return dp[len(a)][len(b)]
}