import java.util.Random;
import java.util.Scanner;

/**
 * A program to split a list into pieces such that every value in one piece is
 * less than or equal to every value in the higher pieces (that is, the pieces
 * closer to the end of the array).
 *
 * @author Mark Young (A00000000)
 */
public class QuickSplit {

    public static final Scanner KBD = new Scanner(System.in);
    public static final Random RAND = new Random();

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // introduction
        printIntroduction();
        pause();

        // get/create data
        int length = getInt("How long should the list be?");
        int max = getInt("What should the maximum value be?");
        int pieces = getInt("How many pieces should it be broken into?");
        int[] numbers = makeArray(length, max);
        int[] places = findSplits(length, pieces);
        pause();

        // find the value
        quickSort(numbers);
        pause();

        // report the results
        System.out.println("The " + pieces + " pieces are bounded by: ");
        for (int i = 0; i < places.length; ++i) {
            System.out.println(" - " + numbers[places[i]]);
        }
        pause();

        // confirm the results
        System.out.println("For confirmation:");
        PrintTrace.printArray(numbers, 0, places[0]);
        pause();
        for (int i = 1; i < places.length; ++i) {
            PrintTrace.printArray(numbers, places[i - 1], places[i]);
            pause();
        }
        PrintTrace.printArray(numbers, places[places.length - 1], length);
        pause();
    }

    /**
     * Quick-sort an entire array.
     *
     * @param numbers the array to sort
     */
    private static void quickSort(int[] numbers) {
        quickSort(numbers, 0, numbers.length);
    }

    /**
     * Sort an array using the quick-sort algorithm.
     *
     * @param arr the array to (partially) sort
     * @param begin the lower bound (inclusive) of the part being sorted
     * @param end the upper bound (exclusive) of the part being sorted
     */
    public static void quickSort(
            int[] arr,
            int begin,
            int end) {
        // only need to sort subsections of length 2 or more
        if (end - begin > 1) {
            // report the range that's being sorted
            System.out.println("Sorting from " + begin + " to " + end + "...");

            // pick pivot
            int pivot = pickAndMovePivot(arr, begin, end);

            // partition
            int pivotPlace = partition(arr, begin, end, pivot);

            // quickSort lower part (for smallest values)
            quickSort(arr, begin, pivotPlace);

            // quickSort upper part
            quickSort(arr, pivotPlace + 1, end);
        }
    }

    /**
     * Use the median-of-three method to pick a pivot value, then move it to the
     * end of the array.
     *
     * @param arr the array to pick the pivot from
     * @param begin the lower bound (inclusive) of the part of the array being
     * sorted
     * @param end the upper bound (exclusive) of the part of the array being
     * sorted
     * @return the value chosen as the pivot
     */
    private static int pickAndMovePivot(int[] arr, int begin, int end) {
        int p1 = begin;
        int p2 = end - 1;
        int p3 = begin + (end - begin) / 2;
        if (arr[p1] < arr[p2]) {
            if (arr[p2] < arr[p3]) {
                return movePivot(arr, p2, end);
            } else if (arr[p1] < arr[p3]) {
                return movePivot(arr, p3, end);
            } else {
                return movePivot(arr, p1, end);
            }
        } else if (arr[p1] < arr[p3]) {
            return movePivot(arr, p1, end);
        } else if (arr[p2] < arr[p3]) {
            return movePivot(arr, p3, end);
        } else {
            return movePivot(arr, p2, end);
        }
    }

    /**
     * Move the pivot value to the end of the part of the array being sorted.
     *
     * @param arr the array being sorted
     * @param pivotStart the index where the pivot value was in the array
     * @param end the upper bound (exclusive) of the part of the array being
     * sorted
     * @return the value moved to the end (i.e. the pivot value)
     */
    private static int movePivot(int[] arr, int pivotStart, int end) {
        swap(arr, pivotStart, end - 1);
        return arr[end - 1];
    }

    /**
     * Partition the part of the array being sorted. That is, move all the
     * smaller values toward the front of the array and the bigger ones toward
     * the back. Bigger and smaller are determined with respect to the pivot
     * value.
     *
     * @param arr the array being sorted
     * @param begin the lower bound (inclusive) of the part of the array being
     * sorted
     * @param end the upper bound (exclusive) of the part of the array being
     * sorted
     * @param pivot the pivot value
     * @return the position the pivot value ended up in
     */
    private static int partition(int[] arr, int begin, int end, int pivot) {
        int lowerEdge = begin;
        int upperEdge = end - 2;   // pivot is in end-1

        // swap near-front-larger and near-back-smaller values until we cross
        // in the middle
        while (true) {
            if (arr[lowerEdge] < pivot) {
                // near-front-small
                lowerEdge++;
            } else if (lowerEdge >= upperEdge) {
                // crossed in the middle
                break;
            } else if (pivot < arr[upperEdge]) {
                // near-back-large
                upperEdge--;
            } else {
                // near-front-large and near-back-small
                swap(arr, lowerEdge, upperEdge);
                lowerEdge++;
                upperEdge--;
            }
        }

        // move the pivot, if necessary
        if (pivot < arr[lowerEdge]) {
            swap(arr, lowerEdge, end - 1);
        }

        // return the location of the/a pivot value
        return lowerEdge;
    }

    private static void swap(int[] arr, int p1, int p2) {
        if (p1 != p2) {
            int temp = arr[p1];
            arr[p1] = arr[p2];
            arr[p2] = temp;
        }
    }

    /**
     * Wait for the user to press the enter key.
     */
    public static void pause() {
        System.out.print("\n...Press ENTER...");
        KBD.nextLine();
        System.out.println();
    }

    private static void printIntroduction() {
        System.out.println("\n"
                + "Quick Split\n"
                + "-----------\n\n"
                + "A program to find the values that break a sorted list "
                + "into equal-length pieces,\n"
                + "without actually sorting the list.\n\n"
                + "Original by Mark Young (A00000000)\n"
                + "Completed by ____ ____ (A00______)");
    }

    private static int getInt(String prompt) {
        System.out.print(prompt + " ");
        int result = KBD.nextInt();
        KBD.nextLine();
        while (result <= 1) {
            System.out.println("You must enter an integer greater than 1.");
            System.out.print(prompt + " ");
            result = KBD.nextInt();
            KBD.nextLine();
        }
        return result;
    }

    /**
     * Create an array of {@code length} values in the range {@code 0 .. max}.
     * 
     * @param length the number of values to create
     * @param max the maximum value to create
     * @return an array of {@code length} values in the range {@code 0 .. max}
     */
    private static int[] makeArray(int length, int max) {
        int[] result = new int[length];
        for (int i = 0; i < length; ++i) {
            result[i] = RAND.nextInt(max + 1);
        }
        return result;
    }

    /**
     * Identify which positions in a sorted array would split it into the given
     * number of pieces such that each piece contains only numbers smaller than
     * (or equal to) the pieces later in the array.
     * 
     * @param length
     * @param pieces
     * @return an array of "split points"
     */
    private static int[] findSplits(int length, int pieces) {
        int[] result = new int[pieces - 1];
        for (int i = 1; i <= result.length; ++i) {
            result[i - 1] = (i * length) / pieces;
        }
        return result;
    }

}