package sorts;

import java.util.LinkedList;

/**
 * SelectionSort that returns the steps taken
 * 
 * @author forrestoliphant, based on
 *         http://www.wanginator.de/studium/applets/selectionsort_en.html
 * 
 */
public class StepSelectionSort {

	/**
	 * Default constructor is private to make it a singleton
	 */
	private StepSelectionSort() {
	}

	// Single instance of the object
	private static StepSelectionSort INSTANCE;

	/**
	 * Singleton instance getter
	 * 
	 * @return StepSelectionSort single instance
	 */
	public static StepSelectionSort getInstance() {
		if (INSTANCE == null)
			INSTANCE = new StepSelectionSort();
		return INSTANCE;
	}

	// LinkedList to hold all of the steps for the animation
	private LinkedList<StepObject> steps;

	// Save each step
	private void opCompare(int a, int b) {
		steps.add(new StepObject(a, b));
	}

	private void opSwap(int a, int b) {
		steps.add(new StepObject(a, b, true));
	}

	/**
	 * Selection sort that returns the steps taken
	 * 
	 * @param a
	 *            Array to sort
	 * @return LinkedList<StepObject> of the steps taken to sort
	 */
	public LinkedList<StepObject> selectionSort(int[] a) {
		steps = new LinkedList<StepObject>();
		// run through the list and swap with the minimum of the remaining list
		for (int i = 0; i < a.length; i++) {
			int swap1 = i;
			int swap2 = minIndex(a, i);
			opSwap(swap1, swap2);
			swap(a, swap1, swap2);
		}
		return steps;
	}

	// find the index of the minimum after position i
	private int minIndex(int[] a, int i) {
		int m = i;
		// set i as provisional minimum
		for (int j = i + 1; j < a.length; j++) {
			// if smaller than minimum, this is our minimum
			if (a[j] < a[m]) {
				m = j;
			}
			opCompare(j, m);
		}
		return m;
	}

	// swap two elements in the array
	private void swap(int[] a, int i, int j) {
		int h = a[i];
		a[i] = a[j];
		a[j] = h;
	}

}