import java.util.Scanner;

/**
 * A program that demonstrates sorting polymorphism. It has four sorting methods
 * and four different types to sort.
 * 
 * The only changes students need to make to this file is in the sorting 
 * methods: bubbleSort, selectionSort, insertionSort and shellSort. In each case 
 * the method needs to be made fully general, so that any sortable array can be
 * sorted by that method.
 *
 * @author Mark Young (A00000000)
 */
public class GeneralSorting {

    public static final Scanner KBD = Common.KBD;
    private static final int HOW_MANY = 10;
    private static final int MAX = 1000;
    private static int traceLevel = 0;

    public static void main(String[] args) {
        int sortChoice;

        System.out.println("\n\n"
                + "General Sorting\n"
                + "===============\n");

        System.out.println("Choose a sorting method from the options below.");
        while ((sortChoice = getSortChoice()) != 0) {
            setTraceLevel(sortChoice);
            switch (sortChoice) {
                case 1 ->
                    doBubbleSort();
                case 2 ->
                    doSelectionSort();
                case 3 ->
                    doInsertionSort();
                case 4 ->
                    doShellSort();
            }
        }
    }

    /**
     * Let the user choose a sorting method.
     */
    private static int getSortChoice() {
        int choice;

        // print menu
        System.out.print("\n"
                + "  0: Quit\n"
                + "  1: Bubble Sort\n"
                + "  2: SelectionSort\n"
                + "  3: Insertion Sort\n"
                + "  4: Shell Sort\n\n"
                + "Choice: ");

        // get and return user selection
        choice = KBD.nextInt();
        KBD.nextLine();
        return choice;
    }

    /**
     * Demonstrate Bubble Sort using an array of Integer
     */
    private static void doBubbleSort() {
        // create an array of random integers
        int[] numbers = Common.randomNumbers(HOW_MANY, MAX / 10, MAX);
        System.out.println("Initial array:");
        Common.printArray(numbers);
        Common.pause();

        // sort it
        bubbleSort(numbers);

        // show it sorted
        System.out.println("Array now sorted");
        Common.printArray(numbers);
        Common.pause();
    }

    /**
     * Demonstrate Selection Sort using an array of String
     */
    private static void doSelectionSort() {
        // create an array of Strings
        String[] words = ("Twas brillig and the slithy toves "
                + "did gyre and gimble in the wabe").split(" ");
        System.out.println("Initial array:");
        Common.printArray(words);
        Common.pause();

        // sort it
        selectionSort(words);

        // show it sorted
        System.out.println("Array now sorted");
        Common.printArray(words);
        Common.pause();
    }

    /**
     * Demonstrate Insertion Sort using an array of Person
     */
    private static void doInsertionSort() {
        // create an array of Strings
        Person[] people = new Person[]{
            new Person("Bob"),
            new Person("Brian"),
            new Person("John"),
            new Person("Cathy"),
            new Person("Mark"),
            new Person("David"),
            new Person("Loretta"),
            new Person("Alex")
        };
        System.out.println("Initial array:");
        Common.printArray(people);
        Common.pause();

        // sort it
        insertionSort(people);

        // show it sorted
        System.out.println("Array now sorted");
        Common.printArray(people);
        Common.pause();
    }

    /**
     * Demonstrate Shell Sort using an array of Student
     */
    private static void doShellSort() {
        // create an array of Strings
        Student[] students = new Student[]{
            new Student("Bob"),
            new Student("Brian"),
            new Student("John"),
            new Student("Cathy"),
            new Student("Mark"),
            new Student("David"),
            new Student("Loretta"),
            new Student("Alex")
        };
        System.out.println("Initial array:");
        Common.printArray(students);
        Common.pause();

        // sort it
        shellSort(students);

        // show it sorted
        System.out.println("Array now sorted");
        Common.printArray(students);
        Common.pause();
    }

    /**
     * Prompt for and read a level of tracing to do. Shell sort (numeric code 4)
     * allows a level up to and including 3, but other methods only allow levels
     * up to 2.
     *
     * @param sortingChoice the numeric code for the sorting method
     */
    public static void setTraceLevel(int sortingChoice) {
        String traceMenu;
        int maxChoice;
        if (sortingChoice != 4) {
            maxChoice = 2;
            traceMenu = "Enter a trace level: \n"
                    + "  0 - no tracing\n"
                    + "  1 - outer loop only\n"
                    + "  2 - inner loop as well\n\n"
                    + "Trace level: ";
        } else {
            maxChoice = 3;
            traceMenu = "Enter a trace level: \n"
                    + "  0 - no tracing\n"
                    + "  1 - outer loop only (n-sorted)\n"
                    + "  2 - middle loop, too (inserted)\n"
                    + "  3 - innermost loop (inserting)\n\n"
                    + "Trace level: ";
        }

        System.out.print(traceMenu);
        traceLevel = KBD.nextInt();
        KBD.nextLine();
        while (traceLevel < 0 || maxChoice < traceLevel) {
            System.out.print(traceMenu);
            traceLevel = KBD.nextInt();
            KBD.nextLine();
        }
    }

