/*
 * queue-01.cc    Standard containers, std::queue, exercise 1.
 *
 * Radix sort.
 */
#include <iostream>
#include <iomanip>
#include <vector>
#include <queue>
#include <random>
using namespace std;

template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v)
{
   unsigned n{ 0 };
   for (const auto& x : v)
   {
      os << setw(4) << x << ((++n % 20 == 0) ? '\n' : '\0');
   }
   return os;
}

template<typename T>
void radixsort(vector<T>& v, int n_digits, unsigned radix = 10)
{
   vector<queue<T>> q{ radix };

   for (int d = 0; d < n_digits; ++d)
   {
      // distribute
      int divisor = static_cast<int>(pow(static_cast<double>(radix), d));
      for (const auto& x : v)
      {
	 q[(x / divisor) % radix].push(x);
      }

      // reassemble
      auto v_pos = v.begin();
      for (int i = 0; i < radix; ++i)
      {
	 while (! q[i].empty())
	 {
	    *v_pos++ = q[i].front();
	    q[i].pop();
	 }
      }
   }
}

int main()
{
   vector<int> v;

   // random number engine, the source of random numbers
   std::mt19937 rng;
   // distribution
   std::uniform_int_distribution<unsigned> uint_dist100{ 0, 100 };

   for (int i = 0; i < 200; ++i)
   {
      // the engine is passed to the function call operator of the
      // distribution to generate the next value.
      v.push_back(uint_dist100(rng));
   }

   cout << "Osorterade värden:\n" << v << endl;
   radixsort(v, 3, 10);
   cout << "Sorterade värden:\n" << v << endl;
   return 0;
}