using namespace std;
#include<iostream>
#include<stdlib.h>
#include<time.h>
#include "pqsort.h"

/****** Polymorphic QuickSort ******/

/*
  We want to extend quicksort so that it works on all types of sortable
  data, not just integers.  This is traditionally accomplished by
  passing quicksort a pointer to a procedure (see the built-in qsort function).
  However, this approach is not object-oriented.  We will thus adopt an
  object-oriented approach using objects and templates.  Although it may
  not be so obvious with C++ code, we will also be using a form of inheritance.

  I will do this for quicksort, and I expect you to do it for heapsort:
*/

/*
  comparator class implementations for integers and doubles:
*/
bool comparator<int>::le(int a, int b)
{  return a<b; }
bool comparator<int>::eq(int a, int b)
{  return a==b; }
bool comparator<double>::le(double a, double b)
{  return a<b; }
bool comparator<double>::eq(double a, double b)
{  return a==b; }


// main quicksort class - we gather the three functions of quicksort
// into one class because it's easier to parameterize one class than
// each function individually.
template <typename ST>
class pqsort
{
public:
  ST *A;  
  int size;
  comparator<ST> *comp;   // parameterized comparison class

  // constructor
  pqsort(int n, ST *B, comparator<ST> *c)
  {
    size = n;
    A = B;
    comp = c;
  }
  ~pqsort() {} // do not delete A as it's used outside of context

int findpivot(int start, int end)
{
  int pi = -1;   // index of pivot
  int i = start;
  while (pi<0 && i<end)
    {
      if ( comp->le(A[i+1],A[i]) ) pi = i+1;
      i++;
    }
  return pi;
}


// partition: separate via swapping of an array into two parts, given
// start, end, pivot.  Returns start index of second partition.

int partition(int start, int end, ST pivot)
{
  int i = start;
  int j = start;
  ST temp;
  while (j<=end)
    {
      if ( comp->le(A[j],pivot) || comp->eq(A[j],pivot) )
	{
	  temp = A[i];
	  A[i] = A[j];
	  A[j] = temp;
	  i++;
	}
      j++;
    } // while
  return i;
}

void quicksort(int start, int end)
{
  int pi;
  int i;
  pi = findpivot(start,end);
  if (pi < 0) return;  // partition already sorted
  i = partition(start,end,A[pi]);
  quicksort(start,i-1);
  quicksort(i,end);
}

};  // class pqsort


/************* a class for rational numbers, and its comparator *********/
class rational
{
public:
  int n;   // numerator
  int d;   // denominator
  rational(int a, int b)
  {
    n=a;  d=b;
    if (d==0) throw "denominator can't be zero!";
  }
  rational()  // alternate constructor makes random values
  {
    n = random() % 10000;
    d = 1+ (random() % 10000);
  }
};

bool comparator<rational*>::le(rational *a, rational *b)
{
  return (a->n*b->d < a->d*b->n);
}
bool comparator<rational*>::eq(rational *a, rational *b)
{
  return (a->n*b->d == a->d*b->n);
}


// Test procedure with timing.  The size of the array is determined
// by the first command-line argument:
int main(int argc, char **argv)
{
  int n;  // size of array, determined by command-line argument
  int *A; // array to be dynamically created
  clock_t t1, t2, t3, t4;  // for time measurements
  n = atoi(argv[1]);   // first command-line argument
  A = new int[n];
  for(int i=0;i<n;i++) A[i] = random();

  // construct comparator class:
  comparator<int> *comp = new comparator<int>();
  // construct pqsort class
  pqsort<int> * pq = new pqsort<int>(n,A,comp);

  t1 = clock();   // record time
  pq->quicksort(0,n-1);
  t2 = clock();   // record time


  /*
  double *D = new double[n];
  comparator<double> *dc = new comparator<double>();
  pqsort<double> *pqd = new pqsort<double>(n,D,dc);
  pqd->quicksort(0,n-1);
  */

  // now for an array of rationals
  rational **B;
  B = new rational*[n];
  for(int i=0;i<n;i++) B[i] = new rational();
  comparator<rational*> *rc = new comparator<rational*>();
  pqsort<rational*> *pqr = new pqsort<rational*>(n,B,rc);
  
  t3 = clock();
  pqr->quicksort(0,n-1);
  t4 = clock();
	 

  // for(int i=0;i<n;i++) cout << A[i] << " ";

  delete(A);  
  for(int i=0;i<n;i++) delete(B[i]);
  delete(B);
  delete(comp);   delete(rc);
  delete(pq); delete(pqr);
  cout << "\nint time ~= " << (t2-t1)/((double)CLOCKS_PER_SEC) 
       << " seconds\n";
  cout << "rational time ~= " << (t4-t3)/((double)CLOCKS_PER_SEC) 
       << " seconds\n";

  return 0;  
}


/*
   Experiments:

[cliang@spacedoc csc155]$ ./pqsort 1000000

int time ~= 0.17 seconds
rational time ~= 0.85 seconds
[cliang@spacedoc csc155]$ ./pqsort 2000000

int time ~= 0.35 seconds
rational time ~= 2.05 seconds
[cliang@spacedoc csc155]$ ./pqsort 3000000

int time ~= 0.54 seconds
rational time ~= 3.49 seconds
[cliang@spacedoc csc155]$ ./pqsort 4000000

int time ~= 0.73 seconds
rational time ~= 5.2 seconds
[cliang@spacedoc csc155]$ ./pqsort 5000000

int time ~= 0.92 seconds
rational time ~= 6.77 seconds

>>> .85/.17
4.9999999999999991
>>> 2.05/.35
5.8571428571428568
>>> 3.49/.54
6.4629629629629628
>>> 5.2/.73
7.1232876712328768
>>> 6.77/.92
7.3586956521739122

As the data indicates, the ratio of the time to sort the rationals over
the time to sort the integers appears to converge to some constant around
8 as the size of the array approaches infinity.
*/