/*
 *  Draco Econometrics
 *  Copyright (C) 2006-2007 Approximatrix, LLC
 *  http://www.approximatrix.com
 *  
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

package com.approximatrix.draco.math;

import java.util.Random;

/** Implements Custom sort routines because the new indices of each entry are
 * needed and the java sorts do not supply these.  Quicksort is used by default,
 * but can result in a StackOverflowError if too many entries are identical.
 * In the case of this error, the routine defaults to a rock-solid bubble sort,
 * which is also crazy-slow.
 * 
 * @see http://maven.smith.edu/~thiebaut/java/sort/quicks
 * @author Jeffrey Armstrong
 *
 */
public class CustomSort {

	/** The prefered quicksort pivot selection technique
	 *  1 - first element of partition
	 *  2 - NOT IMPLEMENTED smart selection
	 *  3 - random selection
	 */
	private static final int METHOD = 3;
	
	/** Random number generator needed for quicksort method 3
	 */
	private static Random random_gen = null;

	/** Routine will perform an in-place sort of the array passed in.  The
	 * elements of array must all be the same type and implement the Comparable
	 * interface, although null entries are also allowed.
	 * 
	 * @param array the array to sort, which will be modified by the routine
	 * @return an array of integers specifying the original indices of each new entry
	 */
	public static int[] QuickSort(Object[] array) {
		int[] indices = new int[array.length];
		for(int i=0;i<indices.length;i++) indices[i] = i;

		if(METHOD == 3)
			random_gen = new Random();
		
		try {
			QuickSort(array,0,array.length-1,0,indices);
		} catch(StackOverflowError soe) {
			BubbleSort(array,indices);
		}
		
		random_gen = null;

		return indices;
	}

	/** Simple entry swap routine that also updates the indices array
	 * 
	 * @param A the array of data
	 * @param l the first index of the data to swap
	 * @param r the other index of the data to swap
	 * @param indices the placement index array
	 */
	private static void Swap(Object[] A, int l, int r, int[] indices) {
		Object temp = A[l];
		A[l]=A[r];
		A[r]=temp;
		
		int ti = indices[l];
		indices[l] = indices[r];
		indices[r] = ti;
	}

	/** Function for determining the pivot point necessary for quick sort.  Chooses
	 * a pivot based on the setting of the METHOD variable.  Requires data to
	 * be passed in in case the smart choice option (which is not implemented)
	 * is selected.
	 * 
	 * @param A the array of data 
	 * @param l the left bound of the partition
	 * @param r the right bound of the partition
	 * @return the index of the pivot point
	 */
	private static int FindPivot(Object[] A, int l, int r)
	{
		switch(METHOD) {
			case 1: // Pivot about first element (slowest theoretically)
				return 1;
			case 2: // Actual selection - not implemented
				return 1; // For now...
			case 3: // Random selection
				return l + random_gen.nextInt(r-l+1);
			default:
				return l;
		}

	}

	/** Perfoms all quicksort partitioning operations.  Find a textbook to determine
	 * why this works...
	 * 
	 * @param A the array of data  
	 * @param l the left bound of the partition
	 * @param r the right bound of the partition
	 * @param indices the placement index array
	 * @return the index of the pivot point used
	 */
	private static int Partition(Object[] A, int l, int r, int[] indices)
	{
		int pivotpos;

		pivotpos = FindPivot(A,l,r);
		Swap(A,l,pivotpos,indices);
		pivotpos = l;
		Object pivot = A[pivotpos];

		for(int i = l+1; i <= r; i++) {
			try {
				if(A[i] == null && pivot != null) {
					pivotpos++;
					Swap(A,pivotpos,i,indices);
				} else if(pivot == null) {
					// Nothing...
				} else if (((Comparable)A[i]).compareTo(pivot) < 0) {
					pivotpos++;
					Swap(A,pivotpos,i,indices);
				}
			} catch (ClassCastException cce) {
				System.err.println("Error in CustomSort - cannot cast as Comparable - Partition routine");
				System.err.print("Element: ");
				System.err.println(i);
				cce.printStackTrace();
			}

		}
		Swap(A,l,pivotpos,indices);
		return pivotpos;
	}

	/** Actual routine for performing the quicksort
	 * 
	 * @param A the array of data  
	 * @param l the left bound of the partition, set to zero for first pass
	 * @param r the right bound of the partition, set to last array index for first pass
	 * @param threshold hmmmm...
	 * @param indices the placement index array
	 */
	private static void QuickSort(Object[] A, int l,int r, int threshold, int[] indices)
	{
		int pivot;

		if (r-l>threshold) {
			pivot = Partition(A,l,r,indices);

			QuickSort(A,l,pivot-1,threshold,indices);
			QuickSort(A,pivot+1,r,threshold,indices);
		}
	}
	
	/** Performs a slow bubble sort (on the order of n^2 ops) of data
	 * 
	 * @param array the array of data  
	 * @param indices the placement index array
	 */
	private static void BubbleSort(Object[] array, int[] indices) {
		for(int i=array.length-1;i>=0;i--) {
			for(int j=0;j<i;j++) {
				if(array[j] != null && array[j+1] == null) 
					Swap(array,j,j+1,indices);
				else if(array[j] == null) {
					// Nothing
				} else if(((Comparable)array[j]).compareTo(array[j+1]) > 0) {
					Swap(array,j,j+1,indices);
				}
			}
		}
	}
}
