import java.util.*;
import java.text.*;


/**
    This class is used to test Assignment 4, CS 146, Spring 2004
*/

public class A4 {



  /**
      Converts an integer to a string of length 7
      @param the integer
      @return the string
*/

  public static String formatterEZ(int n)                       {
    String BLANKS = "       ";   // 7 blanks
    String s = BLANKS + n;
    return s.substring(s.length()-7);                           }


  /**
       Prints a 2-character string depending whose
       value depends on whether an ArrayList (1) is sorted
       and (2) equals a second ArrayList.  The first
       character is an "X" if the ArrayList is sorted,
       otherwise it is a blank.  The second character
       is an "X" if the two ArrayLists are equal, and a
       blank otherwise
       @param output the first ArrayList
       @param insortoutput the second ArrayList
  */
  public static void checkSortedness(ArrayList output,
                                     ArrayList insortoutput)        {
    if (isSorted(output))
      System.out.print(" ");
    else
      System.out.print("X");
    if (equals(output,insortoutput))
      System.out.print(" ");
    else
      System.out.print("X");                                    }


  /**
      Compares two ArrayLists of Comparable elements for equality
      @param a the first ArrayList
      @param b the second ArrayList
      @return <code>true</code> iff the two ArrayLists
       have the same length, and all elements in
       corresponding positions of the two ArrayLists
       are equal as integers.
   */
  public static boolean equals(ArrayList a, ArrayList b)        {
    if (a.size() != b.size())
      return false;
    for (int i=0; i<a.size(); i++)
      if (((Comparable) a.get(i)).compareTo(
           (Comparable) b.get(i)) != 0)
        return false;
    return true;                                                }


  /**
      Determines whether an ArrayList of Comparable elements
      is sorted in nondecreasing order.
      @param a the ArrayList
      @return <code>true</code> iff the ArrayList is sorted
  */
  public static boolean isSorted(ArrayList a)                   {
    int size = a.size();
    for (int i=0; i<size-1; i++)
      if (((Comparable) a.get(i)).compareTo(
           (Comparable) a.get(i+1)) > 0)
        return false;
    return true;                                                }



  /**
       Applies insertion sort, Collections.sort, and two versions
       of quicksort to an ArrayList of Comparable elements,
       and prints the number of comparisons used
       by each.  Flags (by printing an "X") any case where an algorithm
       returns an unsorted array, or an array different than the one
       returned by insertion sort.  A flag for the first type of
       error appears in the column immediately after the comparison
       count; the flag for the second type of error appears in the
       next column.
       @param a the array to be sorted
       @param cc an object that makes and counts the comparisons
  */

  public static void testAllAlgorithms(ArrayList a, CountingComparator cc,
             int firstCutoff, int lastCutoff, int cutoffIncrement)       {
    Sorter qs = new Sorter();

    ArrayList acopy = (ArrayList) a.clone();
    qs.insertionSort(acopy,cc);
    ArrayList output = (ArrayList) acopy.clone();
    System.out.print(formatterEZ(cc.getCounter()));
    checkSortedness(acopy, output);
    cc.reset();

    for (int cutoff=firstCutoff; cutoff<= lastCutoff;
                    cutoff+=cutoffIncrement)                  {
      acopy = (ArrayList) a.clone();
      qs.quicksortNaive(acopy, cutoff, cc);
      System.out.print(formatterEZ(cc.getCounter()));
      checkSortedness(acopy, output);
      cc.reset();                                             }

    System.out.println();
    System.out.print("                        ");

    acopy = (ArrayList) a.clone();
    Collections.sort(acopy,cc);
    System.out.print(formatterEZ(cc.getCounter()));
    checkSortedness(acopy, output);
    cc.reset();

     for (int cutoff=firstCutoff; cutoff<= lastCutoff;
                    cutoff+=cutoffIncrement)                  {
       acopy = (ArrayList) a.clone();
       qs.quicksortWeiss(acopy, cutoff, cc);
       System.out.print(formatterEZ(cc.getCounter()));
       checkSortedness(acopy, output);
       cc.reset();                                            }

    System.out.println();                                               }


