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

public class CollectionOps {    

    public static int seqSearch(List L, Student std) {
    //precond: must search on std's name    
         return -77;  
    } //=== seqSearch

    public static int binSearch(List L, Student std) {
    //precond: must search on std's name    
        return -77;        
    } //=== binSearch
    

    public static void sort(List L) {
        //=== replace this with your implementation of selection or insertion sort
        Collections.sort(L);             
    } //=== sort

    
    public static void insertUnordered(List L, Student item) {
        
    }//=== insertUnordered


    public static void insertOrdered(List L, Student item) {
        
    }//=== insertOrdered


    public static void deleteUnordered(List L, String name) {
        
    }//=== deleteUnordered


    public static void deleteOrdered(List L, String name) {
        
    }//=== deleteOrdered
    
    
    public static void destroy(List L) {
    //postcondtion: every element of L is deleted    
        
    } //=== destroy        
    //===============================================================================================================
    
    public static String TAB = "\t";
    public static final boolean LINKED_LIST = false, ARRAY_LIST = true; 
     
    public static void main(String[] args) {
        MyTerminal.cls();
        System.out.println("\t\t\tList Interface 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>...");
        List A = makeList(19, LINKED_LIST);
        for (;;) {      
            MyTerminal.cls();
            print(A);
            String strChoice;
            strChoice = JOptionPane.showInputDialog(null, new String[]
            {"1.     Search unordered list\n",              "2.     Insert unordered list\n",
             "3.     Delete from unordered list\n",         "4.     Sort list",
             "5.     Search ordered list\n",                "6.     Insert ordered list",  
             "7.     Delete from ordered list\n",           "8.     Destroy list",
             "9.     Time ArrayList & LinkedList sorts\n",  "0.     Quit"} ,
              "ENTER APPROPRIATE NUMBER", JOptionPane.INFORMATION_MESSAGE); 
             int choice;
            if ( strChoice.length() > 1 || strChoice.compareTo("0") < 0 || strChoice.compareTo("9") > 0 )
                JOptionPane.showMessageDialog( null, "ERROR: enter number in [0, 9]", 
                    "INPUT ERROR", JOptionPane.ERROR_MESSAGE);              
            else if ( strChoice.compareTo("0") > 0 )
                exec(A, Integer.parseInt(strChoice));
           else break;           
        }//=== for
        System.out.println("\nProgram over");
        System.exit(0);
    } // main
    
    
    static void exec(List A, int choice) {
        String op = "";
        switch ( choice ) {
            case 1: searchDriver(A, choice); op = "search"; break;        
            case 2: insertDriver(A, choice); op = "insertion"; break;
            case 3: deleteDriver(A, choice ); op = "deletion"; break;
            case 4: sort(A); op = "sort"; break;
            case 5: searchDriver(A, choice ); op = "search"; break;
            case 6: insertDriver(A, choice); op = "insertion"; break;
            case 7: deleteDriver(A, choice); op = "deletion"; break;
            case 8: destroy(A); op = "destroy"; break;
            case 9: sortComp(); op = "sort comparison"; break;
            default: break;
        }
        if ( choice != 1 && choice != 5 && choice != 9 ) {
            System.out.println("List after " + op + ":"); print(A);
            JOptionPane.showMessageDialog(null, op + " results:", 
                    "IMPLEMENTATION RESULTS", JOptionPane.INFORMATION_MESSAGE);  
        }
   } //=== exec
    
    
    static void searchDriver(final List A, int choice) {
        String name = JOptionPane.showInputDialog(null, "Enter lastName, firstName" ,
              "ENTER SEARCH VALUE AS SPECIFIED", JOptionPane.INFORMATION_MESSAGE); 
         int pos;     
         Student dummy = new Student(name, 0, 0); // dummy GPA and YOB values
         if ( choice == 1 ) pos = seqSearch(A, dummy);
         else pos = binSearch(A, dummy);
         String title = choice == 1 ? "SEQUENTIAL SEARCH RESULTS" : "BINARY SEARCH RESULTS", msg;
         if ( pos >= 0 ) msg = name + " found. GPA = " + ((Student)A.get(pos)).getGPA();
         else msg = name + " not found.";
        JOptionPane.showMessageDialog(null, msg, 
                   title, JOptionPane.INFORMATION_MESSAGE);             
    } //=== searchDriver
    
    
    static void insertDriver(List A, int choice) {
        String title = "INSERTING STUDENT IN " + (choice == 2 ? "UNORDERED LIST" : "ORDERED LIST");
        String name = JOptionPane.showInputDialog(null, "Enter lastName, firstName",
              title, JOptionPane.INFORMATION_MESSAGE); 
        String strGPA;
        String msg = "";
        for (;;) {
           strGPA = JOptionPane.showInputDialog(null, msg + "Enter GPA", title, JOptionPane.INFORMATION_MESSAGE);
           if ( strGPA.charAt(0) >= '0' && strGPA.charAt(0)<= '9' || strGPA.charAt(0) == '-' )
                break;
           else
                msg = "INVALID first character: " + strGPA.charAt(0) + " -- ";
        }
        double GPA = Double.parseDouble(strGPA);
        String strYOB;
        msg = "";
        for (;;) {
           strYOB = JOptionPane.showInputDialog(null, msg + "Enter YOB", title, JOptionPane.INFORMATION_MESSAGE);
           if ( strYOB.substring(0,1).compareTo("0") >= 0 &&  strYOB.substring(0,1).compareTo("9") <= 0 )
                break;
           else
                msg = "INVALID first character: " + strYOB.substring(0,1) + " -- ";
        }
        int YOB = Integer.parseInt(strYOB);   
        Student std = new Student(name, GPA, YOB);
        if ( choice == 2 ) insertUnordered(A, std);
        else if ( isSorted(A) ) {
            insertOrdered(A, std); 
        }
         // else isSorted posts a not sorted message        
    } //=== insertDriver
    
    
    static void deleteDriver(List A, int choice) {
        String title = "DELETING STUDENT FROM " + (choice == 3 ? "UNORDERED LIST" : "ORDERED LIST") + " OF " 
            + A.size() + " ITEMS";
        String name = JOptionPane.showInputDialog(null, "Enter lastName, firstName",
              title, JOptionPane.INFORMATION_MESSAGE); 
         if ( choice == 3 ) 
            deleteUnordered(A, name);
         else
            deleteOrdered(A, name);
    } //=== deleteDriver
    
    
   

