package sorts;

import java.util.LinkedList;

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

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

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

	/**
	 * Singleton instance getter
	 * 
	 * @return StepSelectionSort single instance
	 */
	public static StepBubbleSort getInstance() {
		if (INSTANCE == null)
			INSTANCE = new StepBubbleSort();
		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));
	}

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

		// outer for loop (as many passes as elements)
		for (int i = 1; i < a.length; i++) {
			boolean swapdone = false;
			// inner for loop (run til already "bubbled-up" elements)
			for (int j = 0; j < a.length - i; j++) {
				// if in wrong order then swap
				if (a[j] > a[j + 1]) {
					swap(a, j, j + 1);
					opSwap(j, j + 1);
					swapdone = true;
				} else {
					opCompare(j, j + 1);
				}
			}
			
			// End early
			if (!swapdone)
				break;
		}

		return steps;
	}

	// 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;
	}

}