//
// Compile line:  mpiCC -DUSE_MPI -fopenmp -std=c++11  -O2  -o test-std-sort test-std-sort.C
//
// Compiler:
// ceerws2703a:io(master)> which icpc
//      /sierra/sntools/SDK/compilers/intel/composer_xe_2016.1.150/compilers_and_libraries/linux/bin/intel64/icpc
// ceerws2703a:io(master)> which mpiCC
//      /sierra/sntools/SDK/mpi/openmpi/1.8.8-intel-16.0-2016.1.150-RHEL6/bin/mpiCC
// ceerws2703a:io(master)> mpiCC --version
//      icpc (ICC) 16.0.1 20151021
//      Copyright (C) 1985-2015 Intel Corporation.  All rights reserved.
//
// 
// ceerws2703a:io(master)> ./test-std-sort 420000
//
// Sorting 420000 values on processor 0
//  ==================================================================================
//  using std::sort ==================================================================
//  
//  ERROR: map detected non-unique global id/local id pair on processor 0.
//  
//  ERROR: Duplicate global id detected on processor 0.
//         Global id 0 assigned to local 420002 and 420000.
//  
//  ERROR: Duplicate global id detected on processor 0.
//         Global id 0 assigned to local 420003 and 420002.
//  
//    .... delete ...
//  
//  ERROR: Duplicate global id detected on processor 0.
//         Global id 180697 assigned to local 118396 and 118396.
//  
//  ERROR: Duplicate global id detected on processor 0.
//         Global id 180697 assigned to local 118396 and 118396.
//  
//  ERROR: Duplicate global id detected on processor 0.
//         Global id 180697 assigned to local 118396 and 118396.
//  
//  ERROR: Duplicate global id detected on processor 0.
//         Global id 180814 assigned to local 116874 and 116874.
//  
//  ERROR: Duplicate global id detected on processor 0.
//         Global id 180814 assigned to local 116874 and 116874.
//  
//  ERROR: Duplicate global id detected on processor 0.
//         Global id 181804 assigned to local 240255 and 240255.
//  
//  ERROR: Duplicate global id detected on processor 0.
//         Global id 181804 assigned to local 240255 and 240255.
//  ==================================================================================
//  using gds_qsort ==================================================================
//  
//  NOTE: If compiled without -DUSE_MPI, then works correctly.
//        If compiled with -DUSE_MPI, fails for certain sizes even if run on single processor.
//        Fails with -O2; works correctly with -O1 and -O0

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

#ifdef USE_MPI
#include <mpi.h>
#endif

  const int GDS_QSORT_CUTOFF=12;

  template <typename INT>
  void GDS_SWAP(INT *V, size_t I, size_t J)
  {
    std::swap(V[I], V[J]);
  }
    
  template <typename INT>
  size_t gds_median3(INT v[], size_t left, size_t right)
  {
    size_t center;
    center = (left + right) / 2;

    if (v[left] > v[center])
      GDS_SWAP(v, left, center);
    if (v[left] > v[right])
      GDS_SWAP(v, left, right);
    if (v[center] > v[right])
      GDS_SWAP(v, center, right);

    GDS_SWAP(v, center, right-1);
    return right-1;
  }

  template <typename INT>
  void gds_qsort_int(INT v[], size_t left, size_t right)
  {
    size_t pivot;
    size_t i, j;
  
    if (left + GDS_QSORT_CUTOFF <= right) {
      pivot = gds_median3(v, left, right);
      i = left;
      j = right - 1;

      for ( ; ; ) {
	while (v[++i] < v[pivot]);
	while (v[--j] > v[pivot]);
	if (i < j) {
	  GDS_SWAP(v, i, j);
	} else {
	  break;
	}
      }

      GDS_SWAP(v, i, right-1);
      gds_qsort_int(v, left, i-1);
      gds_qsort_int(v, i+1, right);
    }
  }

