5d4edc80f71f1e2ba13a6a73ff900a984a4380b8
8 Heap
* h
= heap_new(int, MIN_T
, 2);
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);
17 lu_assert(heap_empty(h
));
24 Heap
* h
= heap_new(double, MAX_T
, 3);
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);
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);
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);
43 void t_heap_push_pop_basic()
45 Heap
* h
= heap_new(int, MIN_T
, 3);
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);
55 lu_assert_int_eq(a
, 5); //5 has "highest" priority (0.0, MIN_T)
58 lu_assert_int_eq(a
, 1); //1 -> 1.0
61 lu_assert_int_eq(a
, 3); //3 -> 2.0
64 lu_assert_int_eq(a
, 2); //2 -> 3.0
67 lu_assert_int_eq(a
, 4); //4 -> 4.0
69 lu_assert(heap_empty(h
));
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);
81 heap_modify(h
, 3, 4.0);
82 heap_modify(h
, 7, 3.0);
85 lu_assert_int_eq(a
, 5); //5 has highest priority (7.0, MAX_T)
88 lu_assert_int_eq(a
, 6); //6 -> 5.0
91 lu_assert_int_eq(a
, 3); //3 -> 4.0
94 lu_assert_int_eq(a
, 7); //7 -> 3.0
97 lu_assert_int_eq(a
, 1); //1 -> 1.0
99 lu_assert(heap_empty(h
));
104 void t_heap_push_pop_evolved()
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
--)
113 st1
[i
].b
= (double) rand() / RAND_MAX
;
114 heap_insert(h
, *(st1
+ i
), i
); //item i has value i
116 for (int i
= n
- 1; i
>= 0; i
--)
119 heap_top(h
, st1Cell
);
120 lu_assert_int_eq(st1Cell
.a
, i
);
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
--)
130 st2
[i
].a
= (float) rand() / RAND_MAX
;
131 st2
[i
].b
= (StructTest1
*) safe_malloc(sizeof (StructTest1
));
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);
138 for (int i
= n
- 1; i
>= 0; i
--)
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);
145 safe_free(st2Cell
->b
);
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
);
160 lu_assert_int_eq(heap_size(h
), heap_size(hc
));
162 for (int i
= 0; i
< n
; i
++)
166 lu_assert_int_eq(a
, b
);