/**
 * QuickSortBase.java
 */

package sorting;

import java.util.Random;

/**
 * This class provides the partition-method for the quicksort algorithm and a
 * mechanism to specify the method of choosing a pivot element in the
 * partition-method.
 * 
 * @author Armin Staudenmaier
 * 
 */
public abstract class QuickSortBase extends SortingBase 
{
	/** Stores the way of choosing a pivot element. */
	private PivotChoice pivotType;

	/** For generating random numbers. */
	private Random rng;

	/**
	 * Constructor.
	 * 
	 * @param pivotType
	 *            Specify the way of choosing a pivot element.
	 */
	public QuickSortBase( String name, PivotChoice pivotType ) 
	{
		super( name );
		setPivotChoice( pivotType );
		/* Create the randomizer. */
		rng = new Random( System.currentTimeMillis() );
	}

	/**
	 * Returns a random value between left (inclusive) and right (inclusive).
	 * 
	 * @param left
	 *            Lower bound (inclusive).
	 * @param right
	 *            Upper bound (inclusive).
	 * @return A random value between left and right.
	 */
	public int getRandom( int left, int right ) 
	{
		return left + rng.nextInt(right - left + 1);
	}

	/**
	 * Set the method for selecting a pivot element.
	 * 
	 * @param pivotType
	 *            Specifies the method for selecting a pivot element.
	 */
	public void setPivotChoice( PivotChoice pivotType ) 
	{
		this.pivotType = pivotType;
	}

	/**
	 * Get the method for selecting a pivot element.
	 * 
	 * @return The method for selecting a pivot element.
	 */
	public PivotChoice getPivotChoice() 
	{
		return pivotType;
	}

	/**
	 * The partition method used by the quickSort method. It takes an unordered
	 * array A and rearranges its elements between the index p and r by assigning
	 * a pivot element x into three subsets:<br>First subset: all elements < x
	 * (without the pivot element).<br>Second subset: the pivot element ( = x).<br>Third
	 * subset: all elements >= x (without the pivot element).<br>Example:
	 * <br>
	 * In: |<|>|<|<|<|>|>=|<|x|
	 * <br>
	 * Out: |<|<|<|<|<|x|>|>=|>|
	 * 
	 * @param A
	 *            Array
	 * @param left
	 *            Left border
	 * @param right
	 *            Right border
	 * @return Position of Pivot element
	 */
	protected int partition(int[] A, int left, int right) {
		// Aufgabe 4b
		int x = A[right];
		int i = left - 1;
		for (int j = left; j < right - 1; j++){
			comparisons++;
			if (A[j] <= x) {
				i++;
				swap(A,i,j);
			}
		}
		swap(A,i+1,right);
		return i + 1;
	}

	/**
	 * 
	 * This method computes the index of the pivot element depending on the
	 * variable pivotType.
	 * 
	 * @param left Left border index.
	 * @param right Right border index.
	 * @return The index of the pivot element
	 */
	private int getPivotIndex( int[] A, int left, int right ) {
		// Aufgabe 4a
		int pivot = 0;
		int mid = (left + right) / 2;
		int selection = pivotType.ordinal();
		switch (selection) {
			//case MIDPOINT
			case 0: pivot = mid; break;
			//case RANDOMLY
			case 1: pivot = getRandom(left, right); break;
			//case MEDIAN_OF_3
			case 2:
				if (A[left] <= A[mid] && A[mid] <= A[right] || A[right] <= A[mid] && A[mid] <= A[left])
					pivot = mid;
				if (A[mid] <= A[left] && A[left] <= A[right] || A[right] <= A[left] && A[left] <= A[mid])
					pivot = left;
				if (A[left] <= A[right] && A[right] <= A[mid] || A[mid] <= A[right] && A[right] <= A[left])
					pivot = right;
				break;
			//case LEFTBORDER
			case 3: pivot = left; break;
			//case RIGHTBORDER
			case 4: pivot = right; break;
			//case Standard (right element)
			default: pivot = right; break;
		}
		return pivot;
	}

}