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
|
/* Apache License, Version 2.0 */
#include "testing/testing.h"
#include "BLI_inplace_priority_queue.hh"
#include "BLI_rand.hh"
namespace blender::tests {
TEST(inplace_priority_queue, BuildSmall)
{
Array<int> values = {1, 5, 2, 8, 5, 6, 5, 4, 3, 6, 7, 3};
InplacePriorityQueue<int> priority_queue{values};
EXPECT_EQ(priority_queue.peek(), 8);
EXPECT_EQ(priority_queue.pop(), 8);
EXPECT_EQ(priority_queue.peek(), 7);
EXPECT_EQ(priority_queue.pop(), 7);
EXPECT_EQ(priority_queue.pop(), 6);
EXPECT_EQ(priority_queue.pop(), 6);
EXPECT_EQ(priority_queue.pop(), 5);
}
TEST(inplace_priority_queue, DecreasePriority)
{
Array<int> values = {5, 2, 7, 4};
InplacePriorityQueue<int> priority_queue(values);
EXPECT_EQ(priority_queue.peek(), 7);
values[2] = 0;
EXPECT_EQ(priority_queue.peek(), 0);
priority_queue.priority_decreased(2);
EXPECT_EQ(priority_queue.peek(), 5);
}
TEST(inplace_priority_queue, IncreasePriority)
{
Array<int> values = {5, 2, 7, 4};
InplacePriorityQueue<int> priority_queue(values);
EXPECT_EQ(priority_queue.peek(), 7);
values[1] = 10;
EXPECT_EQ(priority_queue.peek(), 7);
priority_queue.priority_increased(1);
EXPECT_EQ(priority_queue.peek(), 10);
}
TEST(inplace_priority_queue, PopAll)
{
RandomNumberGenerator rng;
Vector<int> values;
const int amount = 1000;
for (int i = 0; i < amount; i++) {
values.append(rng.get_int32() % amount);
}
InplacePriorityQueue<int> priority_queue(values);
int last_value = amount;
while (!priority_queue.is_empty()) {
const int value = priority_queue.pop();
EXPECT_LE(value, last_value);
last_value = value;
}
}
TEST(inplace_priority_queue, ManyPriorityChanges)
{
RandomNumberGenerator rng;
Vector<int> values;
const int amount = 1000;
for (int i = 0; i < amount; i++) {
values.append(rng.get_int32() % amount);
}
InplacePriorityQueue<int> priority_queue(values);
for (int i = 0; i < amount; i++) {
const int index = rng.get_int32() % amount;
const int new_priority = rng.get_int32() % amount;
values[index] = new_priority;
priority_queue.priority_changed(index);
}
int last_value = amount;
while (!priority_queue.is_empty()) {
const int value = priority_queue.pop();
EXPECT_LE(value, last_value);
last_value = value;
}
}
TEST(inplace_priority_queue, IndicesAccess)
{
Array<int> values = {4, 6, 2, 4, 8, 1, 10, 2, 5};
InplacePriorityQueue<int> priority_queue(values);
EXPECT_EQ(priority_queue.active_indices().size(), 9);
EXPECT_EQ(priority_queue.inactive_indices().size(), 0);
EXPECT_EQ(priority_queue.all_indices().size(), 9);
EXPECT_EQ(priority_queue.pop(), 10);
EXPECT_EQ(priority_queue.active_indices().size(), 8);
EXPECT_EQ(priority_queue.inactive_indices().size(), 1);
EXPECT_EQ(values[priority_queue.inactive_indices()[0]], 10);
EXPECT_EQ(priority_queue.all_indices().size(), 9);
EXPECT_EQ(priority_queue.pop(), 8);
EXPECT_EQ(priority_queue.inactive_indices().size(), 2);
EXPECT_EQ(values[priority_queue.inactive_indices()[0]], 8);
EXPECT_EQ(values[priority_queue.inactive_indices()[1]], 10);
EXPECT_EQ(priority_queue.all_indices().size(), 9);
}
} // namespace blender::tests
|
