// main.cpp
// Aren Jansen
// Purpose: Test Rational class implementation, define quicksort function,
//          and demonstrate quicksort on rationals.


#include <iostream>
#include "Rational.h"

using std::cin;
using std::cout;
using std::endl;


// -------------------
// Function prototypes
// -------------------

void quickSortRat( Rational * rat, int start, int end );
int partition( Rational * rat, int start, int end );



// ---------------------
// Main function body
// ---------------------

int main( void )
{
   Rational r1( 8, 16 );
   Rational r2( 7, 35 );

   cout << "Demonstration of Rational Class:" << endl;
   cout << "         Rational One: " << r1 << endl;
   cout << "         Rational Two: " << r2 << endl;
   cout << "   Rational One + Two: " << r1 + r2 << endl;
   cout << "   Rational One - Two: " << r1 - r2 << endl;
   cout << "   Rational One * Two: " << r1 * r2 << endl;
   cout << "   Rational One / Two: " << r1 / r2 << endl;
   cout << "        Rational -One: " << -r1 << endl;
   cout << "          One == Two?: " << (r1 == r2) << endl;
   cout << "          One != Two?: " << (r1 != r2) << endl;
   cout << "           One < Two?: " << (r1 < r2) << endl;
   cout << "           One > Two?: " << (r1 > r2) << endl;
   cout << "          One >= Two?: " << (r1 >= r2) << endl;
   cout << "          One <= Two?: " << (r1 <= r2) << endl;
   cout << "          One >= One?: " << (r1 >= r1) << endl;
   cout << "          Two <= Two?: " << (r2 <= r2) << endl;


   cout << "Demonstration of Quicksort on Rationals:" << endl;

   Rational ratarr[20];

   for ( int i = 0; i < 20; i++ )
   {
      ratarr[i] = Rational(1, i%5+1);
   }

   quickSortRat( ratarr, 0, 19 );

   for ( int i = 0; i < 20; i++ )
   {
      cout << "    ratarr[" << i << "] = " << ratarr[i] << endl;
   }


   return 0;
}


// ------------------------------
// QuickSort for Rational objects
// ------------------------------

void quickSortRat( Rational * rat, int start, int end )
{
   if ( start == end )
   {
      return;
   }

   int index = partition( rat, start, end );

   if ( index == start )
   {
      quickSortRat( rat, start+1, end );
   }
   else if ( index == end )
   {
      quickSortRat( rat, start, end-1 );
   }
   else
   {
      quickSortRat( rat, start, index-1 );
      quickSortRat( rat, index+1, end );
   }

   return;
}


// -------------------------------------------
// Partition utility function for quickSortRat
// -------------------------------------------

int partition( Rational * rat, int start, int end )
{
   Rational temp;
   int newPos = start;
   int oldPos = end+1;
   bool forward = false;

   while ( oldPos != newPos )
   {
      if ( forward )
      {
	 if ( oldPos < end )
	 {
	    int i = oldPos+1;
	    while ( i < end && rat[newPos] > rat[i] ) i++;
	    {	    
	       temp = rat[i];
	       rat[i] = rat[newPos];
	       rat[newPos] = temp;
	       
	       oldPos = newPos;
	       newPos = i;
	    }
	 }
	 else 
	 {
	    oldPos = newPos;
	 }
      }
      else
      {
	 if ( oldPos > start )
	 {
	    int i = oldPos-1;
	    while ( i > start && rat[newPos] < rat[i] ) i--;
	    {	    
	       temp = rat[i];
	       rat[i] = rat[newPos];
	       rat[newPos] = temp;
	       
	       oldPos = newPos;
	       newPos = i;
	    }
	 }
	 else 
	 {
	    oldPos = newPos;
	 }
      }

      forward = !forward;
   }

   return newPos;
}