import javax.swing.JOptionPane;
import javax.swing.JTextArea;
import javax.swing.JScrollPane;
import java.util.Stack;
import java.util.Iterator;
import java.util.ListIterator;

public class TreeExample {
    
    public TreeExample() {
        Tree<String> aTree = new Tree<String>("Root");
        aTree.addChild(new Tree<String>("T1"));
        aTree.addChild(new Tree<String>("T2"));
        aTree.addChild(new Tree<String>("T3"));
        aTree.addChild(new Tree<String>("T4"));
        Iterator<Tree<String>> itr = aTree.getChildren().iterator();
        int i = 1;
        while( itr.hasNext() ) {
            Tree<String> aChild = itr.next();
            aChild.addChild(new Tree<String>("T" + i + "1"));
            aChild.addChild(new Tree<String>("T" + i + "2"));
            aChild.addChild(new Tree<String>("T" + i + "3"));
            i++;
        } // end while
        itr = aTree.getChildren().iterator();
        Tree<String> first = itr.next();
        itr = first.getChildren().iterator();
        i = 1;
        while( itr.hasNext() ) {
            Tree<String> aChild = itr.next();
            aChild.addChild(new Tree<String>("T1" + i + "1"));
            aChild.addChild(new Tree<String>("T1" + i + "2"));
            i++;
        } // end while
        itr = aTree.getChildren().iterator();
        Tree<String> last = null;
        while( itr.hasNext() ) {
            last = itr.next();
        } // end while
        itr = last.getChildren().iterator();
        i = 1;
        while( itr.hasNext() ) {
            Tree<String> aChild = itr.next();
            aChild.addChild(new Tree<String>("T4" + i + "1"));
            aChild.addChild(new Tree<String>("T4" + i + "2"));
            i++;
        } // end while
        JTextArea outArea = new JTextArea(35,55);
        JScrollPane outPane = new JScrollPane(outArea);
        outArea.setText("Preorder:\n" + preorder(aTree));
        JOptionPane.showMessageDialog(null,outPane);
        outArea.setText("Inorder:\n" + inorder(aTree));        
        JOptionPane.showMessageDialog(null,outPane);
        outArea.setText("Postorder:\n" + postorder(aTree));
        JOptionPane.showMessageDialog(null,outPane);
        outArea.setText("Level Order:\n" + levelOrder(aTree));
        JOptionPane.showMessageDialog(null,"Number of Nodes:\n" + numberOfNodes(aTree));
        JOptionPane.showMessageDialog(null,"Height:\n" + height(aTree));
        
        String out = "";
        int size = 0;
        for( String s : aTree ) {
            out += s + ", ";
            size ++;
        }// end while
        out = out.substring(0,out.length()-2);
        out += "\nNumber of nodes = " + size;
        
        outArea.setText("Node listed by (preorder) iterator:\n" + out);
        JOptionPane.showMessageDialog(null,outPane);
        outArea.setText("Node listed by toString:\n" + aTree);
        JOptionPane.showMessageDialog(null,outPane);
        JOptionPane.showMessageDialog(null,"aTree contains T412 is " + contains("T412",aTree) + "\n");
        JOptionPane.showMessageDialog(null,"aTree contains Root is " + contains("Root",aTree) + "\n");
        JOptionPane.showMessageDialog(null,"aTree contains 37 is " + contains("37",aTree) + "\n");
        JOptionPane.showMessageDialog(null,"aTree contains T422 is " + contains("T422",aTree) + "\n");
        JOptionPane.showMessageDialog(null,"Level order is\n\n" + levelOrder(aTree) + "\n");        
    } // end constructor
    
    <T> boolean contains(T x, Tree<T> tree) {
        if( tree.isLeaf() ) return x.equals(tree.getData());
        if( x.equals(tree.getData()) ) return true;
        for( Tree<T> child : tree.getChildren() ) {
            if( contains(x,child) ) return true;
        } // end while
        return false;
    }
    
    <T> int numberOfNodes(Tree<T> tree) {
        if( tree.isLeaf() ) return 1;
        int num = 0;
        for( Tree<T> child : tree.getChildren() ) {
            num += numberOfNodes(child);
        } // end while
        return num + 1;
    } // end numberOfNodes
    
    <T> int height(Tree<T> tree) {
        if( tree.isLeaf() ) return 0;
        int h = 0;
        for( Tree<T> child : tree.getChildren() ) {
            int hTemp = height(child);
            if( h < hTemp ) h = hTemp;
        } // end while
        return h + 1;
    } // end height
    
    <T> String levelOrder(Tree<T> root) {
        String out = "Level 0: ";
        Queue<Tree<T>> q1 = new LinkedQueue<Tree<T>>();
        Queue<Integer> q2 = new LinkedQueue<Integer>();
        Integer currentDepth = 0;
        q1.enqueue(root);
        q2.enqueue(currentDepth);
        while( !q1.isEmpty() ) {
            Tree<T> t = q1.dequeue();
            int d = q2.dequeue();
            if( currentDepth < d ) {
                out += "\nLevel " + d + ": ";
                currentDepth = d;
            } // end if
            out += t.getData() + "  ";
            for( Tree<T> child : t.getChildren() ) {
                q1.enqueue(child);
                q2.enqueue(d + 1);
            } // end while
        } // end while
        return out;
    } // end levelOrder
    
    
    <T> String preorder(Tree<T> root) {
        String out = "";
        Stack<Tree<T>> s1 = new Stack<Tree<T>>();
        Stack<Integer> s2 = new Stack<Integer>();
        int currentDepth = 0;
        s1.push(root);
        s2.push(currentDepth);
        while( !s1.isEmpty() ) {
            Tree<T> t = s1.pop();
            int depth = s2.pop();
            for(int i = 0; i < 10*depth; i++ ) {
                out += " ";
            }
            out += t.getData() + "\n";
            ListIterator<Tree<T>> itr = t.getChildren().listIterator(t.getChildren().size());
            while( itr.hasPrevious() ) {
                s1.push(itr.previous());
                s2.push(depth + 1);
            } // end while
        } // end while
        return out;
    } // end preorder
    
    <T> String inorder(Tree<T> t) {
        String out = t.getData() + "  ";
        Iterator<Tree<T>> itr = t.getChildren().iterator();
        if( itr.hasNext() ) out = inorder(itr.next()) + "\n" + out + "\n";
        while( itr.hasNext() ) {
            out += inorder(itr.next()) + "\n";
        } // end while
        return out;
    } // end inorder
    
    <T> String postorder(Tree<T> t) {
        return postorder(t,0);
    } // end postorder
    
    <T> String postorder(Tree<T> t, int depth) {
        String out = "";
        Iterator<Tree<T>> itr = t.getChildren().iterator();
        while( itr.hasNext() ) {
            out += postorder(itr.next(),depth+1);
        } // end while
        for(int i = 0; i < 10*depth; i++ ) {
            out += " ";
        } // end for
        out += t.getData() + "\n";
        return out;
    } // end postorder
    
    public static void main(String[] args) {
        new TreeExample();
        System.exit(0);
    } // end main
    
} // end TreeExample