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

public class InsertionSort 
{    
    /*
     * Purpose: Sorts the items in the array using the insertion sort algorithm
     * Pre: None
     * Post: The array is sorted in ascending order
     * In: The array containing elements
     * Out: None
     */
    public static void insertionSort(Employee[] array)
    {
        //make sure the array is valid before sorting begins
        try
        {   
            validateArray(array);
        }        
        catch(SortException se)
        {
            System.err.println(se);
        }
        
        for(int unsorted = 0; unsorted < array.length; unsorted++)
        {
            //store the first element in the unsorted region
            Employee nextElement = array[unsorted];
            
            int position = unsorted;
            
            //go backwards towards the front of the array and keep swaping elements until the 
            //element stored from earlier is greater than the one it would potnentially be swapped with
            while(position > 0 && array[position - 1].compareTo(nextElement) > 0)
            {
                array[position] = array[position - 1];
                position--;
            }
            
            //store the item in the array at index 'position''
            array[position] = nextElement;
        }
    }
      
    /*
     * 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("Insertion Sort  --- Invalid name: " + empName + ", at array position: " + currentEmployee);
                }
            }
        }
    }
}