home *** CD-ROM | disk | FTP | other *** search
/ GEMini Atari / GEMini_Atari_CD-ROM_Walnut_Creek_December_1993.iso / files / gnu / g__lib / tbag.cc < prev    next >
C/C++ Source or Header  |  1993-07-23  |  9KB  |  348 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. #include "int.XPBag.h"
  96.  
  97. void XPtest()
  98. {
  99.   intXPBag a(SIZE);
  100.   add(nums, a);
  101.   assert(a.length() == SIZE);
  102.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  103.   intXPBag b(SIZE);
  104.   add(odds, b);
  105.   assert(b.length() == SIZE);
  106.   intXPBag c(SIZE);
  107.   add(dups, c); 
  108.   assert(c.length() == SIZE);
  109.   intXPBag d(a);
  110.   add(nums, d);
  111.   assert(d.length() == SIZE*2);
  112.   cout << "a: "; printBag(a);
  113.   cout << "b: "; printBag(b);
  114.   cout << "c: "; printBag(c);
  115.   cout << "d: "; printBag(d);
  116.   for (j = 1; j <= SIZE; ++j) assert(d.nof(j) == 2);
  117.   d.del(1);
  118.   assert(d.nof(1) == 1);
  119.   d.del(1);
  120.   assert(d.nof(1) == 0);
  121.   d.remove(2);
  122.   assert(!d.contains(2));
  123.   for (Pix l = c.first(); l; c.next(l)) d.remove(c(l));
  124.   assert(d.length() == SIZE);
  125.   
  126.   c.clear();
  127.   assert(c.empty());
  128.   for (Pix k = a.first(); k != 0; a.next(k)) c.add(a(k));
  129.   for (k = a.first(); k != 0; a.next(k)) assert(c.contains(a(k)));
  130.   c.del(a(a.first()));
  131.   Pix i = a.first();
  132.   assert(!c.contains(a(i)));
  133.   for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
  134.   c.add(a(a.first()));
  135.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  136.   for (k = b.first(); k != 0; b.next(k)) c.add(b(k));
  137.   for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
  138.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  139.   for (k = a.first(); k != 0; a.next(k)) c.remove(a(k));
  140.   for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
  141.   for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
  142.   assert(c.empty);
  143.   assert(a.OK());
  144.   assert(b.OK());
  145.   assert(c.OK());
  146.  
  147.   generictest(a, b, c);
  148. }
  149.  
  150.  
  151. #include "int.SLBag.h"
  152.  
  153. void SLtest()
  154. {
  155.   intSLBag a;
  156.   add(nums, a);
  157.   assert(a.length() == SIZE);
  158.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  159.   intSLBag b;
  160.   add(odds, b);
  161.   assert(b.length() == SIZE);
  162.   intSLBag c;
  163.   add(dups, c); 
  164.   assert(c.length() == SIZE);
  165.   intSLBag d(a);
  166.   add(nums, d);
  167.   assert(d.length() == SIZE*2);
  168.   cout << "a: "; printBag(a);
  169.   cout << "b: "; printBag(b);
  170.   cout << "c: "; printBag(c);
  171.   cout << "d: "; printBag(d);
  172.   for (j = 1; j <= SIZE; ++j) assert(d.nof(j) == 2);
  173.   d.del(1);
  174.   assert(d.nof(1) == 1);
  175.   d.del(1);
  176.   assert(d.nof(1) == 0);
  177.   d.remove(2);
  178.   assert(!d.contains(2));
  179.   for (Pix l = c.first(); l; c.next(l)) d.remove(c(l));
  180.   assert(d.length() == SIZE);
  181.   
  182.   c.clear();
  183.   assert(c.empty());
  184.   for (Pix k = a.first(); k != 0; a.next(k)) c.add(a(k));
  185.   for (k = a.first(); k != 0; a.next(k)) assert(c.contains(a(k)));
  186.   c.del(a(a.first()));
  187.   Pix i = a.first();
  188.   assert(!c.contains(a(i)));
  189.   for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
  190.   c.add(a(a.first()));
  191.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  192.   for (k = b.first(); k != 0; b.next(k)) c.add(b(k));
  193.   for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
  194.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  195.   for (k = a.first(); k != 0; a.next(k)) c.remove(a(k));
  196.   for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
  197.   for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
  198.   assert(c.empty);
  199.   assert(a.OK());
  200.   assert(b.OK());
  201.   assert(c.OK());
  202.  
  203.   generictest(a, b, c);
  204. }
  205.  
  206.  
  207. #include "int.VHBag.h"
  208.  
  209. void VHtest()
  210. {
  211.   intVHBag a(SIZE);
  212.   add(nums, a);
  213.   assert(a.length() == SIZE);
  214.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  215.   intVHBag b(SIZE);
  216.   add(odds, b);
  217.   assert(b.length() == SIZE);
  218.   intVHBag c(SIZE);
  219.   add(dups, c); 
  220.   assert(c.length() == SIZE);
  221.   intVHBag 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. #include "int.CHBag.h"
  263.  
  264. void CHtest()
  265. {
  266.   intCHBag a(SIZE);
  267.   add(nums, a);
  268.   assert(a.length() == SIZE);
  269.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  270.   intCHBag b(SIZE);
  271.   add(odds, b);
  272.   assert(b.length() == SIZE);
  273.   intCHBag c(SIZE);
  274.   add(dups, c); 
  275.   assert(c.length() == SIZE);
  276.   intCHBag d(a);
  277.   add(nums, d);
  278.   assert(d.length() == SIZE*2);
  279.   cout << "a: "; printBag(a);
  280.   cout << "b: "; printBag(b);
  281.   cout << "c: "; printBag(c);
  282.   cout << "d: "; printBag(d);
  283.   for (j = 1; j <= SIZE; ++j) assert(d.nof(j) == 2);
  284.   d.del(1);
  285.   assert(d.nof(1) == 1);
  286.   d.del(1);
  287.   assert(d.nof(1) == 0);
  288.   d.remove(2);
  289.   assert(!d.contains(2));
  290.   for (Pix l = c.first(); l; c.next(l)) d.remove(c(l));
  291.   assert(d.length() == SIZE);
  292.   
  293.   c.clear();
  294.   assert(c.empty());
  295.   for (Pix k = a.first(); k != 0; a.next(k)) c.add(a(k));
  296.   for (k = a.first(); k != 0; a.next(k)) assert(c.contains(a(k)));
  297.   c.del(a(a.first()));
  298.   Pix i = a.first();
  299.   assert(!c.contains(a(i)));
  300.   for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
  301.   c.add(a(a.first()));
  302.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  303.   for (k = b.first(); k != 0; b.next(k)) c.add(b(k));
  304.   for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
  305.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  306.   for (k = a.first(); k != 0; a.next(k)) c.remove(a(k));
  307.   for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
  308.   for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
  309.   assert(c.empty);
  310.   assert(a.OK());
  311.   assert(b.OK());
  312.   assert(c.OK());
  313.  
  314.   generictest(a, b, c);
  315. }
  316.  
  317. double return_elapsed_time ( double );
  318. double start_timer ( void );
  319.  
  320. main(int argv, char** argc)
  321. {
  322.   if (argv > 1)
  323.   {
  324.     SIZE = abs(atoi(argc[1]));
  325.     SIZE &= ~1;
  326.   }
  327.   else
  328.     SIZE = 100;
  329.   nums = new int[SIZE];
  330.   odds = new int[SIZE];
  331.   dups = new int[SIZE];
  332.   makenums();
  333.   makeodds();
  334.   makedups();
  335.   start_timer();
  336.   cout << "VHtest\n"; VHtest();
  337.   cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  338.   start_timer();
  339.   cout << "CHtest\n"; CHtest();
  340.   cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  341.   start_timer();
  342.   cout << "SLtest\n"; SLtest();
  343.   cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  344.   start_timer();
  345.   cout << "XPtest\n"; XPtest();
  346.   cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  347. }
  348.