#define UNIT r6_radix
#include <vector>
#include "test_main.cpp"

int digit( unsigned num, int digit, int base )
{
    while ( digit --> 0 ) num /= base;
    return num % base;
}

int digit_count( unsigned num, int base )
{
    int digits = 0;

    while ( num )
    {
        ++ digits;
        num /= base;
    }

    return digits;
}

void sort_by_digit( std::vector< unsigned > &to_sort,
                    int position, int base )
{
    std::vector< int > b_size( base, 0 ),
                       b_start( base, 0 ),
                       b_index( base, 0 );

    std::vector< unsigned > sorted( to_sort.size() );

    for ( int num : to_sort )
        b_size[ digit( num, position, base ) ] ++;

    for ( int i = 1; i < base; ++i )
        b_start[ i ] = b_start[ i - 1 ] + b_size[ i - 1 ];

    for ( int num : to_sort )
    {
        int d = digit( num, position, base );
        sorted[ b_start[ d ] + b_index[ d ] ] = num;
        ++ b_index[ d ];
    }

    std::swap( to_sort, sorted );
}

void radixsort( std::vector< unsigned > &to_sort, int base )
{
    if ( to_sort.empty() )
        return;

    unsigned max = *std::max_element( to_sort.begin(), to_sort.end() );
    int max_digits = digit_count( max, base );

    for ( int d = 0; d < max_digits; ++d )
        sort_by_digit( to_sort, d, base );
}