    static void sortComp() {
        final int SORT_SIZE = 2000;
        MyTerminal.cls();
        System.out.println("COMPARING SORTS ON LIST TYPES OF " + SORT_SIZE + " ELEMENTS (be patient):\n");
        System.out.println("LIST TYPE" + TAB + "SECONDS");
        System.out.print("ArrayList" + TAB);
        List AL = makeList(SORT_SIZE, ARRAY_LIST);        
        long t0 = System.currentTimeMillis();
        while ( t0 == System.currentTimeMillis() );
        sort(AL);       
        long t1 = System.currentTimeMillis(), t = t1 - t0;
        isSorted(AL);
        System.out.println(t/1000 + "." + t % 1000);
        //-----------------------------------------------
         System.out.print("LinkedList" + TAB);
        List LL = makeList(SORT_SIZE, LINKED_LIST);
        t0 = System.currentTimeMillis();
        while ( t0 == System.currentTimeMillis() );
        sort(LL);
        t1 = System.currentTimeMillis();  t = t1 - t0;
        isSorted(LL);
        System.out.println(t/1000 + "." + t % 1000 + "\n");
        JOptionPane.showMessageDialog(null, "Sorts over", 
                    "COMPARISON RESULTS", JOptionPane.INFORMATION_MESSAGE);    
    } //=== sortComp

    
    
    static List makeList(int n, boolean listType) {
        List A;
        if ( listType == ARRAY_LIST ) A = new ArrayList(n);
        else A = new LinkedList();
        Student.setListVars();
        for (int k = 0; k < n; k++)
            A.add( new Student() );
        Random rGen = new Random(19);    
        for (int last = A.size(); last > 1; last--) {
            int pos = rGen.nextInt(last);
            Object temp = A.get(pos); A.set(pos, A.get(last-1)); A.set(last-1, temp); 
        }
        return A;        
    }        
    
    static boolean isSorted(final List X) {
        for (int k = 0; k < X.size() - 1; k++) {
            if ( ((Student)X.get(k)).compareTo(X.get(k+1)) > 0 ) {
                Student std_k = (Student)X.get(k), std_kPlus1 = (Student)X.get(k+1);
                String msg = "X.get(" + k + ").name = " + std_k.getName() + " > " + 
                    "X.get(" + (k + 1) + ").name = " + std_kPlus1.getName();
                JOptionPane.showMessageDialog( null, msg, 
                    "SORT FAILED", JOptionPane.ERROR_MESSAGE);
                    return false;
            }
        }
        return true;        
    } //=== isSorted
                  
    
    static void print(final List A) {
        System.out.println("index" + TAB + "____name____" + TAB + "GPA" + TAB + "YOB"); 
        for (int k = 0; k < A.size(); k++) {
            System.out.println(k + TAB + (Student)A.get(k) );   
        }
    }//=== print
    
    
} //=== CollectionOps


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 -77;
        Student other = (Student) obj;
        return name.compareTo(other.name);
    }   
} // === end of Student class