import javax.swing.*;
import java.util.*;

public class SortDriver {    

    public static void selectSort(Student[] X) {
    // precondition: X.length > 0
    //postcondition: X is in ascending order thru selection sort algorithm
        Arrays.sort(X); // remove this statement when implementing this sort       
    } //===  selectSort


    public static void insertSort(Student[] X) {
    // precondition: X.length > 0
    //postcondition: X is in ascending order thru insertion sort algorithm         
        Arrays.sort(X);  // remove this statement when implementing this sort       
    } //=== insertSort


    public static void bubbleSort(Student[] X) {
    // precondition: X.length > 0
    //postcondition: X is in ascending order thru bubble sort algorithm               
        Arrays.sort(X);  // remove this statement when implementing this sort       
    } //===  bubbleSort
    
    
    public static Student[] mergeArrays(Student[] X, Student[] Y) { 
    // precondition: X and Y are in ascending order
    //postcondition: returns an array in which X and Y are merged in ascending order                     
        
        return null;        
     } //===  mergeArrays
     
     
    public static void mergeSort(Student[] X, int lo, int hi) {
    // precondition: X.length > 0, uses method merge as specified below
    //postcondition: X is in ascending order thru mergesort algorithm               
        Arrays.sort(X);  // remove this statement when implementing this sort       
   } //===  mergeSort
          
     
     static void merge(Student[] X, int lo, int mid, int hi) {
    // precondition: X[lo..mid] and X[mid+1..hi] are in ascending order
    //postcondition: X[lo..mid] and X[mid+1..hi] are merged in ascending order
    //   thru mergesort algorithm
 
 
    } //===  merge    
    
    
     public static void quickSort(Student[] X, int lo, int hi) {
    // precondition: uses partition as specified below        
    //postcondition: X[lo..hi] are  in ascending order thru quicksort algorithm
        Arrays.sort(X);
     } //===  quickSort    

     
     static int partition(Student[] X, int lo, int hi) {
     //postcondition: partitions X[lo..hi] such that: 1. pivotValue = X[lo]
     //    2. all X[k] > pivotValue are to right of X[j] where X[j] = pivotValue
     //    3. all X[k] <= pivotValue are to left of X[j] where X[j] = pivotValue
     //    4. returns index j where where X[j] = pivotValue         
         return 0;
      }
         
    //===============================================================================================================
    static final String[] SORTS = { "selection sort", "insertion sort", "bubble sort", 
        "merge arrays", "mergesort", "quicksort"};

    
    public static String TAB = "\t";
     
    public static void main(String[] args) {
        MyTerminal.cls();
        System.out.println("\t\t\tSort Driver Program\n");
        System.out.println("To use this program succesfully:\n\t1.\tStretch BlueJ Terminal Window vertically");
        System.out.println("\t2.\tMinimize all other windows.");                  
        MyTerminal.readString("\nPress <ENTER>...");
        for (;;) {      
            MyTerminal.cls();
            String strChoice = "";
            strChoice = JOptionPane.showInputDialog(null, new String[]
            {"1.     Selection sort\n", "2.     Insertion sort\n",
             "3.     Bubble sort\n",    "4.     Merge sorted arrays\n",
             "5.     Merge sort\n",     "6.     Quick sort\n",  
             "7      Time sorts\n" ,    "0.     Quit"} ,
              "ENTER APPROPRIATE NUMBER", JOptionPane.INFORMATION_MESSAGE); 
             int choice;
            if ( strChoice.compareTo("0") < 0 || strChoice.compareTo("9") > 0 )
                choice = -1;
            else 
                choice = Integer.parseInt(strChoice);
            switch (choice) {
                case 0:  break;  
                case 1:  // fall thru
                case 2:  // fall thru
                case 3:  // fall thru
                case 4:  // fall thru
                case 5:  // fall thru
                case 6: testSort(choice); break;
                case 7: timeSorts(); break;
                default: JOptionPane.showMessageDialog
                    ( null, "ERROR: enter number in [0, 7]", 
                    "INPUT ERROR", JOptionPane.ERROR_MESSAGE);
                    break;
            }//=== switch
            if ( choice == 0 ) break;           
        }//=== for
        System.out.println("\nProgram over");
        System.exit(0);
    } // main
    
    
    static void testSort(int choice) {
        Student A[] = null;
        MyTerminal.cls();
        if ( choice != 4 ) {
            A = makeArray(19);
            System.out.println("Array before sort:");
            print(A);
        }
        switch ( choice ) {
        case 1: selectSort(A); break;
        case 2: insertSort(A); break;
        case 3: bubbleSort(A); break;
        case 4: Student[] temp = makeArray(17);
                A = new Student[9]; Student[] B = new Student[temp.length - A.length];
                for (int k = 0; k < temp.length/2; k++) { A[k] = temp[k]; B[k] = temp[k + temp.length/2];}
                A[A.length-1] = temp[temp.length-1];            
                Arrays.sort(A); Arrays.sort(B);
                System.out.println("1st array before merge:"); print(A);        
                System.out.println("2nd array before merge:"); print(B);
                A = mergeArrays(A, B); break;
        case 5: mergeSort(A, 0, A.length - 1); break;
        case 6: quickSort(A, 0, A.length - 1); break;
        default: break;
        }
        System.out.println("Array after " + ( choice == 4  ? "merge" : "sort"));
        print(A);
        if ( isSorted(A, choice) ) 
            JOptionPane.showMessageDialog(null, SORTS[choice-1] + " succesful", 
                    "IMPLEMENTATION RESULTS", JOptionPane.INFORMATION_MESSAGE);            
    } //=== testSort
    
    
    static Student[] makeArray(int n) {
        Student A[] = new Student[n];
        Student.setListVars();
        for (int k = 0; k < n; k++)
            A[k] = new Student();
        Random rGen = new Random(19);    
        for (int last = A.length; last > 1; last--) {
            int pos = rGen.nextInt(last);
            Student temp = A[pos]; A[pos] = A[last-1]; A[last-1] = temp; 
        }
        return A;        
    }
    
