// FILE: AB96_3.java

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

public class AB96_3 {    

    public static boolean  ValsLess(TreeNode T,  int k) {
    // precondition: T is empty or a binary tree of Integer objects   
    //               intValue is the only Integer method needed.
    //postcondition: returns true if T is null or if all values stored in tree represented
    //     by T are less than k; otherwise returns false

	return false;
    } //=== ValsLess
  
  
    public static boolean IsBST(TreeNode T)  {
    // precondition: T is empty or a binary tree of Integer objects, ValsGreater is avaiable 
    //               intValue is the only Integer method needed.
    // postcondition: returns true if T represents a binary search 
    //   tree containing no duplicate values; otherwise, returns false.

	return false;
    } //=== IsBST

    //====================================================================================================
    
    public static String TAB = "\t";
       
    public static void main(String[] args) {
        MyTerminal.cls();
        ValsLessTest();
        System.out.println("\nIf OK prompt fails to appear, minimize all windows to find it");
        JOptionPane.showMessageDialog(null, "ValsLess test over", "Testing IsBST next" , JOptionPane.INFORMATION_MESSAGE); 
        MyTerminal.cls();
        IsBST_test();   
        System.out.println("\nProgram over");
    } // main
    

    static void ValsLessTest() {
        TreeNode T = buildTree();  
        printTree(T);
        System.out.println("Testing ValsLess:");
        System.out.println("ValsLess(T, 9) = " + ( ValsLess(T, 9) ? "true" : "false") + "\t\t(should = true)");
        System.out.println("ValsLess(T, 8) = " + ( ValsLess(T, 8) ? "true" : "false") + "\t\t(should = false)");
        System.out.println("ValsLess(T.getLeft(), 8) = " + ( ValsLess(T.getLeft(), 8) ? "true" : "false") + "\t\t(should = true)");
        System.out.println("ValsLess(T.getLeft(), 2) = " + ( ValsLess(T.getLeft(), 2) ? "true" : "false") + "\t\t(should = false)");
    }

    static void IsBST_test() {
        TreeNode T = buildTree();  
        printTree(T);
        System.out.println("Testing IsBST with a near BST:");
        System.out.println("IsBST(T) = " + (IsBST(T) ? "true" : "false") + "\t\t(should = false)");       
        System.out.println("IsBST(T.getLeft()) = " + (IsBST(T.getLeft()) ? "true" : "false") + "\t\t(should = true)");       
        System.out.println("IsBST(T.getRight().getRight().getLeft()) = " + (IsBST(T.getRight().getRight().getLeft()) ? "true" : "false") 
            + "\t\t(should = true)");        
    }

    static TreeNode buildTree() {
        TreeNode root;
        root = new TreeNode( new Integer(4),
            new TreeNode( new Integer(3), 
               new TreeNode( new Integer(1), null,
                  new TreeNode( new Integer(2), null, null)
               ), null), 
            new TreeNode( new Integer(5), 
               new TreeNode( new Integer(6), null, null), 
               new TreeNode( new Integer(8), 
                  new TreeNode( new Integer(7), null, null), 
               null)
            )); 
        return root;
    }  
    
    static boolean ValsGreater(TreeNode T, int k) {
        if (T == null) return true;    
        return ( ((Integer)T.getValue()).intValue() > k && ValsGreater(T.getLeft(), k) 
                  && ValsGreater(T.getLeft(), k));
    }


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

    final static int initX = 30;
    final static int ROWS = 11, COLS = 78;
    static double[]  d = new double[ROWS];
    static StringBuffer[] treeMat = new StringBuffer[ROWS];

 
    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 stVal = "" + ((Integer)T.getValue());            
            treeMat[newY].replace(x, x + 1, stVal);
        }
        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 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
    }//===    

} //=== AB96_3