//--------------------------------------------------------------
// Datalogi 2A, February 2002
//
// K opgave: Heap testing program
//
// Martin Zachariasen
//--------------------------------------------------------------
#include <stdio.h>
#include <LEDA/basic.h>
#include <LEDA/random_source.h>
#include <LEDA/array.h>
#include <LEDA/impl/f_heap.h>
#include <LEDA/p_queue.h>
#include <LEDA/graph.h>
#include "my_heap.h"

// Basic class for heap testing algorithms. Methods for collecting
// statistics on number of operations and CPU times.
class pq_test {
public:
  void start_single_run() { 
    cpu_time = used_time();
  }
  
  void finish_single_run() {
    cpu_time = used_time(cpu_time);
    total_cpu_time += cpu_time;
    number_of_runs++;
    if (min_cpu_time > cpu_time) min_cpu_time = cpu_time;
    if (max_cpu_time < cpu_time) max_cpu_time = cpu_time;
  }

  void clear_statistics() {
    count_insert   = 0;
    count_delmin   = 0;
    count_decrease = 0;
    avg_heap_size  = 0;
    total_cpu_time = 0;
    min_cpu_time   = MAXDOUBLE;
    max_cpu_time   = -MAXDOUBLE;
    number_of_runs = 0;
  }

  void print_header() {
    printf("    Size   Insert   Delmin Decrease Avg.Size  Avg.CPU  Min.CPU  Max.CPU\n");
  }
  
  void print_statistics(int size) {
    printf("%8d %8d %8d %8d %8.0f %8.2f %8.2f %8.2f\n", 
	   size,
	   count_insert / number_of_runs, 
	   count_delmin / number_of_runs,
	   count_decrease / number_of_runs,
	   avg_heap_size / count_insert,
	   total_cpu_time / number_of_runs,
	   min_cpu_time,
	   max_cpu_time);
  }

  void print_footer() {
    printf("\n");
  }
  
protected:

  int count_insert, count_delmin, count_decrease, number_of_runs;
  float cpu_time;
  double avg_heap_size, total_cpu_time, min_cpu_time, max_cpu_time;
};


// Heap test : Huffman code construction.
template < class PQ >
class Huffman : public pq_test {
public:
  
  // Huffman construction for an alphabet given as an array of
  // character frequencies   
  void construct_Huffman_code(array<double>& freq) {
    int i, x, y, n = freq.size();
    array<double> F(2*n-1), left(2*n-1), right(2*n-1);
    PQ Q;
    typename PQ::item it;
    
    for (i = 0; i < n; i++) {
      Q.insert(freq[i], i);
      F[i] = freq[i];
      count_insert++;  avg_heap_size += Q.size();
    }
    
    for (i = n; i < 2*n-1; i++) {
      // find pair of elements with minimum frequency and merge them
      it = Q.find_min(); x = Q[it]; Q.del_item(it); left [i] = x;
      count_delmin++;
      it = Q.find_min(); y = Q[it]; Q.del_item(it); right[i] = y;
      count_delmin++;
      F[i] = F[x] + F[y];
      // insert merged pair back into queue
      Q.insert(F[i], i);
      count_insert++;  avg_heap_size += Q.size();
    }
  }

  // Perform complete set of runs for uniform distributions
  // of frequencies.
  void run_uniform(int size_start, int size_end, int size_step, int reps) {
    int i, n, seed;
    random_source S;
    print_header();
    for (n = size_start; n <= size_end; n += size_step) {
      clear_statistics();
      array<double> freq(n);
      for (seed = 1; seed <= reps; seed++) {
	S.set_seed(seed);
	for (i = 0; i < n; i++) S >> freq[i];
	start_single_run();
	construct_Huffman_code(freq); // perform Huffman code construction
	finish_single_run();
      }
      print_statistics(n);
    }
    print_footer();
  }
};


// Heap test:  Minimum spanning tree construction using Prim's algorithm.
template < class PQ >
class Prim : public pq_test {
public:
  
