/*
 * Purpose: This class will sort a data set using the radix sort algorithm.
 * Authors: Ben Hample, Greg Krywicki, Robert Russell
 * Date: 12/18/07
 */

import java.util.LinkedList;

public class RadixSort
{
    private static final int GROUP_TOTAL = 53;
    
   /*
     * Purpose: Determines the length of the longest Employee name for the
     * radix sort algorithm
     * Pre: The array is valid
     * Post: None
     * In: The array of Employees
     * Out: The length of the longest Employee name
     */
    private static int getLongestElementLength(Employee[] array)
    {
        int longest =0;
        
        //go through each Employee in the array
        for(int currentEmployee = 0; currentEmployee < array.length; currentEmployee++)
        {
            //longest becomes the current employee if the name is longer than longest
            if(array[currentEmployee].getName().length() > longest)
            {
                longest = array[currentEmployee].getName().length();
            }
        }
        return longest;
    } 
    
   /*
     * Purpose: Places blank spaces at the end of names shorter than the longest
     * Employee name in the array for the radix sort algorithm
    *  radix sort algorithm
     * Pre: The array is valid and the longest Employee is valid
     * Post: None
     * In: The array of Employees and the length of the longest Employee name
     * Out: The array of Employees
     */
    private static Employee[] namePadding(Employee[] array, int longest)
    {
        //go through each Employee in the array
        for(int currentEmployee = 0; currentEmployee < array.length; currentEmployee++)
        {
            //the name of the current Employee
            String empName = array[currentEmployee].getName();
            
            //concatenate blank spaces if the length is shorter than the longest
            //and keep doing it until the length is the same as the longest
            if(empName.length() < longest)
            {
                while(empName.length() != longest)
                {
                    empName += " ";
                }
                //change the name of the employee since empName is not
                //the actual name, but rather a local variable
                array[currentEmployee].setName(empName);
            }
        }
        return array;
    }
    
    /*
     * Purpose: Sorts the items in the array using the radix sort alogrithm
     * Pre: None
     * Post: The array of Employees being passed into this method is sorted
     * In: The array of Employees
     *Out: None
     */
    public static void radixSort(Employee[] array)
    {
        //make sure the array is valid before sorting
        try
        {
            validateArray(array);
        }
        catch(SortException se)
        {
            System.err.println(se);
        }
        //determine the length of the longest Employee name
        //so the radix sort knows how many times to pass through the names
        int longest = getLongestElementLength(array);
        
        //place spaces at the end of names less than the longest name so all of the names
        //are of equal length for comparision
        Employee[] paddedNames = namePadding(array, longest);
        
        //this is the array than contains a linked list in each position
        LinkedList[] listOfLinkedLists = new LinkedList[GROUP_TOTAL];
        
        //this is how many characters we are comparing
        //stringPosition is 1 less than longest due to the array positioning
        for(int stringPosition = longest - 1; stringPosition >= 0; stringPosition--)
        {

            //for this implementation, 53 linked lists are created for upper case letters,
            //lower case letters, and blank spots in a name
            for(int i = 0; i < GROUP_TOTAL; i++)
            {
                //create a new LinkedList for reference
                LinkedList<Employee> listToAdd = new LinkedList();

                //Add the above LinkedList to the listOfLinkedLists
                listOfLinkedLists[i] = listToAdd;    
            }

            //Go through each item in the array
            for(int i = 0; i < array.length; i++)
            {
                //Get the item at the ith position
                Employee item = array[i];                

                //We are comparing letters, so get the letter(character)
                //at the specified string position for comparing
                Character letter = item.getName().charAt(stringPosition);

                if(Character.isUpperCase(letter))
                {
                    ///if it is upper case, we are going to obtain the int unicode value of
                    //that character minus the value of A, which will give us the index
                    //position /for which linked list to store of this employee name in
                    int index = letter - 'A';
                    
                    //positions 1-26 are reserved for upper case letters
                    listOfLinkedLists[index + 1].add(item);
                }
                else if(Character.isLowerCase(letter))
                {
                     //if it is lower case, we are going to obtain the int unicode value of that
                    //character minus the value of a, which will give us the index position
                    //for which linked list to store of this employee name in
                    int index = letter - 'a';
                    
                    //positions 27-53 are reserved for lower case letters
                    listOfLinkedLists[27 + index].add(item);
                }
                else if (letter.equals(' '))
                {
                    //position 0 is if the character is a space, which means it is placed in the front of the array
                    listOfLinkedLists[0].add(item);
                }
            }

            //we need an array position to use when placing items in order
            int arrayPosition = 0;

            //Go through each LinkedList in the array
            for(int i = 0; i < listOfLinkedLists.length; i++)
            {
                //Get the current referenced LinkedList 
                LinkedList LL = listOfLinkedLists[i];

                //Go through each item in the list, adding it 
                //in order to the array (the initial array)
                for(int j = 0; j < LL.size(); j++)
                {                    
                    array[arrayPosition] = (Employee)LL.get(j);
                    arrayPosition++;
                }
            }
        } 
    }
    
    /*
     * Purpose: Validate the employees in the array to ensure that the characters 
     * used in each Employee name are only lower or upper case letters
     * Pre: None
     * Post: A SortException is thrown if the names cannot fulfill the criteria
     * In: The array of Employees
     * Out: None
     */
    public static  void validateArray(Employee[] array) throws SortException
    {
        //go through each Employee in the array
        for(int currentEmployee = 0; currentEmployee < array.length; currentEmployee++)
        {
            //the name of the current Employee
            String empName = array[currentEmployee].getName();
            
            //go through each character in the current Employee name
            for(int currentChar = 0; currentChar < empName.length(); currentChar++)
            {
                //the int unicode value of the current character
                int charVal = (int) empName.charAt(currentChar);
                
                //if the value is not within the unicode boundaries for upper or lower case,
                //then an exception is thrown
                if(!(charVal >= 65 && charVal <= 122) || (charVal >= 91 && charVal <= 96))
                {
                    throw new SortException("Radix Sort  --- Invalid name: " + empName + ", at array position: " + currentEmployee);
                }
            }
        }
    }
}