/*
 * Purpose: Sorts the items in the array using the quick sort algorithm recursively
 * Authors: Ben Hample, Greg Krywicki, Robert Russell
 * Date: 12/18/07
 */
import java.util.Random;
                                                                                                                 
public class QuickSortRec
{
    //an instance of the Random class to random generate the pivot
    private static Random rand = new Random(); 
    
    /*
     * Purpose: Constructor
     * Pre: None
     * Post: An instance of QuickSortRec is created
     * In: The array of Employees
     * Out: None
     */
    public QuickSortRec(Employee[] array)
    {
        //make sure the array is valid before sorting
        try
        {
            validateArray(array);
        }
        catch(SortException se)
        {
            System.err.println(se);
        }
        //sort the array, 0 is the first position and array.length -1 is the last position
        quickSortRec(array, 0, array.length -1);
    }
    /*
     * Purpose: This method will return the index of the pivot element in the partition
     * Pre: The array being passed in is valid
     * Post: The array being passed in is partitioned and sorted
     * In: The array of  Employees and two ints representing the first and last positions of the partition
     * Out: None
     */
    private static int partition(Employee[] array, int first, int last)
    {
        //first element of the partition
        Employee pivot = array[first];
        
        //the index value of S1 initially is the same of the pivot
        int lastS1 = first;
      
        
        //go through each element in the partition to determine if it 
        //greater or less /than the pivot
        for(int firstUnknown = first +1; firstUnknown <= last; firstUnknown++)
        {
            //elements less than pivot go into S1
            if(array[firstUnknown].compareTo(pivot) < 0)
            {
                //lastS1 is incremented and item in the position of the value
                //of lastS1 is swapped with the current element so the current
                //element is within the section S1
                lastS1++;
                
                Employee  item = array[firstUnknown];
                
                array[firstUnknown] = array[lastS1];
                array[lastS1] = item;
            }
            //no action at all implies it will be greater than the pivot and will be
            //in S2, which means it will be in the back end of the partition
        }

        //pivot is swapped with the last element in S1 so the pivot is after the elements
        //it is greater than and before the elements it is greater than
        Employee firstItem = array[first];
        
        array[first] = array[lastS1];
        array[lastS1] = firstItem;
        
        return lastS1;
    } 

    /*
     * Purpose: This method will return the index of the pivot element in the partition
     * by determining the pivot randomly
     * Pre: The array being passed in is valid
     * Post: The pivot has been selected and placed in the first position of the partition
     * In: The array of  Employees and two ints representing the first and last positions of the partition
     * Out: None
     */
    private static int partitionRand(Employee[] array, int first, int last)
    {
        //obtain and a random number and add the first position to it so the pivot
        //is within range of the partition in the array
        int random = rand.nextInt(last-first);
        int pivotIndex = random + first; 
        
        //the pivot is then swapped with the first element in the partition
        Employee pivot = array[pivotIndex];
        Employee firstObj = array[first];    
        array[first] = pivot;
        array[pivotIndex] = firstObj;

        //the partition is the same as before, so call this method
        return partition(array, first, last);
    }
    
    /*
     * Purpose: Sorts the items in the array using the quick sort algorithm recursively
     * Pre: None
     * Post: The array of Employees being passed into this method is sorted
     * In: The array of objects and two ints representing the first and last positions in the array
     * Out: None
     */
    private static void quickSortRec(Employee[] array, int first, int last)
    {  
        //once first is greater than last, there is nothing left to partition and the recursion is done
        if(first < last)
        {
            int pivotIndex = partitionRand(array, first, last);          

            quickSortRec(array, first, pivotIndex-1);
            quickSortRec(array, pivotIndex+1, last);            
        }        
    }  
    
    /*
     * 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
     */
    private 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("Insertion Sort  --- Invalid name: " + empName + ", at array position: " + currentEmployee);
                }
            }
        }
    }
}