Blender  V3.3
BLI_inplace_priority_queue_test.cc
Go to the documentation of this file.
1 /* SPDX-License-Identifier: Apache-2.0 */
2 
3 #include "testing/testing.h"
4 
6 #include "BLI_rand.hh"
7 
8 namespace blender::tests {
9 
10 TEST(inplace_priority_queue, BuildSmall)
11 {
12  Array<int> values = {1, 5, 2, 8, 5, 6, 5, 4, 3, 6, 7, 3};
13  InplacePriorityQueue<int> priority_queue{values};
14 
15  EXPECT_EQ(priority_queue.peek(), 8);
16  EXPECT_EQ(priority_queue.pop(), 8);
17  EXPECT_EQ(priority_queue.peek(), 7);
18  EXPECT_EQ(priority_queue.pop(), 7);
19  EXPECT_EQ(priority_queue.pop(), 6);
20  EXPECT_EQ(priority_queue.pop(), 6);
21  EXPECT_EQ(priority_queue.pop(), 5);
22 }
23 
24 TEST(inplace_priority_queue, DecreasePriority)
25 {
26  Array<int> values = {5, 2, 7, 4};
27  InplacePriorityQueue<int> priority_queue(values);
28 
29  EXPECT_EQ(priority_queue.peek(), 7);
30  values[2] = 0;
31  EXPECT_EQ(priority_queue.peek(), 0);
32  priority_queue.priority_decreased(2);
33  EXPECT_EQ(priority_queue.peek(), 5);
34 }
35 
36 TEST(inplace_priority_queue, IncreasePriority)
37 {
38  Array<int> values = {5, 2, 7, 4};
39  InplacePriorityQueue<int> priority_queue(values);
40 
41  EXPECT_EQ(priority_queue.peek(), 7);
42  values[1] = 10;
43  EXPECT_EQ(priority_queue.peek(), 7);
44  priority_queue.priority_increased(1);
45  EXPECT_EQ(priority_queue.peek(), 10);
46 }
47 
48 TEST(inplace_priority_queue, PopAll)
49 {
51  Vector<int> values;
52  const int amount = 1000;
53  for (int i = 0; i < amount; i++) {
54  values.append(rng.get_int32() % amount);
55  }
56 
57  InplacePriorityQueue<int> priority_queue(values);
58 
59  int last_value = amount;
60  while (!priority_queue.is_empty()) {
61  const int value = priority_queue.pop();
62  EXPECT_LE(value, last_value);
63  last_value = value;
64  }
65 }
66 
67 TEST(inplace_priority_queue, ManyPriorityChanges)
68 {
70  Vector<int> values;
71  const int amount = 1000;
72  for (int i = 0; i < amount; i++) {
73  values.append(rng.get_int32() % amount);
74  }
75 
76  InplacePriorityQueue<int> priority_queue(values);
77 
78  for (int i = 0; i < amount; i++) {
79  const int index = rng.get_int32() % amount;
80  const int new_priority = rng.get_int32() % amount;
81  values[index] = new_priority;
82  priority_queue.priority_changed(index);
83  }
84 
85  int last_value = amount;
86  while (!priority_queue.is_empty()) {
87  const int value = priority_queue.pop();
88  EXPECT_LE(value, last_value);
89  last_value = value;
90  }
91 }
92 
93 TEST(inplace_priority_queue, IndicesAccess)
94 {
95  Array<int> values = {4, 6, 2, 4, 8, 1, 10, 2, 5};
96  InplacePriorityQueue<int> priority_queue(values);
97 
98  EXPECT_EQ(priority_queue.active_indices().size(), 9);
99  EXPECT_EQ(priority_queue.inactive_indices().size(), 0);
100  EXPECT_EQ(priority_queue.all_indices().size(), 9);
101  EXPECT_EQ(priority_queue.pop(), 10);
102  EXPECT_EQ(priority_queue.active_indices().size(), 8);
103  EXPECT_EQ(priority_queue.inactive_indices().size(), 1);
104  EXPECT_EQ(values[priority_queue.inactive_indices()[0]], 10);
105  EXPECT_EQ(priority_queue.all_indices().size(), 9);
106  EXPECT_EQ(priority_queue.pop(), 8);
107  EXPECT_EQ(priority_queue.inactive_indices().size(), 2);
108  EXPECT_EQ(values[priority_queue.inactive_indices()[0]], 8);
109  EXPECT_EQ(values[priority_queue.inactive_indices()[1]], 10);
110  EXPECT_EQ(priority_queue.all_indices().size(), 9);
111 }
112 
113 } // namespace blender::tests
EXPECT_EQ(BLI_expr_pylike_eval(expr, nullptr, 0, &result), EXPR_PYLIKE_INVALID)
void priority_decreased(const int64_t index)
void priority_increased(const int64_t index)
void priority_changed(const int64_t index)
constexpr int64_t size() const
Definition: BLI_span.hh:240
void append(const T &value)
Definition: BLI_vector.hh:433
TEST(any, DefaultConstructor)
Definition: BLI_any_test.cc:10