test/t.PriorityQueue.c

   1 #include <stdlib.h>
   2 #include "cgds/PriorityQueue.h"
   3 #include "test/helpers.h"
   4 #include "test/lut.h"
   5
   6 void t_priorityqueue_clear()
   7 {
   8     PriorityQueue* pq = priorityqueue_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     priorityqueue_insert(pq, 0, 0.0);
  13     priorityqueue_insert(pq, 0, 0.0);
  14     priorityqueue_insert(pq, 0, 0.0);
  15
  16     priorityqueue_clear(pq);
  17     lu_assert(priorityqueue_empty(pq));
  18
  19     priorityqueue_destroy(pq);
  20 }
  21
  22 void t_priorityqueue_size()
  23 {
  24     PriorityQueue* pq = priorityqueue_new(double, MAX_T, 3);
  25
  26     priorityqueue_insert(pq, 0.0, 0.0);
  27     priorityqueue_insert(pq, 0.0, 0.0);
  28     priorityqueue_insert(pq, 0.0, 0.0);
  29     lu_assert_int_eq(priorityqueue_size(pq), 3);
  30
  31     priorityqueue_insert(pq, 0.0, 0.0);
  32     priorityqueue_insert(pq, 0.0, 0.0);
  33     lu_assert_int_eq(priorityqueue_size(pq), 5);
  34
  35     priorityqueue_insert(pq, 0.0, 0.0);
  36     priorityqueue_insert(pq, 0.0, 0.0);
  37     priorityqueue_insert(pq, 0.0, 0.0);
  38     lu_assert_int_eq(priorityqueue_size(pq), 8);
  39
  40     priorityqueue_destroy(pq);
  41 }
  42
  43 void t_priorityqueue_push_pop_basic()
  44 {
  45     PriorityQueue* pq = priorityqueue_new(int, MIN_T, 3);
  46
  47     priorityqueue_insert(pq, 1, 1.0);
  48     priorityqueue_insert(pq, 2, 3.0);
  49     priorityqueue_insert(pq, 3, 2.0);
  50     priorityqueue_insert(pq, 4, 4.0);
  51     priorityqueue_insert(pq, 5, 0.0);
  52
  53     int a;
  54     priorityqueue_peek(pq, a);
  55     lu_assert_int_eq(a, 5); //5 has "highest" priority (0.0, MIN_T)
  56     priorityqueue_pop(pq);
  57     priorityqueue_peek(pq, a);
  58     lu_assert_int_eq(a, 1); //1 -> 1.0
  59     priorityqueue_pop(pq);
  60     priorityqueue_peek(pq, a);
  61     lu_assert_int_eq(a, 3); //3 -> 2.0
  62     priorityqueue_pop(pq);
  63     priorityqueue_peek(pq, a);
  64     lu_assert_int_eq(a, 2); //2 -> 3.0
  65     priorityqueue_pop(pq);
  66     priorityqueue_peek(pq, a);
  67     lu_assert_int_eq(a, 4); //4 -> 4.0
  68     priorityqueue_pop(pq);
  69     lu_assert(priorityqueue_empty(pq));
  70
  71     pq->heap->hType = MAX_T; //HACK... (why not?)
  72     priorityqueue_insert(pq, 1, 1.0);
  73     priorityqueue_insert(pq, 2, 3.0);
  74     priorityqueue_insert(pq, 3, 2.0);
  75     priorityqueue_insert(pq, 4, 4.0);
  76     priorityqueue_insert(pq, 5, 0.0);
  77     priorityqueue_insert(pq, 6, 0.0);
  78     priorityqueue_insert(pq, 7, 6.0);
  79     priorityqueue_remove(pq, 6);
  80     priorityqueue_remove(pq, 7);
  81     priorityqueue_set(pq, 3, 5.0);
  82     priorityqueue_set(pq, 5, 2.0);
  83
  84     priorityqueue_peek(pq, a);
  85     lu_assert_int_eq(a, 3); //3 has highest priority (5.0, MAX_T)
  86     priorityqueue_pop(pq);
  87     priorityqueue_peek(pq, a);
  88     lu_assert_int_eq(a, 4); //4 -> 4.0
  89     priorityqueue_pop(pq);
  90     priorityqueue_peek(pq, a);
  91     lu_assert_int_eq(a, 2); //2 -> 3.0
  92     priorityqueue_pop(pq);
  93     priorityqueue_peek(pq, a);
  94     lu_assert_int_eq(a, 5); //5 -> 2.0
  95     priorityqueue_pop(pq);
  96     priorityqueue_peek(pq, a);
  97     lu_assert_int_eq(a, 1); // 1 -> 1.0
  98     priorityqueue_pop(pq);
  99
 100     lu_assert(priorityqueue_empty(pq));
 101     priorityqueue_destroy(pq);
 102 }
 103
 104 void t_priorityqueue_push_pop_evolved()
 105 {
 106     int n = 10;
 107
 108     PriorityQueue* pq = priorityqueue_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         priorityqueue_insert(pq, *(st1 + i), i); //item i has priority i
 115     }
 116     for (int i = n - 1; i >= 0; i--)
 117     {
 118         StructTest1 st1Cell;
 119         priorityqueue_peek(pq, st1Cell);
 120         lu_assert_int_eq(st1Cell.a, i);
 121         priorityqueue_pop(pq);
 122     }
 123     safe_free(st1);
 124     priorityqueue_destroy(pq);
 125
 126     pq = priorityqueue_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 priority i+1 if i is even, i-1 if i is odd
 135         // that is to say, priorities are 1 0 3 2 5 4 ...
 136         priorityqueue_insert(pq, st2 + i, i % 2 == 0 ? i + 1 : i - 1);
 137     }
 138     for (int i = n - 1; i >= 0; i--)
 139     {
 140         StructTest2* st2Cell;
 141         priorityqueue_peek(pq, 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         priorityqueue_pop(pq);
 145         safe_free(st2Cell->b);
 146     }
 147     safe_free(st2);
 148     priorityqueue_destroy(pq);
 149 }
 150
 151 void t_priorityqueue_copy()
 152 {
 153     int n = 10;
 154
 155     PriorityQueue* pq = priorityqueue_new(int, MIN_T, 3);
 156     for (int i = 0; i < n; i++)
 157         priorityqueue_insert(pq, rand() % 42, (double) rand() / RAND_MAX);
 158     PriorityQueue* pqc = priorityqueue_copy(pq);
 159
 160     lu_assert_int_eq(priorityqueue_size(pq), priorityqueue_size(pqc));
 161     int a, b;
 162     for (int i = 0; i < n; i++)
 163     {
 164         priorityqueue_peek(pq, a);
 165         priorityqueue_peek(pqc, b);
 166         lu_assert_int_eq(a, b);
 167         priorityqueue_pop(pq);
 168         priorityqueue_pop(pqc);
 169     }
 170     priorityqueue_destroy(pq);
 171     priorityqueue_destroy(pqc);
 172 }