#line 5561 "smat.w"

#line 5742 "smat.w"
#define __GLIBCPP_INTERNAL_TEMPBUF_H
namespace std {
template <class _ForwardIterator, class _Tp> class _Temporary_buffer;
}


#line 5507 "smat.w"
#include "smat.h"
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <iterator>
#include <map>
#include <sstream>
#include <utility>
#include <vector>
#ifdef linux
#include <getopt.h>
#endif
#line 5747 "smat.w"


#undef __GLIBCPP_INTERNAL_TEMPBUF_H
#include "stl_tempbuf.h"

#include <sys/time.h>
#include <unistd.h>

#ifdef TIMER
#include "timer.h"
#endif

#include "early.h"
#include "lomuto.h"
#include "tiled.h"
#line 5561 "smat.w"


#if __GNUC__ == 3 && 2 <= __GNUC_MINOR__
#include <ext/algorithm>        // is_sorted
using __gnu_cxx::is_sorted;


#line 5770 "smat.w"
template <typename T>
struct __type_traits<smat_v<T> > {
  typedef typename __type_traits<T>::has_trivial_default_constructor
    has_trivial_default_constructor;
  typedef __false_type has_trivial_copy_constructor;
  typedef __false_type has_trivial_assignment_operator;
  typedef __false_type has_trivial_destructor;
  typedef __false_type is_POD_type;
};
#line 5567 "smat.w"


#endif

using namespace std;


#line 9204 "smat.w"
#include <boost/random.hpp>

template <typename Elem>
class genrand_limit {
  
#line 9226 "smat.w"
  class mt19937_new_initializer {
    unsigned x, c;
  public:
    explicit mt19937_new_initializer(unsigned i = 1) : x(i), c(0) { }
    unsigned operator()()
    { return ++c == 1 ? x : x = (1812433253U * (x ^ (x >> 30)) + c - 1); }
  };
#line 9208 "smat.w"

  mt19937_new_initializer inimt;
  boost::mt19937 genmt;
  double divisor;
public:
  genrand_limit(unsigned seed = 7U,
                Elem u = std::numeric_limits<Elem>::max())
    : inimt(seed), genmt(inimt),
      divisor((std::numeric_limits<unsigned>::max() + 1.0) / (u + 1.0)) {}
  Elem operator()() { return static_cast<Elem>(genmt() / divisor); }
};
#line 5573 "smat.w"



#line 9187 "smat.w"
template <typename T>
static bool lazy_atoi(T* dst, const char *s)
{
  std::istringstream ist(s);
  return (!(ist >> *dst).fail() && (ist >> std::ws).eof()) ? true : false;
}
#line 5575 "smat.w"



#line 5715 "smat.w"
static void usage(char *progname, int status)
{
  if (status != 0)
    cerr << "Try `" << progname << " -h' for more information.\n";
  else
    {
      cout << "Usage: " << progname << " [OPTION]... ALGO NELEM\n\
Generate random numbers and sort them.  ALGO must be one of \"intro\",\n\
\"merge\", \"heap\", \"early\", \"lomuto\", and \"tiled\".\n\
\n\
  -s NUM    random seed\n\
  -S        choose random seed randomly\n\
  -t NUM    tile size for tiled mergesort (4000 by default)\n\
  -d        output sorted numbers to stderr\n\
\n\
  -h        display this help and exit\n";
    }

  exit(status);
}
#line 5577 "smat.w"


