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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
|
// CookieJar - A contestant's algorithm toolbox
// Copyright (c) 2013 Peter Szilagyi. All rights reserved.
//
// CookieJar is dual licensed: use of this source code is governed by a BSD
// license that can be found in the LICENSE file. Alternatively, the CookieJar
// toolbox may be used in accordance with the terms and conditions contained
// in a signed written agreement between you and the author(s).
package prque
import (
"math/rand"
"testing"
)
func TestPrque(t *testing.T) {
// Generate a batch of random data and a specific priority order
size := 16 * blockSize
prio := rand.Perm(size)
data := make([]int, size)
for i := 0; i < size; i++ {
data[i] = rand.Int()
}
queue := New()
for rep := 0; rep < 2; rep++ {
// Fill a priority queue with the above data
for i := 0; i < size; i++ {
queue.Push(data[i], float32(prio[i]))
if queue.Size() != i+1 {
t.Errorf("queue size mismatch: have %v, want %v.", queue.Size(), i+1)
}
}
// Create a map the values to the priorities for easier verification
dict := make(map[float32]int)
for i := 0; i < size; i++ {
dict[float32(prio[i])] = data[i]
}
// Pop out the elements in priority order and verify them
prevPrio := float32(size + 1)
for !queue.Empty() {
val, prio := queue.Pop()
if prio > prevPrio {
t.Errorf("invalid priority order: %v after %v.", prio, prevPrio)
}
prevPrio = prio
if val != dict[prio] {
t.Errorf("push/pop mismatch: have %v, want %v.", val, dict[prio])
}
delete(dict, prio)
}
}
}
func TestReset(t *testing.T) {
// Generate a batch of random data and a specific priority order
size := 16 * blockSize
prio := rand.Perm(size)
data := make([]int, size)
for i := 0; i < size; i++ {
data[i] = rand.Int()
}
queue := New()
for rep := 0; rep < 2; rep++ {
// Fill a priority queue with the above data
for i := 0; i < size; i++ {
queue.Push(data[i], float32(prio[i]))
if queue.Size() != i+1 {
t.Errorf("queue size mismatch: have %v, want %v.", queue.Size(), i+1)
}
}
// Create a map the values to the priorities for easier verification
dict := make(map[float32]int)
for i := 0; i < size; i++ {
dict[float32(prio[i])] = data[i]
}
// Pop out half the elements in priority order and verify them
prevPrio := float32(size + 1)
for i := 0; i < size/2; i++ {
val, prio := queue.Pop()
if prio > prevPrio {
t.Errorf("invalid priority order: %v after %v.", prio, prevPrio)
}
prevPrio = prio
if val != dict[prio] {
t.Errorf("push/pop mismatch: have %v, want %v.", val, dict[prio])
}
delete(dict, prio)
}
// Reset and ensure it's empty
queue.Reset()
if !queue.Empty() {
t.Errorf("priority queue not empty after reset: %v", queue)
}
}
}
func BenchmarkPush(b *testing.B) {
// Create some initial data
data := make([]int, b.N)
prio := make([]float32, b.N)
for i := 0; i < len(data); i++ {
data[i] = rand.Int()
prio[i] = rand.Float32()
}
// Execute the benchmark
b.ResetTimer()
queue := New()
for i := 0; i < len(data); i++ {
queue.Push(data[i], prio[i])
}
}
func BenchmarkPop(b *testing.B) {
// Create some initial data
data := make([]int, b.N)
prio := make([]float32, b.N)
for i := 0; i < len(data); i++ {
data[i] = rand.Int()
prio[i] = rand.Float32()
}
queue := New()
for i := 0; i < len(data); i++ {
queue.Push(data[i], prio[i])
}
// Execute the benchmark
b.ResetTimer()
for !queue.Empty() {
queue.Pop()
}
}
|
