package sorts;

import java.util.LinkedList;

/**
 * @author forrestoliphant, based on
 *         http://www.wanginator.de/studium/applets/insertionsort_en.html
 */
public class StepInsertionSort {

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

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

	/**
	 * Singleton instance getter
	 * 
	 * @return StepSelectionSort single instance
	 */
	public static StepInsertionSort getInstance() {
		if (INSTANCE == null)
			INSTANCE = new StepInsertionSort();
		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));
	}
	private void opHold(int a) {
		steps.add(new StepObject(a, true));
	}
	private void opUnhold(int a) {
		steps.add(new StepObject(a, false, true));
	}

	/**
	 * Insertion sort that returns the steps taken
	 * 
	 * @param a
	 *            Array to sort
	 * @return LinkedList<StepObject> of the steps taken to sort
	 */
	public LinkedList<StepObject> insertionSort(int[] a) {
		steps = new LinkedList<StepObject>();

		// outer for loop (as many passes as elements)
		for (int i = 0; i < a.length; i++) {
			insert(a, i);
		}

		return steps;
	}

	private void insert (int[] a, int i) { 

		int k = a[i]; // k is element to be inserted
		opHold(i);

		int j = i; 
		// shift all elements > k one position to the right
		while (j != 0 && a[j-1] > k) 
		{ 
			a[j] = a[j-1]; 
			opSwap(j,j-1);
			j--; 
		} 
		// insert k at correct position
		a[j] = k; 
		opUnhold(j);
	}
}