home *** CD-ROM | disk | FTP | other *** search
/ GEMini Atari / GEMini_Atari_CD-ROM_Walnut_Creek_December_1993.iso / files / gnu / g__lib / tmap.cc < prev    next >
C/C++ Source or Header  |  1993-07-23  |  6KB  |  276 lines
  1. /*
  2.  a test file for Maps
  3. */
  4.  
  5. #include <stream.h>
  6. #include <assert.h>
  7.  
  8.  
  9. #define tassert(ex) { cerr << #ex; \
  10.                        if ((ex)) cerr << " OK\n"; \
  11.                        else cerr << " Fail\n"; }
  12.  
  13. #include "int.int.Map.h"
  14.  
  15. unsigned int hash(int x) { return multiplicativehash(x) ; }
  16.  
  17. int SIZE;
  18.  
  19. int *nums;
  20. int *odds;
  21. int *perm;
  22.  
  23. void add(int x[], int y[], intintMap& a)
  24. {
  25.   for (int i = 0; i < SIZE; ++i) a[x[i]] = y[i];
  26. }
  27.  
  28. #include <MLCG.h>
  29.  
  30. MLCG randgen;
  31.  
  32. void permute(int x[])
  33. {
  34.   for (int i = 1; i < SIZE; ++i)
  35.   {
  36.     int j = randgen.asLong() % (i + 1);
  37.     int tmp = x[i]; x[i] = x[j]; x[j] = tmp;
  38.   }
  39. }
  40.  
  41. void makenums()
  42. {
  43.   for (int i = 0; i < SIZE; ++i) nums[i] = i + 1;
  44. }
  45.  
  46. void makeodds()
  47. {
  48.   for (int i = 0; i < SIZE; ++i) odds[i] = 2 * i + 1;
  49.   permute(odds);
  50. }
  51.  
  52. void makeperm()
  53. {
  54.   for (int i = 0; i < SIZE; ++i) perm[i] = i + 1;
  55.   permute(perm);
  56. }
  57.  
  58. void printMap(intintMap& a)
  59. {
  60.   int maxprint = 20;
  61.   cout << "[";
  62.   int k = 0;
  63.   for (Pix i = a.first(); i != 0 && k < maxprint; a.next(i),++k) 
  64.     cout << "(" << a.key(i) << ", " <<  a.contents(i) << ") ";
  65.   if (i != 0) cout << "...]\n";
  66.   else cout << "]\n";
  67. }
  68.  
  69. #include "int.int.SplayMap.h"
  70.  
  71. void Splaytest()
  72. {
  73.   intintSplayMap a(-1);
  74.   add(nums, perm, a);
  75.   intintSplayMap b(-1);
  76.   add(perm, nums, b);
  77.   intintSplayMap c(-1);
  78.   add(perm, odds, c); 
  79.   intintSplayMap d(a);
  80.   add(nums, nums, d);
  81.   cout << "a: "; printMap(a);
  82.   cout << "b: "; printMap(b);
  83.   cout << "c: "; printMap(c);
  84.   cout << "d: "; printMap(d);
  85.   assert(a.length() == SIZE);
  86.   assert(b.length() == SIZE);
  87.   assert(c.length() == SIZE);
  88.   assert(d.length() == SIZE);
  89.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  90.   assert(a[SIZE+1] = -1);
  91.  
  92.   for (j = 1; j <= SIZE; ++j) assert(b.contains(j));
  93.  
  94.   for (j = 1; j <= SIZE; ++j) assert(b[a[j]] == j);
  95.   for (j = 1; j <= SIZE; ++j) assert(a[b[j]] == j);
  96.  
  97.   for (j = 1; j <= SIZE; ++j) assert((c[j] & 1) != 0);
  98.  
  99.   for (j = 1; j <= SIZE; ++j) assert(d[j] == j);
  100.  
  101.   d.del(1);
  102.   assert(!d.contains(1));
  103.   for (j = 1; j <= SIZE; ++j) d.del(j);
  104.   assert(d.empty());
  105.  
  106.   assert(a.OK());
  107.   assert(b.OK());
  108.   assert(c.OK());
  109.   assert(d.OK());
  110.  
  111. }
  112.  
  113. #include "int.int.VHMap.h"
  114.  
  115. void VHtest()
  116. {
  117.   intintVHMap a(-1, SIZE);
  118.   add(nums, perm, a);
  119.   intintVHMap b(-1, SIZE);
  120.   add(perm, nums, b);
  121.   intintVHMap c(-1, SIZE);
  122.   add(perm, odds, c); 
  123.   intintVHMap d(a);
  124.   add(nums, nums, d);
  125.   cout << "a: "; printMap(a);
  126.   cout << "b: "; printMap(b);
  127.   cout << "c: "; printMap(c);
  128.   cout << "d: "; printMap(d);
  129.   assert(a.length() == SIZE);
  130.   assert(b.length() == SIZE);
  131.   assert(c.length() == SIZE);
  132.   assert(d.length() == SIZE);
  133.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  134.   assert(a[SIZE+1] = -1);
  135.  
  136.   for (j = 1; j <= SIZE; ++j) assert(b.contains(j));
  137.  
  138.   for (j = 1; j <= SIZE; ++j) assert(b[a[j]] == j);
  139.   for (j = 1; j <= SIZE; ++j) assert(a[b[j]] == j);
  140.  
  141.   for (j = 1; j <= SIZE; ++j) assert((c[j] & 1) != 0);
  142.  
  143.   for (j = 1; j <= SIZE; ++j) assert(d[j] == j);
  144.  
  145.   d.del(1);
  146.   assert(!d.contains(1));
  147.   for (j = 1; j <= SIZE; ++j) d.del(j);
  148.   assert(d.empty());
  149.  
  150.   assert(a.OK());
  151.   assert(b.OK());
  152.   assert(c.OK());
  153.   assert(d.OK());
  154.  
  155. }
  156.  
  157. #include "int.int.CHMap.h"
  158.  
  159. void CHtest()
  160. {
  161.   intintCHMap a(-1, SIZE);
  162.   add(nums, perm, a);
  163.   intintCHMap b(-1, SIZE);
  164.   add(perm, nums, b);
  165.   intintCHMap c(-1, SIZE);
  166.   add(perm, odds, c); 
  167.   intintCHMap d(a);
  168.   add(nums, nums, d);
  169.   cout << "a: "; printMap(a);
  170.   cout << "b: "; printMap(b);
  171.   cout << "c: "; printMap(c);
  172.   cout << "d: "; printMap(d);
  173.   assert(a.length() == SIZE);
  174.   assert(b.length() == SIZE);
  175.   assert(c.length() == SIZE);
  176.   assert(d.length() == SIZE);
  177.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  178.   assert(a[SIZE+1] = -1);
  179.  
  180.   for (j = 1; j <= SIZE; ++j) assert(b.contains(j));
  181.  
  182.   for (j = 1; j <= SIZE; ++j) assert(b[a[j]] == j);
  183.   for (j = 1; j <= SIZE; ++j) assert(a[b[j]] == j);
  184.  
  185.   for (j = 1; j <= SIZE; ++j) assert((c[j] & 1) != 0);
  186.  
  187.   for (j = 1; j <= SIZE; ++j) assert(d[j] == j);
  188.  
  189.   d.del(1);
  190.   assert(!d.contains(1));
  191.   for (j = 1; j <= SIZE; ++j) d.del(j);
  192.   assert(d.empty());
  193.  
  194.   assert(a.OK());
  195.   assert(b.OK());
  196.   assert(c.OK());
  197.   assert(d.OK());
  198.  
  199. }
  200.  
  201. #include "int.int.AVLMap.h"
  202.  
  203. void AVLtest()
  204. {
  205.   intintAVLMap a(-1);
  206.   add(nums, perm, a);
  207.   intintAVLMap b(-1);
  208.   add(perm, nums, b);
  209.   intintAVLMap c(-1);
  210.   add(perm, odds, c); 
  211.   intintAVLMap d(a);
  212.   add(nums, nums, d);
  213.   cout << "a: "; printMap(a);
  214.   cout << "b: "; printMap(b);
  215.   cout << "c: "; printMap(c);
  216.   cout << "d: "; printMap(d);
  217.   assert(a.length() == SIZE);
  218.   assert(b.length() == SIZE);
  219.   assert(c.length() == SIZE);
  220.   assert(d.length() == SIZE);
  221.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  222.   assert(a[SIZE+1] = -1);
  223.  
  224.   for (j = 1; j <= SIZE; ++j) assert(b.contains(j));
  225.  
  226.   for (j = 1; j <= SIZE; ++j) assert(b[a[j]] == j);
  227.   for (j = 1; j <= SIZE; ++j) assert(a[b[j]] == j);
  228.  
  229.   for (j = 1; j <= SIZE; ++j) assert((c[j] & 1) != 0);
  230.  
  231.   for (j = 1; j <= SIZE; ++j) assert(d[j] == j);
  232.  
  233.   d.del(1);
  234.   assert(!d.contains(1));
  235.   for (j = 1; j <= SIZE; ++j) d.del(j);
  236.   assert(d.empty());
  237.  
  238.   assert(a.OK());
  239.   assert(b.OK());
  240.   assert(c.OK());
  241.   assert(d.OK());
  242.  
  243. }
  244.  
  245. double return_elapsed_time ( double );
  246. double start_timer ( );
  247.  
  248. main(int argv, char** argc)
  249. {
  250.   if (argv > 1)
  251.   {
  252.     SIZE = abs(atoi(argc[1]));
  253.     SIZE &= ~1;
  254.   }
  255.   else
  256.     SIZE = 100;
  257.   nums = new int[SIZE];
  258.   odds = new int[SIZE];
  259.   perm = new int[SIZE];
  260.   makenums();
  261.   makeodds();
  262.   makeperm();
  263.   start_timer();
  264.   cout << "Splaytest\n"; Splaytest();
  265.   cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  266.   start_timer();
  267.   cout << "VHtest\n"; VHtest();
  268.   cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  269.   start_timer();
  270.   cout << "CHtest\n"; CHtest();
  271.   cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  272.   start_timer();
  273.   cout << "AVLtest\n"; AVLtest();
  274.   cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  275. }
  276.