Merge branch 'master' into blender2.8
[blender.git] / tests / gtests / blenlib / BLI_heap_simple_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_simple.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, SimpleEmpty)
28 {
29         HeapSimple *heap;
30
31         heap = BLI_heapsimple_new();
32         EXPECT_TRUE(BLI_heapsimple_is_empty(heap));
33         EXPECT_EQ(BLI_heapsimple_len(heap), 0);
34         BLI_heapsimple_free(heap, NULL);
35 }
36
37 TEST(heap, SimpleOne)
38 {
39         HeapSimple *heap;
40         const char *in = "test";
41
42         heap = BLI_heapsimple_new();
43
44         BLI_heapsimple_insert(heap, 0.0f, (void *)in);
45         EXPECT_FALSE(BLI_heapsimple_is_empty(heap));
46         EXPECT_EQ(BLI_heapsimple_len(heap), 1);
47         EXPECT_EQ(in, BLI_heapsimple_pop_min(heap));
48         EXPECT_TRUE(BLI_heapsimple_is_empty(heap));
49         EXPECT_EQ(BLI_heapsimple_len(heap), 0);
50         BLI_heapsimple_free(heap, NULL);
51 }
52
53 TEST(heap, SimpleRange)
54 {
55         const int items_total = SIZE;
56         HeapSimple *heap = BLI_heapsimple_new();
57         for (int in = 0; in < items_total; in++) {
58                 BLI_heapsimple_insert(heap, (float)in, POINTER_FROM_INT(in));
59         }
60         for (int out_test = 0; out_test < items_total; out_test++) {
61                 EXPECT_EQ(out_test, POINTER_AS_INT(BLI_heapsimple_pop_min(heap)));
62
63         }
64         EXPECT_TRUE(BLI_heapsimple_is_empty(heap));
65         BLI_heapsimple_free(heap, NULL);
66 }
67
68 TEST(heap, SimpleRangeReverse)
69 {
70         const int items_total = SIZE;
71         HeapSimple *heap = BLI_heapsimple_new();
72         for (int in = 0; in < items_total; in++) {
73                 BLI_heapsimple_insert(heap, (float)-in, POINTER_FROM_INT(-in));
74         }
75         for (int out_test = items_total - 1; out_test >= 0; out_test--) {
76                 EXPECT_EQ(-out_test, POINTER_AS_INT(BLI_heapsimple_pop_min(heap)));
77         }
78         EXPECT_TRUE(BLI_heapsimple_is_empty(heap));
79         BLI_heapsimple_free(heap, NULL);
80 }
81
82 TEST(heap, SimpleDuplicates)
83 {
84         const int items_total = SIZE;
85         HeapSimple *heap = BLI_heapsimple_new();
86         for (int in = 0; in < items_total; in++) {
87                 BLI_heapsimple_insert(heap, 1.0f, 0);
88         }
89         for (int out_test = 0; out_test < items_total; out_test++) {
90                 EXPECT_EQ(0, POINTER_AS_INT(BLI_heapsimple_pop_min(heap)));
91         }
92         EXPECT_TRUE(BLI_heapsimple_is_empty(heap));
93         BLI_heapsimple_free(heap, NULL);
94 }
95
96 static void random_heapsimple_helper(
97         const int items_total,
98         const int random_seed)
99 {
100         HeapSimple *heap = BLI_heapsimple_new();
101         float *values = (float *)MEM_mallocN(sizeof(float) * items_total, __func__);
102         range_fl(values, items_total);
103         BLI_array_randomize(values, sizeof(float), items_total, random_seed);
104         for (int i = 0; i < items_total; i++) {
105                 BLI_heapsimple_insert(heap, values[i], POINTER_FROM_INT((int)values[i]));
106         }
107         for (int out_test = 0; out_test < items_total; out_test++) {
108                 EXPECT_EQ(out_test, POINTER_AS_INT(BLI_heapsimple_pop_min(heap)));
109         }
110         EXPECT_TRUE(BLI_heapsimple_is_empty(heap));
111         BLI_heapsimple_free(heap, NULL);
112         MEM_freeN(values);
113 }
114
115 TEST(heap, SimpleRand1)       { random_heapsimple_helper(1, 1234); }
116 TEST(heap, SimpleRand2)       { random_heapsimple_helper(2, 1234); }
117 TEST(heap, SimpleRand100)     { random_heapsimple_helper(100, 4321); }