package sort

import (
	"math/rand"
	"testing"
	quickcheck "testing/quick" // aliased: this package already has a quick() sort

	"codeberg.org/snonux/algorithms/ds"
)

// This file provides property-based verification for every sort. Unlike the
// size-driven tests in sort_test.go, which only assert a.Sorted(), these tests
// also assert the *permutation* invariant: the output must contain exactly the
// same elements as the input. A buggy sort that drops or duplicates an element
// while still returning an ordered slice would pass a Sorted()-only check but
// fail here. Together, "ordered" + "permutation of the input" is the full
// functional-correctness postcondition proven on paper in docs/verification.md.

// sortUnderTest is the shared signature of every sort in this package. An
// ds.ArrayList[int] shares []int's representation, so the property helpers
// convert between them for free.
type sortUnderTest func(ds.ArrayList[int]) ds.ArrayList[int]

// allSorts lists every sort to verify, keyed by name for readable subtests.
func allSorts() map[string]sortUnderTest {
	return map[string]sortUnderTest{
		"Selection":     Selection[int],
		"Insertion":     Insertion[int],
		"Shell":         Shell[int],
		"Merge":         Merge[int],
		"BottomUpMerge": BottomUpMerge[int],
		"ParallelMerge": ParallelMerge[int],
		"Quick":         Quick[int],
		"ParallelQuick": ParallelQuick[int],
		"Quick3Way":     Quick3Way[int],
	}
}

// sameMultiset reports whether b is a permutation of a: equal length and equal
// element multiplicities. This is the invariant the Sorted()-only tests miss.
func sameMultiset(a, b []int) bool {
	if len(a) != len(b) {
		return false
	}
	counts := make(map[int]int, len(a))
	for _, v := range a {
		counts[v]++
	}
	for _, v := range b {
		counts[v]--
		if counts[v] < 0 {
			return false // b has an element a doesn't have (enough of)
		}
	}
	// Equal lengths plus no negative count implies the multisets match exactly.
	return true
}

// sortedPermutationOf runs sort on a copy of orig and checks both invariants:
// the result is ordered and is a permutation of orig. orig is not mutated.
func sortedPermutationOf(sort sortUnderTest, orig []int) bool {
	work := make([]int, len(orig))
	copy(work, orig)
	out := sort(ds.ArrayList[int](work))
	return out.Sorted() && sameMultiset(orig, out)
}

// TestPropertyOrderedPermutation uses testing/quick to throw many randomly
// shaped small slices (arbitrary values, lengths up to ~50) at each sort,
// asserting the ordered-permutation property on every trial.
func TestPropertyOrderedPermutation(t *testing.T) {
	cfg := &quickcheck.Config{MaxCount: 2000}
	for name, sort := range allSorts() {
		name, sort := name, sort
		t.Run(name, func(t *testing.T) {
			t.Parallel()
			prop := func(in []int) bool { return sortedPermutationOf(sort, in) }
			if err := quickcheck.Check(prop, cfg); err != nil {
				t.Errorf("%s violated ordered-permutation property: %v", name, err)
			}
		})
	}
}

// TestPropertySizes exercises input sizes that cross the algorithms' internal
// thresholds: the len<=10 insertion-sort cutoffs, the len<1000 sequential
// fallbacks in the parallel sorts, and the odd-length merge clamp. The largest
// sizes (which drive the real goroutine fan-out) run only outside -short.
func TestPropertySizes(t *testing.T) {
	sizes := []int{0, 1, 2, 10, 11, 100, 999, 1000, 1001}
	if !testing.Short() {
		sizes = append(sizes, 5000, 20001)
	}
	for name, sort := range allSorts() {
		name, sort := name, sort
		t.Run(name, func(t *testing.T) {
			t.Parallel()
			rng := rand.New(rand.NewSource(1))
			for _, n := range sizes {
				in := make([]int, n)
				for i := range in {
					in[i] = rng.Intn(50) - 25 // small range ⇒ many duplicates
				}
				if !sortedPermutationOf(sort, in) {
					t.Errorf("%s failed ordered-permutation at size %d", name, n)
				}
			}
		})
	}
}