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

// Even more aggressively object-oriented:

/************  new header: ***********/
template <typename ST>
class comparable
{
 public:
  virtual bool le(ST b) = 0; 
  virtual bool eq(ST b) = 0; 
};
/************  new header: ***********/

/************* a class for rational numbers, and its comparator *********/
class rational : public comparable<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);
  }
  void print() { cout << ((double)n)/d << " "; }

  bool le(rational *b)
  {
    return (n*b->d < d*b->n);
  }
  bool eq(rational *b)
  {
    return (n*b->d == d*b->n);
  }
};  // rational class




// main quicksort class
template <typename ST>
class pqsort
{
public:
  ST *A;   
  int size;

  // constructor
  pqsort(int n, ST *B)
  {
    size = n;
    A = B;
  }
  ~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)
    {
      comparable<ST> *Ac = (comparable<ST>*)A[i+1]; // type cast
      if (Ac->le(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;
  comparable<ST> *Ac;
  while (j<=end)
    {
      Ac = (comparable<ST>*)A[j];
      if (Ac->le(pivot) || Ac->eq(pivot)) 
	//	  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



// 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

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

  for(int i=0;i<n;i++) B[i]->print(); cout << endl;
  
  for(int i=0;i<n;i++) delete(B[i]);
  delete(B);

  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.
*/