/*
   File : radix_sort.c
   Author : Samuel Hiard
   
   This program is used to sort an array of positive numbers using the radix sort algorithm.
   
   Parameters : N  : The amount of numbers to sort
                n* : Each individual number
                b  : The base

*/

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <string.h>

#define DEBUG 0 //Set to 1 for debug verbose

/*
Used to display the usage of the program

parameters : prog_name : The program name
returns    : nothing
*/
void usage(char* prog_name)
{
	printf("Usage : %s <N> <n1> <n2> ... <nN> <B>\r\n",prog_name);
	printf("where\r\n");
	printf("N = Amount of numbers to sort (strictly positive, in decimal)\r\n");
	printf("n# = #th number to sort (positive, in decimal)\r\n");
	printf("B = The base of the sort (10 for decimal, 2 for binary, ...)\r\n");
}

/*
Used to return the ordinal suffix of a number

parameters : s : a pointer to an array of 2 characters that exists outside the function
             i : the cardinal number
returns    : a pointer to the 2 character-array that was filled with the ordinal suffix
*/
char* ith(char* s, long i)
{
	if(i%10 == 1)
		strcpy(s,"st");
	else if(i%10 == 2)
		strcpy(s,"nd");
	else if(i%10 == 3)
		strcpy(s,"rd");
	else
		strcpy(s,"th");
  if(i > 10 && i < 20)
  	strcpy(s,"th");
	
	return s;
}

/*
Main function

parameters : argc   : The number of arguments (incl. program name)
             argv[] : An array containing the arguments
returns    : and integers indicating programm success or failure
*/
int main(int argc, char* argv[])
{
	
	//Variable declaration
	char* endp;
	char tab[2];
	long i, j, k, N, max, base, NbIter, divisor, rest, index;
	long* lArrayOfNumbers, *lArrayOfIndexes;
	long** tempArray;
	
	//Check the number of parameters
	if(argc < 4)
  {
  	usage(argv[0]);
  	return EXIT_FAILURE;
  }
  
  //Retrieving first parameter N
  N = strtol(argv[1],&endp,10);
  if(errno != 0 || strlen(endp) > 0)
  {
  	printf("First argument <%s> is not a number or is too large\r\n",argv[1]);
  	return EXIT_FAILURE;
  }
  else
  {
  	if(DEBUG)
  		printf("Amount of numbers to sort : %ld\r\n",N);
  }
  
  if(N <= 0)
  {
  	printf("First argument should be a strictly positive number\r\n");
  	return EXIT_FAILURE;
  }
  else
  {
  	if(N != (argc - 3))
  	{
  		printf("The number of arguments should match the number of integers to sort");
  	}
  }
  
  //Allocating array of numbers
  lArrayOfNumbers = malloc(N*sizeof(long));
  if(lArrayOfNumbers == NULL)
  {
  	printf("Problem with malloc\r\n");
  	return EXIT_FAILURE;
  }
  
  //Retrieving numbers to sort and finding the maximum value
  max = -1;
  for(i = 0; i < N; i++)
  {
  	lArrayOfNumbers[i] = strtol(argv[i+2],&endp,10);
  	if(errno != 0 || strlen(endp) > 0)
  	{
  		printf("%d%s argument <%s> is not a number or is too large\r\n",i+1,ith(tab,i+1),argv[i+2]);
  		return EXIT_FAILURE;
  	}
  	else
  	{
  		if(lArrayOfNumbers[i] < 0)
  		{
  			printf("%d%s argument is not positive\r\n",i+1,ith(tab,i+1),argv[i+2]);
  			return EXIT_FAILURE;
  		}
  		if(DEBUG)
  			printf("%d%s number to sort : %ld\r\n",i+1,ith(tab,i+1),lArrayOfNumbers[i]);
  		if(lArrayOfNumbers[i] > max)
  			max = lArrayOfNumbers[i];
  	}
  }
  if(DEBUG)
  	printf("(Info) Maximum number is %ld\r\n",max);
  
  
  //Retrieving base parameter
  base = strtol(argv[i+2],&endp,10);
  if(errno != 0 || strlen(endp) > 0)
  {
  		printf("%d%s argument <%s> is not a number or is too large\r\n",i+1,ith(tab,i+1),argv[i+2]);
  		return EXIT_FAILURE;
  }
  if(base <= 1)
  {
  	printf("Base should be a positive number greater than 1");
  	return EXIT_FAILURE;	
  }
  if(DEBUG)
  	printf("Base for sort is %ld\r\n",base);
  
  //Calculating the number of iterations
  NbIter = 0;
  while(max > 0)
  {
  	max = max/base;
  	NbIter++;
  }
  if(NbIter == 0)
  	NbIter = 1;
  
  if(DEBUG)
  	printf("(Info) Number of iterations : %d\r\n",NbIter);
  
  
  //Allocating the temp array that will contain the numbers currently sorted and the array of indexes
  tempArray = (long**)malloc(base*sizeof(long*));
  lArrayOfIndexes = (long*)malloc(base*sizeof(long));
  if(tempArray == NULL || lArrayOfIndexes == NULL)
  {
  	printf("Problem with malloc (2)\r\n");
  	return EXIT_FAILURE;
  }
  for(i = 0; i < base; i++)
  {
  	tempArray[i] = (long*)malloc(N*sizeof(long));
  	if(tempArray[i] == NULL)
  	{
  		printf("Problem with malloc (tempArray[%d])\r\n",i);
  		return EXIT_FAILURE;
  	}
  }
  
  
  //This is where the sorting actually occurs
  divisor = 1;
  for(i = 0; i < NbIter; i++)
  {
  	
  	//Reset the array of indexes
  	for(j = 0; j < base; j++)
  	  lArrayOfIndexes[j] = 0;
  	 
  	//Put each number in its appropriate bin  
  	for(j = 0; j < N; j++)
  	{
  		rest = (lArrayOfNumbers[j]/divisor)%base;
  		tempArray[rest][lArrayOfIndexes[rest]] = lArrayOfNumbers[j];
  		lArrayOfIndexes[rest]++;
  	}
  	
  	//Take numbers from each bin and put them back in the main array
  	index = 0;
  	for(j = 0; j < base ; j++)
  	{
  		for(k = 0; k < lArrayOfIndexes[j]; k++)
  		{
  			lArrayOfNumbers[index] = tempArray[j][k];
  			index++;
  		}
  	}
  	
  	divisor *= base;	
  	
  }
  
  //Display the result
  printf("The sorted array is \r\n");
  for(i = 0; i < N; i++)
  {
  	printf("%d ",lArrayOfNumbers[i]);
  }
  printf("\r\n");
  
	return EXIT_SUCCESS;
}