// radix_sort.cpp
// Glenn G. Chappell
// 19 Oct 2008
//
// For CS 311 Fall 2009
// Radix Sort Using Forward Iterators

#include <iostream>
using std::cout;
using std::endl;
using std::cin;
#include <vector>  // for std::vector


// radixSort
// Sorts a sequence of 5-digit nonnegative ints, using Radix Sort.
// Requirements on Types:
//     FDIter must be a forward iterator type.
//     FDIter must have value type int.
// Pre:
//     [first, last) is a valid range.
//     Items in [first, last) are all in [0, 99999]
//      (5-digit nonnegative ints)
// Post:
//     [first, last) contains the same items as it did initially,
//      but now sorted by < (in a stable manner).
template <typename FDIter>
void radixSort(FDIter first, FDIter last)
{
    enum { RADIX_SORT_NUM_PLACES = 5 };  // Number of Radix Sort passes
    int powerOfTen = 1;                  // 10 ^ place

    for (int place = 0; place < RADIX_SORT_NUM_PLACES; ++place)
    {
        // Do a Pigeonhole Sort of the data by the 10^place digit
        enum { NUM_BUCKETS = 10 };  // Keys are 0 .. NUM_BUCKETS-1
        std::vector<std::vector<int> > buckets(NUM_BUCKETS);
                                    // Vector of buckets

        // place each item in the appropriate bucket (stable!)
        for (FDIter it = first; it != last; ++it)
        {
            buckets[((*it)/powerOfTen) % 10].push_back(*it);
        }

        // Copy each bucket back to original list, one after the other
        FDIter copyBack = first;
        for (int i = 0; i < 10; ++i)
        {
            copyBack =
                std::copy(buckets[i].begin(), buckets[i].end(), copyBack);
        }

        // Pigeonhole Sort ends here

        // Move to next power of 10
        powerOfTen *= 10;
    }
}


// main
// Test function radixSort (takes iterators)
int main()
{
    const int SIZE = 11;
    //int arr[SIZE] = { 5, 3, 2, 8, 5, 9, 10, 4, 6, 1, -4};
    // Negative values not allowed
    int arr[SIZE] = { 35, 87903, 1, 98, 4344, 281, 271, 180, 0, 50, 50 };
    radixSort(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;
}