source: src/lib/util/container/avltest.cc@ 52aacc

Last change on this file since 52aacc was 5d30c1, checked in by Frederik Heber <heber@…>, 13 years ago

Initial commit based on 3.0.0alpha (here claimed as 2.4).

  • simply added all files.
  • Property mode set to 100644
File size: 13.2 KB
Line 
1//
2// avltest.h --- test program for avl maps and sets
3//
4// Copyright (C) 1996 Limit Point Systems, Inc.
5//
6// Author: Curtis Janssen <cljanss@limitpt.com>
7// Maintainer: LPS
8//
9// This file is part of the SC Toolkit.
10//
11// The SC Toolkit is free software; you can redistribute it and/or modify
12// it under the terms of the GNU Library General Public License as published by
13// the Free Software Foundation; either version 2, or (at your option)
14// any later version.
15//
16// The SC Toolkit is distributed in the hope that it will be useful,
17// but WITHOUT ANY WARRANTY; without even the implied warranty of
18// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19// GNU Library General Public License for more details.
20//
21// You should have received a copy of the GNU Library General Public License
22// along with the SC Toolkit; see the file COPYING.LIB. If not, write to
23// the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
24//
25// The U.S. Government is granted a limited license as per AL 91-7.
26//
27
28#include <iostream>
29#include <math.h>
30#include <stdlib.h>
31
32#ifdef HAVE_CONFIG_H
33#include <scconfig.h>
34#endif
35#include <util/container/eavlmmap.h>
36#include <util/container/avlmap.h>
37#include <util/container/avlset.h>
38
39using namespace std;
40using sc::AVLMap;
41using sc::AVLSet;
42using sc::EAVLMMap;
43using sc::EAVLMMapNode;
44using sc::compare;
45
46class Data {
47 public:
48 EAVLMMapNode<int,Data> map1;
49 EAVLMMapNode<int,Data> map2;
50 public:
51 Data(int k1, int k2 = 0): map1(k1), map2(k2) {};
52 void print(int indent = 0);
53 void change1(int val) { map1.key = val; }
54};
55
56void
57Data::print(int indent)
58{
59 for (int i=0; i<indent; i++) cout << " ";
60 cout << map1.key;
61}
62
63#define TEST1 1
64#define TEST2 1
65#define TEST3 1
66#define TEST4 1
67#define TEST5 1
68#define TEST6 1
69#define TEST7 1
70#define TEST8 0
71#define TEST9 0
72
73static int Ni = 0;
74static int Nr = 0;
75static int Nf = 0;
76
77void
78testmap(EAVLMMap<int, Data>& map, Data** data, int n)
79{
80 for (int i=0; i<n; i++) {
81 for (int j=0; j<n; j++) {
82 map.insert(data[j]);
83 Ni++;
84 }
85#if 0
86 if (i==0) {
87 cout << "--------------------------------------------" << endl;
88 map.check();
89 map.print2();
90 }
91 cout << "............................. removing ";
92 data[i]->print();
93 cout << endl;
94#endif
95 map.remove(data[i]);
96 Nr++;
97#if 0
98 map.print2();
99#endif
100 map.check();
101 map.clear_without_delete();
102 }
103}
104
105void
106rantest(EAVLMMap<int, Data>&map1, Data** data, int n)
107{
108 int i;
109 for (i=0; i<n; i++) {
110 Data* d = data[i];
111 d->change1(random());
112 map1.insert(d);
113 Ni++;
114 }
115 map1.check();
116 for (i=0; i<n; i++) {
117 map1.find(i);
118 Nf++;
119 }
120 for (i=0; i<n; i++) {
121 Data* d = data[i];
122 map1.remove(d);
123 Nr++;
124 }
125 map1.check();
126 map1.clear_without_delete();
127}
128
129int
130main()
131{
132 int i;
133 const int maxkey = 9;
134 EAVLMMap<int,Data> map1(&Data::map1);
135 Data* data[maxkey][maxkey];
136 Data* currentdata[maxkey];
137 for (i=0; i<maxkey; i++) {
138 for (int j=0; j<maxkey; j++) {
139 data[i][j] = new Data(j);
140 }
141 }
142 int max;
143
144 const int unique = 1;
145
146 cout << "emmap:" << endl;
147 EAVLMMap<int,Data> emap(&Data::map1);
148 for (i=0; i<maxkey; i++) {
149 emap.insert(new Data(i/2,i));
150 emap.check();
151 }
152 for (EAVLMMap<int,Data>::iterator im=emap.begin(); im!=emap.end(); im++) {
153 cout << " " << im.key() << " " << im->map2.key << endl;
154 }
155
156 cout << "map:" << endl;
157 AVLMap<int, char> icmap;
158 for (i=0; i<maxkey; i++) {
159 int d = random();
160 icmap.insert(d, i+'a');
161 icmap.insert(d, i+'a');
162 icmap.check();
163 }
164 icmap.print();
165 for (AVLMap<int,char>::iterator ic=icmap.begin(); ic!=icmap.end(); ic++) {
166 cout << " " << ic.key() << " " << ic.data() << endl;
167 }
168
169 cout << "set:" << endl;
170 AVLSet<int> iset;
171 for (i=0; i<10; i++) {
172 iset.insert(i);
173 }
174 if (iset.length() != 10) abort();
175 iset.remove(100);
176 if (iset.length() != 10) abort();
177 if (!iset.contains(3)) abort();
178 iset.remove(3);
179 if (iset.contains(3)) abort();
180 if (iset.length() != 9) abort();
181 for (i=0; i<10; i++) iset.remove(i);
182 if (iset.length() != 0) abort();
183 if (iset.contains(3)) abort();
184 if (iset.length() != 0) abort();
185 iset.clear();
186 for (i=0; i<maxkey; i++) {
187 int d = random();
188 iset.insert(d);
189 iset.insert(d);
190 iset.check();
191 }
192 iset.print();
193 for (AVLSet<int>::iterator is=iset.begin(); is!=iset.end(); is++) {
194 cout << " " << is.key() << endl;
195 }
196
197#if TEST1
198 cout << "=================================================" << endl;
199 max = 1;
200 for (i=0; i<max; i++) {
201 currentdata[0] = data[0][i];
202
203 testmap(map1, currentdata, max);
204 }
205#endif
206
207#if TEST2
208 cout << "=================================================" << endl;
209 max = 2;
210 for (i=0; i<max; i++) {
211 currentdata[0] = data[0][i];
212 for (int j=0; j<max; j++) {
213 if (unique && i == j) continue;
214 currentdata[1] = data[0][j];
215 testmap(map1, currentdata, max);
216 }
217 }
218#endif
219
220#if TEST3
221 cout << "=================================================" << endl;
222 max = 3;
223 for (i=0; i<max; i++) {
224 currentdata[0] = data[0][i];
225 for (int j=0; j<max; j++) {
226 if (unique && i == j) continue;
227 currentdata[1] = data[0][j];
228 for (int k=0; k<max; k++) {
229 if (unique && k==i || k==j) continue;
230 currentdata[2] = data[0][k];
231
232 testmap(map1, currentdata, max);
233 }
234 }
235 }
236#endif
237
238#if TEST4
239 cout << "=================================================" << endl;
240 max = 4;
241 for (i=0; i<max; i++) {
242 currentdata[0] = data[0][i];
243 for (int j=0; j<max; j++) {
244 if (unique && i == j) continue;
245 currentdata[1] = data[0][j];
246 for (int k=0; k<max; k++) {
247 if (unique && k==i || k==j) continue;
248 currentdata[2] = data[0][k];
249 for (int l=0; l<max; l++) {
250 if (unique && l==i || l==j || l==k) continue;
251 currentdata[3] = data[0][l];
252
253 testmap(map1, currentdata, max);
254 }
255 }
256 }
257 }
258#endif
259
260#if TEST5
261 cout << "=================================================" << endl;
262 max = 5;
263 for (i=0; i<max; i++) {
264 currentdata[0] = data[0][i];
265 for (int j=0; j<max; j++) {
266 if (unique && i == j) continue;
267 currentdata[1] = data[0][j];
268 for (int k=0; k<max; k++) {
269 if (unique && k==i || k==j) continue;
270 currentdata[2] = data[0][k];
271 for (int l=0; l<max; l++) {
272 if (unique && l==i || l==j || l==k) continue;
273 currentdata[3] = data[0][l];
274 for (int m=0; m<max; m++) {
275 if (unique && m==i || m==j || m==k || m==l) continue;
276 currentdata[4] = data[0][m];
277
278 testmap(map1, currentdata, max);
279 }
280 }
281 }
282 }
283 }
284#endif
285
286#if TEST6
287 cout << "=================================================" << endl;
288 max = 6;
289 for (i=0; i<max; i++) {
290 currentdata[0] = data[0][i];
291 for (int j=0; j<max; j++) {
292 if (unique && i == j) continue;
293 currentdata[1] = data[0][j];
294 cout << "6: i = " << i << " j = " << j << endl;
295 for (int k=0; k<max; k++) {
296 if (unique && k==i || k==j) continue;
297 currentdata[2] = data[0][k];
298 for (int l=0; l<max; l++) {
299 if (unique && l==i || l==j || l==k) continue;
300 currentdata[3] = data[0][l];
301 for (int m=0; m<max; m++) {
302 if (unique && m==i || m==j || m==k || m==l) continue;
303 currentdata[4] = data[0][m];
304 for (int n=0; n<max; n++) {
305 if (unique && n==i || n==j || n==k || n==l || n==m) continue;
306 currentdata[5] = data[0][n];
307
308 testmap(map1, currentdata, max);
309
310 }
311 }
312 }
313 }
314 }
315 }
316#endif
317
318#if TEST7
319 cout << "=================================================" << endl;
320 max = 7;
321 for (i=0; i<max; i++) {
322 currentdata[0] = data[0][i];
323 for (int j=0; j<max; j++) {
324 if (unique && i == j) continue;
325 currentdata[1] = data[0][j];
326 for (int k=0; k<max; k++) {
327 if (unique && k==i || k==j) continue;
328 currentdata[2] = data[0][k];
329 cout << "7: i = " << i << " j = " << j << " k = " << k << endl;
330 for (int l=0; l<max; l++) {
331 if (unique && l==i || l==j || l==k) continue;
332 currentdata[3] = data[0][l];
333 for (int m=0; m<max; m++) {
334 if (unique && m==i || m==j || m==k || m==l) continue;
335 currentdata[4] = data[0][m];
336 for (int n=0; n<max; n++) {
337 if (unique && n==i || n==j || n==k || n==l || n==m) continue;
338 currentdata[5] = data[0][n];
339 for (int o=0; o<max; o++) {
340 if (unique && o==i || o==j || o==k || o==l || o==m || o==n) continue;
341 currentdata[6] = data[0][o];
342
343 testmap(map1, currentdata, max);
344
345 }
346 }
347 }
348 }
349 }
350 }
351 }
352#endif
353
354#if TEST8
355 cout << "=================================================" << endl;
356 max = 8;
357 for (i=0; i<max; i++) {
358 currentdata[0] = data[0][i];
359 for (int j=0; j<max; j++) {
360 if (unique && i == j) continue;
361 currentdata[1] = data[0][j];
362 for (int k=0; k<max; k++) {
363 if (unique && k==i || k==j) continue;
364 currentdata[2] = data[0][k];
365 for (int l=0; l<max; l++) {
366 if (unique && l==i || l==j || l==k) continue;
367 currentdata[3] = data[0][l];
368 cout << "7: i = " << i << " j = " << j << " k = " << k
369 << " l = " << l << endl;
370 for (int m=0; m<max; m++) {
371 if (unique && m==i || m==j || m==k || m==l) continue;
372 currentdata[4] = data[0][m];
373 for (int n=0; n<max; n++) {
374 if (unique && n==i || n==j || n==k || n==l || n==m) continue;
375 currentdata[5] = data[0][n];
376 for (int o=0; o<max; o++) {
377 if (unique && o==i || o==j || o==k || o==l || o==m || o==n) continue;
378 currentdata[6] = data[0][o];
379 for (int p=0; p<max; p++) {
380 if (unique && p==i||p==j||p==k||p==l||p==m||p==n||p==o) continue;
381 currentdata[7] = data[0][p];
382
383 testmap(map1, currentdata, max);
384
385 }
386 }
387 }
388 }
389 }
390 }
391 }
392 }
393#endif
394
395#if TEST9
396 cout << "=================================================" << endl;
397 max = 9;
398 for (i=0; i<max; i++) {
399 currentdata[0] = data[0][i];
400 for (int j=0; j<max; j++) {
401 if (unique && i == j) continue;
402 currentdata[1] = data[0][j];
403 for (int k=0; k<max; k++) {
404 if (unique && k==i || k==j) continue;
405 currentdata[2] = data[0][k];
406 for (int l=0; l<max; l++) {
407 if (unique && l==i || l==j || l==k) continue;
408 currentdata[3] = data[0][l];
409 for (int m=0; m<max; m++) {
410 if (unique && m==i || m==j || m==k || m==l) continue;
411 currentdata[4] = data[0][m];
412 cout << "7: i = " << i << " j = " << j << " k = " << k
413 << " l = " << l << " m = " << m << endl;
414 for (int n=0; n<max; n++) {
415 if (unique && n==i || n==j || n==k || n==l || n==m) continue;
416 currentdata[5] = data[0][n];
417 for (int o=0; o<max; o++) {
418 if (unique && o==i || o==j || o==k || o==l || o==m || o==n) continue;
419 currentdata[6] = data[0][o];
420 for (int p=0; p<max; p++) {
421 if (unique && p==i||p==j||p==k||p==l||p==m||p==n||p==o) continue;
422 currentdata[7] = data[0][p];
423 for (int q=0; q<max; q++) {
424 if (unique && q==i||q==j||q==k||q==l||q==m||q==n||q==o||q==p) continue;
425 currentdata[8] = data[0][q];
426
427 testmap(map1, currentdata, max);
428
429 }
430 }
431 }
432 }
433 }
434 }
435 }
436 }
437 }
438#endif
439
440 cout << "Ni = " << Ni << ", Nr = " << Nr << ", N = " << Ni+Nr << endl;
441
442 const int maxdat2 = 2000;
443 Data * data2[maxdat2];
444 for (i=0; i<maxdat2; i++) {
445 data2[i] = new Data(i);
446 }
447 for (i=0; i<maxdat2; i++) {
448 if (i%100 == 0) cout << "-";
449 }
450 cout << endl;
451 for (i=0; i<maxdat2; i++) {
452 if (i%100 == 0) {
453 cout << ".";
454 }
455 rantest(map1, data2, i);
456 }
457 cout << endl;
458
459 cout << "Ni = " << Ni << ", Nr = " << Nr << ", Nf = " << Nf
460 << ", N = " << Ni+Nr << endl;
461
462 return 0;
463}
464
465#ifdef EXPLICIT_TEMPLATE_INSTANTIATION
466template class AVLMapNode<int, char>;
467template class EAVLMMap<int,AVLMapNode<int, char> >;
468template class AVLMapNode<int, int>;
469template class EAVLMMap<int,AVLMapNode<int, int> >;
470template class EAVLMMap<int, Data >;
471#endif
472
473/////////////////////////////////////////////////////////////////////////////
474
475// Local Variables:
476// mode: c++
477// c-file-style: "CLJ"
478// End:
Note: See TracBrowser for help on using the repository browser.