package com.andreimosso.util;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.List;

/**
 * @author Andrei Mosso Mendoza
 * @version 1.0.1
 */
public class ScalableSort {

	public static final int SINGLE_THREAD_SORT_THRESHOLD = 1000;
	
	private ScalableSort() {}
	
	/**
	 * 
	 * @param list The list to be sorted.
	 * @param numCores The number of execution threads to be used.
	 */
	public static <T extends Comparable<? super T>> void sort(final List<T> list, final int numCores) {
	
		T arr1[] = (T[])Array.newInstance(Comparable.class, list.size());
		final T arr[] = list.toArray(arr1);
		
		if (list.size() > SINGLE_THREAD_SORT_THRESHOLD && numCores > 1) {
			final Thread timer = new Thread() {
				
				public void run() {
				
					try {
						Thread.sleep(1000000000000000L);
					}
					catch (InterruptedException ie) {}
				}
			};
			timer.start();
			
			final boolean finished[] = new boolean[numCores];
			final int cuts[] = new int[numCores + 1];
			
			// Dividimos el arreglo en partes "iguales".
			for (int i = 0; i < numCores; i++) {
				cuts[i] = arr.length / numCores * i;
			}
			cuts[cuts.length - 1] = arr.length;
			
			for (int i = 0; i < numCores; i++) {
				final int v = i;
				
				new Thread() {
				
					public void run() {
					
						// Ordenamos cada sección del arreglo.
						Arrays.sort(arr, cuts[v], cuts[v + 1]);
						// Al terminar, cada hilo marca su bandera.
						finished[v] = true;
						
						// Revisamos que todos los hilos hayan terminado.
						for (int i = 0; i < finished.length; i++) {
							if (!finished[i]) {
								return;
							}
						}
						
						merge(arr, cuts);
						
						for (int j = 0; j < arr.length; j++) {
							list.set(j, (T)arr[j]);
						}
						
						timer.interrupt();
					}
				}.start();
			}
			
			try {
				timer.join();
			}
			catch (InterruptedException ie) {}
		}
		else {
			Arrays.sort(arr);
			
			for (int j = 0; j < arr.length; j++) {
				list.set(j, (T)arr[j]);
			}
		}
	}
	
	private static <T extends Comparable<? super T>> void merge(T arr[], int cuts[]) {
	
		int index = 0;
		int indices[] = new int[cuts.length - 1];
		boolean finished[] = new boolean[cuts.length - 1];
		T candidates[] = (T[])Array.newInstance(Comparable.class, cuts.length - 1);
		T src[] = arr.clone();
		
		for (int i = 0; i < indices.length; i++) {
			indices[i] = cuts[i];
		}
		
		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < candidates.length; j++) {
				try {
					candidates[j] = src[indices[j]];
				}
				catch (ArrayIndexOutOfBoundsException aioobe) {}
			}
			
			index = smallest(candidates, finished);
			arr[i] = candidates[index];
			indices[index]++;
			if (indices[index] >= cuts[index + 1]) {
				finished[index] = true;
			}
		}
	}
	
	private static <T extends Comparable<? super T>> int smallest(T candidates[], boolean finished[]) {
	
		T smallest = candidates[0];
		int index = 0;
		
		while (finished[index]) {
			index++;
			smallest = candidates[index];
		}
		
		for (int i = 0; i < candidates.length; i++) {
			if (candidates[i].compareTo(smallest) < 0 && !finished[i]) {
				smallest = candidates[i];
				index = i;
			}
		}
		
		return index;
	}
}