import java.io.*;                      // PrintWriter
import java.util.Scanner;              // Console dialog
import java.text.DecimalFormat;        // Force three digits after "."
import java.util.Calendar;             // Field definitions for Greg.Cal.
import java.util.Collections;          // Collections.sort()
import java.util.GregorianCalendar;    // Generate current time
import java.util.LinkedList;           // For Collections.sortd
import java.util.Random;               // Generator for repeatable series
import java.util.Iterator;             // Used in boolean ordered()
/**
 * Driver class to exercise several linked list sorting algorithms
 *
 * Tasks:
 * --- User dialog to get the parameters for the experimental run.
 * --- For each list size in the run, perform the appropriate trial
 *     runs with each algorithm, capturing the performance statistics
 *     and writing out to the CSV file for later examination
 *
 * Method used by main:
 *   void openOutput                   // open a PrintWriter
 *   void getStats                     // do the experiment
 *
 * Methods used by getStats
 *   int[] makeArray(int nMax)         // Array with [1..nMax]
 *   void shuffle (src, n)             // Shuffle first n items
 *   void fillList (src, n, working)   // List working gets n items
 *   String currentTimeString()        // Format current time
 *   and, of course, the assorted sorting algorithms in ListOps.
 *
 * Language restriction:
 *   This program uses java.util.Scanner.  Consequently it requires
 *   use of Java verison 1.5.x.
 *
 * @author  Timothy Rolfe
 */

