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