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

public class TreeDriver {    

    public static TreeNode searchNode(TreeNode T, char name) {
    // precond: must search on std's name   
    //postcond: returns TreeNode containing name
        return T;
    } //=== search

   
    public static TreeNode insertNode(TreeNode T, Student item) {
    //postcond: item inserted in natural order
        return T;
     }//=== insertNode


    public static TreeNode deleteNode(TreeNode root, char name) {
    //postcond:  Returns L's 1st node; if item with name found, it's removed      
        return root;
     }//=== deleteNode


    public static void preOrder(final TreeNode T) {
    //postcond:  Prints T's nodes in preorder traversal
        System.out.print( "\tpreOrder(() not installed." );               
     }//=== preOrder
     
     
    public static void postOrder(final TreeNode T) {
    //postcond:  Prints T's nodes in postorder traversal
        System.out.print( "\tpostOrder(() not installed." );   
    }//=== postOrder
     
     
    public static void inOrder(final TreeNode T) {
    //postcond:  Prints T's nodes in inOrder traversal
        System.out.print( "\tinOrder(() not installed." );   
     }//=== inOrder
     

    public static int countNodes(final TreeNode T) {
    //postcond:  Returns number of nodes in tree T
        return -77;
     }//=== countNodes


    public static int height(final TreeNode T) {
    //postcond:  Returns height of tree T
        return -77;
      }//=== height

    
    public static TreeNode destroy(TreeNode T) {
    //postcondtion: every element of L is deleted  
    //===========================================
    // Use this method to test your implementation of deleteNode
    //-----------------------------------------------------------
        int count = 0;
        while ( T != null && count <= 25 ) {
            T = deleteNode(T, ((Student)T.getValue()).getName() );   
            count += 1;
        }
        return T;
    } //=== destroy        
    //===============================================================================================================
    
    public static String TAB = "\t";
       
