| 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() //FTEST |
| 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() //FTEST |
| 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() //FTEST |
| 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() //FTEST |
| 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() //FTEST |
| 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 | } |