Fix T72412: Weld Modifier: Merged edges not displayed in wireframe
[blender.git] / tests / gtests / blenlib / BLI_heap_test.cc
1 /* Apache License, Version 2.0 */
2
3 #include "testing/testing.h"
4 #include <string.h>
5
6 extern "C" {
7 #include "BLI_compiler_attrs.h"
8 #include "BLI_heap.h"
9 #include "BLI_utildefines.h"
10 #include "BLI_rand.h"
11
12 #include "MEM_guardedalloc.h"
13 };
14
15 #define SIZE 1024
16
17 static void range_fl(float *array_tar, const int size)
18 {
19   float *array_pt = array_tar + (size - 1);
20   int i = size;
21   while (i--) {
22     *(array_pt--) = (float)i;
23   }
24 }
25
26 TEST(heap, Empty)
27 {
28   Heap *heap;
29
30   heap = BLI_heap_new();
31   EXPECT_TRUE(BLI_heap_is_empty(heap));
32   EXPECT_EQ(BLI_heap_len(heap), 0);
33   BLI_heap_free(heap, NULL);
34 }
35
36 TEST(heap, One)
37 {
38   Heap *heap;
39   const char *in = "test";
40
41   heap = BLI_heap_new();
42
43   BLI_heap_insert(heap, 0.0f, (void *)in);
44   EXPECT_FALSE(BLI_heap_is_empty(heap));
45   EXPECT_EQ(BLI_heap_len(heap), 1);
46   EXPECT_EQ(in, BLI_heap_pop_min(heap));
47   EXPECT_TRUE(BLI_heap_is_empty(heap));
48   EXPECT_EQ(BLI_heap_len(heap), 0);
49   BLI_heap_free(heap, NULL);
50 }
51
52 TEST(heap, Range)
53 {
54   const int items_total = SIZE;
55   Heap *heap = BLI_heap_new();
56   for (int in = 0; in < items_total; in++) {
57     BLI_heap_insert(heap, (float)in, POINTER_FROM_INT(in));
58   }
59   for (int out_test = 0; out_test < items_total; out_test++) {
60     EXPECT_EQ(out_test, POINTER_AS_INT(BLI_heap_pop_min(heap)));
61   }
62   EXPECT_TRUE(BLI_heap_is_empty(heap));
63   BLI_heap_free(heap, NULL);
64 }
65
66 TEST(heap, RangeReverse)
67 {
68   const int items_total = SIZE;
69   Heap *heap = BLI_heap_new();
70   for (int in = 0; in < items_total; in++) {
71     BLI_heap_insert(heap, (float)-in, POINTER_FROM_INT(-in));
72   }
73   for (int out_test = items_total - 1; out_test >= 0; out_test--) {
74     EXPECT_EQ(-out_test, POINTER_AS_INT(BLI_heap_pop_min(heap)));
75   }
76   EXPECT_TRUE(BLI_heap_is_empty(heap));
77   BLI_heap_free(heap, NULL);
78 }
79
80 TEST(heap, RangeRemove)
81 {
82   const int items_total = SIZE;
83   Heap *heap = BLI_heap_new();
84   HeapNode **nodes = (HeapNode **)MEM_mallocN(sizeof(HeapNode *) * items_total, __func__);
85   for (int in = 0; in < items_total; in++) {
86     nodes[in] = BLI_heap_insert(heap, (float)in, POINTER_FROM_INT(in));
87   }
88   for (int i = 0; i < items_total; i += 2) {
89     BLI_heap_remove(heap, nodes[i]);
90     nodes[i] = NULL;
91   }
92   for (int out_test = 1; out_test < items_total; out_test += 2) {
93     EXPECT_EQ(out_test, POINTER_AS_INT(BLI_heap_pop_min(heap)));
94   }
95   EXPECT_TRUE(BLI_heap_is_empty(heap));
96   BLI_heap_free(heap, NULL);
97   MEM_freeN(nodes);
98 }
99
100 TEST(heap, Duplicates)
101 {
102   const int items_total = SIZE;
103   Heap *heap = BLI_heap_new();
104   for (int in = 0; in < items_total; in++) {
105     BLI_heap_insert(heap, 1.0f, 0);
106   }
107   for (int out_test = 0; out_test < items_total; out_test++) {
108     EXPECT_EQ(0, POINTER_AS_INT(BLI_heap_pop_min(heap)));
109   }
110   EXPECT_TRUE(BLI_heap_is_empty(heap));
111   BLI_heap_free(heap, NULL);
112 }
113
114 static void random_heap_helper(const int items_total, const int random_seed)
115 {
116   Heap *heap = BLI_heap_new();
117   float *values = (float *)MEM_mallocN(sizeof(float) * items_total, __func__);
118   range_fl(values, items_total);
119   BLI_array_randomize(values, sizeof(float), items_total, random_seed);
120   for (int i = 0; i < items_total; i++) {
121     BLI_heap_insert(heap, values[i], POINTER_FROM_INT((int)values[i]));
122   }
123   for (int out_test = 0; out_test < items_total; out_test++) {
124     EXPECT_EQ(out_test, POINTER_AS_INT(BLI_heap_pop_min(heap)));
125   }
126   EXPECT_TRUE(BLI_heap_is_empty(heap));
127   BLI_heap_free(heap, NULL);
128   MEM_freeN(values);
129 }
130
131 TEST(heap, Rand1)
132 {
133   random_heap_helper(1, 1234);
134 }
135 TEST(heap, Rand2)
136 {
137   random_heap_helper(2, 1234);
138 }
139 TEST(heap, Rand100)
140 {
141   random_heap_helper(100, 4321);
142 }
143
144 TEST(heap, ReInsertSimple)
145 {
146   const int items_total = SIZE;
147   Heap *heap = BLI_heap_new();
148   HeapNode **nodes = (HeapNode **)MEM_mallocN(sizeof(HeapNode *) * items_total, __func__);
149   for (int in = 0; in < items_total; in++) {
150     nodes[in] = BLI_heap_insert(heap, (float)in, POINTER_FROM_INT(in));
151   }
152   for (int i = 0; i < items_total; i++) {
153     BLI_heap_node_value_update(heap, nodes[i], (float)(items_total + i));
154   }
155
156   for (int out_test = 0; out_test < items_total; out_test++) {
157     EXPECT_EQ(out_test, POINTER_AS_INT(BLI_heap_pop_min(heap)));
158   }
159
160   EXPECT_TRUE(BLI_heap_is_empty(heap));
161   BLI_heap_free(heap, NULL);
162   MEM_freeN(nodes);
163 }
164
165 static void random_heap_reinsert_helper(const int items_total, const int random_seed)
166 {
167   Heap *heap = BLI_heap_new();
168   HeapNode **nodes = (HeapNode **)MEM_mallocN(sizeof(HeapNode *) * items_total, __func__);
169   for (int in = 0; in < items_total; in++) {
170     nodes[in] = BLI_heap_insert(heap, (float)in, POINTER_FROM_INT(in));
171   }
172   BLI_array_randomize(nodes, sizeof(HeapNode *), items_total, random_seed);
173   for (int i = 0; i < items_total; i++) {
174     BLI_heap_node_value_update(heap, nodes[i], (float)i);
175   }
176   EXPECT_TRUE(BLI_heap_is_valid(heap));
177
178   for (int out_test = 0; out_test < items_total; out_test++) {
179     HeapNode *node_top = BLI_heap_top(heap);
180     float out = BLI_heap_node_value(node_top);
181     EXPECT_EQ(out, BLI_heap_top_value(heap));
182     EXPECT_EQ((float)out_test, out);
183     BLI_heap_pop_min(heap);
184   }
185   EXPECT_TRUE(BLI_heap_is_empty(heap));
186   BLI_heap_free(heap, NULL);
187   MEM_freeN(nodes);
188 }
189
190 TEST(heap, ReInsertRandom1)
191 {
192   random_heap_reinsert_helper(1, 1234);
193 }
194 TEST(heap, ReInsertRandom2)
195 {
196   random_heap_reinsert_helper(2, 1234);
197 }
198 TEST(heap, ReInsertRandom100)
199 {
200   random_heap_reinsert_helper(100, 4321);
201 }
202 TEST(heap, ReInsertRandom1024)
203 {
204   random_heap_reinsert_helper(1024, 9876);
205 }
206 TEST(heap, ReInsertRandom2048)
207 {
208   random_heap_reinsert_helper(2048, 5321);
209 }