public class SortDriver
{
   // Turn this flag on to enable validity checks after each sort
   static private final boolean DEBUG = false;

/**
 * The main itself does the user dialog or capture of the command line
 * arguments.  It then opens the output file and calls the getStats
 * method to do the numerical experiments themselves.
 */
   public static void main ( String[] args )
   {
      int n,                 // initial size,
          nMax,              // largest size
          nStep,             // increment for size
          nPasses;           // number of random lists to average together
      PrintWriter outFile;   // CSV file for later generate a spreadsheet
      Scanner console = new Scanner(System.in);
      String now,
             fileName = ( args.length > 4 ) ? args[4]
                                            : "SortCmp.csv";

      // Initial dialog --- allowing for command-line arguments
      System.out.print ("Initial size:  ");
      if ( args.length > 0 )
      {
         n = Integer.parseInt(args[0]);
         System.out.println(n);
      }
      else
         n = console.nextInt();

      System.out.print ("Final size:  ");
      if ( args.length > 1 )
      {
         nMax = Integer.parseInt(args[1]);
         System.out.println(nMax);
      }
      else
         nMax = console.nextInt();

      System.out.print ("Increment for size:  ");
      if ( args.length > 2 )
      {
         nStep = Integer.parseInt(args[2]);
         System.out.println(nStep);
      }
      else
         nStep = console.nextInt();

      System.out.print ("Samples for each size:  ");
      if ( args.length > 3 )
      {
         nPasses = Integer.parseInt(args[3]);
         System.out.println(nPasses);
      }
      else
         nPasses = console.nextInt();

      outFile = openOutput ( fileName );

      getStats ( n, nMax, nStep, nPasses, outFile );

      outFile.close();
   }

/**
 * Using the file name passed as a parameter, open the output file as
 * a PrintWriter.  If the open fails, enter into dialog with the user
 * to try different file names until one succeeds.
 *
 * @param     fileName  the initial name to be used for opening the file
 * @return    PrintWriter opened
 */
   static private PrintWriter openOutput ( String fileName )
   {
      PrintWriter outFile = null;

      while ( outFile == null )
      {
         try
         {  File f  = new File(fileName);
         // PrintWriter second argument:  autoflush
         //  FileWriter second argument:  append
            outFile = new PrintWriter(new FileWriter(f, true), true);
         }
         catch (IOException e)
         {  System.err.println ("File open failed for " + fileName + "\n" + e);
            System.out.println ("Try again:\n");
            outFile = null;  // PROBABLY superfluous, but just to be sure . . .
         }
      }
      return outFile;
   }

// Generator to allow repetition of a series of pseudorandom numbers
   static private Random generator = new Random();

/**
 * Perform the numerican experiments to characterize the behavior of the
 * sorting algorithms.  For each size (n), a number of lists (nPasses) are
 * generated and then sorted by the various algorithms.  After each sorting,
 * the number of compareTo() calls and milliseconds are added into the
 * appropriate arrays to accumulate sums that will then generate averages.
 *
 * @param     n        initial list size
 * @param     nMax     largest list size
 * @param     nStep    increment for the list size
 * @param     nPass    the number of lists of a given size to run
 * @param     outFile  comma-separated-value file for results
 */
   static private void getStats ( int n, int nMax, int nStep,
                                  int nPasses, PrintWriter outFile )
   {
      int[] src = makeArray(nMax);          // Fill with [1..nMax]
      int k, pass;                          // Loop variables
      long seed;                            // for generator.setSeed
      long start, finish;                   // for capturing time

      KWLinkedList   working = new KWLinkedList(); // List holding the data
      LinkedList     list    = new LinkedList();   // Option 7
      double[]      nCompares, mSecs;       // Summation arrays for stats
      DecimalFormat fmt = new DecimalFormat("0.000");
      String        now;                    // current time as a string
      int           alg = 0,                // Subscript
                    n_Alg = 8;

      outFile.println ("n,Select Cmp Iter,Select mSec Iter,"
                       + "Select Cmp Direct,Select mSec Direct,"
                       + "Insert Cmp Iter,Insert mSec Iter,"
                       + "Insert Cmp Direct,Insert mSec Direct,"
                       + "Merge Cmp Iter,Merge mSec Iter,"
                       + "Merge Cmp Direct,Merge mSec Direct,"
                       + "MyCol.cmp,MyCol.mSec,"
                       + "Coll. Cmp,Coll.mSec");

      seed = generator.nextLong();

      for ( ; n <= nMax ; n += nStep)
      {
         // Quick way to zero out the arrays
         nCompares = new double[n_Alg];
         mSecs     = new double[n_Alg];
         // Minimal output to the screen to keep the user happy.
         System.out.print ("Begin n=" + n); System.out.flush();

         for ( alg = 0; alg < n_Alg; alg++ )
         {
            String[] algorithm = { "selection iterator", "selection direct",
                                   "insertion iterator", "insertion direct",
                                   "merge iterator", "merge direct",
                                   "ListSort.sort", "Collections.sort" };

            generator.setSeed(seed);
            // Set the src array into the same state for each algorithm
            java.util.Arrays.sort(src,0,n);
            start = System.currentTimeMillis();
            for ( pass = 0; pass < nPasses; pass++ )
            {
               shuffle (src, n);
               if ( alg < n_Alg-1 )
               {
                  fillList (src, n, working);
               }
               else
               {
                  fillList (src, n, list);
               }
               switch ( alg )
               {
                  case 0:  ListSort.selectSort(working);  break;
                  case 1:   working.selectSort() ;        break;
                  case 2:  ListSort.insertSort(working);  break;
                  case 3:   working.insertSort() ;        break;
                  case 4:  ListSort.mergeSort (working);  break;
                  case 5:   working.mergeSort () ;        break;
                  case 6:  ListSort.sort(working);        break;
                  case 7:  Collections.sort(list);        break;
               }
               if ( DEBUG )
                  if ( alg < n_Alg-1 && !ordered(working, n) )
                  {
                     throw new RuntimeException ( "Sorting failed in " +
                        algorithm[alg] + " sort.");
                  }
                  else if ( alg == n_Alg-1 && !ordered(list, n) )
                  {
                     throw new RuntimeException ( "Sorting failed in " +
                        algorithm[alg] + " sort.");

                  }

               if ( alg < n_Alg-1 )
                  working.clear();
               else
                  list.clear();
            }
            finish = System.currentTimeMillis();
            nCompares[alg] = MyComparable.nCompares();
            mSecs[alg] = (double) (finish - start);
         }

         // Write the results to the output file
         outFile.print ( n );
         for ( k = 0; k < n_Alg; k++ )
            outFile.print (", " + fmt.format(nCompares[k]/nPasses) +
                           ", " + fmt.format(mSecs[k]/nPasses) );
         outFile.println();

         System.out.println ("\tFinished " + currentTimeString() );
         seed = generator.nextLong();
      }
      outFile.close();
   }

/**
 * Generate an array of "size" ints and fill it with values in order from
 * 1 up through "size".
 *
 * @param     size  the size for the array, and value for [size-1]
 * @return    array of int values from 1 to size
 */
   static private int[] makeArray(int size)
   {
      int k;
      int x[] = new int[size];

      for ( k = 0; k < size; k++ )
         x[k] = k;

      return x;
   }

/**
 * Shuffle the first "size" elements in the array x.
 *
 * @param  x     the array to be shuffled (from [0] to [size-1])
 * @param  size  the number of elements in x used in the shuffle
 * @see    "Timothy Rolfe, \"Algorithm Alley: Randomized Shuffling\", <B>Dr.
 *         Dobb's Journal</B>, Vol. 25, No. 1 (January 2000), pp. 113-14."
 */
   static private void shuffle(int[] x, int size)
   {
      while ( size > 2)
      {  int k, tmp;

         k = generator.nextInt(size--);
         tmp = x[size];
         x[size] = x[k];
         x[k] = tmp;
      }
   }

/**
 * Fill the linked list "lst" based on values in "x", generating "size"
 * entries in the linked list.  The list is actually filled with
 * MyComparable objects which contain Integer objects as their values.
 * This will generate a warning message, which we will ignore.
 *
 * @param     x     the array holding the values to go into the list
 * @param     size  the number of elements in x to be used
 * @param     lst   the linked list to receive the MyComparable objects
 */
   static private void fillList (int[] x, int size, KWLinkedList lst)
   {
      int k;

      for ( k = 0; k < size; k++ )
         lst.addLast(new MyComparable<Integer>(x[k]));// Use autoboxing
   }
// Identical method, but for a Java API LinkedList
   static private void fillList (int[] x, int size, LinkedList lst)
   {
      int k;

      for ( k = 0; k < size; k++ )
         lst.addLast(new MyComparable<Integer>(x[k]));// Use autoboxing
   }

/**
 * Utility method to check whether a KWLinkedList is in order.
 * This will generate two warning messages, which we will ignore.
 *
 * @param     testList  the linked list being examined.
 * @param     n  the number of cells to examine in the linked list
 */
   public static boolean ordered(KWLinkedList testList, int n)
   {
      MyComparable prevItem = null, thisItem;
      Iterator <MyComparable> iter = testList.iterator();

      if ( n != testList.size() )
      {
         System.out.println("Size mismatch.  Expect " + n +
            ", find " + testList.size() );
         return false;
      }

      if (iter.hasNext())
         prevItem = iter.next();
      // Traverse ordered list and display any out of order pair.
      while (iter.hasNext())
      {
         thisItem = iter.next();
         if (prevItem.freeCompare(thisItem) > 0)
         {
            System.out.println("*** FAILED:  " + prevItem +
                               " > " + thisItem);
            return false;
         }
         prevItem = thisItem;
      }
      return true;
   }

/**
 * Utility method to check whether a LinkedList is in order.
 * This will generate two warning messages, which we will ignore.
 *
 * @param     testList  the linked list being examined.
 * @param     n  the number of cells to examine in the linked list
 */
   public static boolean ordered(LinkedList testList, int n)
   {
      MyComparable prevItem = null, thisItem;
      Iterator <MyComparable> iter = testList.iterator();

      if ( n != testList.size() )
      {
         System.out.println("Size mismatch.  Expect " + n +
            ", find " + testList.size() );
         return false;
      }

      if (iter.hasNext())
         prevItem = iter.next();
      // Traverse ordered list and display any out of order pair.
      while (iter.hasNext())
      {
         thisItem = iter.next();
         if (prevItem.freeCompare(thisItem) > 0)
         {
            System.out.println("*** FAILED:  " + prevItem +
                               " > " + thisItem);
            return false;
         }
         prevItem = thisItem;
      }
      return true;
   }

/**
 * Utility method to display on screen the contents of a linked list
 *
 * @param     list  the linked list being displayed
 */
   public static void display(KWLinkedList list)
   {  list.display(); }

/**
 * Generate a character string containing the present time down to
 * the second.  This uses a GregorianCalendar object to get the
 * necessary data, based on methods specified in the abstract class
 * Calendar.
 *
 * @return    the character string with the current time
 */
   private static String currentTimeString()
   {
      // To capture the CURRENT time, needs to be fresh each time
      GregorianCalendar cal = new GregorianCalendar();

      return cal.get(Calendar.YEAR) + "/" +
             cal.get(Calendar.MONTH) + "/" +
             cal.get(Calendar.DAY_OF_MONTH) + " " +
             cal.get(Calendar.HOUR_OF_DAY) + ":" +
             cal.get(Calendar.MINUTE) + ":" +
             cal.get(Calendar.SECOND);
   }
}