template <typename INT>
void gds_isort_int(INT v[], size_t N)
{
  size_t i,j;
  size_t ndx = 0;
  INT small;
  INT tmp;
  
  if (N <= 1) return;
  small = v[0];
  for (i = 1; i < N; i++) {
    if (v[i] < small) {
      small = v[i];
      ndx = i;
    }
  }
  /* Put smallest value in slot 0 */
  GDS_SWAP(v, 0, ndx);

  for (i=1; i <N; i++) {
    tmp = v[i];
    for (j=i; tmp < v[j-1]; j--) {
      v[j] = v[j-1];
    }
    v[j] = tmp;
  }
}

template <typename INT>
void gds_qsort(std::vector<INT> &v)
{
  if (v.size() <= 1) return;
  gds_qsort_int(v.data(), 0, v.size()-1);
  gds_isort_int(v.data(), v.size());
}

template <typename T>
bool is_unique(std::vector<T> vec)
{
  auto last = std::unique(vec.begin(), vec.end());
  return last == vec.end();
}

void verify_no_duplicate_ids(const std::vector<std::pair<int64_t, int64_t>> &reverse_map, int processor)
{
  // Check for duplicate ids...
  for (size_t i=1; i < reverse_map.size(); i++) {
    if (reverse_map[i-1].first == reverse_map[i].first) {
      std::cerr << "\nERROR: Duplicate global id detected on processor "
		<< processor << ".\n"
		<< "       Global id " << reverse_map[i].first
		<< " assigned to local "
		<< reverse_map[i].second << " and "
		<< reverse_map[i-1].second << ".\n";
    }
  }
}

void build_reverse_map(int64_t num_to_get, int64_t offset, int processor)
{
  std::vector<int64_t> map(num_to_get);
  std::iota(map.begin(), map.end(), 0);
  std::random_shuffle(map.begin(), map.end());

  {
    std::cout << "==================================================================================\n";
    std::cout << "using std::sort ==================================================================\n";
    std::vector<std::pair<int64_t, int64_t> > new_ids;
    new_ids.reserve(num_to_get);
    for (int64_t i=0; i < num_to_get; i++) {
      int64_t local_id = i ;
      new_ids.push_back(std::make_pair(map[local_id], local_id));
    }

    // Sort that vector...
    std::sort(new_ids.begin(), new_ids.end());

    if (!is_unique(new_ids)) {
      std::cerr << "\nERROR: map detected non-unique global id/local id pair on processor "
		<< processor << ".\n";

      verify_no_duplicate_ids(new_ids, processor);
    }
  }

  {
    std::cout << "==================================================================================\n";
    std::cout << "using gds_qsort ==================================================================\n";
    // Now repeat using gds_qsort...
    std::vector<std::pair<int64_t, int64_t> > new_ids;
    new_ids.reserve(num_to_get);
    for (int64_t i=0; i < num_to_get; i++) {
      int64_t local_id = i ;
      new_ids.push_back(std::make_pair(map[local_id], local_id));
    }

    // Sort that vector...
    gds_qsort(new_ids);

    if (!is_unique(new_ids)) {
      std::cerr << "\nERROR: map detected non-unique global id/local id pair on processor "
		<< processor << ".\n";

      verify_no_duplicate_ids(new_ids, processor);
    }
  }


}

int main(int argc, char *argv[])
{
  int rank = 0;
  size_t num_to_get = 1025;
  size_t offset = 42;
  
#ifdef USE_MPI
  MPI_Init(&argc, &argv);
  MPI_Comm_rank(MPI_COMM_WORLD, &rank);
#endif

  if (argc > 1) {
    num_to_get = atoi(argv[1]);
  }
  
  std::cout << "Sorting " << num_to_get << " values on processor " << rank << "\n";
  build_reverse_map(num_to_get, offset, rank);

#ifdef USE_MPI
  MPI_Finalize();
#endif
}