import java.util.Iterator;
import java.util.Stack;

import javax.swing.JOptionPane;

public class BinaryTreeExample {
    BinaryTree<Integer> t1;
    
    public BinaryTreeExample() throws Exception {
        BinaryTree<Integer> t4 = new BinaryTree<Integer>(111);
        BinaryTree<Integer> t7 = new BinaryTree<Integer>(4);
        BinaryTree<Integer> t8 = new BinaryTree<Integer>(10);
        BinaryTree<Integer> t6 = new BinaryTree<Integer>(21,t7,t8);
        BinaryTree<Integer> t5 = new BinaryTree<Integer>(73,new BinaryTree<Integer>(),t6);
        BinaryTree<Integer> t3 = new BinaryTree<Integer>(7,t4,new BinaryTree<Integer>());
        BinaryTree<Integer> t2 = new BinaryTree<Integer>(3,new BinaryTree<Integer>(),t3);
        t1 = new BinaryTree<Integer>(37,t2,t5);
        String out = "";
        out += "Prefix Listing\n" + t1.toPreFixString() + "\n";
        out += "Infix Listing\n" + t1.toInFixString() + "\n";
        out += "Postfix Listing\n" + t1.toPostFixString() + "\n";
        JOptionPane.showMessageDialog(null,out);
        out = "Using inorder iterator\n";
        Iterator<Integer> itr = t1.inorderIterator();
        while( itr.hasNext() ) {
            out += itr.next() + " ";
        } // end while
        out += "\n\nUsing preorder iterator\n";
        itr = t1.preorderIterator();
        while( itr.hasNext() ) {
            out += itr.next() + " ";
        } // end while
        out += "\n\nt1 contains 111 " + contains(111,t1);
        out += "\nt1 contains 37 " + contains(37,t1);
        out += "\nt1 contains 36 " + contains(36,t1);
        out += "\nt1 contains 0 " + contains(0,t1);
        out += "\n\nt1 has height " + height(t1);
        JOptionPane.showMessageDialog(null,out);
        out = "Using PreorderIterator defined outside the class\n\n";
        itr = new PreorderIterator<Integer>(t1);
        while( itr.hasNext() ) {
            out += itr.next() + "  ";
        }// end while
        out += "\n";
        JOptionPane.showMessageDialog(null,out);
    } // end constructor
    
    <T> boolean contains(T x, BinaryTree<T> tree) {
        if( tree.isEmpty() ) return false;
        if( x.equals(tree.getData()) ) return true;
        if( contains(x, tree.left()) ) return true;
        if( contains(x, tree.right()) ) return true;
        return false;
    } // end contains
    
    <T> int height(BinaryTree<T> tree) {
        if( tree.isLeaf() ) return 0;
        int h1 = 0;;
        if( !tree.left().isEmpty() ) {
            h1 = height(tree.left());
        } // end if
        int h2 = 0;
        if( !tree.right().isEmpty() ) {
            h2 = height(tree.right());
        } // end if
        if( h1 > h2 ) return h1+1;
        return h2+1;
    } // end height
    
    // This shows how to define an iterator outside the class
    class PreorderIterator<T> implements Iterator<T> {
        Stack<BinaryTree<T>> s;
        
        PreorderIterator(BinaryTree<T> tree) {
            s = new Stack<BinaryTree<T>>();
            s.push(tree);
        } // end constructor
        
        public boolean hasNext() {
            return !s.isEmpty();
        } // end hasNext
        
        public T next() {
            BinaryTree<T> next = s.pop();
            if( !next.right().isEmpty() ) s.push(next.right());
            if( !next.left().isEmpty() ) s.push(next.left());
            return next.getData();
        } // end next
        
        public void remove() {
            throw new UnsupportedOperationException();
        } // end remove
    } // end PreorderIterator
    
    public static void main(String[] args) throws Exception {
        new BinaryTreeExample();
        System.exit(0);
    } // end main
    
    
} // end BinaryTreeExample