import java.util.Arrays;
import java.util.Random;

public class SplitPivot {

	public static void splitLomuto(int[] A) {
		int pivot = A[A.length - 1];
		int ll = -1; // ll is the "last of the little numbers"
		for (int bu = 0; bu < A.length - 1; bu++) {
			// bu is the "beginning of the unknown"
			if (A[bu] < pivot) {
				ll++;
				//				swap(A, ll, bu);
				int tmp = A[ll];
				A[ll] = A[bu];
				A[bu] = tmp;
			}
		}
	}

	public static void splitOutsideIn(int[] A) {
		int pivot = A[A.length - 1];
		int l = 0, r = A.length - 2;
		while (l < r) {
			while (A[l] < pivot) {
				l++;
			}
			;
			while (r >= 0 && A[r] >= pivot) {
				r--;
			}
			;
			if (l < r) {
				//				swap(A, l, r);
				int tmp = A[l];
				A[l] = A[r];
				A[r] = tmp;
				l++;
				r--;
			}
		}
	}

	public static void splitHoare(int[] A) {
		int pivot = A[A.length - 1];
		int l = -1, r = A.length;
		while (true) {
			do {
				l++;
			} while (A[l] < pivot);
			do {
				r--;
			} while (A[r] > pivot);
			if (l < r) {
				//				swap(A, l, r);
				int tmp = A[l];
				A[l] = A[r];
				A[r] = tmp;
			} else {
				return;
			}
		}
	}

	public static void swap(int[] A, int i, int j) {
		int tmp;
		tmp = A[i];
		A[i] = A[j];
		A[j] = tmp;
	}

	public static int[] randomArray(int size, int max) {
		Random random = new Random();
		int[] A = new int[size];
		for (int i = 0; i < size; i++) {
			A[i] = random.nextInt(max);
		}
		return A;
	}

	public static int[] arrayCopy(int[] A) {
		int[] B = new int[A.length];
		for (int i = 0; i < A.length; i++) {
			B[i] = A[i];
		}
		return B;
	}

	public static double averageDouble(double[] A) {
		double sum = 0;
		for (double a : A) {
			sum += a;
		}
		return ((double) sum) / A.length;
	}

	public static float averageLong(long[] A) {
		long sum = 0;
		//      for (long a : A) {
		for (int i = 1; i < A.length; i++) {
			//sum += a;
			sum += A[i];
		}
		return ((float) sum) / (A.length - 1);
	}

	public static long numberOfSwapsLomuto(int[] A) {
		long swaps = 0;
		int pivot = A[A.length - 1];
		int ll = -1; // ll is the "last of the little numbers"
		for (int bu = 0; bu < A.length - 1; bu++) {
			// bu is the "beginning of the unknown"
			if (A[bu] < pivot) {
				ll++;
				swap(A, ll, bu);
				swaps++;
			}
		}
		return swaps;
	}

	public static long numberOfSwapsOutsideIn(int[] A) {
		long swaps = 0;

		int pivot = A[A.length - 1];
		int l = 0, r = A.length - 2;
		while (l < r) {
			while (A[l] < pivot) {
				l++;
			}
			;
			while (r >= 0 && A[r] >= pivot) {
				r--;
			}
			;
			if (l < r) {
				swap(A, l, r);
				swaps++;
				l++;
				r--;
			}
		}
		return swaps;
	}

	public static long numberOfSwapsHoare(int[] A) {
		int swaps = 0;

		int pivot = A[A.length - 1];
		int l = -1, r = A.length;
		while (true) {
			do {
				l++;
			} while (A[l] < pivot);
			do {
				r--;
			} while (A[r] > pivot);
			if (l < r) {
				swap(A, l, r);
				swaps++;
			} else {
				return swaps;
			}
		}
	}

	public static long runningTimeLomuto(int[] A) {
		// size stands for the size of the arrays to be tested
		// starting time
		long start = System.nanoTime();
		// run function
		splitLomuto(A);
		// ending time
		long end = System.nanoTime();
		return (end - start) / 1000;
	}

	public static long runningTimeOutsideIn(int[] A) {
		// size stands for the size of the arrays to be tested
		// starting time
		long start = System.nanoTime();
		// run function
		splitOutsideIn(A);
		// ending time
		long end = System.nanoTime();
		return (end - start) / 1000;
	}

	public static long runningTimeHoare(int[] A) {
		// size stands for the size of the arrays to be tested
		// starting time
		long start = System.nanoTime();
		// run function
		splitHoare(A);
		// ending time
		long end = System.nanoTime();
		return (end - start) / 1000;
	}

	public static void runtimeTests(int size, int numberOfExecs) {
		double[] runningTimesLomuto = new double[numberOfExecs + 1];
		double[] runningTimesOutsideIn = new double[numberOfExecs + 1];
		double[] runningTimesHoare = new double[numberOfExecs + 1];
		for (int i = 0; i <= numberOfExecs; i++) {
			int[] A = randomArray(size, 100 * size);
			int[] B = arrayCopy(A);
			int[] C = arrayCopy(A);
			runningTimesLomuto[i] = runningTimeLomuto(A);
			runningTimesOutsideIn[i] = runningTimeOutsideIn(B);
			runningTimesHoare[i] = runningTimeHoare(C);
		}
		System.out.println("These are the running times for size " + size + ".\n");
		System.out.println("Lomuto: ");
		System.out.println(Arrays.toString(runningTimesLomuto));
		System.out.println("Outside In: ");
		System.out.println(Arrays.toString(runningTimesOutsideIn));
		System.out.println("Hoare: ");
		System.out.println(Arrays.toString(runningTimesHoare));
	}

