/*
 * Quicksort.java
 *
 * Author: Alexander Breen (abreen@bu.edu)
 * with code from the Sort.java class from the S-111 website
 */

import java.util.Scanner;

public class Quicksort {

    private static int numPartitions = 0;
    private static int numSwaps = 0;
    private static int speed = 3000;

    private static int partition(int[] arr, int first, int last) {
        printp("*** partition #%d\n", ++numPartitions);

        int pivot = arr[(first + last)/2];
        int i = first - 1;  // index going left to right
        int j = last + 1;   // index going right to left

        printp("*** before partition:\n");
        indicate(arr, first, last, i, j);

        printp("*** chose %d as pivot value\n", pivot);

        while (true) {
            do {
                i++;
                printp("*** incrementing i (new value: %d)\n", i);
                indicate(arr, first, last, i, j);
                printp("*** arr[i] < pivot == %d < %d == %s\n", arr[i],
                       pivot, arr[i] < pivot);
            } while (arr[i] < pivot);

            printp("*** stop moving i\n");

            do {
                j--;
                printp("*** decrementing j (new value: %d)\n", j);
                indicate(arr, first, last, i, j);
                printp("*** arr[j] > pivot == %d > %d == %s\n", arr[j],
                       pivot, arr[j] > pivot);
            } while (arr[j] > pivot);

            printp("*** stop moving j\n");

            if (i < j) {
                printp("*** i < j == %d < %d == true, so swap index " +
                       "%d (%d) with index %d (%d)\n", i, j, i,
                       arr[i], j, arr[j]);

                printp("*** before swap:\n");
                indicate(arr, first, last, i, j);

                swap(arr, i, j);

                printp("*** after swap (%d swap%s so far):\n",
                       numSwaps, numSwaps == 1 ? "" : "s");
                indicate(arr, first, last, i, j);
            } else {
                printp("*** i < j == %d < %d == false, so return " +
                       "j (%d)\n", i, j, j);

                return j;   // index of last element in the left subarray
            }
        }
    }

    private static void qSort(int[] arr, int first, int last) {
        int split = partition(arr, first, last);

        if (first < split)
            qSort(arr, first, split);      // left subarray

        if (last > split + 1)
            qSort(arr, split + 1, last);   // right subarray
    }

    public static void quickSort(int[] arr) {
        qSort(arr, 0, arr.length - 1); 
    }

    /*
     * Given an array and two start and end indices, print a pretty
     * picture of the array. If start > 0 and/or end < arr.length - 1,
     * print a representation of the subarray that
     * contains arr[start] to arr[end], inclusive. Furthermore, if
     * start < 0 or end > arr.length - 1, add imaginary array elements
     * to the left and/or right side of the array.
     */
    private static void printSubarray(int[] array, int start, int end) {
        int extraLeft = 0, extraRight = 0;

        if (start < 0)
            extraLeft = Math.abs(start);

        if (end > array.length - 1)
            extraRight = end - array.length + 1;

        int totalNum = Math.min(end, array.length - 1) - Math.max(start, 0) +
                       1 + extraLeft + extraRight;

        int maxDigits = maxNumDigits(array, start + extraLeft, end - extraRight);

        // printed width of an array element, including spaces and | on right
        int elementWidth = maxDigits + 3;

        // print top of array picture
        for (int i = 1; i <= totalNum; i++) {
            System.out.print("+");

            for (int j = 1; j <= elementWidth - 1; j++)
                System.out.print("-");
        }
        System.out.println("+");

        System.out.print("|");
        // print all imaginary on left
        for (int i = 1; i <= extraLeft; i++)
            System.out.printf(" %-" + maxDigits + "s |", "-");

        // print all actual array values
        for (int i = Math.max(start, 0); i <= Math.min(end, array.length - 1); i++)
            System.out.printf(" %-" + maxDigits + "d |", array[i]);

        // print all imaginary on right
        for (int i = 1; i <= extraRight; i++)
            System.out.printf(" %-" + maxDigits + "s |", "-");

        System.out.println();

        // print bottom of array picture
        for (int i = 1; i <= totalNum; i++) {
            System.out.print("+");

            for (int j = 1; j <= elementWidth - 1; j++)
                System.out.print("-");
        }
        System.out.println("+");
    }

    /*
     * Given an array and start and end parameters, print the subarray
     * between start and end, inclusive. Then print two markers (simply
     * indices between start and end, inclusive) under the array, with
     * carets that point to the beginning of the appropriate array position.
     */
    private static void indicate(int[] array, int start, int end,
                                 int markerI, int markerJ)
    {
        printSubarray(array, Math.min(start, markerI), Math.max(end, markerJ));

        /*
         * iPos (for markerI) and jPos (for markerJ) are the adjusted positions
         * of each marker in the array printed by printSubarray(). This
         * calculation must be done because we need the possible marker positions
         * to start from 0 in the array printed by printSubarray(), which might
         * even contain imaginary elements added to the left and right.
         */
        int iPos = (markerI - Math.min(start, markerI));
        int jPos = (markerJ - Math.min(start, markerI));

        int first = Math.min(iPos, jPos);
        int second = Math.max(iPos, jPos);

        int maxDigits = maxNumDigits(array, start, end);

        // printed width of an array element, including spaces and | on right
        int elementWidth = maxDigits + 3;

        // print the caret(s)
        for (int i = 1; i <= first * elementWidth + 1; i++)
            System.out.print(" ");

        System.out.print("^");

        /*
         * If both markers are in the same column, only print
         * one caret. "i" and "j" will both go under it.
         */
        if (iPos != jPos) {
            for (int i = 1; i <= (second - first) * elementWidth - 1; i++)
                System.out.print(" ");

            System.out.print("^");
        }

        System.out.println();

        // print i/j
        for (int i = 1; i <= first * elementWidth + 1; i++)
            System.out.print(" ");

        if (iPos <= jPos) {
            System.out.print("i");
        } else {
            System.out.print("j");
        }

        for (int i = 1; i <= (second - first) * elementWidth - 1; i++)
            System.out.print(" ");

        if (jPos > iPos) {
            System.out.print("j");
        } else if (iPos == jPos) {
            System.out.print(", j");
        } else {
            System.out.print("i");
        }

        System.out.println();

        try {
            Thread.sleep(speed);
        } catch (InterruptedException e) {
            System.exit(1);
        }

        System.out.println();
    }

    private static int maxNumDigits(int[] arr, int start, int end) {
        int max = 0;

        for (int i = start; i <= end; i++) {
            int numDigits = (int)(Math.log(arr[i]) / Math.log(10)) + 1;
            if (numDigits > max)
                max = numDigits;
        }

        return max;
    }

    private static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;

        numSwaps++;
    }

    /*
     * printp acts exactly like System.out.printf(), except that
     * it pauses after doing the printing.
     */
    private static void printp(String fmt, Object... rest) {
        System.out.printf(fmt, rest);

        try {
            Thread.sleep(speed);
        } catch (InterruptedException e) {
            System.exit(1);
        }
    }

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        System.out.print("Time between steps (in seconds): ");
        int time = s.nextInt();

        Quicksort.speed = time * 1000;

        int[] arr = {7, 39, 20, 11, 16, 5};
        quickSort(arr);

        printp("*** complete!\n");

        printSubarray(arr, 0, arr.length - 1);
    }

}