/*

Example program for measuring the computing time of algorithms.
This program only measures times; it does not count operations
(for which see tsort2.cpp and tsort3.cpp).

*/

/*
 * 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 "intsort.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)
{
  switch (k) {
  case 0: introsort(x.begin(), x.end());
     break;
  case 1: sort(x.begin(), x.end());
     break;
  case 2: partial_sort(x.begin(), x.end(), x.end());
     break;
  }
}

const char* headings[number_of_algorithms] =
{"|    Introsort   ",
 "|    Quicksort   ",
 "|    Heapsort    "};


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

  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;

    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);
        }
        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;
}