// quicksort1.cpp
// Glenn G. Chappell
// 14 Oct 2009
//
// For CS 311 Fall 2009
// Quicksort
// Version #1: Basic
// Uses forward iterators

#include <iostream>
using std::cout;
using std::endl;
using std::cin;
#include <algorithm>
using std::iter_swap;


// partition
// Partitions a sequence about a given pivot.
// Returns the new pivot position.
// 
// NOTE: This is the partition algorithm in the text.
//
// Requirements on Types:
//     FDIter must be a forward iterator type.
//     operator< must be a total order on the value type of FDIter.
// Pre:
//     [first, last) is a valid nonempty range.
//     pivotIter is an iterator in the range [first, last).
// Post:
//     [first, last) contains the same items as it did initially,
//      but now each ITEM before pivotIter has ITEM < *pivotIter,
//      and each ITEM after pivotIter has !(ITEM < *pivotIter).
//     pivotIter lies in [first, last) and references an item with
//      the same value as *pivotIter before the function call.
template <typename FDIter>
void partition(FDIter first, FDIter last, FDIter & pivotIter)
{
    // Put the pivot at the start of the list
    iter_swap(first, pivotIter);

    // Now "first" points to the pivot

    // Make the "left list": list of items less than pivot
    FDIter leftFinal = first;  // points to final item in left list
    FDIter check = first;      // item to check
    for (++check;              // start after pivot, iterate through list
         check != last;
         ++check)
    {
        if (*check < *first)              // if item < PIVOT
        {
            ++leftFinal;                  // move up end mark
            iter_swap(leftFinal, check);  // and put item in left list
        }
    }

    // Note new pivot position, for caller, and put pivot there
    pivotIter = leftFinal;
    iter_swap(first, pivotIter);
}


// partition_ALT
// Partitions a sequence about a given pivot.
// Returns the new pivot position.
// 
// NOTES:
//   - This is another common parition algorithm.
//   - We could do this with bidirectional iterators, but it gets a
//      little messy.
//
// Requirements on Types:
//     RAIter must be a random-access iterator type.
//     operator< must be a total order on the value type of RAIter.
// Pre:
//     [first, last) is a valid nonempty range.
//     pivotIter is an iterator in the range [first, last).
// Post:
//     [first, last) contains the same items as it did initially,
//      but now each ITEM before pivotIter has !(*pivotIter < ITEM),
//      and each ITEM after pivotIter has !(ITEM < *pivotIter).
//     pivotIter lies in [first, last) and references an item with
//      the same value as *pivotIter before the function call.
template <typename RAIter>
void partition_ALT(RAIter first, RAIter last, RAIter & pivotIter)
{
    // Put the pivot at the start of the list
    iter_swap(first, pivotIter);

    // Now "first" points to the pivot

    // Iterator left: all items before it have !(PIVOT < ITEM)
    RAIter left = first+1;
    // Iterator right: all items after it have !(ITEM < PIVOT)
    RAIter right = last-1;
    // In the loop below, we stop when items before left + items
    //  after right are the entire list.

    while (left <= right)
    {
        // Move left & right in as far as we can
        if (!(*first < *left))        // if *left <= PIVOT
            ++left;
        else if (!(*right < *first))  // if *right >= PIVOT
            --right;
        // If we can move neither left nor right, then swap their items
        else
        {
            iter_swap(left, right);
            ++left;
            --right;
        }
    }

    // Note new pivot position, for caller, and put pivot there
    pivotIter = right;
    iter_swap(first, pivotIter);
}


// quicksort
// Sorts a sequence, using Quicksort.
// Recursive.
// Requirements on Types:
//     FDIter must be a forward iterator type.
//     operator< must be a total order on the value type of FDIter.
// Pre:
//     [first, last) is a valid range.
// Post:
//     [first, last) contains the same items as it did initially,
//      but now sorted by <.
template <typename FDIter>
void quicksort(FDIter first, FDIter last)
{
    // BASE CASE
    if (first == last)
        return;

    // RECURSIVE CASE

    // Simple pivot choice: let the pivot be the first item
    FDIter pivotIter = first;

    // Do partition & recursive sorts
    partition(first, last, pivotIter);
    // NOTE: To use the alternate partition algorithm, replace "partition"
    //  in the above line with "partition_ALT", and note that this function
    //  now requires random-access iterators.
    quicksort(first, pivotIter);
    FDIter afterPivot = pivotIter;  // Make iter to item just after pivot
    ++afterPivot;
    quicksort(afterPivot, last);
}


// main
// Test function quicksort (takes iterators)
int main()
{
    const int SIZE = 11;
    int arr[SIZE] = { 5, 3, 2, 8, 5, 9, 10, 4, 6, 1, -4};
    quicksort(arr, arr+SIZE);
    for (int i = 0; i < SIZE; ++i)
        cout << arr[i] << " ";
    cout << endl;
    cout << endl;

    cout << "Press ENTER to quit ";
    while (cin.get() != '\n') ;

    return 0;
}