// pigeonhole_sort.cpp
// Glenn G. Chappell
// 19 Oct 2008
//
// For CS 311 Fall 2009
// Pigeonhole Sort Using Forward Iterators
// Preliminary to Radix Sort

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


// pigeonholeSort
// Sorts a sequence of 1-digit nonnegative ints, using Pigeonhole 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, 9]
//      (1-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 pigeonholeSort(FDIter first, FDIter last)
{
    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].push_back(*it);
    }

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


// main
// Test function pigeonholeSort (takes iterators)
int main()
{
    const int SIZE = 11;
    //int arr[SIZE] = { 5, 3, 2, 8, 5, 9, 10, 4, 6, 1, -4};
    // Values must be 0..9
    int arr[SIZE] = { 6, 1, 9, 5, 8, 8, 5, 0, 2, 1, 5 };
    pigeonholeSort(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;
}