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
71
72
73
74
75
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)
}
})
}
}
|
