import java.util.*;

/*
     A class to test insertion, deletion, and traversal in a binary
       search tree, and to observe the number of element comparisons
       used.
 */



public class A1 
{
    
    // used to tell BST constructor not to mutate input list
    // avoids the use of a "magic boolean"
    
    public static final boolean PRESERVE_INPUT_LIST = true; 
    
    
    
    /**
         Tests insertion and traversal in small
           balanced and unbalanced binary search trees, 
           and prints the number of comparisons used.
    */
    
    public static void test1()                            {
        BinarySearchTree t = new BinarySearchTree();
        t.insert(new Integer(8));
        t.insert(new Integer(5));
        t.insert(new Integer(4));
        t.insert(new Integer(9));
        t.insert(new Integer(1));
        t.insert(new Integer(7));
        t.insert(new Integer(6));
        t.insert(new Integer(3));
        t.insert(new Integer(2));
        t.insert(new Integer(0));
        System.out.println(t.traverse());
        System.out.print(t.getCounter());
        System.out.println(" comparisons used");

        ArrayList list = new ArrayList();
        for (int i=0; i<10; i++)
          list.add(new Integer(i));          
        t = new BinarySearchTree(list);        
        System.out.println(t.traverse());
        System.out.print(t.getCounter());
        System.out.println(" comparisons used");
        System.out.println();
        
        Random r = new Random(1);
        BinarySearchTree t1 = 
          new BinarySearchTree(list, r, PRESERVE_INPUT_LIST);
        System.out.println(t1.traverse());
        System.out.print(t1.getCounter());
        System.out.println(" comparisons used");
        System.out.println();             

        r = new Random(1);
        t1 = new BinarySearchTree(list, r, !PRESERVE_INPUT_LIST);
        System.out.println(t1.traverse());
        System.out.print(t1.getCounter());
        System.out.println(" comparisons used");
        System.out.println();             
        System.out.println("randomized list: " + list);           
        System.out.println();                                       }
                                      


    /**
         Tests insertion into, and traversal of,
            larger balanced and unbalanced binary search trees, 
           and prints the number of comparisons used.
     */
    
    public static void test2()                                      {
        BinarySearchTree t = new BinarySearchTree();
        Random r = new Random(2);
        boolean wasElementInserted;
        Integer ii;
        for (int i = 0; i<100; i++)                             { 
          ii = new Integer(r.nextInt(1000));
          wasElementInserted = t.insert(ii);
          if (!wasElementInserted)  
            System.out.println(ii + " is already in tree -- " +
                       "no duplicate insertion performed");     }
        System.out.println(t.traverse());
        System.out.print(t.getCounter());
        System.out.println(" comparisons used");
        System.out.println();                                      
        
        ArrayList list = new ArrayList();
        for (int i=0; i<100; i++)
          list.add(new Integer(i));          
        t = new BinarySearchTree(list);        
        System.out.println(t.traverse());
        System.out.print(t.getCounter());
        System.out.println(" comparisons used");
        System.out.println();
        
        r = new Random(3);
        BinarySearchTree t1 = 
          new BinarySearchTree(list, r, PRESERVE_INPUT_LIST);
        System.out.println(t1.traverse());
        System.out.print(t1.getCounter());
        System.out.println(" comparisons used");
        System.out.println();             

        r = new Random(3);
        t1 = new BinarySearchTree(list, r, !PRESERVE_INPUT_LIST);
        System.out.println(t1.traverse());
        System.out.print(t1.getCounter());
        System.out.println(" comparisons used");
        System.out.println();             
        System.out.println("randomized list: " + list);           
        System.out.println();                                         }
        
        
            
    
    /**
         Tests insertion of random data into a binary search tree,
           traversal of the resulting tree, and the method that
           resets the comparison counter.
     */
    
    public static void test3()                                     {
        BinarySearchTree t = new BinarySearchTree();

        Random r = new Random(4);
        for (int i = 0; i<200; i++)                     
            t.insert(new Integer(r.nextInt(1000)));
        System.out.println(t.traverse());
        System.out.print(t.getCounter());
        System.out.println(" comparisons used");
        System.out.println();                                      
        
        t = new BinarySearchTree();
        r = new Random(4);
        for (int i = 0; i<100; i++)                     
            t.insert(new Integer(r.nextInt(1000)));
        System.out.println(t.traverse());
        System.out.print(t.getCounter());
        System.out.println(" comparisons used");
        t.resetCounter();
        System.out.println();                                      

        for (int i = 100; i<200; i++)                     
            t.insert(new Integer(r.nextInt(1000)));
        System.out.println(t.traverse());
        System.out.print(t.getCounter());
        System.out.println(" comparisons used");
        System.out.println();                                      }    



      /**
          Tests handling of incommensurable values
            in BinarySearchTree constructors.
      */
      
      public static void test4()                                   {
      BinarySearchTree t;
      Random r;
        try                                                     {
          t = new BinarySearchTree();
          t.insert(new Integer(8));
          t.insert(new Integer(5));
          t.insert("four");                                     }
        catch (ClassCastException e)                            {
          e.printStackTrace();                                  }
        try                                                     {
          ArrayList list = new ArrayList();
          for (int i=0; i<10; i++)
            list.add(new Integer(i));          
          list.add("eleven");  
          t = new BinarySearchTree(list);                       }  
        catch (ClassCastException e)                            {
          e.printStackTrace();                                  }
        try                                                     {
          r = new Random(5);
          ArrayList list = new ArrayList();
          for (int i=0; i<10; i++)
            list.add(new Integer(i));          
          list.add("eleven");  
          t = new BinarySearchTree(list,r,PRESERVE_INPUT_LIST); }  
        catch (ClassCastException e)                            {
          e.printStackTrace();                                  }
        try                                                     {
          r = new Random(5);
          ArrayList list = new ArrayList();
          for (int i=0; i<10; i++)
            list.add(new Integer(i));          
          list.add("eleven");  
          t = new BinarySearchTree(list,r,PRESERVE_INPUT_LIST); }  
        catch (ClassCastException e)                            {
          e.printStackTrace();                                  }  }


     /**
         Performs the various tests on the BinarySearchTree class.
         @param args the command line arguments
     */
     // test class cast error (not Comparable)??
     //   in two nontrivial constructors
     //     with both boolean args in 3d ctor??
     //   in randomization algorithm -- just doc
     // test noncomparable, and incommensurable comparables
     
    public static void main(String[] args)                               {
        test1();
        System.out.println();                                            
        test2();
        System.out.println();                                            
        test3();
        System.out.println();                                            
        test4();
        System.out.println();                                            }
                                           
    
}