import java.util.*;

public class A2
{
    
    /**
        This method constructs an array of integers of a given size,
        with random elements ranging uniformly from 0 up to but not including 
        a given integer value.  It assumes that the size is nonnegative.
        @param size the given size
        @param r a Random object to generate the array elements.
        @param bound the given integer value  
        @return the constructed array
     */
       
    public static int[] buildRandomArray(int size, Random r, int bound)   {
      int[] a = new int[size];        
      for (int i=0; i<size; i++)
          a[i] = r.nextInt(bound);
      return a;                                                           }
     
    
    /**
        This method constructs a sorted array of integers of a given size,
        with consecutive elements differing by an increment varying randomly
        and uniformly from 0 up to but not including a given maximum increment.
        It assumes that the size is positive.
        @param size the given size
        @param r a Random object to generate the array increments.
        @param maxIncrement the given maximum increment 
        @return the sorted array
     */
    
    public static int[] buildRandomSortedArray(int size, Random r, 
                                                int maxIncrement)         {
      int[] a = new int[size];
      a[0] = r.nextInt(maxIncrement);
      for (int i=1; i<size; i++)
          a[i] = a[i-1] + r.nextInt(maxIncrement);
      return a;                                                           }
        

  
    
    /**
       A quick and dirty method to print the value of a given integer
       in a given number of spaces.  The integer will overflow the
       given number of spaces if it's long enough
       @param val the given integer
       @param len the given number of spaces
     */
     // Concatenation shouldn't be too inefficient, 
     // since <code>len</code> is usually small
    
    public static String ezFormatter(long val, int len)                    {
        String s = String.valueOf(val);
        for (int i=s.length(); i<=len; i++)
            s = " " + s;
        return s;                                                          }

    
    /**
        A program to test the Duplicate Tester class by testing the
        three methods for checking duplicates on different sized arrays.
        Currently, each of 9 different array sizes is tested 10 times,
        and the maximum number of comparisons for any of the 10 tests
        is printed.
     */
    
    public static void main(String args[])                            {
          // a DuplicateTester object to be tested
      DuplicateTester dt = new DuplicateTester();
          // an array to hold the test data
      int[] a;
          // the number of different array sizes to test
      int numberOfSizes = 9;
          // for counting numbers of comparisons
          // there's one array for each of the three methods
      long[] counter1 = new long[numberOfSizes];
      long[] counter2 = new long[numberOfSizes];
      long[] counter3 = new long[numberOfSizes];
           // initial array size
      int size = 4;
           // stores the worst-case number of comparisons for each size
      int counter = 0;

      // perform the tests and print the results

          System.out.print("   size                              ");
          System.out.println("results of 10 tests");
          System.out.print("                   naive              ");
          System.out.println("inefficient sort          efficient sort");

      // for each size, perform 10 tests on a random array, for each
      //   of the 3 methods.  Print "t" or "f" as the result of each 
      //   test, and update the comparison counter for that
      //   size and method if the number of comparisons is larger than
      //   the largest number that's been seen so far for that size.
          
      for (int j = 0; j < numberOfSizes; j++)                   {
          
          // test the first method
          
          Random r = new Random(1);
          System.out.print(ezFormatter(size,6));
          System.out.print("     ");
          counter = 0;
          for (int trial=1; trial<= 10; trial++)             {
             a = buildRandomArray(size,r,size*size);
             dt.resetCounter();
             System.out.print(" " + 
               String.valueOf(
                 dt.hasDuplicatesUnsorted(a)).charAt(0));
             if (dt.getCounter()>counter)
                 counter = dt.getCounter();                  } 
           System.out.print("    ");
           counter1[j] = counter;

          // test the 2nd method
          
           r = new Random(1);
           counter = 0;
          for (int trial=1; trial<= 10; trial++)             {
             a = buildRandomArray(size,r,size*size);
             dt.resetCounter();
             System.out.print(" " + 
               String.valueOf(
                 dt.hasDuplicates(a)).charAt(0));
             if (dt.getCounter()>counter)
                 counter = dt.getCounter();                  } 
          System.out.print("    ");
          counter2[j] = counter;  

          // test the 3rd method
          
           r = new Random(1);
           counter = 0;
          for (int trial=1; trial<= 10; trial++)            {
             a = buildRandomArray(size,r,size*size);
             dt.resetCounter();
             System.out.print(" " + 
               String.valueOf(
                 dt.hasDuplicatesEfficient(a)).charAt(0));
             if (dt.getCounter()>counter)
                 counter = dt.getCounter();                  }   
          System.out.print("    ");
          counter3[j] = counter;  
      
          size *= 2;               // try a larger array size                              
          System.out.println();                                  }

          // print the number of comparisons (in the worst case)
      
          System.out.println();
          System.out.print("                         ");
          System.out.println("largest number of comparisons in 10 tests");
          System.out.print("   size            naive              ");
          System.out.println("inefficient sort          efficient sort");
          System.out.println();
          
          size = 4;
          for (int j = 0; j < numberOfSizes; j++)                {
            System.out.print(ezFormatter(size,6));  
            System.out.print(ezFormatter(counter1[j],16));  
            System.out.print(ezFormatter(counter2[j],22));  
            System.out.print(ezFormatter(counter3[j],22));  
            System.out.println();  
            size *=2;                                            }    }
    
}