/*
 * Titus Winters - titus@cs.ucr.edu
 * CS 14 - Fall 2003 
 * Radix Sort - Sample Solution
 * 
 * This is a demonstration of two things:
 *  1 - Radix sort, an O(n) sorting algorithm
 *  2 - The power of STL
 *
 */

#include <list>
#include <vector>
#include <iostream>
#include <cmath>

using namespace std;

// Powers of 10 up to 1 billion, the largest power of 10 that fits in
// an unsigned int.
const unsigned int powersOf10[] = {1,
				   10,
				   100,
				   1000,
				   10000,
				   100000,
				   1000000,
				   10000000,
				   100000000,
				   1000000000};
			  

// Return the dth digit of n
inline int dthDigit(int n, int d)
{
  // Divide by 10^d to "shift the number right" by d places
  // Then mod by 10 to cut off everything greater than the new 1s digit.
  return (n / powersOf10[d]) % 10;
}

int main()
{
  // What we will use when our numbers aren't in buckets
  list<unsigned int> nums;

  // The buckets we will use for the sorting
  vector<list<unsigned int> > buckets;
  buckets.resize(10);

  // A temp for reading in
  unsigned int num;

  // Intialize max to the lowest valid number.  This is legal
  // because we know that we will only be getting non-negative values,
  // so even if everything is as low as possible, we have guessed correct.
  // Generally YOU CANNOT initialize a "max" value to 0.
  unsigned int maxVal = 0;
  while (cin >> num)
    {
      // Track maximum
      if (num > maxVal) 
	maxVal = num;

      // Add to list.  This is O(1), since we have tail pointers and a 
      // doubly linked list.
      nums.push_back(num);
    }

  
  // Do the sorting
  // Find the maximum number of times that we need to do the bucketing.
  // This is equal to the maximum number of digits in any of our input.
  // THAT is equal to the log base 10 of the maximum value, rounded down.
  unsigned int maxDigit = (unsigned int)log10((double)maxVal);
  
  // This loops at most 10 times
  for (unsigned int digit = 0; digit <= maxDigit; ++digit)
    {
      // This loops O(n) times 
      for (list<unsigned int>::iterator i = nums.begin(); i != nums.end(); ++i)
	{
	  // Figure out what bucket to put this into
	  unsigned int bucket = dthDigit(*i, digit);

	  // This is O(1)
	  // Put it into that bucket
	  buckets[bucket].push_back(*i);
	}

      // Now put all the buckets back into the nums list so we can start
      // again.
      // This is O(n)
      nums.clear();
      
      // This happens exactly 10 times
      for (unsigned int i = 0; i < 10; ++i)
	{
	  // This is a much simpler, and slightly faster, way of 
	  // doing what the code below does.  This runs in O(n)
	  // It inserts ALL of buckets[i] before nums.end() (so, 
	  // take the ith bucket and add it to the end of nums
	  nums.insert(nums.end(), buckets[i].begin(), buckets[i].end());

	  /*
	  // This is O(n) (roughly n/10 on average)
	  for (list<unsigned int>::iterator j = buckets[i].begin(); 
	       j != buckets[i].end(); ++j)
	    {
	      // This is O(1)
	      nums.push_back(*j);
	    }
	  // This is O(n)
	  */

	  buckets[i].clear();

	}
    }
  
  // Print out the results, in O(n)
  for (list<unsigned int>::iterator i = nums.begin(); i != nums.end(); ++i)
    {
      cout << *i << endl;
    }
  
}