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 }