//---------------------------------------------------------------------
//    Automated version of LEDAdijkstra.cc
//---------------------------------------------------------------------

#include <iostream>
using namespace std;

//#define LEDA_CHECKING_OFF
#define LEDA_CHECKING_ON

#define SMPL_SIZ   5       // Find average over how big a sample size

#include <LEDA/graph/graph_alg.h>
#include <LEDA/core/_p_queue.h>
#include <LEDA/core/impl/k_heap.h>
#include <LEDA/core/impl/f_heap.h>
#include <LEDA/core/impl/bin_heap.h>
#include <LEDA/core/impl/m_heap.h>
#include <LEDA/core/impl/p_heap.h>
#include <LEDA/core/impl/r_heap.h>
#include <LEDA/core/impl/list_pq.h>
using namespace leda;

//---------------------------------------------------------------------
//  This version of dijkstra's algorithm allows us to implement the
//  priority queue using different data structures.
//  You should examine this code carefully to learn how the different
//  implementations are done using only one program...  LHW(10/98)
//---------------------------------------------------------------------
template<class pq_impl>
void dijkstra(graph& G, 
              node s, 
              edge_array<int>&  cost, 
              node_array<int>&  dist,
              node_array<edge>& pred,
              p_queue<int,node,pq_impl>& PQ)    // additional parameter to specify
{                                               // PQ implementation...
  typedef typename p_queue<int,node,pq_impl>::item pq_item;
  node_array<pq_item> I(G);
  node v;
  edge e;
  pq_item it;
                                                                               
  forall_nodes(v,G)                       // Initialization phase
  { pred[v] = nil;
    dist[v] = MAXINT;
   }

  dist[s] = 0;                            // Build the priority queues
  I[s] = PQ.insert(0,s);

  while (! PQ.empty())                // Main loop..
  { it = PQ.find_min();           // Find node with min. label
    node u = PQ.inf(it);
    int du = dist[u];
    forall_adj_edges(e,u)                 // Update labels of adj vtxes
    { v = G.target(e);
      int c = du + cost[e];
      if (c < dist[v])
      { if (dist[v] == MAXINT)
          I[v] = PQ.insert(c,v);
        else
          PQ.decrease_p(I[v],c);          // The decrease_key operation
        dist[v] = c;
        pred[v] = e;
       }
     }
     PQ.del_item(it);                       // Delete node from PQ
   }
}


main(int argc, char ** argv)
{
  GRAPH<int,int> G;
  int n, m, M;

  if (argc < 4)
  {
    cout << "Usage: " << argv[0] << " <n> <m> <M>\n"
         << "n=#nodes, m=#edges, M=max(cost(edge))"
         << endl
         << "Find avg. time of Dijkstra on 7 implementations of p_queues."
         << endl << "line 1 = f_heap"
         << endl << "line 2 = k_heap"
         << endl << "line 3 = m_heap"
         << endl << "line 4 = list_pq"
         << endl << "line 5 = p_heap"
         << endl << "line 6 = r_heap"
         << endl << "line 7 = bin_heap"
         << endl << "line 8 = LEDA's impl. of Dijkstra" << endl;
    exit(1);
  }
  else
    if (((n = atoi(argv[1])) < 0) ||
        ((m = atoi(argv[2])) < 0) ||
        ((M = atoi(argv[3])) < 0))
      exit(1);

  float T_avg[8];                  // note: use T_avg[7] for default DIJKSTRA

  for (int i = 0; i < 8; i++) T_avg[i] = 0.0;  

  for (int t = SMPL_SIZ; t > 0; t--)
  {
    random_graph(G,n,m);           // generate random directed graph G
    edge_array<int>  cost(G);      // build edge-cost array
    node_array<int>  dist0(G);     // labels computed by default DIJKSTRA
    node_array<int>  dist(G);    
    node_array<edge> pred(G);

    edge e;                        // now assign edge weights randomly
    forall_edges(e,G)
      G[e] = cost[e] = rand_int(0,M);
  
    node s = G.choose_node();      // pick a start node s
 
 
    float T = used_time();         // default DIJKSTRA
    DIJKSTRA (G,s,cost,dist0,pred);
    T_avg[7] += used_time(T);

    for (int i = 0; i < 7; i++)
    { 

      float T = used_time();       // other implementations
	  
	  switch (i) {
		case 0: {
					p_queue<int,node,f_heap> PQ;
					dijkstra(G, s, cost, dist, pred, PQ);
					break;
				}
		case 1: {
					p_queue<int,node,k_heap> PQ(n);
					dijkstra(G, s, cost, dist, pred, PQ);
					break;
				}
		case 2: {
					p_queue<int,node,m_heap> PQ(M+1);
					dijkstra(G, s, cost, dist, pred, PQ);
					break;
				}
		case 3: {
					p_queue<int,node,list_pq> PQ;
					dijkstra(G, s, cost, dist, pred, PQ);
					break;
				}
		case 4: {
					p_queue<int,node,p_heap> PQ;
					dijkstra(G, s, cost, dist, pred, PQ);
					break;
				}
		case 5: {
					p_queue<int,node,r_heap> PQ(M);
					dijkstra(G, s, cost, dist, pred, PQ);
					break;
				}
		case 6: {
					p_queue<int,node,bin_heap> PQ(n);
					dijkstra(G, s, cost, dist, pred, PQ);
					break;
				}
		default: exit(0);
	  }
	  
	  T_avg[i] += used_time(T);
      node v;                      // verify solution against default DIJKSTRA
      forall_nodes(v,G)
        if( dist[v] != dist0[v]) 
        {
          cout << "Error (" << i << "):";
          G.print_node(v);
          cout << ". dist = " << dist[v] << "  dist0 = " << dist0[v] << "\n";
        }
      cout<<". ";
      cout.flush();
  }

  }
  cout << endl;

  for (int i = 0; i < 8; i++)
    cout << T_avg[i]/(float)SMPL_SIZ << endl;

  return 0;
}