/*
 * Purpose: Sorts the items in the array using the quick sort algorithm iteratively
 * Authors: Ben Hample, Greg Krywicki, Robert Russell
 * Date: 12/18/07
 */

import java.util.Random;
          
public class QuickSort
{ 
    /*
     * Purpose: This method will return the index of the pivot element in the array
     * and an assumption is that it  chooses the element in the first position as the pivot
     * 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 in the partition
        Object 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: Sorts the items in the array using the quick sort algorithm iteratively
     * Pre: None
     * Post: The array of Employees being passed into this method is sorted
     * In: The array of Employees and two ints representing the first and last positions in the array
     * Out: None
     */
    public static void quickSort(Employee[] array, int first, int last)
    {
        //make sure the array is valid before sorting
        try
        {
            validateArray(array);
        }
        catch(SortException se)
        {
            System.err.println(se);
        }
        
        int pivotIndex = 1;
        
        int[] firstQueue = new int[array.length];
        int[] lastQueue = new int[array.length];

        int inPointer = 1; //location for inserting the new first and last variables
        int outPointer = 0; //location for reading first and last variables

        firstQueue[0] = first;
        lastQueue[0] = last;

        while(inPointer > outPointer)
        {
            //Get the pivot index through partitioning
            pivotIndex = partition(array, firstQueue[outPointer], lastQueue[outPointer]);

            //Remember to do the partition from firstQueue[outPointer] to pivotIndex-1
            //Store the values to be used
            if(firstQueue[outPointer] < pivotIndex-1)
            {
                firstQueue[inPointer] = firstQueue[outPointer];
                lastQueue[inPointer] = pivotIndex-1;

                inPointer++;
            }

            //Remember to do the partition from pivotIndex+1 to lastQueue[outPointer]
            //Store the values to be used
            if(pivotIndex+1 < lastQueue[outPointer])
            {
                firstQueue[inPointer] = pivotIndex+1;
                lastQueue[inPointer] = lastQueue[outPointer];
                
                inPointer++;
            }
            outPointer++;
        }
    }
    
    /*
     * 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("Quick Sort  --- Invalid name: " + empName + ", at array position: " + currentEmployee);
                }
            }
        }
    }
}