import java.util.*;
import java.util.concurrent.*;
import easyIO.*;
// file: QuickSort.java
// eksempel p? sekvensiell og parallell sortering med quick-sort
// ulike enkle endringer merket XX kan lage tre parallell l?sninger  som gir  speeduo fra 0.008 til 4,5

class QuickSort{
	// ****** Problemets FELLES DATA HER
	int i;

	int [] a;
	final String navn = "TEST AV QuickSort med BIG_LIMIT";
	final static int LIMIT = 32, BIG_LIMIT = 100000;
	static int max_depth=5;

	 // Felles system-variable - samme for 'alle' programmer
	 int antTraader;
	 int antKjerner;
	 static int numIter ;          // antall ganger for ? lage median (1,3,5,,)
	 static int nLow,nStep,nHigh;  // laveste, multiplikator, hoyeste n-verdi
	 static int n;	                      // problemets st?rrelse
	 static String filnavn;
	 volatile boolean stop = false;
	 int med;
	 Out ut;

	 double [] seqTime ;
	 double [] parTime ;

	 /** for ogs? utskrift p? fil */
	 synchronized void println(String s) {
		 ut.outln(s);
		 System.out.println(s);
	 }

	 /** for ogs? utskrift p? fil */
	 synchronized void print(String s) {
		 ut.out(s);
		 System.out.print(s);
	 }

	 /** initieringen i main-tr?den */
	 void intitier() {
		     seqTime = new double [numIter];
		     parTime = new double [numIter];
		     ut = new Out(filnavn, true);

			 antKjerner = Runtime.getRuntime().availableProcessors();

			 antTraader = antKjerner;
			 int depth = antTraader;
			 while (depth > 2 ) {
				 depth = depth /2;
				 max_depth ++;
			 }

	} // end initier


	public static void main (String [] args) {
		if ( args.length != 5)	{
			System.out.println("use: >java QuickSort <nLow> <nStep> <nHigh> <num iterations> <fil>");
	    } else {
		    nLow = Integer.parseInt(args[0]);
		    nStep = Integer.parseInt(args[1]);
		    nHigh = Integer.parseInt(args[2]);
		    numIter = Integer.parseInt(args[3]);

		    filnavn = args[4];
		    new QuickSort().utforTest();
	    }
	 } // end main


	void  utforTest () {
		intitier();
	    println("Test av  "+ navn+ "\n med "+
	              antKjerner + " kjerner ,   Median av:" + numIter+" iterasjoner, LIMIT:" + LIMIT+
	              ", BIG_LIMIT:"+ BIG_LIMIT + "\n");
	    println("\n      n      sekv.tid(ms)   para.tid(ms)    Speedup ");

        for (n = nHigh; n >= nLow; n=n/nStep) {
		    for (med = 0; med < numIter; med++) {

				  a = new int[n];
				  Random r = new Random (123);
				  for (int i =0; i<n; i++) a[i] = r.nextInt(n);

				 long t = System.nanoTime();  // start tidtagning parallell
		         // Start alle tr?dene parallell beregning n?
			     // Kall Parallell Quicksort
			     RekPara(a,0,a.length-1);

				 t = (System.nanoTime()-t);
				 parTime[med] =t/1000000.0;

				   sjekkSortering(a,"Para");

				 for (int i =0; i<n; i++) a[i] = r.nextInt(n);

				 t = System.nanoTime(); // start tidtagning sekvensiell
				 //**** KALL P? DIN SEKVENSIELLE METODE  H E R ********
				 sekvensiellMetode (n,numIter);
				 t = (System.nanoTime()-t);
				 seqTime[med] =t/1000000.0;

				 sjekkSortering(a,"Sekv");

		    } // end for med

		    println(Format.align(n,10)+
		         Format.align(median(seqTime,numIter),12,3)+
			     Format.align(median(parTime,numIter),15,3)+
			     Format.align(median(seqTime,numIter)/median(parTime,numIter),13,4));

	    } // end n-llop

        ut.close();
	 } // utforTest

