// Heap2.java
//========================================================================
// INSTRUCTIONS: 
//   1. save to directory that has MyTerminal.java and PriorityQueue.java
//   2. implement isEmpty, and add
//   3. implement removeMin (and trickleDown, which supports removeMin)
//   4.
//   5. implement heapSort (and add2 & trickleDown2)
//=========================================================================
import javax.swing.*;
import java.util.*;

public class Heap2 implements PriorityQueue {
    private ArrayList A;
    
    public Heap2() {
        A = new ArrayList(); A.add("");
    }
    
    public Heap2(Heap2 h) {
        A = h.A;        
    }
    
    public boolean isEmpty() {
        return A.size() == 1;   
    }
    
    public Object peekMin() {
        return null;   
    }
    
    public void add(Object obj) {
 
 
    }


    public Object removeMin() {
    //precond: trickleDown has been implemented
        return null;
    }
       
   
    public void trickleDown(int parent) {

    }
        
    public void destroy() {
       for (int k = A.size()-1; k > 0; k--) 
            A.remove(k);
    }
    

    public void heapSort() { 
    //precond: add2 and trickleDown2 are implemented     
 
 
    }


    public void trickleDown2(int parent, int last) {

    }


    void add2(Object obj, int last) {

    }



    public String toString() {
        String heapSt = "";
        for (int k = 1; k < A.size(); k++)
            heapSt += " " + A.get(k);
        return heapSt;
    }
    
    public int last() {
       return A.size() - 1; 
    }
     
    
    public static void main(String[] arg) {
        Heap2 H; 
        MyTerminal.cls();
        System.out.println("\t\t\tMin-Heap/Priority Queue Driver Program\n");
        System.out.println("To use this program succesfully:\n\t1.\tStretch BlueJ Terminal Window HORIZONTALLY");
        System.out.println("\t2.\tMinimize all other windows.");                  
        MyTerminal.readString("\nPress <ENTER>...");
        H = buildHeap();
        for (;;) {      
            H.print();
            String strChoice;
            strChoice = JOptionPane.showInputDialog(null, new String[]
            {"1.     add()",    
             "2.     removeMin()",
             "3.     Pre-built heap",       
             "4.     Destroy heap",        
             "5.     Heap sort",         
             "0.     Quit"} ,             
             "MIN-HEAP/PRIORITY QUEUE OPERATIONS", JOptionPane.INFORMATION_MESSAGE);             
             int choice;
             if ( strChoice.length() > 1 || strChoice.compareTo("0") < 0 || strChoice.compareTo("5") > 0 ) {
                JOptionPane.showMessageDialog( null, "ERROR: enter number in [0, 5]", 
                    "INPUT ERROR", JOptionPane.ERROR_MESSAGE);              
             }
             else if ( strChoice.compareTo("0") > 0 )
                H = exec(H, Integer.parseInt(strChoice));
             else break;    
        }//=== for
        System.out.println("\nProgram over");
       
    } //=== main
    
   
    static Heap2 exec(Heap2 H, int choice) {
        switch ( choice ) {
            case 1: insertDriver(H);  break;        
            case 2: deleteDriver(H); break;
            case 3: H = buildHeap(); break;
            case 4: H.destroy();  break;
            case 5: sortDriver(H); break;
            default: break;
        }
        return H;
   } //=== exec
  

    public void print() {
        MyTerminal.cls();
        System.out.println("\n\n    H = " + this);
        System.out.print(  "index = ");
        for (int k = 1; k < A.size(); k++) { 
            Integer n = new Integer(k);
            String s = "  " + n + " ";  
            if ( k > 9 ) s = s.substring(0, s.length()-1);
            System.out.print(s);       
        }   
        System.out.println("\n\nH.isHeap() = " + isHeap());
        System.out.println("H.isSorted() = " + isSorted() + "\n\n\n");
    }
    
 
    static void insertDriver(Heap2 H) {
        String title = "INSERTING STUDENT INTO MIN-HEAP";
        String name = JOptionPane.showInputDialog(null, "Enter one-character name",
              title, JOptionPane.INFORMATION_MESSAGE); 
        Student std = new Student(name.substring(0,1));
        H.add(std);        
    } //=== insertDriver
 
 
    static void deleteDriver(Heap2 H) {
        String title = "DELETING STUDENT FROM MIN-HEAP";
        String objectSt = H.removeMin().toString();
        if ( objectSt == null ) objectSt = "null";
        JOptionPane.showMessageDialog(null, "Student = " + objectSt,
              title, JOptionPane.INFORMATION_MESSAGE); 
     } //=== insertDriver
 
 
    static void sortDriver(Heap2 H) {
        String title = "Scrambling heap before heap sort";
        H.scramble();      
        H.print();
        JOptionPane.showMessageDialog(null, "new data",
              title, JOptionPane.INFORMATION_MESSAGE); 
        H.heapSort();      
     } //=== insertDriver
     
     
     public void scramble() {
         for ( int m = 1, n = A.size() - 1; m < n; m++, n--) {
            Object tmp = A.get(m); A.set(m, A.get(n)); A.set(n, tmp);   
         }         
     }

 
    static Heap2 buildHeap() {
        Heap2 H = new Heap2();
        String s = "SHCKESPMTRE";
        for (int k = 0; k < s.length(); k++)
            H.add( new Student(s.substring(k, k+1)));
        return H;
    }
    
    boolean isHeap() {
        for (int child = 2; child < A.size(); child++) {
            if ( ((Comparable)A.get(child)).compareTo(A.get(child/2)) < 0 )
                return false;
        }
        return true;
    }
    
    boolean isSorted() {
        for (int succ = 2; succ < A.size(); succ++) {
            if ( ((Comparable)A.get(succ)).compareTo(A.get(succ-1)) < 0 )
                return false;
        }
        return true;
    }
    
    
    public Object foo(int k) {
        if ( k < 1 || k >= A.size() ) return null;
        return A.get(k);
    }
    
    
} //==== Heap2



class Student implements Comparable {
    private String name;

    private static Random rGen = new Random(17);
      
    private static char currentName = 'A';
    
    public static void setTreeNodeVars() { 
        currentName = 'A'; rGen.setSeed(17); 
    }               
    
   public Student() {
        name = "" + currentName; 
        if ( currentName < 'Z' ) currentName++;
        else currentName = 'A';
   }

    public Student(char ch) {
        name = "" + ch;  
    }    
    
    public Student(String name) {
        this.name = name;   
    }
    
    public String getName() {
        return name;   
    }
     
    public String toString() {
        return "[" + name + "]";                        
    }
    
    public boolean equals(Student e) {
        if ( e == null ) return false;
        else return (name.equals(e.name));   
    }
        
    
    public int compareTo(Object obj) {
        if ( obj == null || !obj.getClass().getName().equals(getClass().getName()) ) return -77;        
        return name.compareTo(((Student)obj).getName());        
    }   
} // === end of Student class