	public static void averageRuntimeTests(int size, int numberOfExecs) {
		double[] runningTimesLomuto = new double[numberOfExecs + 1];
		double[] runningTimesOutsideIn = new double[numberOfExecs + 1];
		double[] runningTimesHoare = new double[numberOfExecs + 1];
		for (int i = 0; i <= numberOfExecs; i++) {
			int[] A = randomArray(size, 100 * size);
			int[] B = arrayCopy(A);
			int[] C = arrayCopy(A);
			runningTimesLomuto[i] = runningTimeLomuto(A);
			runningTimesOutsideIn[i] = runningTimeOutsideIn(B);
			runningTimesHoare[i] = runningTimeHoare(C);
		}
		System.out.println("Times for " + numberOfExecs + " runs and array size " + size + ".\n");
		System.out.println("Lomuto: ");
		System.out.println(averageDouble(runningTimesLomuto));
		System.out.println("Outside In: ");
		System.out.println(averageDouble(runningTimesOutsideIn));
		System.out.println("Hoare: ");
		System.out.println(averageDouble(runningTimesHoare));
	}

	public static void swapTests(int size, int range, int numberOfExecs) {
		double[] swapNumbersLomuto = new double[numberOfExecs + 1];
		double[] swapNumbersOutsideIn = new double[numberOfExecs + 1];
		double[] swapNumbersHoare = new double[numberOfExecs + 1];
		for (int i = 0; i <= numberOfExecs; i++) {
			int[] A = randomArray(size, range);
			int[] B = arrayCopy(A);
			int[] C = arrayCopy(A);
			swapNumbersLomuto[i] = numberOfSwapsLomuto(A);
			swapNumbersOutsideIn[i] = numberOfSwapsOutsideIn(B);
			swapNumbersHoare[i] = numberOfSwapsHoare(C);
		}
		System.out.println("Numbers of swaps for size " + size + ".");
		System.out.println("Lomuto: ");
		System.out.println(Arrays.toString(swapNumbersLomuto));
		System.out.println("Outside In: ");
		System.out.println(Arrays.toString(swapNumbersOutsideIn));
		System.out.println("Hoare: ");
		System.out.println(Arrays.toString(swapNumbersHoare));
	}

	public static void averageSwapsTests(int size, int range, int numberOfExecs) {
		long[] swapNumbersLomuto = new long[numberOfExecs + 1];
		long[] swapNumbersOutsideIn = new long[numberOfExecs + 1];
		long[] swapNumbersHoare = new long[numberOfExecs + 1];
		for (int i = 0; i <= numberOfExecs; i++) {
			int[] A = randomArray(size, range);
			int[] B = arrayCopy(A);
			int[] C = arrayCopy(A);
			swapNumbersLomuto[i] = numberOfSwapsLomuto(A);
			swapNumbersOutsideIn[i] = numberOfSwapsOutsideIn(B);
			swapNumbersHoare[i] = numberOfSwapsHoare(C);
		}
		System.out.println("Average numbers of swaps for size " + size + " and " + numberOfExecs + " runs.\n");
		System.out.println("Lomuto: ");
		System.out.println(averageLong(swapNumbersLomuto));
		System.out.println("Outside In: ");
		System.out.println(averageLong(swapNumbersOutsideIn));
		System.out.println("Hoare: ");
		System.out.println(averageLong(swapNumbersHoare));
	}

	public static void main(String[] args) {
		//		int[] A = {1, 3, 2, 6, 15, 7, 11, 12, 14, 13};
		//		int[] A = {7, 3, 12, 17, 4, 3, 11, 12, 5, 8};
		//		int[] A = {1, 3, 2, 6, 15, 7, 11, 12, 14, 13};
		//		int[] A = { 1,3,5,7,9, 2,4,6,8,10};
		//		int[] A = {14, 13};
		//		int[] A = { 1, 3 };

		/*
		 * System.out.println(Arrays.toString(A)); splitInEvenAndOdds(A);
		 * System.out.println(Arrays.toString(A)); split2(A);
		 */
		//		 System.out.println(Arrays.toString(A)); 

		//		runtimeTests(100000, 20);
		//      averageRuntimeTests(100, 1000);
		//		System.out.println("\n");
		//
		//		swapTests(100, 20000000, 20);
		averageSwapsTests(100, 200000, 10000);

		//		System.out.println(numberOfSwapsLomuto(A));
		//		System.out.println(Arrays.toString(randomArray(100,100)));
		//		System.out.println(Arrays.toString(arrayCopy(randomArray(100,100))));

		//		 int[] A = randomArray(20, 1000000); 
		//		 System.out.println(Arrays.toString(A));
		//		 splitHoare(A); System.out.println(Arrays.toString(A));

	}

}