// Test driver for sorting routines.

#include <vector>
#include <algorithm>
#include <iostream>
#include <iomanip>

#include "timer.h"
#include "counter.h"
#include "quicksort.h"


// Check whether or not a container is correctly sorted,
// printing an error message if not.

template <class Iterator>
void check_if_sorted(Iterator first, Iterator last)
{
  Iterator next = first + 1;
  while (next != last)
  {
    if (*first > *next)
    {
      std::cout << "ERROR! Not correctly sorted!" << std::endl;
      exit(1);
    }
    first = next;
    ++next;
  }
}


void main()
{
  const int size = 10000;	// Size of test cases.
  const int trials = 10;	// Number of trials.

  // We'll use two vectors, one of integers and the second of a special
  // class (an "object adapter") that acts just like an integer except
  // that it keeps track of the number of assignment and comparison
  // operations that are performed.
  std::vector<int> a1;
  std::vector<counter<int> > a2;
  for (int i=1; i <= size; ++i)
  {
    a1.push_back(i);
    a2.push_back(i);
  }

  // Initialize the timer and comparison & assignment counters.
  timer stopwatch;
  stopwatch.reset();
  unsigned n_comparisons = 0;
  unsigned n_assignments = 0;

  // Run the test for some number of trials to ensure we get
  // a good random sampling.
  for (int t=0; t < trials; ++t)
  {

    // Mix up one test vector, then copy it to the other one ensuring
    // that both tests are identical.
    std::random_shuffle(a1.begin(), a1.end());
    std::copy(a1.begin(), a1.end(), a2.begin());

    // Time the execution of the sort.
    // The stopwatch time will be cumulative over the trials.
    stopwatch.start();
    std::sort(a1.begin(), a1.end());
    stopwatch.stop();

    // Count number of comparisons and assignments.
    counter<int>::reset();
    std::sort(a2.begin(), a2.end());
    n_comparisons += counter<int>::comparisons;
    n_assignments += counter<int>::assignments;

    // Make sure the sorting algorithm worked correctly.
    // We really only need to check one of these, since they are identical.
    check_if_sorted(a1.begin(), a1.end());
    check_if_sorted(a2.begin(), a2.end());
  }

  // Output results.
  std::cout << std::setprecision(10);
  std::cout << "Sorting vector of size:     " << size << std::endl;
  std::cout << "Average time in seconds:    " 
	    << stopwatch.time()/trials << std::endl;
  std::cout << "Average no. of comparisons: " 
	    << (float) n_comparisons/trials << std::endl;
  std::cout << "Average no. of assignments: " 
  	    << (float) n_assignments/trials << std::endl;
}