    static boolean isSorted(final Student[] X, int choice) {
        for (int k = 0; k < X.length - 1; k++) {
            if ( X[k].compareTo(X[k+1]) > 0 ) {
                String msg = "X[" + k + "].name = " + X[k].getName() + " > " + "X[" + (k + 1) + "].name = " + X[k+1].getName();
                JOptionPane.showMessageDialog( null, msg, 
                    "IMPLEMENTATION FAILED: " + SORTS[choice-1], JOptionPane.ERROR_MESSAGE);
                    return false;
            }
        }
        return true;        
    } //=== isSorted
    
    
    static void timeSorts() {
        final int SIZE = 3000;
        MyTerminal.cls();
        int choice;
        System.out.println("COMPARING SORTS OF " + SIZE + " Student ELEMENTS (be patient):\n");
        System.out.println("SORTING ALGORITHM" + TAB + "SECONDS");
        for (int k = 1; k < SORTS.length; k++ ) {
            choice = k;
            if ( k > 3 ) choice = k + 1;            
            System.out.print(SORTS[choice-1] + ":       " + TAB);
            long t0 = System.currentTimeMillis();
            while ( System.currentTimeMillis() == t0 ); t0++;
            Student[] A = makeArray(SIZE);
            switch ( choice ) {
                case 1: selectSort(A); break;
                case 2: insertSort(A); break;
                case 3: bubbleSort(A); break;
                case 5: mergeSort(A, 0, A.length-1); break;
                case 6: quickSort(A, 0, A.length-1); break;
                default:  JOptionPane.showMessageDialog( null, "timeSorts method error", 
                    "FIX timeSorts", JOptionPane.ERROR_MESSAGE);
            } //===switch
            long t1 = System.currentTimeMillis();
            long t = t1 - t0;
            isSorted(A, choice);
            System.out.println(t/1000 + "." + t % 1000);            
        }//=== for k      
        JOptionPane.showMessageDialog(null, "Comparison on identical arrays is over", 
                    "SORT RESULTS IN SECONDS", JOptionPane.INFORMATION_MESSAGE);                    
    } //=== timeSorts
            
    
    static void print(final Student[] A) {
        System.out.println("index" + TAB + "____name____" + TAB + "GPA" + TAB + "YOB"); 
        for (int k = 0; k < A.length; k++) {
            System.out.println(k + TAB + A[k] );   
        }
    }//=== print
    
    
} //=== SortDriver


class Student implements Comparable {
    private final String name;
    private double GPA;
    private int YOB;
    private static Random rGen = new Random(17);
    
    
    private static final String[] nameList = {"Pat", "Leslie", "Ying", "Jan"};
    private static int listTraversals = 0;    
    private static int listIndex = 0;
    public static void setListVars() { listTraversals = listIndex = 0; rGen.setSeed(17); } 
    
   public Student() {
        this(nameList[listIndex] + listTraversals + ", " + nameList[(listIndex + 1) % nameList.length], 
             1 + rGen.nextInt(3) + 0.2* rGen.nextInt(5), 1986 + rGen.nextInt(4));
        listIndex = (listIndex + 1) % nameList.length;
        if ( listIndex == 0 ) listTraversals += 1;              
   }

    public Student(String name, double GPA, int YOB) {
        this.name = name; this.GPA = GPA; this.YOB = YOB;   
    }    
    
    public String getName() {
        return name;   
    }

    public double getGPA() {
        return GPA;   
    }
       
    public String toString() {
        return name + "\t" + GPA + "\t" + YOB;                        
    }
    
    public boolean equals(Student e) {
        if ( e == null ) return false;
        else return name.equals(e.name) && GPA == e.GPA && YOB == e.YOB;   
    }
    
    public int compareTo(Object obj) {
        if ( !obj.getClass().getName().equals(getClass().getName()) ) return -1;
        Student other = (Student) obj;
        return name.compareTo(other.name);
    }   
} // === end of Student class