import java.util.*;

/*
    This is a class for testing the behavior of the AVL class,
    for Assignment 2, CS 146, Spring 2003.
    All of the methods are static, so the default constructor
    is acceptable.
*/




public class A2
{

  /**
       Prints the elements of a List on the same line,
       separated by single spaces.
     @param the list
   */

  public static void traverseList(List l)                   {
    Iterator lit = l.iterator();
    while (lit.hasNext())
      System.out.print(lit.next() + " ");
    System.out.println();                                   }



  /**
      Constructs a randomly created String of length 3
      consisting of random lower-case letters, except
      that the 2nd letter is 'a'.
      @param r a Random object used to create the characters
      @return the randomly created String.
  */

  public static String randomString(Random r)               {
    StringBuffer sb = new StringBuffer(3);
    sb.append((char) ('a'+r.nextInt(26)));
    sb.append('a');
    sb.append((char) ('a'+r.nextInt(26)));
    return new String(sb);                                  }


  /**
      Tests the AVL class
      @param args is ignored.
  */

  public static void main(String[] args)                    {
    Random r = new Random(2);

    AVL a = new AVL();
    BinarySearchTree b = new BinarySearchTree();
    AVL a2 = new AVL(b);

    List l = b.traverse();

    System.out.println("the size of B is " + l.size());
	System.out.println("the height of B is " + b.height());
    System.out.println();

	System.out.println("the size of A is " + a.size());
    System.out.println("the height of A is " + a.height());
	System.out.println();

	System.out.println("the size of A2 is " + a2.size());
    System.out.println("the height of A2 is " + a2.height());
	System.out.println();
    System.out.println();


    int key=2;
    int factor = 7;
    int n=17;
    for (int i=1; i<n; i++)                     {
        a.insert(new Integer(10*key));
        b.insert(new Integer(10*key));
        key = key * factor % n;                 }
    a2 = new AVL(b);

    l = b.traverse();
    traverseList(l);
    System.out.println();
    System.out.print(b.getCounter());
	System.out.println(" comparisons were used for B");
    b.resetCounter();
	System.out.println("the size of B is " + l.size());
	System.out.println("the height of B is " + b.height());
	System.out.println();

	l = a.traverse();
	traverseList(l);
	System.out.println();
	System.out.print(a.getCounter());
    System.out.println(" comparisons were used for A");
	a.resetCounter();
    System.out.println("the size of A is " + a.size());
	System.out.println("the height of A is " + a.height());
    System.out.println();

	l = a2.traverse();
	traverseList(l);
	System.out.println();
	System.out.print(a2.getCounter());
    System.out.println(" comparisons were used for A2");
	a2.resetCounter();
	System.out.println("the size of A2 is " + a2.size());
	System.out.println("the height of A2 is " + a2.height());
	System.out.println();
	System.out.println();


    a = new AVL();
    b = new BinarySearchTree();
    boolean wasInserted;
	for (int i=1; i<n; i++)                                  {
      int k = r.nextInt(20);
      wasInserted = a.insert(new Integer(k));
      if (!wasInserted)                                   {
        System.out.print(k + " is already in A");
        System.out.println(" and was not inserted");      }  
	  wasInserted = b.insert(new Integer(k));
      if (!wasInserted)                                   {
		System.out.print(k + " is already in B");
		System.out.println(" and was not inserted");      }  } 
    a2 = new AVL(b);
	System.out.println();
    
	l = b.traverse();
	traverseList(l);
	System.out.println();
	System.out.print(b.getCounter());
    System.out.println(" comparisons were used for B");
	b.resetCounter();
	System.out.println("the size of B is " + l.size());
	System.out.println("the height of B is " + b.height());
	System.out.println();

	l = a.traverse();
    traverseList(l);
    System.out.println();
	System.out.print(a.getCounter());
	System.out.println(" comparisons were used for A");
	a.resetCounter();
	System.out.println("the size of A is " + a.size());
	System.out.println("the height of A is " + a.height());
	System.out.println();

	l = a2.traverse();
	traverseList(l);
	System.out.println();
	System.out.print(a2.getCounter());
	System.out.println(" comparisons were used for A2");
	a2.resetCounter();
	System.out.println("the size of A2 is " + a2.size());
	System.out.println("the height of A2 is " + a2.height());
	System.out.println();
	System.out.println();



    a = new AVL();
    b = new BinarySearchTree();
    for (int i=1; i<=300; i++)                 {
      String s = randomString(r);	
      a.insert(s);
      b.insert(s);                             }
    a2 = new AVL(b);  

	l = b.traverse();
	System.out.print(b.getCounter());
    System.out.println(" comparisons were used for B");
	b.resetCounter();
    System.out.println("the size of B is " + l.size());
	System.out.println("the height of B is " + b.height());
    System.out.println();

    System.out.print(a.getCounter());
	System.out.println(" comparisons were used for A");
	a.resetCounter();
	System.out.println("the size of A is " + a.size());
	System.out.println("the height of A is " + a.height());
	System.out.println();

	System.out.print(a2.getCounter());
	System.out.println(" comparisons were used for A2");
	a2.resetCounter();
	System.out.println("the size of A2 is " + a2.size());
	System.out.println("the height of A2 is " + a2.height());
	System.out.println();
	System.out.println();



    a = new AVL();
    b = new BinarySearchTree();
    for (int i=1; i<=5000; i++)                         {
      double d = r.nextDouble();
      a.insert(new Double(d));
      b.insert(new Double(d));                          }
    a2 = new AVL(b);    

    List la = a.traverse();
	List lb = b.traverse();
    List la2 = a2.traverse();

	System.out.print(b.getCounter());
	System.out.println(" comparisons were used for B");
	b.resetCounter();
	System.out.println("the size of B is " + lb.size());
	System.out.println("the height of B is " + b.height());
	System.out.println();

	System.out.print(a.getCounter());
	System.out.println(" comparisons were used for A");
    a.resetCounter();
    System.out.println("the size of A is " + a.size());
	System.out.println("the height of A is " + a.height());
	System.out.println();

	System.out.print(a2.getCounter());
	System.out.println(" comparisons were used for A2");
	a2.resetCounter();
	System.out.println("the size of A2 is " + a2.size());
	System.out.println("the height of A2 is " + a2.height());
	System.out.println();

    System.out.println(lb.equals(la2));
    System.out.println(la.equals(la2));
    
  }
}; // end of A2