test/t.Heap.c

   1 #include <stdlib.h>
   2 #include "cgds/Heap.h"
   3 #include "test/helpers.h"
   4 #include "test/lut.h"
   5
   6 void t_heap_clear()
   7 {
   8     Heap* h = heap_new(int, MIN_T, 2);
   9
  10     // NOTE: items with same priorities are supported;
  11     // since it is unused in this test, we arbitrarily choose 0.0
  12     heap_insert(h, 0, 0.0);
  13     heap_insert(h, 0, 0.0);
  14     heap_insert(h, 0, 0.0);
  15
  16     heap_clear(h);
  17     lu_assert(heap_empty(h));
  18
  19     heap_destroy(h);
  20 }
  21
  22 void t_heap_size()
  23 {
  24     Heap* h = heap_new(double, MAX_T, 3);
  25
  26     heap_insert(h, 0.0, 0.0);
  27     heap_insert(h, 0.0, 0.0);
  28     heap_insert(h, 0.0, 0.0);
  29     lu_assert_int_eq(heap_size(h), 3);
  30
  31     heap_insert(h, 0.0, 0.0);
  32     heap_insert(h, 0.0, 0.0);
  33     lu_assert_int_eq(heap_size(h), 5);
  34
  35     heap_insert(h, 0.0, 0.0);
  36     heap_insert(h, 0.0, 0.0);
  37     heap_insert(h, 0.0, 0.0);
  38     lu_assert_int_eq(heap_size(h), 8);
  39
  40     heap_destroy(h);
  41 }
  42
  43 void t_heap_push_pop_basic()
  44 {
  45     Heap* h = heap_new(int, MIN_T, 3);
  46
  47     heap_insert(h, 1, 1.0);
  48     heap_insert(h, 2, 3.0);
  49     heap_insert(h, 3, 2.0);
  50     heap_insert(h, 4, 4.0);
  51     heap_insert(h, 5, 0.0);
  52
  53     int a;
  54     heap_top(h, a);
  55     lu_assert_int_eq(a, 5); //5 has "highest" priority (0.0, MIN_T)
  56     heap_pop(h);
  57     heap_top(h, a);
  58     lu_assert_int_eq(a, 1); //1 -> 1.0
  59     heap_pop(h);
  60     heap_top(h, a);
  61     lu_assert_int_eq(a, 3); //3 -> 2.0
  62     heap_pop(h);
  63     heap_top(h, a);
  64     lu_assert_int_eq(a, 2); //2 -> 3.0
  65     heap_pop(h);
  66     heap_top(h, a);
  67     lu_assert_int_eq(a, 4); //4 -> 4.0
  68     heap_pop(h);
  69     lu_assert(heap_empty(h));
  70
  71     h->hType = MAX_T; //HACK... (why not?)
  72     heap_insert(h, 1, 1.0);
  73     heap_insert(h, 2, 3.0);
  74     heap_insert(h, 3, 2.0);
  75     heap_insert(h, 4, 4.0);
  76     heap_insert(h, 5, 7.0);
  77     heap_insert(h, 6, 5.0);
  78     heap_insert(h, 7, 6.0);
  79     heap_remove(h, 4);
  80     heap_remove(h, 2);
  81     heap_modify(h, 3, 4.0);
  82     heap_modify(h, 7, 3.0);
  83
  84     heap_top(h, a);
  85     lu_assert_int_eq(a, 5); //5 has highest priority (7.0, MAX_T)
  86     heap_pop(h);
  87     heap_top(h, a);
  88     lu_assert_int_eq(a, 6); //6 -> 5.0
  89     heap_pop(h);
  90     heap_top(h, a);
  91     lu_assert_int_eq(a, 3); //3 -> 4.0
  92     heap_pop(h);
  93     heap_top(h, a);
  94     lu_assert_int_eq(a, 7); //7 -> 3.0
  95     heap_pop(h);
  96     heap_top(h, a);
  97     lu_assert_int_eq(a, 1); //1 -> 1.0
  98     heap_pop(h);
  99     lu_assert(heap_empty(h));
 100
 101     heap_destroy(h);
 102 }
 103
 104 void t_heap_push_pop_evolved()
 105 {
 106     int n = 10;
 107
 108     Heap* h = heap_new(StructTest1, MAX_T, 2);
 109     StructTest1* st1 = (StructTest1*) safe_malloc(n * sizeof (StructTest1));
 110     for (int i = n - 1; i >= 0; i--)
 111     {
 112         st1[i].a = i;
 113         st1[i].b = (double) rand() / RAND_MAX;
 114         heap_insert(h, *(st1 + i), i); //item i has value i
 115     }
 116     for (int i = n - 1; i >= 0; i--)
 117     {
 118         StructTest1 st1Cell;
 119         heap_top(h, st1Cell);
 120         lu_assert_int_eq(st1Cell.a, i);
 121         heap_pop(h);
 122     }
 123     safe_free(st1);
 124     heap_destroy(h);
 125
 126     h = heap_new(StructTest2*, MAX_T, 4);
 127     StructTest2* st2 = (StructTest2*) safe_malloc(n * sizeof (StructTest2));
 128     for (int i = n - 1; i >= 0; i--)
 129     {
 130         st2[i].a = (float) rand() / RAND_MAX;
 131         st2[i].b = (StructTest1*) safe_malloc(sizeof (StructTest1));
 132         st2[i].b->a = i;
 133         st2[i].b->b = (double) rand() / RAND_MAX;
 134         // item i has value i+1 if i is even, i-1 if i is odd
 135         // that is to say, values are 1 0 3 2 5 4 ...
 136         heap_insert(h, st2 + i, i % 2 == 0 ? i + 1 : i - 1);
 137     }
 138     for (int i = n - 1; i >= 0; i--)
 139     {
 140         StructTest2* st2Cell;
 141         heap_top(h, st2Cell);
 142         // NOTE: i |--> i%2==0 ? i+1 : i-1 is an involution
 143         lu_assert_int_eq(st2Cell->b->a, i % 2 == 0 ? i + 1 : i - 1);
 144         heap_pop(h);
 145         safe_free(st2Cell->b);
 146     }
 147     safe_free(st2);
 148     heap_destroy(h);
 149 }
 150
 151 void t_heap_copy()
 152 {
 153     int n = 10;
 154
 155     Heap* h = heap_new(int, MIN_T, 2);
 156     for (int i = 0; i < n; i++)
 157         heap_insert(h, rand() % 42, (double) rand() / RAND_MAX);
 158     Heap* hc = heap_copy(h);
 159
 160     lu_assert_int_eq(heap_size(h), heap_size(hc));
 161     int a, b;
 162     for (int i = 0; i < n; i++)
 163     {
 164         heap_top(h, a);
 165         heap_top(hc, b);
 166         lu_assert_int_eq(a, b);
 167         heap_pop(h);
 168         heap_pop(hc);
 169     }
 170     heap_destroy(h);
 171     heap_destroy(hc);
 172 }