/*
 * Copyright 2013, 2014 Brenden Towey
 */

package SimpleUtils.sort;

import java.util.Comparator;

/**  Sort utilities.
 *
 * @author Brenden Towey
 */
public class Sort
{

   /**
    * Sorts an array of Comparable.  Null values are moved to the end of the
    * array by this routine, so arrays containing null values can be safely
    * sorted.
    *
    * @param <T> Any Comparable.
    * @param table The array to be sorted.
    * @return The number of non-null elements in the array.
    */
   public static <T extends Comparable<? super T>> int sort( T[] table )
   {
      int newLength = moveNullsToEnd( table );
      quickSort( table, Comparator.naturalOrder(), 0, newLength - 1 );
      return newLength;
   }

   /**
    * Moves null values to the end of an array.  This is done in
    * preparation for sorting to remove nulls from the array.  The
    * idea of moving nulls to the end of an array is synonymous with compacting
    * the array by moving all non-null elements to the beginning.
    *
    * <p>This method returns the number of non-null elements in the array.
    * The index of the last non-null element will be the one less than the
    * return value.
    *
    * @param table Table to move nulls to end.
    * @return The number of non-null elements.
    */
   public static int moveNullsToEnd( Object[] table )
   {
      int end = table.length-1;
      for( int i = 0 ;; ) {
         while( i < table.length && table[i] != null ) i++;
         if( i == table.length ) break;
         while( table[end] == null ) end--;
         if( i < end ) {
            table[i] = table[end];
            table[end] = null;
         } else
            break;
      }
      return end+1;
   }

   /**
    * A quicksort implementation for arrays.  Null values are not checked by
    * this method.  Therefore a "null safe" Comparator must be used, such
    * as {@code Comparator.nullsFirst()}, or the array range to be sorted
    * must be free of nulls.
    *
    * @param <T> Any type.
    * @param comp A Comparator for T.
    * @param table An array of T to sort.
    * @param first First element in the (sub) array to sort, inclusive.
    * @param last Last element in the (sub) array to sort, inclusive.
    */
   public static <T> void quickSort( T[] table, Comparator<T> comp, int first,
           int last )
   {
//  System.out.println( "first="+first+", last="+last+" table="+Arrays.deepToString( table ) );

      // The value of INSERT is empirically determined.  Basically smaller values
      // are assumed to be better, up to a point, then they get worse.
      // In testing, sort times are quite close, differing only by few
      // tens of milliseconds over one million elements.
      // 10 is used here as it "theorectically" should be good all other
      // things being equal, and its times were generally smaller than other
      // numbers, although only slightly.

      final int INSERT = 10;

      if( last - first < INSERT )
         insertionSort( table, comp, first, last );
      else {
         int pivot = partition( table, comp, first, last );
         quickSort( table, comp, first, pivot - 1 );
         quickSort( table, comp, pivot + 1, last );
      }
   }

   /**
    * A stable insertion sort.  This routine does not check for nulls before
    * sorting.  Therefore a "null-safe" comparator must be used, such as
    * {@code Comparator.nullsLast()}, or the array range must be free of
    * null values.
    *
    * @param <T> Any type.
    * @param table An array to be sorted.
    * @param comp A Comparator to use.
    * @param first The first element to sort, inclusive.
    * @param last The last element to sort, inclusive.
    *
    * @throws ArrayIndexOutOfBoundsException if either first or last are beyond the
    * bounds of the array table.
    * @throws NullPointerException if the array contains nulls and a "null-safe"
    * Comparator is not used.
    *
    * @throws NullPointerException if table or any element is null.
    */
   public static <T> void insertionSort( T[] table, Comparator<T> comp,
           int first, int last )
   {
      for( int i = first+1; i < last+1; i++ ) {
         T temp = table[i];
         int j = i-1;
         for( ; (j >= 0) && comp.compare( table[j], temp ) > 0; j-- ) {
            table[j+1] = table[j];
         }
         table[j+1] = temp;
      }
   }

   /**
    * Partition for quicksort.
    *
    * @param <T> Any type.
    * @param table An array to sort.
    * @param comp Comparator to use.
    * @param first Index of first element to sort, inclusive.
    * @param last Index of last element to sort, inclusive.
    * @return
    */
   private static <T> int partition( T[] table, Comparator<T> comp, final int first,
           final int last )
   {
      int pivotIndex =  getPivotIndex( table, comp, first, last );
      T pivot = table[ pivotIndex ];
      swap( table, first, pivotIndex );

      int lower = first+1;
      int upper = last;
      do {
         while( (lower < upper) && comp.compare( pivot, table[lower] ) >= 0 )
            lower++;
         while( comp.compare( pivot, table[upper] ) < 0 )
            upper--;
         if( lower < upper )
            swap( table, lower, upper );
      } while( lower < upper );
      swap( table, first, upper );
      return upper;
   }

   /**
    * Finds a pivot index by comparing up to nine values, to
    * determine the middle of those nine.
    *
    * @param <T> This works out to "anything that is Comparable"
    * @param table Array of Comparable.
    * @param first index of array to start looking for pivot.
    * @param last index of array of last value to consider for pivot.
    * @return The index of the pivot to use.s
    */
   private static <T> int getPivotIndex( T[] table, Comparator<T> comp,
           int first, int last )
   {
      int middle = (last+first) >>> 1;  // divide by 2

      // if less than 9 total just return the middle one
      if( last - first < 9 ) return middle;

      // compute an offset to create a wider range of values
      int offset = (last-first) >>> 3;  // divide by 8

      // if 9 or more then we have nine values we can consider
      int mid1 = mid( table, comp, first, first + offset, first + offset * 2 );
      int mid2 = mid( table, comp, middle - offset, middle, middle + offset );
      int mid3 = mid( table, comp, last, last - offset, last - offset * 2 );
      return mid( table, comp, mid1, mid2, mid3 );
   }

   /**
    * Find the middle value out of three, for an array of Comparable.
    *
    * @param <T> Any type with a Comparator.
    * @param table A table of type T.
    * @param comp A Comparator for type T.
    * @param first index of first element to compare.
    * @param second index of second element to compare.
    * @param third index of third element to compare.
    * @return index of middle element.
    */
   // package private for testing
   static <T> int mid( T[] table, Comparator<T> comp, int first, int second, int third )
   {
      T firstv = table[first];
      T secondv = table[second];
      T thirdv = table[third];

      // return (a > b) ^ (a > c) ? a : (a > b) ^ (b > c) ? c : b;
      boolean aGTb = comp.compare( firstv, secondv ) > 0;
      boolean aGTc = comp.compare( firstv, thirdv ) > 0;
      boolean bGTc = comp.compare( secondv, thirdv ) > 0;

      return (aGTb ^ aGTc) ? first : (aGTb ^ bGTc) ? third : second;
   }

   /**
    * Swaps two references in an array.
    *
    * @param table Array to swap elements.
    * @param s1 index of first element to swap.
    * @param s2 index of second element to swap.
    *
    * @throws IndexOutOfBoundsException if either index is outside of the
    * bounds of the array.
    */
   public static void swap( Object[] table, int s1, int s2 ) {
      Object temp = table[s1];
      table[s1] = table[s2];
      table[s2] = temp;
   }
}