66417e5c6941833818546edf991e561db3fb8232
[cgds.git] / 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 }