test/t.Heap.c

   1 #include <stdlib.h>
   2 #include "cgds/Heap.h"
   3 #include "helpers.h"
   4 #include "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 }