home *** CD-ROM | disk | FTP | other *** search
/ GEMini Atari / GEMini_Atari_CD-ROM_Walnut_Creek_December_1993.iso / files / gnu / g__lib / tset.cc < prev    next >
Encoding:
C/C++ Source or Header  |  1993-07-23  |  9.9 KB  |  425 lines
  1. /*
  2.  a test file for sets
  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. unsigned int hash(int x) { return multiplicativehash(x) ; }
  14.  
  15. #include "int.Set.h"
  16.  
  17. int SIZE;
  18.  
  19. int *nums;
  20. int *odds;
  21. int *dups;
  22.  
  23. void printset(intSet& a)
  24. {
  25.   int maxprint = 20;
  26.   cout << "[";
  27.   int k = 0;
  28.   for (Pix i = a.first(); i != 0 && k < maxprint; a.next(i),++k) 
  29.     cout << a(i) << " ";
  30.   if (i != 0) cout << "...]\n";
  31.   else cout << "]\n";
  32. }
  33.  
  34. void add(int x[], intSet& a)
  35. {
  36.   for (int i = 0; i < SIZE; ++i) a.add(x[i]);
  37. }
  38.  
  39. #include <MLCG.h>
  40.  
  41. MLCG randgen;
  42.  
  43. void permute(int x[])
  44. {
  45.   for (int i = 1; i < SIZE; ++i)
  46.   {
  47.     int j = randgen.asLong() % (i + 1);
  48.     int tmp = x[i]; x[i] = x[j]; x[j] = tmp;
  49.   }
  50. }
  51.  
  52.  
  53. void makenums()
  54. {
  55.   for (int i = 0; i < SIZE; ++i) nums[i] = i + 1; 
  56. }
  57.  
  58. void makeodds()
  59. {
  60.   for (int i = 0; i < SIZE; ++i) odds[i] = 2 * i + 1;
  61.   permute(odds);
  62. }
  63.  
  64. void makedups()
  65. {
  66.   for (int i = 0; i < SIZE; i += 2) dups[i] = dups[i+1] = i/2 + 1;
  67.   permute(dups);
  68. }
  69.                
  70.  
  71. void generictest(intSet& a, intSet& b, intSet& c)
  72. {
  73.   c.clear();
  74.   assert(c.empty());
  75.   c |= a;
  76.   assert(c == a);
  77.   assert(c <= a);
  78.   c.del(a(a.first()));
  79.   assert(c <= a);
  80.   assert(c != a);
  81.   Pix i = a.first();
  82.   assert(!c.contains(a(i)));
  83.   for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
  84.   c.add(a(a.first()));
  85.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  86.   c |= b;
  87.   assert(b <= c);
  88.   for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
  89.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  90.   c &= a;
  91.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  92.   c -= a;
  93.   assert(!(a <= c));
  94.   for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
  95.   for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
  96.   assert(c.empty());
  97.   assert(a.OK());
  98.   assert(b.OK());
  99.   assert(c.OK());
  100. }
  101.  
  102. #include "int.XPSet.h"
  103.  
  104. void XPtest()
  105. {
  106.   intXPSet a(SIZE);
  107.   add(nums, a);
  108.   assert(a.length() == SIZE);
  109.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  110.   intXPSet b(SIZE);
  111.   add(odds, b);
  112.   assert(b.length() == SIZE);
  113.   intXPSet c(SIZE);
  114.   add(dups, c); 
  115.   assert(c.length() == SIZE/2);
  116.   assert(c <= a);
  117.   intXPSet d(a);
  118.   d &= b;
  119.   cout << "a: "; printset(a);
  120.   cout << "b: "; printset(b);
  121.   cout << "c: "; printset(c);
  122.   cout << "d: "; printset(d);
  123.   assert(d.length() == SIZE/2);
  124.   for (Pix p = d.first(); p; d.next(p)) assert((d(p) & 1) != 0);
  125.   a.del(1);
  126.   assert(a.length() == SIZE-1);
  127.   assert(!a.contains(1));
  128.  
  129.   c.clear();
  130.   assert(c.empty());
  131.   c |= a;
  132.   assert(c == a);
  133.   assert(c <= a);
  134.   c.del(a(a.first()));
  135.   assert(c <= a);
  136.   assert(c != a);
  137.   Pix i = a.first();
  138.   assert(!c.contains(a(i)));
  139.   for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
  140.   c.add(a(a.first()));
  141.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  142.   c |= b;
  143.   assert(b <= c);
  144.   for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
  145.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  146.   c &= a;
  147.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  148.   c -= a;
  149.   assert(!(a <= c));
  150.   for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
  151.   for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
  152.   assert(c.empty());
  153.   assert(a.OK());
  154.   assert(b.OK());
  155.   assert(c.OK());
  156.  
  157.   generictest(a, b, c);
  158. }
  159.  
  160.  
  161. #include "int.SLSet.h"
  162.  
  163. void SLtest()
  164. {
  165.   intSLSet a;
  166.   add(nums, a);
  167.   assert(a.length() == SIZE);
  168.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  169.   intSLSet b;
  170.   add(odds, b);
  171.   assert(b.length() == SIZE);
  172.   intSLSet c;
  173.   add(dups, c); 
  174.   assert(c.length() == SIZE/2);
  175.   assert(c <= a);
  176.   intSLSet d(a);
  177.   d &= b;
  178.   cout << "a: "; printset(a);
  179.   cout << "b: "; printset(b);
  180.   cout << "c: "; printset(c);
  181.   cout << "d: "; printset(d);
  182.   assert(d.length() == SIZE/2);
  183.   for (Pix p = d.first(); p; d.next(p)) assert((d(p) & 1) != 0);
  184.   a.del(1);
  185.   assert(a.length() == SIZE-1);
  186.   assert(!a.contains(1));
  187.  
  188.   c.clear();
  189.   assert(c.empty());
  190.   c |= a;
  191.   assert(c == a);
  192.   assert(c <= a);
  193.   c.del(a(a.first()));
  194.   assert(c <= a);
  195.   assert(c != a);
  196.   Pix i = a.first();
  197.   assert(!c.contains(a(i)));
  198.   for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
  199.   c.add(a(a.first()));
  200.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  201.   c |= b;
  202.   assert(b <= c);
  203.   for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
  204.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  205.   c &= a;
  206.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  207.   c -= a;
  208.   assert(!(a <= c));
  209.   for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
  210.   for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
  211.   assert(c.empty());
  212.   assert(a.OK());
  213.   assert(b.OK());
  214.   assert(c.OK());
  215.  
  216.   generictest(a, b, c);
  217. }
  218.  
  219.  
  220. #include "int.VHSet.h"
  221.  
  222. void VHtest()
  223. {
  224.   intVHSet a(SIZE);
  225.   add(nums, a);
  226.   assert(a.length() == SIZE);
  227.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  228.   intVHSet b(SIZE);
  229.   add(odds, b);
  230.   assert(b.length() == SIZE);
  231.   intVHSet c(SIZE);
  232.   add(dups, c); 
  233.   assert(c.length() == SIZE/2);
  234.   assert(c <= a);
  235.   intVHSet d(a);
  236.   d &= b;
  237.   cout << "a: "; printset(a);
  238.   cout << "b: "; printset(b);
  239.   cout << "c: "; printset(c);
  240.   cout << "d: "; printset(d);
  241.   assert(d.length() == SIZE/2);
  242.   for (Pix p = d.first(); p; d.next(p)) assert((d(p) & 1) != 0);
  243.   a.del(1);
  244.   assert(a.length() == SIZE-1);
  245.   assert(!a.contains(1));
  246.  
  247.   c.clear();
  248.   assert(c.empty());
  249.   c |= a;
  250.   assert(c == a);
  251.   assert(c <= a);
  252.   c.del(a(a.first()));
  253.   assert(c <= a);
  254.   assert(c != a);
  255.   Pix i = a.first();
  256.   assert(!c.contains(a(i)));
  257.   for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
  258.   c.add(a(a.first()));
  259.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  260.   c |= b;
  261.   assert(b <= c);
  262.   for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
  263.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  264.   c &= a;
  265.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  266.   c -= a;
  267.   assert(!(a <= c));
  268.   for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
  269.   for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
  270.   assert(c.empty());
  271.   assert(a.OK());
  272.   assert(b.OK());
  273.   assert(c.OK());
  274.  
  275.   generictest(a, b, c);
  276. }
  277.  
  278. #include "int.VOHSet.h"
  279.  
  280. void VOHtest()
  281. {
  282.   intVOHSet a(SIZE);
  283.   add(nums, a);
  284.   assert(a.length() == SIZE);
  285.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  286.   intVOHSet b(SIZE);
  287.   add(odds, b);
  288.   assert(b.length() == SIZE);
  289.   intVOHSet c(SIZE);
  290.   add(dups, c); 
  291.   assert(c.length() == SIZE/2);
  292.   assert(c <= a);
  293.   intVOHSet d(a);
  294.   d &= b;
  295.   cout << "a: "; printset(a);
  296.   cout << "b: "; printset(b);
  297.   cout << "c: "; printset(c);
  298.   cout << "d: "; printset(d);
  299.   assert(d.length() == SIZE/2);
  300.   for (Pix p = d.first(); p; d.next(p)) assert((d(p) & 1) != 0);
  301.   a.del(1);
  302.   assert(a.length() == SIZE-1);
  303.   assert(!a.contains(1));
  304.  
  305.   c.clear();
  306.   assert(c.empty());
  307.   c |= a;
  308.   assert(c == a);
  309.   assert(c <= a);
  310.   c.del(a(a.first()));
  311.   assert(c <= a);
  312.   assert(c != a);
  313.   Pix i = a.first();
  314.   assert(!c.contains(a(i)));
  315.   for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
  316.   c.add(a(a.first()));
  317.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  318.   c |= b;
  319.   assert(b <= c);
  320.   for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
  321.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  322.   c &= a;
  323.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  324.   c -= a;
  325.   assert(!(a <= c));
  326.   for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
  327.   for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
  328.   assert(c.empty());
  329.   assert(a.OK());
  330.   assert(b.OK());
  331.   assert(c.OK());
  332.  
  333.   generictest(a, b, c);
  334. }
  335.  
  336. #include "int.CHSet.h"
  337.  
  338. void CHtest()
  339. {
  340.   intCHSet a(SIZE);
  341.   add(nums, a);
  342.   assert(a.length() == SIZE);
  343.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  344.   intCHSet b(SIZE);
  345.   add(odds, b);
  346.   assert(b.length() == SIZE);
  347.   intCHSet c(SIZE);
  348.   add(dups, c); 
  349.   assert(c.length() == SIZE/2);
  350.   assert(c <= a);
  351.   intCHSet d(a);
  352.   d &= b;
  353.   cout << "a: "; printset(a);
  354.   cout << "b: "; printset(b);
  355.   cout << "c: "; printset(c);
  356.   cout << "d: "; printset(d);
  357.   assert(d.length() == SIZE/2);
  358.   for (Pix p = d.first(); p; d.next(p)) assert((d(p) & 1) != 0);
  359.   a.del(1);
  360.   assert(a.length() == SIZE-1);
  361.   assert(!a.contains(1));
  362.  
  363.   c.clear();
  364.   assert(c.empty());
  365.   c |= a;
  366.   assert(c == a);
  367.   assert(c <= a);
  368.   c.del(a(a.first()));
  369.   assert(c <= a);
  370.   assert(c != a);
  371.   Pix i = a.first();
  372.   assert(!c.contains(a(i)));
  373.   for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
  374.   c.add(a(a.first()));
  375.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  376.   c |= b;
  377.   assert(b <= c);
  378.   for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
  379.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  380.   c &= a;
  381.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  382.   c -= a;
  383.   assert(!(a <= c));
  384.   for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
  385.   for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
  386.   assert(c.empty());
  387.   assert(a.OK());
  388.   assert(b.OK());
  389.   assert(c.OK());
  390.  
  391.   generictest(a, b, c);
  392. }
  393.  
  394. main(int argv, char** argc)
  395. {
  396.   if (argv > 1)
  397.   {
  398.     SIZE = abs(atoi(argc[1]));
  399.     SIZE &= ~1;
  400.   }
  401.   else
  402.     SIZE = 100;
  403.   nums = new int[SIZE];
  404.   odds = new int[SIZE];
  405.   dups = new int[SIZE];
  406.   makenums();
  407.   makeodds();
  408.   makedups();
  409.   start_timer();
  410.   cout << "VHtest\n"; VHtest();
  411.   cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  412.   start_timer();
  413.   cout << "VOHtest\n"; VOHtest();
  414.   cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  415.   start_timer();
  416.   cout << "CHtest\n"; CHtest();
  417.   cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  418.   start_timer();
  419.   cout << "SLtest\n"; SLtest();
  420.   cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  421.   start_timer();
  422.   cout << "XPtest\n"; XPtest();
  423.   cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  424. }
  425.