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 
{
    
    
    /**
         Tests insertion, deletion, and traversal in a small
           binary search tree, 
           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));
        t.traverse();
        System.out.print(t.getCounter());
        System.out.println(" comparisons used");
        t.resetCounter();
        t.delete(new Integer(10));  t.traverse();
        t.delete(new Integer(5));   t.traverse();
        t.delete(new Integer(7));   t.traverse();
        t.delete(new Integer(6));   t.traverse();
        t.delete(new Integer(0));   t.traverse();
        t.delete(new Integer(1));   t.traverse();
        t.delete(new Integer(8));   t.traverse();
        t.delete(new Integer(3));   t.traverse();
        t.delete(new Integer(2));   t.traverse();
        t.delete(new Integer(9));   t.traverse();
        t.delete(new Integer(4));   t.traverse();
        t.delete(new Integer(5));   t.traverse();  
        System.out.print(t.getCounter());
        System.out.println(" comparisons used");
        t.resetCounter();
        System.out.println();                                        }


    
    /**
         Tests insertion into, and traversal of,
            a larger and unbalanced binary search tree, 
           and prints the number of comparisons used.
     */
    
    public static void test2()                                      {
        BinarySearchTree t = new BinarySearchTree();
        for (int i = 0; i<100; i++)                     
            t.insert(new Integer(i));
        t.traverse();  
        System.out.print(t.getCounter());
        System.out.println(" comparisons used");
        t.resetCounter();
        System.out.println();                                      }
            
    
    /**
         Tests insertion of random data into a binary search tree,
           and traversal of the resulting tree, 
           and prints the number of comparisons used.
     */

    public static void test3()                                        {
        BinarySearchTree t = new BinarySearchTree();
        int temp;
        boolean wasOperationPerformed;
        Random r = new Random(1);
        for (int i = 0; i<100; i++)                                 {
            temp = r.nextInt(1000);
            wasOperationPerformed = t.insert(new Integer(temp));
            if (!wasOperationPerformed)                           {
              System.out.print("duplicate insertion ");
              System.out.print("of " + temp);
              System.out.println(" not performed");               }
            temp = r.nextInt(1000);
            wasOperationPerformed = t.insert(new Integer(temp));
            if (!wasOperationPerformed)                           {
              System.out.print("duplicate insertion ");
              System.out.print("of " + temp);
              System.out.println(" not performed");               }
            temp = r.nextInt(1000);                                  } 
        t.traverse();  
        System.out.print(t.getCounter());
        System.out.println(" comparisons used");
        t.resetCounter();
        System.out.println();                                      }
            
    
    /**
         Tests insertion of random data into a binary search tree,
           asymmetric deletion from the tree, 
           and traversal of the resulting tree, 
           and prints the number of comparisons used.
     */
    
    public static void test4()                                         {
        BinarySearchTree t = new BinarySearchTree();
        int temp;
        boolean wasOperationPerformed;
        Random r = new Random(1);
        for (int i = 0; i<100; i++)                                 {
            temp = r.nextInt(1000);
            wasOperationPerformed = t.insert(new Integer(temp));
            if (!wasOperationPerformed)                           {
              System.out.print("duplicate insertion ");
              System.out.print("of " + temp);
              System.out.println(" not performed");               }
            temp = r.nextInt(1000);
            wasOperationPerformed = t.insert(new Integer(temp));
            if (!wasOperationPerformed)                           {
              System.out.print("duplicate insertion ");
              System.out.print("of " + temp);
              System.out.println(" not performed");               }
            temp = r.nextInt(1000);
            wasOperationPerformed = t.delete(new Integer(temp)); 
            if (wasOperationPerformed)
              System.out.println("  element " + temp + " deleted"); } 
        t.traverse();  
        System.out.print(t.getCounter());
        System.out.println(" comparisons used");
        t.resetCounter();
        System.out.println();                                           }

    
    /**
         Tests insertion of random data into a binary search tree,
           symmetric deletion from the tree, 
           and traversal of the resulting tree, 
           and prints the number of comparisons used.
     */
    
    public static void test5()                                          {
        BinarySearchTree t = new BinarySearchTree();
        int temp;
        boolean wasOperationPerformed;
        Random r = new Random(1);
        for (int i = 0; i<100; i++)                                 {
            temp = r.nextInt(1000);
            wasOperationPerformed = t.insert(new Integer(temp));
            if (!wasOperationPerformed)                           {
              System.out.print("duplicate insertion ");
              System.out.print("of " + temp);
              System.out.println(" not performed");     }
            temp = r.nextInt(1000);
            wasOperationPerformed = t.insert(new Integer(temp));
            if (!wasOperationPerformed)                           {
              System.out.print("duplicate insertion ");
              System.out.print("of " + temp);
              System.out.println(" not performed");     }
            temp = r.nextInt(1000);
            wasOperationPerformed = 
              t.deleteSymmetric(new Integer(temp)); 
            if (wasOperationPerformed)
              System.out.println("  element " + temp + " deleted");} 
        t.traverse();  
        System.out.print(t.getCounter());
        System.out.println(" comparisons used");
        t.resetCounter();
        System.out.println();                                            }
    
     /**
         Performs the various tests on the BinarySearchTree class.
         @param args the command line arguments
     */
    public static void main(String[] args)                               {
        test1();
        System.out.println();                                            
        test2();
        System.out.println();                                            
        test3();
        System.out.println();                                            
        test4();
        System.out.println();                                            
        test5();
        System.out.println();                                            }
                                           
    
}