    public static void main(String[] args) {
        MyTerminal.cls();
        System.out.println("\t\t\tBinary Search Tree 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>...");
        TreeNode T  = null;
        for (;;) {      
            print(T);
            String strChoice;
            strChoice = JOptionPane.showInputDialog(null, new String[]
            {"1.     Search for node",    "2.     Insert node",
             "3.     Delete node",        "4.     Traverse tree",
             "5.     Count nodes",        "6.     Find height",  
             "7.     Get tree",           "8.     Destroy tree",
             "9.     Print tree",         "0.     Quit"} ,             
             "BINARY TREE 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.compareTo("0") > 0 )
                T = exec(T, Integer.parseInt(strChoice));
             else break;    
        }//=== for
        System.out.println("\nProgram over");
        System.exit(0);
    } // main
    
    
    static TreeNode exec(TreeNode T, int choice) {
        switch ( choice ) {
            case 1: searchDriver(T);  break;        
            case 2: T = insertDriver(T); break;
            case 3: T = deleteDriver(T); break;
            case 4: traverseDriver(T);  break;
            case 5: // fall thru
            case 6: countHeightDriver(T, choice); break; 
            case 7: T = buildTree();  break;
            case 8: T = destroy(T);  break;
            case 9: break;
            default: break;
        }
        return T;
   } //=== exec
    
    
    static void searchDriver(final TreeNode T) {
        String nameSt = JOptionPane.showInputDialog(null, "Enter one-character name" ,
              "ENTER SEARCH VALUE AS SPECIFIED", JOptionPane.INFORMATION_MESSAGE); 
         char name = nameSt.charAt(0);
         TreeNode n = searchNode(T, name);          
         String title = "SEARCH TREE RESULTS", msg;         
         if ( n != null && ((Student)n.getValue()).getName() == name ) { 
             msg = name + " found. "; 
         }
         else msg = name + " not found.";
        JOptionPane.showMessageDialog(null, msg, 
                   title, JOptionPane.INFORMATION_MESSAGE);             
    } //=== searchDriver
    
    
    static TreeNode insertDriver(TreeNode T) {
        String title = "INSERTING STUDENT IN TREE";
        String name = JOptionPane.showInputDialog(null, "Enter one-character name",
              title, JOptionPane.INFORMATION_MESSAGE); 
        Student std = new Student(name.charAt(0));
        return insertNode(T, std);        
    } //=== insertDriver
    
    
    static TreeNode deleteDriver(TreeNode T) {
        String title = "DELETING STUDENT FROM TREE";
        String nameSt = JOptionPane.showInputDialog(null, "Enter name:",        
              title, JOptionPane.INFORMATION_MESSAGE); 
         char name = nameSt.charAt(0);              
         return deleteNode(T, name);
    } //=== deleteDriver
    


    static void countHeightDriver(TreeNode T, int choice) {
        String msg;
        if ( choice == 5 ) {  // count
            msg =  "countNodes(T) == " + countNodes(T);          
        }
        else {
            msg =  "height(T) == " + height(T);              
        }        
        JOptionPane.showMessageDialog(null, msg, 
                    "IMPLEMENTATION RESULTS", JOptionPane.INFORMATION_MESSAGE);                            
    } //=== countHeightDriver


    static void traverseDriver(final TreeNode T) {
        String title = "SPECIFY TRAVERSAL";
        char ch;
        do {
            //MyTerminal.cls();
            String str = JOptionPane.showInputDialog(null, "Select preorder, postorder, or inorder (1, 2, or 3)" ,
                title, JOptionPane.INFORMATION_MESSAGE); 
            ch = str.charAt(0);
            if ( ch == '1' ) { preOrder(T); }
            else if ( ch == '2' ) postOrder(T);
            else if ( ch == '3' ) inOrder(T);
            else title = "INVALID CHOICE---TRY AGAIN";
        } while ( ch < '1' || ch > '3' );
        System.out.print( "\n\n" );   
        JOptionPane.showMessageDialog(null, "", 
                    "TRAVERSAL RESULTS", JOptionPane.INFORMATION_MESSAGE);                             
    } //=== traverseDriver


    static TreeNode buildTree() {
        TreeNode root;
        root = new TreeNode(new Student('M'),
            new TreeNode(new Student('D'), null, 
               new TreeNode(new Student('H'), 
                  new TreeNode(new Student('F'), null, null), 
                  new TreeNode(new Student('K'), null, null))),
             new TreeNode(new Student('Q'), 
                new TreeNode(new Student('O'), null, null),
                new TreeNode(new Student('S'), null, 
                   new TreeNode(new Student('X'), 
                      new TreeNode(new Student('U'), null, null),
                      new TreeNode(new Student('Y'), null, null)))));          
        return root;
    }        


    //=====================================================
    //  printTree ROUTINES and info: max, height, markXY,
    //     initX, ROWS, COLS
    //=====================================================

    final static int initX = 39;
    final static int ROWS = 15, COLS = 78;
    static double[]  d = new double[ROWS];
    static StringBuffer[] treeMat = new StringBuffer[ROWS];
       
    static int max(int a, int b) {
        if ( a >= b ) return a;
        else return b;
    }

    static int hgt(TreeNode T) {
        if ( T == null ) return 0;
        else return 1 + max( hgt(T.getLeft()), hgt(T.getRight()) );
    }
    
    static void clearMat(StringBuffer[] M) {
        for (int r = 0; r < M.length; r++) {   
            M[r] = new StringBuffer(" ");
            for (int c = 0; c < COLS-1; c++)
                M[r].insert(c, " "); 
            
        }        
    }

    static void markXY(TreeNode T, int x, int level) {
        int dx = (int)(  initX/Math.floor(Math.exp(level * Math.log(2))) );   
        int newY = 2 * level - 1;
        String arcString = "+";
        if ( dx > 1 ) {
            for (int c = 1; c < dx; c++) {
                arcString += '-'; 
            }
            arcString += "+";            
        }
        else {
            arcString = "+";
        }
        if (T.getLeft() !=  null) {
            markXY(T.getLeft(), x - dx, level + 1);          
            treeMat[newY+1].replace(x - dx, x + dx, arcString);  //****
        }
        if ( x >= 0 && x < COLS && newY >= 0 && newY < ROWS) {
            String stName = "" + ((Student)T.getValue()).getName();            
            treeMat[newY].replace(x, x + 1, stName);
        }
        if (T.getRight() !=  null) {
            markXY(T.getRight(), x + dx, level + 1);
            treeMat[newY+1].replace(x, x + dx+1, arcString);     
        }        
    }//=== markXY
    

    static void printTree(TreeNode T) {
        final String title = "THE CURRENT TREE";
        final String title2 = "Printing not reliable for height > 6";
        System.out.println( "\t\t\t\t\t" + title);
        System.out.println( "\t\t\t\t\t" + title2 + "\n");        
        final String title3 = "Tree";
        String spaces = "";
        for (int c = 1; c <= initX - title3.length()/2; c++) spaces += ' ';
        System.out.println(spaces + title3); 
        clearMat(treeMat); 
        treeMat[0].setCharAt(initX, '|');
        if ( T == null )
            treeMat[1].replace(initX-2, initX+2, "null");            
        else 
             markXY(T, initX, 1);         
         for (int r = 0; r < ROWS; r++) {
            System.out.println( treeMat[r] ); 
         } // for
       System.out.println("\n\n\n\n\n\n\n");
    }//=== p    


    //=====================================================
    //          print ROUTINES: print2 and print
    //=====================================================

    static int print2(TreeNode T, int nodes) {
        //System.out.println("\tprint1 called: node = " + nodes);
        if ( T != null ) {
            nodes = print2(T.getLeft(), nodes);
            System.out.print( ((Student)T.getValue()).getName() + " ");
            nodes += 1;
            nodes = print2(T.getRight(), nodes);
        }
        return nodes;
    }//=== print2

    static void print(TreeNode T) {
        MyTerminal.cls();
        int nodes = 0;
        System.out.print( "Current tree: ");
        if ( T == null )
            System.out.println( "is empty");
        else
            nodes = print2(T, nodes);
        System.out.println( "\nNumber of nodes: " + nodes);;
        System.out.print( "Value of root: ");
        if ( T != null ) System.out.println( ((Student)T.getValue()).getName());
        else System.out.println( "Not applicable");
        System.out.println( "Height: " + hgt(T));  
        printTree(T); //===========================
   }//===print     
    
} //=== TreeDriver


class Student implements Comparable {
    private char 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 char getName() {
        return name;   
    }
     
    public String toString() {
        return "[" + name + "]";                        
    }
    
    public boolean equals(Student e) {
        if ( e == null ) return false;
        else return (name == e.name);   
    }
    
    public int compareTo(Object obj) {
        if ( !obj.getClass().getName().equals(getClass().getName()) ) return -77;
        Student other = (Student) obj;
        return name - other.name;
    }   
} // === end of Student class