/**
 * Driving main to exercise the algorithm and compare with utility method.

 *  Just exercising code, so everything is static or local.
 */
import java.io.*;

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

   static boolean DISPLAY = false;          // Display results
   static boolean CHECK   = false;          // Check validity of sorting

   public static void main ( String [] args )
   {  Integer [] test;                      // Array of int objects
      int        size, maxSize, sizeStep;   // control outer loop
      int        nPasses, pass;             // inner loop
      double     start,                     // initial times in msec.
                 elapsed[] = new double[2]; // two 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 = cs1.Keyboard.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 = cs1.Keyboard.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 = cs1.Keyboard.readInt();
      else
      {  sizeStep = Integer.parseInt(args[2]);
         System.out.println (sizeStep);
      } // end if/else regarding args[2]
      if ( DISPLAY )
         nPasses = 1;
      else
      {  System.out.print ("Number of passes:  ");
         if ( args.length < 4 )
            nPasses = cs1.Keyboard.readInt();
         else
         {  nPasses = Integer.parseInt(args[3]);
            System.out.println (nPasses);
         } // end if/else regarding args[3]
      } // end if/else

      test = new Integer [maxSize];
      fillArray ( test );

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

//       Array sort method from java.util.Arrays
         start = System.currentTimeMillis();
         generator.setSeed(seed);
         for ( pass = 0; pass < nPasses; pass++ )
         {  shuffleArray ( test, size );
            if (DISPLAY)
               showArray ( test, size );
//          Note:  from-index inclusive to to-index EXCLUSIVE
            java.util.Arrays.sort( test, 0, size );
            if ( CHECK && !sorted ( test, size ) )
            {  System.out.println("Sort failed.  Abort in pass "+(pass+1));
               break;
            }
         } // end for
         elapsed[0] = (System.currentTimeMillis() - start)/1000.0;

//       Iterative merge sort
         start = System.currentTimeMillis();
         generator.setSeed(seed);
         for ( pass = 0; pass < nPasses; pass++ )
         {  shuffleArray ( test, size );
            if (DISPLAY)
               showArray ( test, size );
//          MergeArray.mergeSort ( test, size );
            MergeArray.mergeSortRec ( test );
            if ( CHECK && !sorted ( test, size ) )
            {  System.out.println("Sort failed.  Abort in pass "+(pass+1));
               break;
            }
         } // end for
         elapsed[1] = (System.currentTimeMillis() - start)/1000.0;

         if (DISPLAY)
         {  System.out.println ();
            showArray ( test, size );
         }

         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 ( Integer [] x )
   {  for ( int k = 0; k < x.length; k++ )
         x[k] = new Integer(k+1);
   } // end fillArray()

/**
 * Shuffle the entire array, using the class scope generator
 */
   static void shuffleArray ( Object [] x, int lim )
   {  while ( lim > 1 )
      {  int item;
         Object save = x[lim-1];
         item = generator.nextInt(lim);
         x[--lim] = x[item];                // Note predecrement on lim
         x[item] = save;
      } // end while
   } // end shuffleArray()

/**
 * Display in lines of 10 values --- if DISPLAY is true
 */
   static void showArray ( Integer [] x, int lim )
   {  int k;

      for ( k = 0; k < lim; k++ )
      {  StringBuffer front = new StringBuffer("       ");
         String       back  = "" + x[k].intValue();
         front.setLength(front.length()-back.length());
         System.out.print (front+back);
         if ( (k+1) % 10 == 0 )
            System.out.println("");
      } // end for
      if ( k % 10 != 0 )
         System.out.println("");
   } // end showArray()

/**
 * Verify that the array is correctly sorted --- if CHECK is true
 */
   static boolean sorted ( Comparable[] x, int n )
   {  for ( int k = 1; k < n; k++ )
         if ( x[k-1].compareTo(x[k]) > 0 )
            return false;
      return true;
   } // end sorted()

} // end TestMerge()