// //////////////////////////////////////////////////////////
// parallelSort.cpp
// Copyright (c) 2011 Stephan Brumme. All rights reserved.
// see http://create.stephan-brumme.com/disclaimer.html
//

// g++ -O3 -fopenmp -march=native parallelSort.cpp -o parallelSort

#include <omp.h>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <parallel/algorithm>

//#define USE_WINDOWS_TIMER
#ifdef USE_WINDOWS_TIMER
#include <windows.h>
#else
#include <sys/time.h>
#endif


// OS-specific timing
static double seconds()
{
#ifdef USE_WINDOWS_TIMER
  LARGE_INTEGER frequency, now;
  QueryPerformanceFrequency(&frequency);
  QueryPerformanceCounter  (&now);
  return now.QuadPart / double(frequency.QuadPart);
#else
  timeval now;
  gettimeofday(&now, NULL);
  return now.tv_sec + now.tv_usec/1000000.0;
#endif
}


int main(int argc, char* argv[])
{
  // number of elements to be sorted is passed via command-line, "sort 12345678"
  const char *query = "12345678";
  if (argc == 2)
    query = argv[1];
  int numElements = atoi(query);

  // only positive numbers
  if (numElements == 0)
    numElements = 12345678;
  if (numElements < 0)
    numElements = -numElements;

  printf("sorting %d elements ...\n", numElements);
  printf("max. OpenMP threads: %d (%d processors)\n", omp_get_max_threads(), omp_get_num_procs());

  // initialize containers
  std::vector<int> data(numElements);
  for (int i = 0; i < numElements; i++)
    data[i] = i;
  std::vector<int> random(numElements);
  srand(0); // keep randomness reproducible ;-)
  for (int i = 0; i < numElements; i++)
    random[i] = rand();

  double timeInverted = 0;
  double timeSorted   = 0;
  double timeRandom   = 0;

  // std::sort
  // inverted data
  for (int i = 0; i < numElements; i++)
    data[i] = numElements - (i+1);
  timeInverted = seconds();
  std::sort(data.begin(), data.end());
  timeInverted = seconds() - timeInverted;

  // sorted data
  timeSorted = seconds();
  std::sort(data.begin(), data.end());
  timeSorted = seconds() - timeSorted;

  // random data
  data = random;
  timeRandom = seconds();
  std::sort(data.begin(), data.end());
  timeRandom = seconds() - timeRandom;

  printf("stl::sort:\n"
         "sorted  : %.3fms\n"
         "inverted: %.3fms\n"
         "random  : %.3fms\n\n",
         1000*timeSorted, 1000*timeInverted, 1000*timeRandom, 1000*(timeSorted+timeInverted+timeRandom));

  // __gnu_parallel::sort
  // inverted data
  for (int i = 0; i < numElements; i++)
    data[i] = numElements - (i+1);
  timeInverted = seconds();
  __gnu_parallel::sort(data.begin(), data.end());
  timeInverted = seconds() - timeInverted;

  // sorted data
  timeSorted = seconds();
  __gnu_parallel::sort(data.begin(), data.end());
  timeSorted = seconds() - timeSorted;

  // random data
  data = random;
  timeRandom = seconds();
  __gnu_parallel::sort(data.begin(), data.end());
  timeRandom = seconds() - timeRandom;

  printf("__gnu_parallel::sort:\n"
         "sorted  : %.3fms\n"
         "inverted: %.3fms\n"
         "random  : %.3fms\n",
         1000*timeSorted, 1000*timeInverted, 1000*timeRandom, 1000*(timeSorted+timeInverted+timeRandom));

  return 0;
}