// Implementing Quicksort with stacks
// Algorithms from Data Structure Techniques by Thomas A. Standish (25-27)
// Code by Nick Cash

#include <cstdlib>
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

// the range of integers we randomly generate
#define RANDOM_LOW  0
#define RANDOM_HIGH 999

// Uncomment for comprehensive output
// Print out stack values, swaps, and i/j steps for partition
// Note: Increases the time of the sort, so the time will not be accurate
// #define COMPREHENSIVE_OUTPUT

// Uncomment to print the sorted and unsorted vectors
#define PRINT_VECTORS

// for use on the stack
struct sPair
{
   int left;
   int right;
};

// function prototypes
int    RandomInt        ( int low, int high );
void   GenerateNumbers  ( const int & x, vector<int>& v );
void   PrintTable       ( const int & x, vector<int>& v );
void   Partition        ( vector<int>& v, const int& L, const int& R, sPair& less, sPair& more );

// QuickSort a vector of integers of of size length
void QuickSort( const int & size, vector<int>& v )
{
   stack<sPair> S;          // S is the stack that holds the order of partitions
   sPair x;                 // x is a pair of integers containing the interval less then v[L]
   sPair y;                 // y is a pair of integers containing the interval greater then v[L]
   int L = 0, R = (size-1); // L is the left most number, R is the rightmost
   
   // loop until the code breaks
   while ( true )
   {
         x.left = x.right = y.left = y.right = 0;
         Partition(v, L, R, x, y);

         // examine intervals
         if ( (x.right - x.left) > (y.right - y.left) )
         {
           S.push(x); // put x on the stack to be done later
           L = y.left;
           R = y.right;
         }
         else
         {
           S.push(y); // put x on the stack to be done later
           L = x.left;
           R = x.right;        
         }

         while ( R <= L )
         {
             if (S.empty()) // terminate on empty stack
              return;
              
             // grab data (store in x temporarily) and pop
             x = S.top();
             S.pop();

#ifdef COMPREHENSIVE_OUTPUT
             cout << "\nX.left: " << x.left << ", X.right: " << x.right << endl;
#endif
             
             L = x.left;
             R = x.right;
         }
   }
   
   
}

void Partition ( vector<int>& v, const int& L, const int& R, sPair& less, sPair& more )
{
  int i = L, j = R;

  // loop until we exit the algorithm. Alternate between decreasing j and increasing i
  while ( true )
  {
      while ( v[j] >= v[i] && (j > 0) )
       j--;

#ifdef COMPREHENSIVE_OUTPUT
      cout << "A: j = " << j << ", i = " << i << endl;
      cout << "A: v[j] = " << v[j] << ", v[i] = " << v[i] << endl;
#endif

      // swap?
      if ( j > i && (v[j] != v[i]))
      {
         int temp = v[j];
         v[j] = v[i];
         v[i] = temp;
         
#ifdef COMPREHENSIVE_OUTPUT
      cout << "SWAP A: j = " << j << ", i = " << i << endl;
      cout << "SWAP A: v[j] = " << v[j] << ", v[i] = " << v[i] << endl;
#endif
      }
      else // guess not, set intervals
      {
          less.left = L;
          less.right = i-1;

          more.left = i+1;
          more.right = R;
          return;
      }

      while ( v[i] <= v[j] && (i < R))
       i++;

#ifdef COMPREHENSIVE_OUTPUT
      cout << "B: j = " << j << ", i = " << i << endl;
      cout << "B: v[j] = " << v[j] << ", v[i] = " << v[i] << endl;
#endif

      // swap?
      if ( j > i && (v[j] != v[i]))
      {
         int temp = v[j];
         v[j] = v[i];
         v[i] = temp;

#ifdef COMPREHENSIVE_OUTPUT
      cout << "SWAP B: j = " << j << ", i = " << i << endl;
      cout << "SWAP B: v[j] = " << v[j] << ", v[i] = " << v[i] << endl;
#endif
      }
      else // guess not, set intervals
      {
          less.left = L;
          less.right = j-1;

          more.left = j+1;
          more.right = R;
          return;
      }
      
  }
}

int main( void )
{
    int x;             // specified by user, number of random numbers to sort
    vector<int> table; // array/table of random numbers

    // timer variables
    time_t start, end;
    
    // seed random num gen with time
    srand(time(NULL));

    // loop until the user enters 0
    while ( true )
    {
        cout << "\nHow many random numbers (between " << RANDOM_LOW << " and " << RANDOM_HIGH << ") shall we sort?\n";
        cin >> x;

        // We need at least 2 numbers
        if ( x <= 1 )
         break;

        time(&start);
        GenerateNumbers( x, table );
        time(&end);

        cout << "\n\n" << x << " random integers generated in " << difftime(end,start) << " seconds. Sorting...\n\n";

#ifdef PRINT_VECTORS
        cout << "\nUnsorted: ";
        PrintTable( x, table );
#endif

        // do the actual sorting
        time(&start);
        QuickSort(x, table);
        time(&end);

#ifdef PRINT_VECTORS
        cout << "\nSorted: ";
        PrintTable( x, table );
#endif

        cout << "\n\nTime: " << difftime(end,start) << endl << endl;
    }

    cin.get();
    return EXIT_SUCCESS;
}

// Random int between low and high
int RandomInt( int low, int high )
{
   int num = rand() % (high+1);

   num = (num < low ? low : (num > high ? high : num ) );
 
   return num;
}

// generate x random numbers and put them into an integer table
void GenerateNumbers( const int & x, vector<int>& v )
{
     if ( v.size() > 0 )
      v.clear();

     // the test case from the book
     if ( x == 9 )
     {
      v.insert( v.begin(), 79 );
      v.insert( v.begin(), 28 );
      v.insert( v.begin(), 57 );
      v.insert( v.begin(), 96 );
      v.insert( v.begin(), 35 );
      v.insert( v.begin(), 84 );
      v.insert( v.begin(), 13 );
      v.insert( v.begin(), 62 );
      v.insert( v.begin(), 41 );
     }
     else if ( x == 11 ) // test case in the book, plus two nondistinct random numbers
     {
      int temp = RandomInt( RANDOM_LOW, RANDOM_HIGH );
      
      v.insert( v.begin(), temp);
      v.insert( v.begin(), 79 );
      v.insert( v.begin(), 28 );
      v.insert( v.begin(), 57 );
      v.insert( v.begin(), 96 );
      v.insert( v.begin(), 35 );
      v.insert( v.begin(), temp);
      v.insert( v.begin(), 84 );
      v.insert( v.begin(), 13 );
      v.insert( v.begin(), 62 );
      v.insert( v.begin(), 41 );
     }
     else
      for ( int i = 0; i < x; i++ )
       v.insert( v.end(), RandomInt( RANDOM_LOW, RANDOM_HIGH ) );
}

// Loop through and print values
void PrintTable( const int & x, vector<int>& v )
{
     cout << endl;
     cout << "[ ";
     
     for ( int i = 0; i < x; i++ )
      cout << v[i] << " ";
      
     cout << "]\n";
}