1 files changed, 76 insertions, 0 deletions
diff --git a/queue/property_test.go b/queue/property_test.go
new file mode 100644
index 0000000..e4ab044
--- /dev/null
+++ b/queue/property_test.go
@@ -0,0 +1,76 @@
+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)
+			}
+		})
+	}
+}