1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
|
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "pqueue.h"
#include "basic_traits.h"
typedef Int MinInt;
int MinInt_cmp(Int lhs, Int rhs) {
return -Int_cmp(lhs, rhs);
}
void MinInt_show(Int self, FILE* fp) {
Int_show(self, fp);
}
VECTOR_DEF(MinInt);
VECTOR_IMPL(MinInt);
PQUEUE_DEF(MinInt);
PQUEUE_IMPL(MinInt);
int main() {
printf("[TEST] pqueue\n");
IntPQueue pq;
IntPQueue_init(&pq);
int elems[10] = {1, 3, 2, 4, 6, 5, 9, 7, 8, 10};
for (int i = 0; i < 10; i++) {
int e = elems[i];
IntPQueue_push(&pq, e);
}
for (int i = 10; i >= 1; i--) {
int *top = IntPQueue_top(&pq);
assert(i == *top);
IntPQueue_pop(&pq);
}
assert(IntPQueue_top(&pq) == NULL);
MinIntPQueue minpq;
MinIntPQueue_init(&minpq);
for (int i = 0; i < 10; i++) {
int e = elems[i];
MinIntPQueue_push(&minpq, e);
}
for (int i = 1; i <= 10; i++) {
int *top = MinIntPQueue_top(&minpq);
assert(i == *top);
MinIntPQueue_pop(&minpq);
}
assert(MinIntPQueue_top(&minpq) == NULL);
MinIntVector_free(&minpq.vec);
int elems2[10] = {-10, -8, -7, -9, -5, -6, -4, -2, -3, -1};
int expected[10] = {-10, -8, -7, -7, -5, -5, -4, -2, -2, -1};
for (int i = 0; i < 10; i++) {
int e = elems2[i];
IntPQueue_push(&pq, e);
int *top = IntPQueue_top(&pq);
assert(*top == expected[i]);
}
IntVector_free(&pq.vec);
printf("[PASS] pqueue\n");
return 0;
}
|
