/*

Example program for measuring the computing time of algorithms.
This program both measures times and counts operations; for
a simpler example of only measuring times, see tsort1.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 <assert.h>
#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 "recorder.h"
#include "counter.h"
#include "itercount.h"
#include "distcount.h"

typedef int U;

typedef double counter_t;

//typedef counter<U, counter_t>
//        cdata;
// Should be able to use cdata in following definitions
// but there is a bug in apCC that prevents it

typedef  distance_counter<vector<counter<U, counter_t> >::iterator,
                          vector<counter<U, counter_t> >::difference_type, 
                                 counter_t>
         cdistance;

typedef iteration_counter<vector<counter<U, counter_t> >::iterator, 
                          counter<U, counter_t> ,
                          counter<U, counter_t> &, cdistance,
                          vector<counter<U, counter_t> >::difference_type, 
                          counter_t>
        citer;

timer timer1;

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

template <class Container>
void algorithm(int k, Container& x)
{
  switch (k) {
  case 0: introsort(citer(x.begin()), citer(x.end()));
     break;
  case 1: sort(citer(x.begin()), citer(x.end()));
     break;
  case 2: partial_sort(citer(x.begin()), citer(x.end()), citer(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 ofs1("read.dat");
  ofstream ofs2("graph.dat");

  vector<recorder<counter<U, counter_t> , citer, cdistance, timer, counter_t> >
    stats(number_of_algorithms);

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

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

  int n;


  cout << endl;
  ofs1 << endl;

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

    N = N0 * factor;

    cout << "Size: " << setw(4) << N0 << "   Trials: " << flush;
    ofs1  << "Size: " << setw(4) << N0 << flush;
    ofs2  << setw(4) << N0 << flush;

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

    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;
      counter<U, counter_t> ::assignments = 0;

      cout << p+1 << ":" << flush;

      for (n = 0; n < number_of_algorithms; ++n) {
        timer1.restart();
        for (q = 0; q < repetitions; ++q) {
          x = y;
          counter<U, counter_t> ::assignments -= N;
          algorithm(n, x);
        }
        timer1.stop();

        for (int z = 0; z < N; ++z)
	         assert(x[z] == z);

        if (p == -1) {  // to turn this on replace -1 with 0
           cdistance::report(cout);
           cdistance::report(ofs1);
        }
        cout << n+1 << flush;
        stats[n].record(timer1);
      }
      cout << ", " << flush;
    }

    cout << endl <<
  " Algorithm           Time    Comps   Assmts     Iters     Dists      Total  ";
    cout << endl;
    ofs1 << endl <<
  " Algorithm           Time    Comps   Assmts     Iters     Dists      Total  ";
    ofs1 << endl;

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

    cout << endl;
    ofs1 << endl;
    ofs2 << endl;

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

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