/**
 * Driving main to exercise and compare algorithms.
 *
 *  Just exercising code, so everything is static or local.
 */
import java.io.*;

public class BenchMerge
{//Random generator is seeded in main, but used in shuffle.
   static java.util.Random generator = new java.util.Random();

   static final boolean DEBUG = false;

   public static void main ( String [] args )
   {  List       data = null;
      int[]      test;
      int[]      scratch;
      int        size, maxSize, sizeStep;   // control outer loop
      int        nPasses, pass;             // inner loop
      double     start,                     // initial times in msec.
                 elapsed[] = new double[5]; // five elapsed times
      PrintWriter csvFile = null;

      try
      {  File f  = new File("MergeSort.csv");
      // Boolean true in FileWriter opens the file in append mode
      // Boolean true in PrintWriter enables automatic line flushing
         csvFile = new PrintWriter(new FileWriter(f, true), true);
      }
      catch (IOException e)
      {  System.err.println ("CSV file open failed: " + e);
         System.exit(-1);
      }

      System.out.print ("Initial array length,  ");
      if ( args.length < 1 )
         size = readInt();
      else
      {  size = Integer.parseInt(args[0]);
         System.out.println (size);
      } // end if/else regarding args[0]

      System.out.print ("Maximum array length,  ");
      if ( args.length < 2 )
         maxSize = readInt();
      else
      {  maxSize = Integer.parseInt(args[1]);
         System.out.println (maxSize);
      } // end if/else regarding args[1]

      System.out.print ("Increment for length,  ");
      if ( args.length < 3 )
         sizeStep = readInt();
      else
      {  sizeStep = Integer.parseInt(args[2]);
         System.out.println (sizeStep);
      } // end if/else regarding args[2]

      System.out.print ("Number of passes,  ");
      if ( args.length < 4 )
         nPasses = readInt();
      else
      {  nPasses = Integer.parseInt(args[3]);
         System.out.println (nPasses);
      } // end if/else regarding args[3]

      test = new int [maxSize];
      scratch = new int [maxSize];
      fillArray ( test );

      csvFile.println ("n,mergeRecur,mergeIter,mergeNatural,quickSort,iterMerge");
      System.out.println ("n,mergeRecur,mergeIter,mergeNatural,quickSort,iterMerge");

      while ( size <= maxSize )
      {  long seed = generator.nextLong();  // Same sequence in all

         start = System.currentTimeMillis();
         generator.setSeed(seed);
         for ( pass = 0; pass < nPasses; pass++ )
         {  shuffleArray ( test, size );
            data = fillList(test, size);
            data.mergeRecur();
            if ( !validate (data) )
            {
               System.out.println ("Error in sorting.  BREAK");
               break;
            }
         } // end for
         elapsed[0] = (System.currentTimeMillis() - start)/1000.0;

         data.empty();

         start = System.currentTimeMillis();
         generator.setSeed(seed);
         for ( pass = 0; pass < nPasses; pass++ )
         {  shuffleArray ( test, size );
            data = fillList(test, size);
            data.mergeIter();
            if ( !validate (data) )
            {
               System.out.println ("Error in sorting.  BREAK");
               break;
            }
         } // end for
         elapsed[1] = (System.currentTimeMillis() - start)/1000.0;

         start = System.currentTimeMillis();
         generator.setSeed(seed);
         for ( pass = 0; pass < nPasses; pass++ )
         {  shuffleArray ( test, size );
            data = fillList(test, size);
            data.mergeNatural();
            if ( !validate (data) )
            {
               System.out.println ("Error in sorting.  BREAK");
               break;
            }
         } // end for
         elapsed[2] = (System.currentTimeMillis() - start)/1000.0;

         start = System.currentTimeMillis();
         generator.setSeed(seed);
         for ( pass = 0; pass < nPasses; pass++ )
         {  shuffleArray ( test, size );
            copyArray ( scratch, test, size);
            data.quickSort();
            if ( !validate (scratch, size) )
            {
               System.out.println ("Error in sorting.  BREAK");
               break;
            }
         } // end for
         elapsed[3] = (System.currentTimeMillis() - start)/1000.0;

         start = System.currentTimeMillis();
         generator.setSeed(seed);
         for ( pass = 0; pass < nPasses; pass++ )
         {  shuffleArray ( test, size );
            copyArray ( scratch, test, size);
            MergeSort.mergeSort (scratch, size);
            if ( !validate (scratch, size) )
            {
               System.out.println ("Error in sorting.  BREAK");
               break;
            }
         } // end for
         elapsed[4] = (System.currentTimeMillis() - start)/1000.0;

         System.out.print (size);
         csvFile.print (size);
         for ( int k = 0; k < elapsed.length; k++ )
         {
            System.out.print ( "," + elapsed[k] );
            csvFile.print ( "," + elapsed[k] );
         }
         System.out.println();
         csvFile.println();

         size += sizeStep;             // Next size
      } // end while ( size <= maxSize )
   } // end main()

/**
 * Fill the array with increasing sequence starting at 1
 */
   static void fillArray ( int[] x )
   {  for ( int k = 0; k < x.length; k++ )
         x[k] = (k+1);
   } // end fillArray()

/**
 * Fill the list from x[]
 */
   static List fillList ( int[] x, int n )
   {
      List data = new List();

      for (int k = 0; k < n; k++ )
         data.addBack(x[k]);
      return data;
   }

   static void copyArray ( int[] out, int[] x, int size )
   {  for ( int k = 0; k < size; k++ )
         out[k] = x[k];
   } // end fillArray()

/**
 * Shuffle the entire array, using the class scope generator
 */
   static void shuffleArray ( int[] x, int lim )
   {  while ( lim > 1 )
      {  int item;
         int save = x[lim-1];

         item = generator.nextInt(lim);
         x[--lim] = x[item];                // Note predecrement on lim
         x[item] = save;
      } // end while
   } // end shuffleArray()

   static boolean validate ( List list )
   {
      if (DEBUG)
      {
         ListNode entry = list.head;
         ListNode last = entry;

         entry = entry.next;
         while ( entry != null )
         {
            if ( last.compareTo(entry) > 0 )
               return false;
            entry = entry.next;
         }
      }
      return true;
   }

   static boolean validate ( int[] x, int size )
   {
      if (DEBUG)
      {
         for ( int k = 1; k < size; k++ )
            if ( x[k-1] > x[k] )
               return false;
      }
      return true;
   }

// Code for reading console from "Java in a Nutshell", p. 166
// Wrap System.in as a BufferedReader.
   static BufferedReader console = new BufferedReader
                                  (new InputStreamReader(System.in));

   public static String readLine()
   {  String rtnVal = "";

      try
      {  rtnVal = console.readLine(); }
      catch (java.io.IOException e)
      {  System.err.println ("File input failed: " + e);
         System.exit(-1);
      }
      return rtnVal;
   } // end readLine()

   public static int readInt()
   {
      String lineInp = readLine();

      try
      {  return Integer.parseInt( lineInp.trim() );  }
      catch (Exception e)
      {  System.err.println (e);
         System.err.println ("Offending line:  " + lineInp);
         System.err.println ("Returning zero.");
         return 0;
      }
   }
}