/* 

Example program for measuring the computing time of algorithms.  It is
a variant of tsort1.cpp, modified slightly to test partial sorting
algorithms (for placing the k smallest elements of a sequence at the
beginning, in nonincreasing order, without completely sorting the
sequence). Such algorithms have an additional parameter relative to
the sorting algorithms measured in tsort1.cpp.  This
program only measures times; it does not count operations.

*/

/*
 * Copyright (c) 1997 Rensselaer Polytechnic Institute
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Rensselaer Polytechnic Institute makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 */

#include <algo.h>
#include <vector.h>
#include <random.cpp>
#include <iostream.h>
#include <iomanip.h>
#include <fstream.h>
#include "partial_sort.h"
#include "timer.h"
#include "recorder0.h"

timer timer1;

typedef int U;

const int number_of_algorithms = 3;
const int number_of_trials = 7;

template <class Container>
inline void algorithm(int k, Container& x, int K)
{
  switch (k) {
  case 0:
    nth_element(x.begin(), x.begin() + K, x.end());
    sort(x.begin(), x.begin() + K);
    break;
  case 1:
    partial_sort(x.begin(), x.begin() + K, x.end());
    break;
  case 2:
    partial_sort1(x.begin(), x.begin() + K, x.end(),
                  less<int>());
    break;
  }
}

const char* headings[number_of_algorithms] =
{"|nth_element,sort",
 "|  partial_sort  ",
 "|  partial_sort1 "};

int main()
{
  int N0, N1, N2, N, S, K;

  const int factor = 1000;

  cout << "All sequence sizes are in multiples of " << factor << ".\n";
  cout << "Input the smallest and largest sequence sizes: " << flush;

  cin >> N1 >> N2;

  cout << "Input random seed control (a positive integer): ";

  cin >> S;

  while (S--)
    __long_random(10);

  ofstream ofs("results");

  vector<recorder<timer> > stats(number_of_algorithms);

  vector<U> x, y;
  x.reserve(N2*factor);
  y.reserve(N2*factor);

  int repetitions = max(32/N1, 1);

  int n;

  cout << "____";
  for (n = 0; n < number_of_algorithms; ++n)
    cout << headings[n];
  cout << endl;

  cout << "Size";
  for (n = 0; n < number_of_algorithms; ++n)
    cout << "|      Time      ";
  cout << endl;

  for (N0 = N1; N0 <= N2; N0 *= 2) {

    N = N0 * factor;

    K = N/2;

    for (int i = 0; i < N; ++i)
      x.push_back(i);

    cout << setw(4) << N0 << flush;
    ofs << setw(4) << N0;

    int p, q;

    for (n = 0; n < number_of_algorithms; ++n)
      stats[n].reset();

    for (p = 0; p < number_of_trials; ++p) {

      random_shuffle(x.begin(), x.end());
      y = x;

      for (n = 0; n < number_of_algorithms; ++n) {
        timer1.restart();
        for (q = 0; q < repetitions; ++q) {
          x = y;
          algorithm(n, x, K);
        }
        timer1.stop();

        stats[n].record(timer1);
      }
    }

    for (n = 0; n < number_of_algorithms; ++n) {
      stats[n].report(cout, repetitions);
      stats[n].report(ofs, repetitions);
    }

    cout << endl;
    ofs << endl;

    x.erase(x.begin(), x.end());

    if (repetitions > 1)
      repetitions /= 2;
  }
  return 0;
}