package queue

import (
	"testing"
	"testing/quick"
)

// Property-based verification for the priority queues. The existing tests in
// queue_test.go only check that DeleteMax yields a non-increasing sequence; they
// never check *completeness* -- that every inserted element comes back out. A
// queue that dropped, duplicated, or invented an element could still emit an
// ordered sequence and pass. These tests add the missing multiset (permutation)
// invariant, and -- because testing/quick generates negative values too -- they
// also exercise inputs the fixed-seed NewRandomArrayList tests never reach.

// sameMultiset reports whether b is a permutation of a.
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
		}
	}
	return true
}

// drainedInOrder inserts every value of in into a fresh queue, then drains it
// with DeleteMax, checking two invariants: the drained sequence is
// non-increasing (max-first) AND it is a permutation of the input (nothing
// dropped, duplicated, or invented). Size must also match after all inserts.
func drainedInOrder(newQ func() PriorityQueue, in []int) bool {
	q := newQ()
	for _, v := range in {
		q.Insert(v)
	}
	if q.Size() != len(in) {
		return false
	}

	out := make([]int, 0, len(in))
	prev, started := 0, false
	for !q.Empty() {
		m := q.DeleteMax()
		if started && m > prev {
			return false // not non-increasing
		}
		prev, started = m, true
		out = append(out, m)
	}
	return sameMultiset(in, out)
}

func TestPropertyPriorityQueues(t *testing.T) {
	queues := map[string]func() PriorityQueue{
		"ElementaryPriority": func() PriorityQueue { return NewElementaryPriority[int](1) },
		"HeapPriority":       func() PriorityQueue { return NewHeapPriority[int](1) },
	}
	cfg := &quick.Config{MaxCount: 2000}
	for name, newQ := range queues {
		name, newQ := name, newQ
		t.Run(name, func(t *testing.T) {
			t.Parallel()
			prop := func(in []int) bool { return drainedInOrder(newQ, in) }
			if err := quick.Check(prop, cfg); err != nil {
				t.Errorf("%s violated ordered-permutation property: %v", name, err)
			}
		})
	}
}