import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.IOException;

/**
   This program measures how long it takes to sort an
   array of a user-specified size with the quicksort
   algorithm.

   Revised to sort a number of different arrays with
   various orderings of the original contents, such as
   already sorted, reverse-sorted, ascending order with
   the first element out of order, most elements equal,
   and several random orderings.

   This test suite catches StackOverflowErrors so that
   subsequent tests can still be performed.  On my system,
   attempts to quicksort an already sorted, reverse-sorted,
   or almost sorted (first element out-of-order) array of
   size 100,000 using the first element as the pivot resulted
   in stack overflow errors.  Using the middle element as a 
   pivot overflowed the stack when sorting a 150,000-element 
   array sorted by halves.

   @author Cay Horstmann; rev. J. Mohr
*/
public class QuickSortTimer
{  
   private final static long[] SEEDS = 
   { 1L, 47L, 1234567890L, 0xABCDEFL, 0xDECAL };

   private static boolean stackOverflowed = false;   

   public static void main(String[] args)
   {  
      int[] a;
      long time;
      long totalTime = 0;

      int n = readInt("Enter array size: ");

      // Construct five random arrays for sorting.
      System.out.println("Sorting five random arrays:");
      for (int i = 0; i < SEEDS.length; i++ )
      {
	 a = ArrayUtil.randomIntArray( n, n, SEEDS[i] );
	 //ArrayUtil.print(a);
	 try
	 {
	    time = timeSort(a);
	    totalTime += time;
	    //ArrayUtil.print(a);
	    System.out.println("   " + time + " milliseconds");
	 }
	 catch ( StackOverflowError error )
	 {
	    System.out.println("ERROR: stack overflow.");
	    stackOverflowed = true;
	 }
      }

      System.out.println("\nAlready sorted array (ascending order):");
      a = ArrayUtil.ascendingIntArray(n);
      try
      {
	 time = timeSort(a);
	 totalTime += time;
	 System.out.println("   " + time + " milliseconds");
      }
      catch ( StackOverflowError error )
      {
	 System.out.println("ERROR: stack overflow.");
	 stackOverflowed = true;
      }

      System.out.println("\nReverse sorted array (descending order):");
      a = ArrayUtil.descendingIntArray(n);
      try
      {
	 time = timeSort(a);
	 totalTime += time;
	 System.out.println("   " + time + " milliseconds");
      }
      catch ( StackOverflowError error )
      {
	 System.out.println("ERROR: stack overflow.");
	 stackOverflowed = true;
      }

      System.out.println("\nArray sorted by halves " 
			 + "(double ascending order):");
      a = ArrayUtil.doubleAscendingIntArray(n);
      try
      {
	 time = timeSort(a);
	 totalTime += time;
	 System.out.println("   " + time + " milliseconds");
      }
      catch ( StackOverflowError error )
      {
	 System.out.println("ERROR: stack overflow.");
	 stackOverflowed = true;
      }

      System.out.println("\nSorted array except for first element "
			 + "(first element out-of-order):");
      a = ArrayUtil.firstOutOfOrderIntArray(n);
      try
      {
	 time = timeSort(a);
	 totalTime += time;
	 System.out.println("   " + time + " milliseconds");
      }
      catch ( StackOverflowError error )
      {
	 System.out.println("ERROR: stack overflow.");
	 stackOverflowed = true;
      }

      System.out.println("\nArray of mostly equal values:");
      a = ArrayUtil.mostEqualIntArray(n, n);
      try
      {
	 time = timeSort(a);
	 totalTime += time;
	 System.out.println("   " + time + " milliseconds");
      }
      catch ( StackOverflowError error )
      {
	 System.out.println("ERROR: stack overflow.");
	 stackOverflowed = true;
      }

      if ( ! stackOverflowed )
	 System.out.println("\nTotal sort time: " 
			    + totalTime + " milliseconds");
      else
	 System.out.println("\nTotal sort time unknown.");

      System.exit(0);
   }

   private static long timeSort(int[] a)
   {
      QuickSort sorter = new QuickSort(a);
      
      // use stopwatch to time sort
      StopWatch timer = new StopWatch();
      timer.start();
      sorter.sort();
      timer.stop();
      
      return timer.getElapsedTime();
   }
        
   private static int readInt(String prompt)
   {
      BufferedReader reader = new BufferedReader
	 (new InputStreamReader(System.in)); 

      int n = 0;
      boolean done = false;
      while (!done)
      {
	 System.out.print(prompt);
	 try
	 {
	    String inputString = reader.readLine();
	    n = Integer.parseInt(inputString);
	    done = true;
	 }
	 catch (IOException exception )
	 {
	    System.out.println("I/O error" + exception);
	 }
	 catch (NumberFormatException exception )
	 {
	    System.out.println("Input was not a number.  Try again.");
	 }
      }
      return n;
   }
}