fix typo in README
[cgds.git] / 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 }