// Measure execution times of two algorithms for computing 
// the 10 largest numbers in a list.
// 
// Must compile using the -std=c++11 option.
//
// Usage:
//    ./<exec name> <size of list>

#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <queue>

using namespace std;

//
// Given a vector V and an integer n, copy the n largest 
// numbers to rest.  This algorithm uses sorting.
//
void nHighest(vector <float> &V, int n, vector <float> &res) {
  sort(V.begin(), V.end());
  res.resize(n);
  copy(V.begin()+V.size()-n, V.end(), res.begin());
}


//
// Given a vector V and an integer n, copy the n largest 
// numbers to rest.  This algorithm uses a priority queue.
//
void nHighestWithPQ(const vector <float> &V, int n, vector <float> &res) {
  res.resize(0);
  priority_queue<float, std::vector<float> , std::greater<float>> q;

  // put the first n+1 elements into the queue
  for (int i = 0; i <= n; i++) q.push(V[i]);
  
  // for the rest, if they are higher than the smallest in the queue,
  // then enqueue
  for (int i = n+1; i < V.size(); i++) {
    if (V[i] > q.top()) {
  	  q.pop();       // pop the 11th largest element
      q.push(V[i]);  // push one element
    }
  }
  q.pop();

  while (!q.empty()) {
    res.push_back(q.top());
    q.pop();
  }
}



int main(int argc, char *argv[]) {
  
  // get the command line argument
  if (argc < 2) { 
  	cout << "Usage: " << argv[0] << " <size> \n"; 
    exit(1);
  }
  int size = atoi(argv[1]);
  

  vector<float> v,w;
  
    // fill the v vector with random integers
  for (int i = 0; i < size; i++) 
  	v.push_back(rand() / static_cast<float>(RAND_MAX));
  
  // copy v to w
  w = v;
  
  // initialize the random seed
  srand(time(NULL));
  
  vector<float> res1, res2;
  
  double elapsed_secs;

  // measure the time for the sorting version
  clock_t begin = clock();
  nHighest(v, 10, res1);
  clock_t end = clock();

  elapsed_secs = static_cast<double>(end - begin) / CLOCKS_PER_SEC;
  cout << "\nAlgorithm A: " << elapsed_secs << " seconds\n";

  // measure the time for the priority queue version
  begin = clock();
  nHighestWithPQ(w, 10, res2);
  end = clock();

  elapsed_secs = static_cast<double>(end - begin) / CLOCKS_PER_SEC;
  cout << "Algorithm B: " << elapsed_secs << " seconds\n";

  #ifdef DEBUG  
  cout << "Results for algorithm A:\n";
  for (auto e: res1) cout << e <<" ";
  cout << '\n';

  cout << "Results for algorithm B:\n";
  for (auto e: res1) cout << e <<" ";
  cout << '\n';
  #endif 
  
  if (res1 == res2) 
    cout << "Congratulations. Both algorithms had the ame results!\n\n";
  else              
    cout << "Bad new. The algorithms obtained different results :-(\n";
  
  return 0;
}

//  125000
//  250000
//  500000
// 1000000