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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
|
#include <stdio.h>
#include <stdlib.h>
#include "config.h"
#include "BHeap.h"
#include "FHeap.h"
#include "BinHeap.h"
#include "PLList.h"
char N[] = {
5, 9, 10, 29, 6, 1, 15, 18, 25, 11,
2, 14, 23, 16, 17, 3, 8, 24, 20, 13,
30, 21, 26, 4, 7, 28, 12, 27, 19, 22,
};
void exception(int e, char *msg)
{
fprintf(stderr, "%s\n", msg);
exit(-1);
}
PriorityList *newlist(void)
{
return new FHeap;
}
void DoCombTest(int number)
{
int i, n;
Key_t K, oK;
Datas_t Datas;
PriorityList *T;
cerr << _("Creation of a priority list and adding ") << number << _(" random entrie(s)...");
T = newlist();
for (i = 1; i <= number; i++) {
T->Insert(rand() % P_INFINITY, NULL);
}
cerr << _("Ok.\nDeleting the list...");
oK = P_INFINITY;
for (i = number; i >= 1; i--) {
if (T->n() != i) {
cerr << _("List has ") << T->n() << _(" keys. Expecting ") << i << endl;
exception(1, _("List corrupted."));
}
if ((n = T->rn()) != i) {
cerr << _("List has ") << T->rn() << _(" keys (real count). Expecting ") << i << endl;
exception(1, _("List corrupted."));
}
K = T->Extract_Min(Datas);
if (oK < K)
exception(1, _("Incorrect order."));
}
delete T;
cerr << "Ok.\n";
}
void FullTest(void)
{
PriorityList *T;
Datas_t Datas;
Cell C1, C2;
Key_t K;
int i;
cerr << _("Size of a PriorityList cell: ") << sizeof(PriorityList) << endl;
cerr << _("Size of a BHeap cell : ") << sizeof(BHeap) << endl;
cerr << _("Size of a FHeap cell : ") << sizeof(FHeap) << endl;
cerr << _("Size of a PLList header : ") << sizeof(PLList) << endl;
cerr << _("Size of a CList cell : ") << sizeof(CList) << endl;
cerr << _("Size of a SList cell : ") << sizeof(SList) << endl;
cerr << _("Size of a BinHeap header : ") << sizeof(BinHeap) << endl;
cerr << _("Size of a BinHeap cell : ") << sizeof(binheap_t) << endl;
DoCombTest(0);
DoCombTest(10);
DoCombTest(70);
DoCombTest(1000);
DoCombTest(10000);
#ifdef BT
DoCombTest(100000);
#ifdef VBT
DoCombTest(1000000);
#endif
#endif
cerr << _("Creating a priority list and adding keys:\n");
T = newlist();
for (i = 0; i < 30; i++) {
fprintf(stderr, "%i ", N[i]);
T->Insert(N[i], NULL);
}
fprintf(stderr, "59 54 -10\n");
C1 = T->Insert(59, NULL);
C2 = T->Insert(54, NULL);
T->Insert(-10, NULL);
cerr << _("Ok.\nList browsing...\n");
T->Dump(cerr);
cerr << _("Ok.\nExtract_Min + List browsing...\n");
cerr << T->Extract_Min(Datas) << endl;
T->Dump(cerr);
cerr << _("Ok.\nLower_Key(-12) over 59...\n");
T->Lower_Key(C1, -12);
cerr << _("Ok.\nList browsing...\n");
T->Dump(cerr);
cerr << _("Ok.\nDelete over 54...\n");
T->Delete(Datas, C2);
cerr << _("Ok.\nList browsing...\n");
T->Dump(cerr);
cerr << "Ok.\nExtract_Min...\n";
cerr << T->Extract_Min(Datas) << endl;
cerr << _("Ok.\nExtracting datas...\n");
for (i = 1; i <= 30; i++) {
cerr << _("Minimum #") << i << " = " << (K = (T->Extract_Min(Datas)))
<< endl;
if (K != i)
exception(1, _("Incorrect order."));
}
cerr << _("Ok.\n\nAll the tests were successfull\n");
return;
}
int main(int argc, char **argv)
{
FullTest();
}
|
