home *** CD-ROM | disk | FTP | other *** search
/ GEMini Atari / GEMini_Atari_CD-ROM_Walnut_Creek_December_1993.iso / files / gnu / g__lib / tpq.cc < prev    next >
Encoding:
C/C++ Source or Header  |  1993-07-23  |  5.2 KB  |  264 lines

  1. /*
  2.  a test file for PQs
  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.PQ.h"
  14.  
  15.  
  16. int SIZE;
  17.  
  18. int *nums;
  19. int *odds;
  20. int *dups;
  21.  
  22. void add(int x[], intPQ& a)
  23. {
  24.   for (int i = 0; i < SIZE; ++i) a.enq(x[i]);
  25. }
  26.  
  27. #include <MLCG.h>
  28.  
  29. MLCG randgen;
  30.  
  31. void permute(int x[])
  32. {
  33.   for (int i = 1; i < SIZE; ++i)
  34.   {
  35.     int j = randgen.asLong() % (i + 1);
  36.     int tmp = x[i]; x[i] = x[j]; x[j] = tmp;
  37.   }
  38. }
  39.  
  40. void makenums()
  41. {
  42.   for (int i = 0; i < SIZE; ++i) nums[i] = i + 1;
  43.   permute(nums);
  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 makedups()
  53. {
  54.   for (int i = 0; i < SIZE; i += 2) dups[i] = dups[i+1] = i/2 + 1;
  55.   permute(dups);
  56. }
  57.  
  58. void printPQ(intPQ& 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(i) << " ";
  65.   if (i != 0) cout << "...]\n";
  66.   else cout << "]\n";
  67. }
  68.  
  69. #include "int.XPPQ.h"
  70.  
  71. void XPtest()
  72. {
  73.   intXPPQ a(SIZE);
  74.   add(nums, a);
  75.   intXPPQ b(SIZE);
  76.   add(odds, b);
  77.   intXPPQ c(SIZE);
  78.   add(dups, c); 
  79.   intXPPQ d(a);
  80.   add(nums, d);
  81.   cout << "a: "; printPQ(a);
  82.   cout << "b: "; printPQ(b);
  83.   cout << "c: "; printPQ(c);
  84.   cout << "d: "; printPQ(d);
  85.   assert(a.length() == SIZE);
  86.   assert(b.length() == SIZE);
  87.   assert(c.length() == SIZE);
  88.   assert(d.length() == SIZE*2);
  89.   assert(a.front() == 1);
  90.   assert(b.front() == 1);
  91.   assert(c.front() == 1);
  92.   assert(d.front() == 1);
  93.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  94.   d.del_front();
  95.   assert(d.front() == 1);
  96.   for (j = 1; j <= SIZE; ++j) assert(a.deq() == j);
  97.   assert(a.empty());
  98.   for (j = 1; j <= SIZE*2; j+=2) assert(b.deq() == j);
  99.   assert(b.empty());
  100.   Pix indices[SIZE];
  101.   int m = 0;
  102.   for (Pix i = c.first(); i != 0; c.next(i), c.next(i)) indices[m++] = i;
  103.   assert(m == SIZE/2);
  104.   while (--m >= 0) c.del(indices[m]);
  105.   assert(c.length() == SIZE/2);
  106.   int last = -1;
  107.   j = 0;
  108.   while (!c.empty())
  109.   {
  110.     int current = c.deq();
  111.     assert(last <= current);
  112.     last = current;
  113.     ++j;
  114.   }
  115.   assert(j == SIZE/2);
  116.  
  117.   d.clear();
  118.   assert(d.empty());
  119.   assert(a.OK());
  120.   assert(b.OK());
  121.   assert(c.OK());
  122.   assert(d.OK());
  123. }
  124.  
  125. #include "int.PHPQ.h"
  126.  
  127. void PHtest()
  128. {
  129.   intPHPQ a(SIZE);
  130.   add(nums, a);
  131.   intPHPQ b(SIZE);
  132.   add(odds, b);
  133.   intPHPQ c(SIZE);
  134.   add(dups, c); 
  135.   intPHPQ d(a);
  136.   add(nums, d);
  137.   cout << "a: "; printPQ(a);
  138.   cout << "b: "; printPQ(b);
  139.   cout << "c: "; printPQ(c);
  140.   cout << "d: "; printPQ(d);
  141.   assert(a.length() == SIZE);
  142.   assert(b.length() == SIZE);
  143.   assert(c.length() == SIZE);
  144.   assert(d.length() == SIZE*2);
  145.   assert(a.front() == 1);
  146.   assert(b.front() == 1);
  147.   assert(c.front() == 1);
  148.   assert(d.front() == 1);
  149.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  150.   d.del_front();
  151.   assert(d.front() == 1);
  152.   for (j = 1; j <= SIZE; ++j) assert(a.deq() == j);
  153.   assert(a.empty());
  154.   for (j = 1; j <= SIZE*2; j+=2) assert(b.deq() == j);
  155.   assert(b.empty());
  156.   Pix indices[SIZE];
  157.   int m = 0;
  158.   for (Pix i = c.first(); i != 0; c.next(i), c.next(i)) indices[m++] = i;
  159.   assert(m == SIZE/2);
  160.   while (--m >= 0) c.del(indices[m]);
  161.   assert(c.length() == SIZE/2);
  162.   int last = -1;
  163.   j = 0;
  164.   while (!c.empty())
  165.   {
  166.     int current = c.deq();
  167.     assert(last <= current);
  168.     last = current;
  169.     ++j;
  170.   }
  171.   assert(j == SIZE/2);
  172.  
  173.   d.clear();
  174.   assert(d.empty());
  175.   assert(a.OK());
  176.   assert(b.OK());
  177.   assert(c.OK());
  178.   assert(d.OK());
  179. }
  180.  
  181. #include "int.SplayPQ.h"
  182.  
  183. void Splaytest()
  184. {
  185.   intSplayPQ a;
  186.   add(nums, a);
  187.   intSplayPQ b;
  188.   add(odds, b);
  189.   intSplayPQ c;
  190.   add(dups, c); 
  191.   intSplayPQ d(a);
  192.   add(nums, d);
  193.   cout << "a: "; printPQ(a);
  194.   cout << "b: "; printPQ(b);
  195.   cout << "c: "; printPQ(c);
  196.   cout << "d: "; printPQ(d);
  197.   assert(a.length() == SIZE);
  198.   assert(b.length() == SIZE);
  199.   assert(c.length() == SIZE);
  200.   assert(d.length() == SIZE*2);
  201.   assert(a.front() == 1);
  202.   assert(b.front() == 1);
  203.   assert(c.front() == 1);
  204.   assert(d.front() == 1);
  205.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  206.   d.del_front();
  207.   assert(d.front() == 1);
  208.   for (j = 1; j <= SIZE; ++j) assert(a.deq() == j);
  209.   assert(a.empty());
  210.   for (j = 1; j <= SIZE*2; j+=2) assert(b.deq() == j);
  211.   assert(b.empty());
  212.   Pix indices[SIZE];
  213.   int m = 0;
  214.   for (Pix i = c.first(); i != 0; c.next(i), c.next(i)) indices[m++] = i;
  215.   assert(m == SIZE/2);
  216.   while (--m >= 0) c.del(indices[m]);
  217.   assert(c.length() == SIZE/2);
  218.   int last = -1;
  219.   j = 0;
  220.   while (!c.empty())
  221.   {
  222.     int current = c.deq();
  223.     assert(last <= current);
  224.     last = current;
  225.     ++j;
  226.   }
  227.   assert(j == SIZE/2);
  228.  
  229.   d.clear();
  230.   assert(d.empty());
  231.   assert(a.OK());
  232.   assert(b.OK());
  233.   assert(c.OK());
  234.   assert(d.OK());
  235. }
  236.  
  237.  
  238.  
  239. main(int argv, char** argc)
  240. {
  241.   if (argv > 1)
  242.   {
  243.     SIZE = abs(atoi(argc[1]));
  244.     SIZE &= ~1;
  245.   }
  246.   else
  247.     SIZE = 100;
  248.   nums = new int[SIZE];
  249.   odds = new int[SIZE];
  250.   dups = new int[SIZE];
  251.   makenums();
  252.   makeodds();
  253.   makedups();
  254.   start_timer();
  255.   cout << "Splaytest\n"; Splaytest();
  256.   cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  257.   start_timer();
  258.   cout << "PHtest\n"; PHtest();
  259.   cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  260.   start_timer();
  261.   cout << "XPtest\n"; XPtest();
  262.   cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  263. }
  264.