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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
|
/*
file: ttest.cc
*/
#include "ttest.h"
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define LUNG 5000
static int V[LUNG];
static char buff[128];
typedef VDKBtree<int> intbt;
typedef VDKValueList<int> intlist;
////////////////////////////////////////
DEFINE_SIGNAL_LIST(BTreeWindow,VDKForm);
///////////////////////////////////
int main (int argc, char *argv[])
{
MyApp app(&argc, argv);
app.Run();
return 0;
}
//////////////////////////////////
/*
*/
void
BTreeWindow::Setup()
{
text = new VDKTextView(this);
text->Font = new VDKFont(this,"Courier Medium 12");
Add(text);
sprintf(buff,"Tests with %d <int> nodes",LUNG);
VDKBox* hbox = new VDKBox(this,h_box);
hbox->Add(start = new VDKCustomButton(this,buff));
hbox->Add(showsource = new VDKCustomButton(this,"Show source"));
hbox->Add(quit = new VDKCustomButton(this,"Quit"));
Add(hbox,l_justify,false,false,false);
SetUsize(VDKPoint(450,400));
SignalConnect(start,"clicked",&BTreeWindow::Start);
SignalConnect(showsource,"clicked",&BTreeWindow::ShowSource);
SignalConnect(quit,"clicked",&BTreeWindow::Quit);
}
/*
*/
bool
BTreeWindow::ShowSource(VDKObject*)
{
text->Clear();
text->LoadFromFile("ttest.cc");
return true;
}
/*
*/
bool
BTreeWindow::Start(VDKObject*)
{
intbt btree;
intlist list;
// random initialize vector
int t;
text->Clear();
srand(time(NULL));
text->TextInsert("\n** TEST BEGINS **");
sprintf(buff,"\nRandom initializing %d nodes",LUNG);
text->TextInsert(buff);
for (t=0;t<LUNG;t++)
V[t]=random()%100;
// add nodes to btree
sprintf(buff,"\nadding %d nodes to btree...",LUNG);
text->TextInsert(buff);
for (t=0;t<LUNG;t++)
btree.add(V[t]);
sprintf(buff,"\n\ttree size:%u",btree.size());
text->TextInsert(buff);
// add items to list
sprintf(buff,"\nadding %d sorted items to list...",LUNG);
text->TextInsert(buff);
for (t=0;t<LUNG;t++)
list.insert(V[t]);
sprintf(buff,"\n\tlist size:%u",list.size());
text->TextInsert(buff);
// makes an heap using vector
text->TextInsert("\nmaking an heap & sorting...");
VDKHeap<int> heap(V,LUNG);
heap.Sort();
text->TextInsert("\n\tdone.");
// checks tree vs heap
// if all tree nodes match heap nodes
text->TextInsert("\nchecking tree vs heap...");
// make a btree iterator
// iterator begins from lowest key
intbt::Iterator iter(btree,BtMinKey);
for(t=0; (t < heap.size()) && iter;t++,iter++)
{
if( (iter.current() != heap[t]))
{
text->TextInsert("\nbad tree construct");
break;
}
}
// if loop was broken before match not found
if(t<heap.size())
text->TextInsert("\n\tbtree test break before end");
else
text->TextInsert("\n\tdone, btree and heap match");
// checks list vs heap
text->TextInsert("\nchecking list vs heap...");
// makes a list iterator
// iterator begins from list head
VDKValueListIterator<int> liter(list);
for(t=0; (t < heap.size()) && liter;t++,liter++)
{
if(liter.current() != heap[t] )
{
text->TextInsert("\n\tbad list construct");
break;
}
}
if(t < heap.size())
text->TextInsert("\n\tlist test break before end");
else
text->TextInsert("\n\tdone, list and heap match");
// test search on Btree
text->TextInsert("\nSearch test on btree:");
for(t=0; t < heap.size() ;t++)
{
if(! btree.find(heap[t]) )
break;
}
if(t < heap.size())
text->TextInsert("\n\ttest break before end");
else
text->TextInsert("\n\tdone, test ok");
// tests search on List
text->TextInsert("\nSearch test on list:");
for(t=0; t < heap.size();t++)
{
if(! list.find(heap[t]) )
break;
}
if(t < heap.size())
text->TextInsert("\n\ttest break before end");
else
text->TextInsert("\n\tdone, test ok");
// removes all keys from Btree
text->TextInsert("\nRemoving all nodes from btree:");
for(t=0; t < heap.size();t++)
btree.unlink(heap[t]);
// should be 0
sprintf(buff,"\n\ttree size:%d",btree.size());
text->TextInsert(buff);
// removes all keys from list
text->TextInsert("\nRemoving all items from list:");
for(t=0; t < heap.size();t++)
{
// finds heap[t] ordinal position into list
int pos = list.at(heap[t]);
// if at() fails returns -1
if(pos >= 0)
list.unlink(pos);
}
sprintf(buff,"\n\tlist size:%d",list.size());
text->TextInsert(buff);
text->TextInsert("\n** TEST END **");
return true;
}
|
