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

public class LinkedListDriver {    

    public static ListNode seqSearch(ListNode L, String name) {
    // precond: must search on std's name   
    //postcond: returns ListNode containing name
        return L;  
    } //=== seqSearch

    public static ListNode seqSearchOrdered(ListNode L, String name) {
    //precond: must search on std's name    
    //postcond: returns ListNode containing name. Order is exploited
        return L;
    } //=== seqSearchOrdered
    
   
    public static ListNode insertUnordered(ListNode L, Student item) {
    //postcond: Returns L's first node, item inserted at end of L
        return L;  
    }//=== insertUnordered


    public static ListNode insertOrdered(ListNode L, Student item) {
    //postcond: Returns L's 1st node, item inserted in "natural order" of Student class 
        return L;
    }//=== insertOrdered


    public static ListNode deleteUnordered(ListNode L, String name) {
    //postcond:  Returns L's 1st node; if item with name found, it's removed
        return L;
    }//=== deleteUnordered


    public static ListNode deleteOrdered(ListNode L, String name) {
    // precond: L is in order.      
    //postcond:  Returns L's 1st node; if item with name is found, it's removed. The order of L is exloited.    
        return L;
    }//=== deleteOrdered
    

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

    
    public static ListNode destroy(ListNode L) {
    //postcondtion: every element of L is deleted    
        return L;
    } //=== destroy        
    //===============================================================================================================
    
