home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / ledar34.zip / leda-r-3_4_tar / LEDA-3.4 / prog / prio / prio_test.c < prev    next >
C/C++ Source or Header  |  1996-09-03  |  3KB  |  135 lines
  1. #include <LEDA/_prio.h>
  2.  
  3. #include <LEDA/impl/m_heap.h>
  4. #include <LEDA/impl/k_heap.h>
  5. #include <LEDA/impl/p_heap.h>
  6. #include <LEDA/impl/list_pq.h>
  7.  
  8. typedef float FLOAT;
  9.  
  10.  
  11. void prio_test(priority_queue<int,int>& D, int N, int* A, char* name)
  12. { 
  13.   pq_item* I = new pq_item[N];
  14.  
  15.   cout << string("%-12s",name);
  16.   cout.flush();
  17.  
  18.   float T;
  19.   float T0 = T = used_time();
  20.  
  21.   int i;
  22.   for(i=0; i<N; i++)  I[i] = D.insert(i,A[i]);
  23.   cout << string("%10.2f",used_time(T));
  24.   cout.flush();
  25.  
  26.   for(i=0; i<N; i++)  D.decrease_inf(I[i],A[i]/2);
  27.   cout << string("%14.2f",used_time(T));
  28.   cout.flush();
  29.  
  30.   int old_min = -MAXINT;
  31.  
  32.   for(i=0; i<N; i++)  
  33.   { if (D.inf(D.find_min()) < old_min) cout << "error in del_min\n";
  34.     old_min = D.inf(D.find_min()); 
  35.     D.del_min();
  36.    }
  37.  
  38.   cout << string("%10.2f",used_time(T));
  39.  
  40.   cout << string("%10.2f",used_time(T0));
  41.  
  42.   if (!D.empty()) cout << " NOT EMPTY !!\n";    
  43.  
  44.   newline;
  45.  
  46.   delete I;
  47. }
  48.  
  49.  
  50. void prio_test(priority_queue<FLOAT,FLOAT>& D, int N, FLOAT* A, char* name)
  51. { 
  52.   pq_item* I = new pq_item[N];
  53.  
  54.   cout << string("%-12s",name);
  55.   cout.flush();
  56.  
  57.   float T;
  58.   float T0 = T = used_time();
  59.  
  60.  
  61.   int i;
  62.   for(i=0; i<N; i++)  I[i] = D.insert(FLOAT(i),A[i]);
  63.   cout << string("%10.2f",used_time(T));
  64.   cout.flush();
  65.  
  66.   for(i=0; i<N; i++)  D.decrease_inf(I[i],A[i]/2);
  67.   cout << string("%14.2f",used_time(T));
  68.   cout.flush();
  69.  
  70.   FLOAT old_min = -MAXINT;
  71.  
  72.   for(i=0; i<N; i++)  
  73.   { if (D.inf(D.find_min()) < old_min) cout << "error in del_min\n";
  74.     old_min = D.inf(D.find_min());
  75.     D.del_min();
  76.    }
  77.  
  78.   cout << string("%10.2f",used_time(T));
  79.  
  80.   cout << string("%10.2f",used_time(T0));
  81.  
  82.   if (!D.empty()) cout << " NOT EMPTY !!\n";    
  83.  
  84.   newline;
  85.  
  86.   delete I;
  87. }
  88.  
  89.  
  90.  
  91. main()
  92. { priority_queue<int,int>            Q;
  93.   priority_queue<FLOAT,FLOAT>        Qf;
  94.  
  95.   int    N     = read_int("# keys = ");
  96.   int*   Int   = new int[N];
  97.   FLOAT* Float = new FLOAT[N];
  98.  
  99.   random_source ran(0,1000000);
  100.  
  101.   for(int i=0; i<N; i++) Float[i] = Int[i] = ran();
  102.  
  103.   _priority_queue<int,int,m_heap>    m_q(N);
  104.   _priority_queue<int,int,k_heap>    k_q(N);
  105.   _priority_queue<int,int,p_heap>    p_q;
  106.   _priority_queue<int,int,list_pq>   l_q;
  107.  
  108.   _priority_queue<FLOAT,FLOAT,m_heap>    m_qf(N);
  109.   _priority_queue<FLOAT,FLOAT,k_heap>    k_qf(N);
  110.   _priority_queue<FLOAT,FLOAT,p_heap>    p_qf;
  111.   _priority_queue<FLOAT,FLOAT,list_pq>   l_qf;
  112.  
  113.  
  114.   newline;
  115.   cout << "                insert   decrease_inf  del_min    total\n";
  116.   newline;
  117.  
  118.   prio_test(Q,N,Int,"prio");
  119.   //prio_test(m_q,N,Int,"m_heap");
  120.   prio_test(k_q,N,Int,"k_heap");
  121.   prio_test(p_q,N,Int,"p_heap");
  122.   //prio_test(l_q,N,Int,"list_pq");
  123.   newline;
  124.  
  125.  
  126.   prio_test(Qf,N,Float,"prio");
  127.   //prio_test(m_qf,N,Float,"m_heap");
  128.   prio_test(k_qf,N,Float,"k_heap");
  129.   prio_test(p_qf,N,Float,"p_heap");
  130.   //prio_test(l_qf,N,Float,"list_pq");
  131.   newline;
  132.  
  133.   return 0;
  134. }
  135.