    /**
     * Perform bubble sort on the given array.
     *
     * @param arr the array to sort
     */
    public static void bubbleSort(int[] arr) {
        String msg;
        for (int i = arr.length - 1; i > 0; --i) {
            for (int j = 0; j < i; ++j) {
                if (traceLevel > 1) {
                    Common.printArray(arr, j, j + 2);
                }
                if (arr[j] > arr[j + 1]) {
                    msg = "swap";
                    Common.swap(arr, j, j + 1);
                } else {
                    msg = "ok";
                }
                if (traceLevel > 1) {
                    System.out.println("...." + msg + "....");
                    Common.pause();
                }
            }
            if (traceLevel > 0) {
                System.out.println("One more bubbled up");
                Common.printArray(arr, i, arr.length);
                Common.pause();
            }
        }
    }

    /**
     * Perform insertion sort on the given array.
     *
     * @param arr the array to sort
     */
    public static void insertionSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; ++i) {
            int p = i + 1;
            int temp = arr[p];
            if (traceLevel > 1) {
                System.out.println("...inserting " + temp + "...");
                Common.printArray(arr, 0, i + 1);
                Common.pause();
            }
            while (p > 0 && arr[p - 1] > temp) {
                arr[p] = arr[p - 1];
                --p;
                if (traceLevel > 1) {
                    System.out.println("...inserting " + temp + "...");
                    System.out.println("...copy up " + arr[p] + "...");
                    Common.printArray(arr, 0, i + 2);
                    Common.pause();
                }
            }
            arr[p] = temp;
            if (traceLevel > 0) {
                System.out.println("one more inserted: ");
                Common.printArray(arr, 0, i + 2);
                Common.pause();
            }
        }
    }

    /**
     * Perform insertion sort on the given array.
     *
     * @param arr the array to sort
     */
    public static void selectionSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; ++i) {
            int p = i;
            for (int j = i + 1; j < arr.length; ++j) {
                if (traceLevel > 1) {
                    System.out.println("...looking for smaller than " + arr[p]
                            + "...");
                    Common.printTwoOf(arr, j, p);
                    Common.pause();
                }
                if (arr[j] < arr[p]) {
                    p = j;
                }
            }
            Common.swap(arr, i, p);
            if (traceLevel > 1) {
                System.out.println("...swapped smallest into position...");
                Common.printTwoOf(arr, i, p);
                Common.pause();
            }
            if (traceLevel > 0) {
                System.out.println("one more selected: ");
                Common.printArray(arr, 0, i + 1);
                Common.pause();
            }
        }
    }

    /**
     * Perform insertion sort on the given array.
     *
     * @param arr the array to sort
     */
    public static void shellSort(int[] arr) {
        int gap = arr.length / 2;
        while (gap >= 1) {
            if (gap % 2 == 0) {
                ++gap;
            }
            if (traceLevel > 1) {
                System.out.println("..." + gap + "-sorting...");
                Common.printArray(arr);
                Common.pause();
            }
            for (int i = 0; i < arr.length - gap; ++i) {
                int p = i + gap;
                int temp = arr[p];
                if (traceLevel > 2) {
                    System.out.println("...inserting " + temp + "...");
                    Common.printOffset(arr, gap, i % gap);
                    Common.pause();
                }
                while (p >= gap && arr[p - gap] > temp) {
                    arr[p] = arr[p - gap];
                    p -= gap;
                    if (traceLevel > 2) {
                        System.out.println("...inserting " + temp + "...");
                        System.out.println("...copy up " + arr[p] + "...");
                        Common.printOffset(arr, gap, i % gap);
                        Common.pause();
                    }
                }
                arr[p] = temp;
                if (traceLevel > 1) {
                    System.out.println("one more inserted: ");
                    Common.printOffset(arr, gap, i % gap);
                    Common.pause();
                }
            }
            if (traceLevel > 0) {
                System.out.println("now " + gap + "-sorted");
                for (int rem = 0; rem < gap; ++rem) {
                    System.out.println("...offset " + rem);
                    Common.printOffset(arr, gap, rem);
                }
                Common.pause();
            }
            gap /= 2;
        }
    }

}