int main(int argc, char *argv[])
{
  int c;
  bool dump = false;
  unsigned tile_size = 4000U, seed = 7U, nelem;

  ios::sync_with_stdio(false);
  cin.tie(0);

  
#line 5652 "smat.w"
  while ((c = getopt(argc, argv, "t:s:Sdh")) != -1)
    {
      switch (c)
        {
        case 't':
          if (! lazy_atoi(&tile_size, optarg) || tile_size < 16)
            {
              cerr << argv[0] << ": invalid tile size `" << optarg << "'\n";
              return EXIT_FAILURE;
            }
          break;
  
        case 's':
          if (! lazy_atoi(&seed, optarg))
            {
              cerr << argv[0] << ": invalid seed `" << optarg << "'\n";
              return EXIT_FAILURE;
            }
          break;
  
        case 'S':
          {
            struct timeval tv;
            gettimeofday(&tv, NULL);
            seed = (unsigned long int)getpid() * tv.tv_sec * tv.tv_usec;
            cerr << "seed: " << seed << '\n';
          }
          break;
  
        case 'd':
          dump = true;
          break;
  
        case 'h':
          usage(argv[0], EXIT_SUCCESS); break;
  
        default:
          usage(argv[0], EXIT_FAILURE); break;
        }
    }
  
  if (optind != argc - 2)
    usage(argv[0], EXIT_FAILURE);
  
  if (argv[optind][0] != 'i' && argv[optind][0] != 'e'
      && argv[optind][0] != 'l' && argv[optind][0] != 'm'
      && argv[optind][0] != 't' && argv[optind][0] != 'h')
    {
      cerr << argv[0] << ": invalid algorithm `" << argv[optind] << "'\n";
      return EXIT_FAILURE;
    }
  
  if (! lazy_atoi(&nelem, argv[optind + 1]))
    {
      cerr << argv[0] << ": invalid number of elements `"
           << argv[optind + 1] << "'\n";
      return EXIT_FAILURE;
    }
#line 5588 "smat.w"


  vector<unsigned> v(nelem);
  typedef smat<vector<unsigned>::iterator>::type Iter;


#line 5610 "smat.w"
#ifdef TIMER

  timer t(1500000000.0); // 1.5GHz
  do {
    generate(v.begin(), v.end(), genrand_limit<unsigned>(seed));
    t.restart();
    
#line 5632 "smat.w"
    if (argv[optind][0] == 'i')
      sort(Iter(v.begin()), Iter(v.end()));
    else if (argv[optind][0] == 'e')
      early_introsort(Iter(v.begin()), Iter(v.end()));
    else if (argv[optind][0] == 'l')
      lomuto_introsort(Iter(v.begin()), Iter(v.end()));
    else if (argv[optind][0] == 'm')
      stable_sort(Iter(v.begin()), Iter(v.end()));
    else if (argv[optind][0] == 't')
      {
        if (! tiled_mergesort(Iter(v.begin()), Iter(v.end()), tile_size))
          {
            cerr << argv[0] << ": cannot allocate memory\n";
            return EXIT_FAILURE;
          }
      }
    else // if (argv[optind][0] == 'h')
      partial_sort(Iter(v.begin()), Iter(v.end()), Iter(v.end()));
#line 5616 "smat.w"

    t.pause();
  } while (t.elapsed() < 0.2);
  cerr << t.elapsed() * 1000.0 / t.npause() << '\n';

#else  // not TIMER

  generate(v.begin(), v.end(), genrand_limit<unsigned>(seed));
  
#line 5632 "smat.w"
  if (argv[optind][0] == 'i')
    sort(Iter(v.begin()), Iter(v.end()));
  else if (argv[optind][0] == 'e')
    early_introsort(Iter(v.begin()), Iter(v.end()));
  else if (argv[optind][0] == 'l')
    lomuto_introsort(Iter(v.begin()), Iter(v.end()));
  else if (argv[optind][0] == 'm')
    stable_sort(Iter(v.begin()), Iter(v.end()));
  else if (argv[optind][0] == 't')
    {
      if (! tiled_mergesort(Iter(v.begin()), Iter(v.end()), tile_size))
        {
          cerr << argv[0] << ": cannot allocate memory\n";
          return EXIT_FAILURE;
        }
    }
  else // if (argv[optind][0] == 'h')
    partial_sort(Iter(v.begin()), Iter(v.end()), Iter(v.end()));
#line 5624 "smat.w"


#endif // not TIMER
#line 5593 "smat.w"


  if (dump)
    copy(v.begin(), v.end(), ostream_iterator<unsigned>(cerr, "\n"));

  if (! is_sorted(v.begin(), v.end()))
    return EXIT_FAILURE;

  return EXIT_SUCCESS;
}