	   void sjekkSortering (int [] a, String s)
	   // ----------------------------------------------
	   // sjekk sortering, print hvis feil
	   //----------------------------------------------
	   { int i, numerr =0, firsterr = -1, num =n;
	     if(n > 100) num= 100;

	     for (i = 1; i < n-1; i++ )
	       if (a[i] > a[i+1] ) {
	              if (i>0) System.out.print(s+"- sort-error;, a["+(i-1)+"]:"+ a[i-1]);
	              System.out.print(", a["+i+"]:"+a[i]);
	              System.out.println(", a["+(i+1)+"]:"+a[i+1]);

	             while (i == i); // Stop output, terminate with ctrl-C
	        }
    }// end sjekkSortering

     /*** HER er din egen sekvensielle metode
          som  selvsagt IKKE ER synchronized, */
	 void sekvensiellMetode (int n,int numIter){
		 quicksortSek(a,0,n-1);
     } // end sekvensiellMetode

     void quicksortSek(int[] a, int left, int right) {
		 if (right-left < LIMIT) insertSort (a,left,right); // XX -A
		 else {												// XX -A
			   int piv = partition (a, left, right); // del i to
			   int piv2 = piv-1,   pivotVal = a[piv];
			   while (piv2 > left  && a[piv2] == pivotVal) {
					 piv2--; // skip like elementer i midten
				}
			   if ( piv2-left >0) quicksortSek(a, left,  piv2);
			   if ( right-piv >1) quicksortSek(a, piv + 1, right);
			}                                                  //XX -A
	 	} // end quicksort


	   	// del opp a[] i to: smaa og storre
	 	int partition (int [] a, int left, int right) {
	 	     int pivVal = a[(left + right) / 2];
	 	     int index = left;
	 	     // plasser pivot-element helt til h?yre
	 	     swap(a, (left + right) / 2, right);

	 	     for (int i = left; i < right; i++) {
	 	          if (a[i] <= pivVal) {
	 	   	        swap(a, i, index);
	 	  	        index++;
	 	          }
	 	      } // end for
	 	      swap(a, index, right); // sett pivot tilbake
	 	      return index;
	 	 } // end partition

	 	 void swap(int [] a, int left, int right) {
	 	       int temp = a[left];
	 	       a[left] = a[right];
	 	       a[right] = temp;
	 	 } // end swap


	   	void insertSort(int a[],int left, int right) {
	   		if (left < right) {
	   			int i,k,t;

				for (k = left+1 ; k <= right; k++) {
					t = a[k] ;
					i = k;

					while ( a[i-1]  > t ) {
						 a[i] = a[i-1];
						 if (--i == left) break;
					}
					a[i] = t;
	   			} // end k
	   		 } // left < right
  	    } // end insertSort

  	void RekPara(int [] a, int left, int right) {
		//System.out.println("RekPara:  left:"+left+", right:"+right);
		//<del opp omradet a[left..right]>
		if (right-left<BIG_LIMIT) quicksortSek(a,left,right);      // XX -B
		else {                                                      // XX - B
			int deling = partition (a, left,right);
			Thread t1 =null, t2=null;

		//	if (deling - left > LIMIT )
				(t1 = new Thread (new Para(a,left,deling-1))).start();
		//	else insertSort(a,left,deling-1);
		//	if (right - deling > LIMIT)
				(t2 = new Thread (new Para(a,deling, right))).start();
		//	else  insertSort(a,deling, right);
			try{if (t1!= null)t1.join();if (t2!= null) t2.join();} catch(Exception e){return;};
		}                                                             // XX - B
	}


     /*** HER er evt. de parallelle metodene som ER synchronized */


	 class Para implements Runnable{
           int left, right;
		   Para(int [] a, int l, int r) {
			   left=l;
			   right = r;

		   } // konstruktor

	       /*** HER er dine  parallelle metoder som IKKE er synchronized */

	        public void run() { // Her er det som kjores i parallell:
				  //**** KALL P? DINE PARALLELLE METODER  H E R ********
				  RekPara(a,left,right); // parameter: traanummeret: ind

			} // end run
     } // end class Para

	 /** sort double-array a to find median */
	 double median(double a[], int right) {
				int i,k;
				double t;

				for (k = 1 ; k < right; k++) {
					t = a[k] ;
					i = k;

					while ((a[i-1] ) > t ) {
						 a[i] = a[i-1];
						 if (--i == 0) break;
					}
					a[i] = t;
				} // end k
				return (a[a.length/2]);
	 } // end insertSort
}// END class Parallell