   /**
       Creates various arrays of integers and tests sorting
        algorithms on them, while counting the number of
        comparisons they use.
       @param cc the comparator that maintains the count, and
        is also used for comparing the array elements.
   */

public static void test(CountingComparator cc)                          {
  int asize = 300;
  ArrayList a = new ArrayList(300);
  Random r = new Random(1);

  int firstCutoff = 4;
  int lastCutoff = 14;
  int cutoffIncrement = 2;

  System.out.println();
  System.out.println();
  System.out.print("                             number of element");
  System.out.println(" comparisons made ");
  System.out.println();
  System.out.print("                    ");
  System.out.print(" insertion sort     ");
  System.out.println("     naive quicksort ");
  System.out.print("                    ");
  System.out.print("Collections.sort    ");
  System.out.println("     Weiss's quicksort");
  System.out.print("cutoff value:                 ");

//  formatter.setMaximumIntegerDigits(7);
  for (int i=firstCutoff; i<=lastCutoff; i+=cutoffIncrement) {
    System.out.print("  ");
    System.out.print(formatterEZ(i));                        }
  System.out.println();

  System.out.print("random input            "     );
  a = new ArrayList(300);
  for (int i=0; i<=asize-1; i++)
      a.add(new Integer(r.nextInt(10000)));
  testAllAlgorithms(a, cc, firstCutoff, lastCutoff, cutoffIncrement);
  System.out.println();

  System.out.print("random input 2          "     );
  a = new ArrayList(300);
  for (int i=0; i<=asize-1; i++)
      a.add(new Double(r.nextDouble()));
  testAllAlgorithms(a, cc, firstCutoff, lastCutoff, cutoffIncrement);
  System.out.println();

  System.out.print("largely sorted input    "     );
  a = new ArrayList(300);
  for (int i=0; i<=asize-1; i++)
    a.add(new Integer(r.nextInt(10*i+2)));
  testAllAlgorithms(a, cc, firstCutoff, lastCutoff, cutoffIncrement);
  System.out.println();

  System.out.print("sorted input            "     );
  a = new ArrayList(300);
  for (int i=0; i<=asize-1; i++)
    a.add(new Integer(2*i));
  testAllAlgorithms(a, cc, firstCutoff, lastCutoff, cutoffIncrement);
  System.out.println();

  System.out.print("reverse sorted input    "     );
  a = new ArrayList(300);
  for (int i=0; i<=asize-1; i++)
    a.add(new Integer(2*(asize-i)));
  testAllAlgorithms(a, cc, firstCutoff, lastCutoff, cutoffIncrement);
  System.out.println();

  System.out.print("constant input sequence "     );
  a = new ArrayList(300);
  for (int i=0; i<=asize-1; i++)
    a.add("hello");
  testAllAlgorithms(a, cc, firstCutoff, lastCutoff, cutoffIncrement);
  System.out.println();                                                  }




   /**
       Tests two versions of quicksort and prints the
       maximum stack size (depth of recursion) used
       by each of them on two randomly generated
       ArrayLists of Integers
      @param cc the comparator that is used for comparing
       the array elements, and that maintains counts of
       element comparisons.  These counts are not used
       by the method
   */

public static void testStack(CountingComparator cc)          {
  ArrayList a = new ArrayList(100000);
  ArrayList b = new ArrayList(100000);
  Random r = new Random(1);
  Sorter qs = new Sorter();

  for (int i=0; i<100000; i++)                    {
    a.add(new Integer(r.nextInt(1000000)));
    b.add(new Integer(r.nextInt(1000000)));       }

  System.out.print(
    "max stack size, 1st random input, no optimization: ");
  System.out.println(qs.quicksortWeiss(a,5,cc));
  System.out.print(
    "max stack size, 2nd random input, no optimization: ");
  System.out.println(qs.quicksortWeiss(b,5,cc));
  System.out.print(
    "max stack size, 1st random input, with optimization: ");
  System.out.println(qs.newQuicksortWeiss(a,5,cc));
  System.out.print(
    "max stack size, 2nd random input, with optimization: ");
  System.out.println(qs.newQuicksortWeiss(b,5,cc));           }



    /**
        Creates various arrays of integers and tests sorting
        algorithms on them
        @param args is ignored
    */

public static void main(String args[])                         {

  Sorter qs = new Sorter();
  CountingComparator cc = new CountingComparator();

  qs.insertionSort(null,cc);
  qs.quicksortNaive(null,4,cc);
  qs.quicksortWeiss(null,4,cc);

  ArrayList a = new ArrayList(100);
  Random r = new Random(0);
  for (int i=0; i<=99; i++)
      a.add(new Integer(r.nextInt(10000)));

  qs.insertionSort(a,null);
  qs.quicksortNaive(a,4,null);
  qs.quicksortWeiss(a,4,null);

  test(cc);
  testStack(cc);                                                    }


  }