home *** CD-ROM | disk | FTP | other *** search
/ GEMini Atari / GEMini_Atari_CD-ROM_Walnut_Creek_December_1993.iso / files / gnu / g__lib / tset2.cc < prev    next >
Encoding:
C/C++ Source or Header  |  1993-07-23  |  9.9 KB  |  427 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.  
  103. #include "int.OXPSet.h"
  104.  
  105. void OXPtest()
  106. {
  107.   intOXPSet a(SIZE);
  108.   add(nums, a);
  109.   assert(a.length() == SIZE);
  110.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  111.   intOXPSet b(SIZE);
  112.   add(odds, b);
  113.   assert(b.length() == SIZE);
  114.   intOXPSet c(SIZE);
  115.   add(dups, c); 
  116.   assert(c.length() == SIZE/2);
  117.   assert(c <= a);
  118.   intOXPSet d(a);
  119.   d &= b;
  120.   cout << "a: "; printset(a);
  121.   cout << "b: "; printset(b);
  122.   cout << "c: "; printset(c);
  123.   cout << "d: "; printset(d);
  124.   assert(d.length() == SIZE/2);
  125.   for (Pix p = d.first(); p; d.next(p)) assert((d(p) & 1) != 0);
  126.   a.del(1);
  127.   assert(a.length() == SIZE-1);
  128.   assert(!a.contains(1));
  129.  
  130.   c.clear();
  131.   assert(c.empty());
  132.   c |= a;
  133.   assert(c == a);
  134.   assert(c <= a);
  135.   c.del(a(a.first()));
  136.   assert(c <= a);
  137.   assert(c != a);
  138.   Pix i = a.first();
  139.   assert(!c.contains(a(i)));
  140.   for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
  141.   c.add(a(a.first()));
  142.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  143.   c |= b;
  144.   assert(b <= c);
  145.   for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
  146.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  147.   c &= a;
  148.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  149.   c -= a;
  150.   assert(!(a <= c));
  151.   for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
  152.   for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
  153.   assert(c.empty());
  154.   assert(a.OK());
  155.   assert(b.OK());
  156.   assert(c.OK());
  157.  
  158.   generictest(a, b, c);
  159. }
  160.  
  161.  
  162.  
  163. #include "int.OSLSet.h"
  164.  
  165. void OSLtest()
  166. {
  167.   intOSLSet a;
  168.   add(nums, a);
  169.   assert(a.length() == SIZE);
  170.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  171.   intOSLSet b;
  172.   add(odds, b);
  173.   assert(b.length() == SIZE);
  174.   intOSLSet c;
  175.   add(dups, c); 
  176.   assert(c.length() == SIZE/2);
  177.   assert(c <= a);
  178.   intOSLSet d(a);
  179.   d &= b;
  180.   cout << "a: "; printset(a);
  181.   cout << "b: "; printset(b);
  182.   cout << "c: "; printset(c);
  183.   cout << "d: "; printset(d);
  184.   assert(d.length() == SIZE/2);
  185.   for (Pix p = d.first(); p; d.next(p)) assert((d(p) & 1) != 0);
  186.   a.del(1);
  187.   assert(a.length() == SIZE-1);
  188.   assert(!a.contains(1));
  189.  
  190.   c.clear();
  191.   assert(c.empty());
  192.   c |= a;
  193.   assert(c == a);
  194.   assert(c <= a);
  195.   c.del(a(a.first()));
  196.   assert(c <= a);
  197.   assert(c != a);
  198.   Pix i = a.first();
  199.   assert(!c.contains(a(i)));
  200.   for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
  201.   c.add(a(a.first()));
  202.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  203.   c |= b;
  204.   assert(b <= c);
  205.   for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
  206.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  207.   c &= a;
  208.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  209.   c -= a;
  210.   assert(!(a <= c));
  211.   for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
  212.   for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
  213.   assert(c.empty());
  214.   assert(a.OK());
  215.   assert(b.OK());
  216.   assert(c.OK());
  217.  
  218.   generictest(a, b, c);
  219. }
  220.  
  221. #include "int.BSTSet.h"
  222.  
  223. void BSTtest()
  224. {
  225.   intBSTSet a;
  226.   add(nums, a);
  227.   assert(a.length() == SIZE);
  228.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  229.   intBSTSet b;
  230.   add(odds, b);
  231.   assert(b.length() == SIZE);
  232.   intBSTSet c;
  233.   add(dups, c); 
  234.   assert(c.length() == SIZE/2);
  235.   assert(c <= a);
  236.   intBSTSet d(a);
  237.   d &= b;
  238.   cout << "a: "; printset(a);
  239.   cout << "b: "; printset(b);
  240.   cout << "c: "; printset(c);
  241.   cout << "d: "; printset(d);
  242.   assert(d.length() == SIZE/2);
  243.   for (Pix p = d.first(); p; d.next(p)) assert((d(p) & 1) != 0);
  244.   a.del(1);
  245.   assert(a.length() == SIZE-1);
  246.   assert(!a.contains(1));
  247.  
  248.   c.clear();
  249.   assert(c.empty());
  250.   c |= a;
  251.   assert(c == a);
  252.   assert(c <= a);
  253.   c.del(a(a.first()));
  254.   assert(c <= a);
  255.   assert(c != a);
  256.   Pix i = a.first();
  257.   assert(!c.contains(a(i)));
  258.   for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
  259.   c.add(a(a.first()));
  260.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  261.   c |= b;
  262.   assert(b <= c);
  263.   for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
  264.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  265.   c &= a;
  266.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  267.   c -= a;
  268.   assert(!(a <= c));
  269.   for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
  270.   for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
  271.   assert(c.empty());
  272.   assert(a.OK());
  273.   assert(b.OK());
  274.   assert(c.OK());
  275.  
  276.   generictest(a, b, c);
  277. }
  278.  
  279. #include "int.AVLSet.h"
  280.  
  281. void AVLtest()
  282. {
  283.   intAVLSet a;
  284.   add(nums, a);
  285.   assert(a.length() == SIZE);
  286.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  287.   intAVLSet b;
  288.   add(odds, b);
  289.   assert(b.length() == SIZE);
  290.   intAVLSet c;
  291.   add(dups, c); 
  292.   assert(c.length() == SIZE/2);
  293.   assert(c <= a);
  294.   intAVLSet d(a);
  295.   d &= b;
  296.   cout << "a: "; printset(a);
  297.   cout << "b: "; printset(b);
  298.   cout << "c: "; printset(c);
  299.   cout << "d: "; printset(d);
  300.   assert(d.length() == SIZE/2);
  301.   for (Pix p = d.first(); p; d.next(p)) assert((d(p) & 1) != 0);
  302.   a.del(1);
  303.   assert(a.length() == SIZE-1);
  304.   assert(!a.contains(1));
  305.  
  306.   c.clear();
  307.   assert(c.empty());
  308.   c |= a;
  309.   assert(c == a);
  310.   assert(c <= a);
  311.   c.del(a(a.first()));
  312.   assert(c <= a);
  313.   assert(c != a);
  314.   Pix i = a.first();
  315.   assert(!c.contains(a(i)));
  316.   for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
  317.   c.add(a(a.first()));
  318.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  319.   c |= b;
  320.   assert(b <= c);
  321.   for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
  322.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  323.   c &= a;
  324.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  325.   c -= a;
  326.   assert(!(a <= c));
  327.   for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
  328.   for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
  329.   assert(c.empty());
  330.   assert(a.OK());
  331.   assert(b.OK());
  332.   assert(c.OK());
  333.  
  334.   generictest(a, b, c);
  335. }
  336.  
  337. #include "int.SplaySet.h"
  338.  
  339. void Splaytest()
  340. {
  341.   intSplaySet a;
  342.   add(nums, a);
  343.   assert(a.length() == SIZE);
  344.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  345.   intSplaySet b;
  346.   add(odds, b);
  347.   assert(b.length() == SIZE);
  348.   intSplaySet c;
  349.   add(dups, c); 
  350.   assert(c.length() == SIZE/2);
  351.   assert(c <= a);
  352.   intSplaySet d(a);
  353.   d &= b;
  354.   cout << "a: "; printset(a);
  355.   cout << "b: "; printset(b);
  356.   cout << "c: "; printset(c);
  357.   cout << "d: "; printset(d);
  358.   assert(d.length() == SIZE/2);
  359.   for (Pix p = d.first(); p; d.next(p)) assert((d(p) & 1) != 0);
  360.   a.del(1);
  361.   assert(a.length() == SIZE-1);
  362.   assert(!a.contains(1));
  363.  
  364.   c.clear();
  365.   assert(c.empty());
  366.   c |= a;
  367.   assert(c == a);
  368.   assert(c <= a);
  369.   c.del(a(a.first()));
  370.   assert(c <= a);
  371.   assert(c != a);
  372.   Pix i = a.first();
  373.   assert(!c.contains(a(i)));
  374.   for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
  375.   c.add(a(a.first()));
  376.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  377.   c |= b;
  378.   assert(b <= c);
  379.   for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
  380.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  381.   c &= a;
  382.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  383.   c -= a;
  384.   assert(!(a <= c));
  385.   for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
  386.   for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
  387.   assert(c.empty());
  388.   assert(a.OK());
  389.   assert(b.OK());
  390.   assert(c.OK());
  391.  
  392.   generictest(a, b, c);
  393. }
  394.  
  395.  
  396. main(int argv, char** argc)
  397. {
  398.   if (argv > 1)
  399.   {
  400.     SIZE = abs(atoi(argc[1]));
  401.     SIZE &= ~1;
  402.   }
  403.   else
  404.     SIZE = 100;
  405.   nums = new int[SIZE];
  406.   odds = new int[SIZE];
  407.   dups = new int[SIZE];
  408.   makenums();
  409.   makeodds();
  410.   makedups();
  411.   start_timer();
  412.   cout << "OXPtest\n"; OXPtest();
  413.   cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  414.   start_timer();
  415.   cout << "OSLtest\n"; OSLtest();
  416.   cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  417.   start_timer();
  418.   cout << "BSTtest\n"; BSTtest();
  419.   cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  420.   start_timer();
  421.   cout << "AVLtest\n"; AVLtest();
  422.   cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  423.   start_timer();
  424.   cout << "Splaytest\n"; Splaytest();
  425.   cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  426. }
  427.