    public static String TAB = "\t";
    
   
    public static void main(String[] args) {
        MyTerminal.cls();
        System.out.println("\t\t\tLinked List Driver Program\n");
        System.out.println("To use this program succesfully:\n\t1.\tStretch BlueJ Terminal Window HORIZONTALLY and VERTICALLY");
        System.out.println("\t2.\tMinimize all other windows.");                  
        MyTerminal.readString("\nPress <ENTER>...");
        ListNode A  = null;
        for (;;) {      
            MyTerminal.cls();
            print(A);
            String strChoice;
            strChoice = JOptionPane.showInputDialog(null, new String[]
            {"1.     Search unordered linked list\n",              "2.     Insert at end of unordered list\n",
             "3.     Delete from unordered list\n",                "4.     Get ready-made linked list",
             "5.     Search ordered linked list\n",                "6.     Insert into ordered linked list",  
             "7.     Delete from ordered linked list\n",           "8.     Destroy linked list",
             "9.     User-defined sort",                           "0.     Quit"} ,
              "LINKED LIST OPERARATIONS", 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.equals("4") ) {
                A = makeList(5);
                A = exec(A, Integer.parseInt(strChoice));
            }
            else if ( strChoice.compareTo("0") > 0 )
                A = exec(A, Integer.parseInt(strChoice));
           else break;    
        }//=== for
        System.out.println("\nProgram over");
        System.exit(0);
    } // main
    
    
    static ListNode exec(ListNode A, int choice) {
        String op = "";
        switch ( choice ) {
            case 1: searchDriver(A, choice); op = "search"; break;        
            case 2: A = insertDriver(A, choice); op = "insertion"; break;
            case 3: A = deleteDriver(A, choice ); op = "deletion"; break;
            case 4: String strChoice = JOptionPane.showInputDialog(null, "Ordered List (Y/N)?: " ,
                    "READY-MADE LIST", JOptionPane.INFORMATION_MESSAGE); op = "ready-made linked list";
                    if ( strChoice.charAt(0) == 'Y' || strChoice.charAt(0) == 'y' ) {
                        ArrayList AList = new ArrayList();
                        ListNode n;
                        for (n = A; n != null; n = n.getNext()) AList.add(n.getValue());
                        Collections.sort(AList);
                        ListIterator iter =  AList.listIterator();
                        n = A;
                        while ( iter.hasNext() ) {
                            n.setValue( iter.next() );  n = n.getNext();                           
                        }                        
                    }
                    break;
            case 5: searchDriver(A, choice ); op = "search"; break;
            case 6: A = insertDriver(A, choice); op = "insertion"; break;
            case 7: A = deleteDriver(A, choice); op = "deletion"; break;
            case 8: A = destroy(A); op = "destroy"; break;
            case 9: sort(A); op = "sort"; 
                    if ( !isSorted(A) ) op = "unsuccessful " + op; 
                    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);                     
        }
        return A;
   } //=== exec
    
    
    static void searchDriver(final ListNode A, int choice) {
        String name = JOptionPane.showInputDialog(null, "Enter name" ,
              "ENTER SEARCH VALUE AS SPECIFIED", JOptionPane.INFORMATION_MESSAGE); 
         ListNode p;     
         if ( choice == 1 ) p = seqSearch(A, name);
         else p = seqSearchOrdered(A, name);        
         String title = choice == 1 ? "SEQUENTIAL SEARCH (unordered list) RESULTS" : "SEQUENTIAL SEARCH (ordered list) RESULTS", msg;         
         if ( p != null ) { 
             msg = name + " found. GPA = " + ((Student)p.getValue()).getGPA();         
         }
         else msg = name + " not found.";
        JOptionPane.showMessageDialog(null, msg, 
                   title, JOptionPane.INFORMATION_MESSAGE);             
    } //=== searchDriver
    
    
    static ListNode insertDriver(ListNode A, int choice) {
        String title = "INSERTING STUDENT IN " + (choice == 2 ? "UNORDERED LIST" : "ORDERED LIST");
        String name = JOptionPane.showInputDialog(null, "Enter name",
              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 ) return insertUnordered(A, std);
        else { 
            isSorted(A);
            return insertOrdered(A, std); 
        }
    } //=== insertDriver
    
    
    static ListNode deleteDriver(ListNode A, int choice) {
        String title = "DELETING STUDENT FROM " + (choice == 3 ? "UNORDERED List" : "ORDERED List") + " OF " 
            + listSize(A) + " ITEMS";
        String name = JOptionPane.showInputDialog(null, "Enter name:",
              title, JOptionPane.INFORMATION_MESSAGE); 
         if ( choice == 3 ) 
            return deleteUnordered(A, name);
         else
            return deleteOrdered(A, name);
    } //=== deleteDriver
    

   static ListNode makeList(int n) {
        Student.setListNodeVars();
        ListNode A = new ListNode(new Student(), null);  
        ListNode curr = A;
        for (int k = 2; k <= n; k++) {
            curr.setNext(new ListNode(new Student(), null));
            curr = curr.getNext();           
        }           
        Random rGen = new Random(19);      
        for (int last = n; last > 1; last--) {
            int pos = rGen.nextInt(last);
            curr = A;
            int k;
            for (k = 1; k < pos; k++) curr = curr.getNext();
            ListNode lastNode = curr;
            for (; k < last; k++) lastNode = lastNode.getNext();  
            Object temp = curr.getValue(); curr.setValue(lastNode.getValue());
            lastNode.setValue(temp);
        }
        return A;        
    }        
       
            
    static boolean isSorted(final ListNode X) {
        ListNode curr = X , next;
        if ( curr == null || curr.getNext() == null )
            return true;              
        while ( curr.getNext() != null ) {
            next = curr.getNext();  
            Student currStd = (Student)curr.getValue();
            Student nextStd = (Student)next.getValue();
            if ( currStd.compareTo(nextStd) > 0 ) {
                   JOptionPane.showMessageDialog(null, "Items not in ascending order", 
                   "SORT RESULTS", JOptionPane.INFORMATION_MESSAGE);             
                return false;
            }
            currStd = nextStd;  
            curr = next;
        } //=== while              
        return true;
    } //=== isSorted
                  
    
    static void print(final ListNode A) {
        ListNode n;
        System.out.print("L-->");
        for (n = A; n != null; n = n.getNext() ) {
            Student std = (Student)n.getValue();
            System.out.print("[" + std.getName() + ", " + std.getGPA() + "]-->");   
        }
        System.out.println("null");
        System.out.println("\n\n\n\n\n\n\n\n\n");
    }//=== print
    
    
    static int listSize(final ListNode A) {
        if ( A == null ) return 0;
        else {
            int count = 1;
            for ( ListNode next = A.getNext(); next != null; next = next.getNext() ) 
                count += 1;
            return count;             
        }
    }//== listSize
    
    
} //=== LinkedListNodeDriver


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 setListNodeVars() { ListTraversals = ListIndex = 0; rGen.setSeed(17); } 
    
   public Student() {
        this(nameList[ListIndex] + ListTraversals /* + ", " + nameList[(ListNodeIndex + 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