  // Construct MST for a given graph G using Prim's algorithm
  void Prim_MST(graph& G, edge_array<int>& cost) {
    node u, v, r = G.first_node();
    edge e;
    int mst_length = 0;
    node_array< typename PQ::item > node_it(G);
    node_array< bool > chosen(G, false);
    PQ Q;
    typename PQ::item it;
    
    forall_nodes(u, G) node_it[u] = 0;
    node_it[r] = Q.insert(0, r); 
    count_insert++;  avg_heap_size += Q.size();
    
    while (!Q.empty()) {
      // pick node with minimum priority
      it = Q.find_min(); 
      mst_length += Q.prio(it);
      u = Q[it]; 
      Q.del_item(it); 
      chosen[u] = true;
      count_delmin++;
      
      // update priority for all neighbouring nodes
      forall_inout_edges(e, u) {
	v = G.opposite(u,e);
	if (chosen[v]) continue;
	if (node_it[v]) {
	  it = node_it[v];
	  if (Q.prio(it) > cost[e]) {
	    Q.decrease_p(it, cost[e]);
	    count_decrease++;
	  }
	}
	else {
	  node_it[v] = Q.insert(cost[e], v);
	  count_insert++;  avg_heap_size += Q.size();
	}
      }
    }
  }

  // Perform complete set of runs for 2D grid graphs with random edge
  // weights in the interval 1..1000. 
  void run_grid(int size_start, int size_end, int size_step, int reps) {
    int n, seed;
    edge e;
    random_source S;
    S.set_range(1,1000);
    print_header();
    for (n = size_start; n <= size_end; n += size_step) {
      clear_statistics();
      graph G;
      grid_graph(G, (int) sqrt(n/2));
      edge_array<int> cost(G);
      for (seed = 1; seed <= reps; seed++) {
	S.set_seed(seed);
	forall_edges(e, G) S >> cost[e];
	start_single_run();
	Prim_MST(G, cost); // construct minimum spanning tree
	finish_single_run();
      }
      print_statistics(n);
    }
    print_footer();
  }

  // Perform complete set of runs for complete graphs with random edge
  // weights in the interval 1..1000.
  void run_complete(int size_start, int size_end, int size_step, int reps) {
    int n, seed;
    edge e;
    random_source S;
    S.set_range(1,1000);
    print_header();
    for (n = size_start; n <= size_end; n += size_step) {
      clear_statistics();
      graph G;
      complete_ugraph(G, (int) sqrt(2*n));
      edge_array<int> cost(G);
      for (seed = 1; seed <= reps; seed++) {
	S.set_seed(seed);
	forall_edges(e, G) S >> cost[e];
	start_single_run();
	Prim_MST(G, cost); // construct minimum spanning tree
	finish_single_run();
      }
      print_statistics(n);
    }
    print_footer();
  }

};


int main() {

  // Set up test classes for each priority queue
  Huffman< my_heap<double,int> >         myHuff;
  Huffman< p_queue<double,int,f_heap> > fibHuff;
  Prim< my_heap<int,node> >              myPrim;
  Prim< p_queue<int,node,f_heap> >      fibPrim;
  
  // Perform experiments

  cout << "Huffman using my heap:" << endl;
  myHuff.run_uniform(10000,100000,10000,10);
  
  cout << "Huffman using Fibonacci heap:" << endl;
  fibHuff.run_uniform(10000,100000,10000,10);

  cout << "Prim complete graph using my heap:" << endl;
  myPrim.run_complete(100000,1000000,100000,10);

  cout << "Prim complete graph using Fibonacci heap:" << endl;
  fibPrim.run_complete(100000,1000000,100000,10);

  cout << "Prim grid graph using my heap:" << endl;
  myPrim.run_grid(100000,1000000,100000,10);

  cout << "Prim grid graph using Fibonacci heap:" << endl;
  fibPrim.run_grid(100000,1000000,100000,10);
}