89e271d516731bdc6c393418ef2ef91ebc2447a4
[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
18 static void range_fl(float *array_tar, const int size)
19 {
20         float *array_pt = array_tar + (size - 1);
21         int i = size;
22         while (i--) {
23                 *(array_pt--) = (float)i;
24         }
25 }
26
27 TEST(heap, Empty)
28 {
29         Heap *heap;
30
31         heap = BLI_heap_new();
32         EXPECT_TRUE(BLI_heap_is_empty(heap));
33         EXPECT_EQ(BLI_heap_size(heap), 0);
34         BLI_heap_free(heap, NULL);
35 }
36
37 TEST(heap, One)
38 {
39         Heap *heap;
40         const char *in = "test";
41
42         heap = BLI_heap_new();
43  
44         BLI_heap_insert(heap, 0.0f, (void *)in);
45         EXPECT_FALSE(BLI_heap_is_empty(heap));
46         EXPECT_EQ(BLI_heap_size(heap), 1);
47         EXPECT_EQ(in, BLI_heap_popmin(heap));
48         EXPECT_TRUE(BLI_heap_is_empty(heap));
49         EXPECT_EQ(BLI_heap_size(heap), 0);
50         BLI_heap_free(heap, NULL);
51 }
52
53 TEST(heap, Range)
54 {
55         const int items_total = SIZE;
56         Heap *heap = BLI_heap_new();
57         for (int in = 0; in < items_total; in++) {
58                 BLI_heap_insert(heap, (float)in, SET_INT_IN_POINTER(in));
59         }
60         for (int out_test = 0; out_test < items_total; out_test++) {
61                 EXPECT_EQ(out_test, GET_INT_FROM_POINTER(BLI_heap_popmin(heap)));
62
63         }
64         EXPECT_TRUE(BLI_heap_is_empty(heap));
65         BLI_heap_free(heap, NULL);
66 }
67
68 TEST(heap, RangeReverse)
69 {
70         const int items_total = SIZE;
71         Heap *heap = BLI_heap_new();
72         for (int in = 0; in < items_total; in++) {
73                 BLI_heap_insert(heap, (float)-in, SET_INT_IN_POINTER(-in));
74         }
75         for (int out_test = items_total - 1; out_test >= 0; out_test--) {
76                 EXPECT_EQ(-out_test, GET_INT_FROM_POINTER(BLI_heap_popmin(heap)));
77         }
78         EXPECT_TRUE(BLI_heap_is_empty(heap));
79         BLI_heap_free(heap, NULL);
80 }
81
82 TEST(heap, RangeRemove)
83 {
84         const int items_total = SIZE;
85         Heap *heap = BLI_heap_new();
86         HeapNode **nodes = (HeapNode **)MEM_mallocN(sizeof(HeapNode *) * items_total, __func__);
87         for (int in = 0; in < items_total; in++) {
88                 nodes[in] = BLI_heap_insert(heap, (float)in, SET_INT_IN_POINTER(in));
89         }
90         for (int i = 0; i < items_total; i += 2) {
91                 BLI_heap_remove(heap, nodes[i]);
92                 nodes[i] = NULL;
93         }
94         for (int out_test = 1; out_test < items_total; out_test += 2) {
95                 EXPECT_EQ(out_test, GET_INT_FROM_POINTER(BLI_heap_popmin(heap)));
96         }
97         EXPECT_TRUE(BLI_heap_is_empty(heap));
98         BLI_heap_free(heap, NULL);
99         MEM_freeN(nodes);
100 }
101
102 TEST(heap, Duplicates)
103 {
104         const int items_total = SIZE;
105         Heap *heap = BLI_heap_new();
106         for (int in = 0; in < items_total; in++) {
107                 BLI_heap_insert(heap, 1.0f, 0);
108         }
109         for (int out_test = 0; out_test < items_total; out_test++) {
110                 EXPECT_EQ(0, GET_INT_FROM_POINTER(BLI_heap_popmin(heap)));
111         }
112         EXPECT_TRUE(BLI_heap_is_empty(heap));
113         BLI_heap_free(heap, NULL);
114 }
115
116 static void random_heap_helper(
117         const int items_total,
118         const int random_seed)
119 {
120         Heap *heap = BLI_heap_new();
121         float *values = (float *)MEM_mallocN(sizeof(float) * items_total, __func__);
122         range_fl(values, items_total);
123         BLI_array_randomize(values, sizeof(float), items_total, random_seed);
124         for (int i = 0; i < items_total; i++) {
125                 BLI_heap_insert(heap, values[i], SET_INT_IN_POINTER((int)values[i]));
126         }
127         for (int out_test = 0; out_test < items_total; out_test++) {
128                 EXPECT_EQ(out_test, GET_INT_FROM_POINTER(BLI_heap_popmin(heap)));
129         }
130         EXPECT_TRUE(BLI_heap_is_empty(heap));
131         BLI_heap_free(heap, NULL);
132         MEM_freeN(values);
133 }
134
135 TEST(heap, Rand1)       { random_heap_helper(1, 1234); }
136 TEST(heap, Rand2)       { random_heap_helper(2, 1234); }
137 TEST(heap, Rand100)     { random_heap_helper(100, 4321); }
138
139
140 TEST(heap, ReInsertSimple)
141 {
142         const int items_total = SIZE;
143         Heap *heap = BLI_heap_new();
144         HeapNode **nodes = (HeapNode **)MEM_mallocN(sizeof(HeapNode *) * items_total, __func__);
145         for (int in = 0; in < items_total; in++) {
146                 nodes[in] = BLI_heap_insert(heap, (float)in, SET_INT_IN_POINTER(in));
147         }
148         for (int i = 0; i < items_total; i++) {
149                 BLI_heap_node_value_update(heap, nodes[i], (float)(items_total + i));
150         }
151
152         for (int out_test = 0; out_test < items_total; out_test++) {
153                 EXPECT_EQ(out_test, GET_INT_FROM_POINTER(BLI_heap_popmin(heap)));
154         }
155
156         EXPECT_TRUE(BLI_heap_is_empty(heap));
157         BLI_heap_free(heap, NULL);
158         MEM_freeN(nodes);
159 }
160
161 static void random_heap_reinsert_helper(
162         const int items_total,
163         const int random_seed)
164 {
165         Heap *heap = BLI_heap_new();
166         HeapNode **nodes = (HeapNode **)MEM_mallocN(sizeof(HeapNode *) * items_total, __func__);
167         for (int in = 0; in < items_total; in++) {
168                 nodes[in] = BLI_heap_insert(heap, (float)in, SET_INT_IN_POINTER(in));
169         }
170         BLI_array_randomize(nodes, sizeof(HeapNode *), items_total, random_seed);
171         for (int i = 0; i < items_total; i++) {
172                 BLI_heap_node_value_update(heap, nodes[i], (float)i);
173         }
174         EXPECT_TRUE(BLI_heap_is_valid(heap));
175
176         for (int out_test = 0; out_test < items_total; out_test++) {
177                 HeapNode *node_top = BLI_heap_top(heap);
178                 float out = BLI_heap_node_value(node_top);
179                 EXPECT_EQ((float)out_test, out);
180                 BLI_heap_popmin(heap);
181         }
182         EXPECT_TRUE(BLI_heap_is_empty(heap));
183         BLI_heap_free(heap, NULL);
184         MEM_freeN(nodes);
185 }
186
187 TEST(heap, ReInsertRandom1)       { random_heap_reinsert_helper(1, 1234); }
188 TEST(heap, ReInsertRandom2)       { random_heap_reinsert_helper(2, 1234); }
189 TEST(heap, ReInsertRandom100)     { random_heap_reinsert_helper(100, 4321); }
190 TEST(heap, ReInsertRandom1024)     { random_heap_reinsert_helper(1024, 9876); }
191 TEST(heap, ReInsertRandom2048)     { random_heap_reinsert_helper(2048, 5321); }