import java.util.*;
import java.util.concurrent.*;
import easyIO.*;

class FinnM{

	CyclicBarrier vent,ferdig ;
	int [] a;
	int antTr?der;
	int antKjerner;
	int[]lokalMax ;
	static int aLen;
	static int numIter;
	volatile boolean stop = false;

	void intitier(int [] param) {
		 antKjerner = Runtime.getRuntime().availableProcessors();
		 antTr?der = antKjerner;
		 vent   = new CyclicBarrier(antTr?der+1); //+1, ogs? main
		 ferdig = new CyclicBarrier(antTr?der+1); //+1, ogs? main
		 lokalMax = new int [antTr?der];
		 a = param;

		 // start threads
		 for (int i = 0; i< antTr?der; i++)
			 new Thread(new Para(i)).start();

	} // end initier

   	public static void main (String [] args) {
   		if ( args.length != 2)	{
   			System.out.println("use: >java FinnM <length of array> <num iterations>");
   	    } else {
   		    aLen = Integer.parseInt(args[0]);
   		    numIter = Integer.parseInt(args[1]);
   		    new FinnM().utf?rTest(aLen);
   	    }
	 } // end main


    int FinnMaxSeq( int [] a) {
		 int totalMax = 0;
		 for (int i=0;i < a.length;i++)
		   if(a[i] > totalMax) totalMax = a[i];
		   return totalMax;
	 }// end FinnMaxSeq

	 void  utf?rTest (int n) {
	    a= new int[n]; // ?kende lengde med ?kende antTr?der
	    int totalMax ;

		Random r = new Random(1337);
		for (int i =0; i< a.length;i++)
		   a[i] = Math.max(r.nextInt(a.length)-i,0); // random fill >=0

		 double [] seqTime = new double [numIter];
		 double [] parTime = new double [numIter];


	     for (int m = 0; m < numIter; m++) {
			long t ;

			 // Parallell FinnMaks
			 t = System.nanoTime();       // start klokke

			 totalMax = finnMaxPara(a);   // start tr?der og beregn resultatet

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

			 System.out.println("Kj?ring:"+m+") ant kjerner:"+ antKjerner + ", antTr?der:" + antTr?der);
			 System.out.println("Max verdi parallell   i a:"+totalMax +
			 ", paa: "+  parTime[m]+ " ms. " );

			 // sammenlign med sekvensiell utf?ring av finnMax
			 t = System.nanoTime();

			 totalMax = FinnMaxSeq(a);

			 t = (System.nanoTime()-t);
			 seqTime[m] =t/1000000.0;

		     System.out.println("Max verdi sekvensiell i a:"+totalMax +", paa: "+
		                 seqTime[m]+ " ms.\n");
        } // end for m

        insertSort(seqTime, 0, numIter-1);
        insertSort(parTime, 0, numIter-1);

        System.out.println("\nMedian sequential time:"+seqTime[seqTime.length/2]+ ", median parallel time:"+ parTime[seqTime.length/2+1]
        + ",\n Speedup:"+ Format.align(seqTime[seqTime.length/2 +1]/parTime[seqTime.length/2],6,2) +", n = "+n);

        stop = true;
        try{ // make all threads terminate
			 	vent.await();
	 	} catch (Exception e) {}

	 } // utf?r

	 int finnMaxPara (int [] a) {
		 // denne g?r p? main-tr?den - bare ett eks.
	 	   if (vent == null) intitier (a);
	 	   int totalMax = -1;

	 	   try{ // start all treads
	 			vent.await();
	 		} catch (Exception e) {return 0;}

			try{ // wait for all treads to complete one round
				ferdig.await();
			} catch (Exception e) {return 0;}

			// finn den st?rste max fra alle tr?dene
			for (int i=0;i < antTr?der;i++)
				if(lokalMax[i] > totalMax) totalMax = lokalMax[i];

			return totalMax;

	 } // end finnMaxPara


	 class Para implements Runnable{
		   int ind;
		   Para(int i) { ind =i;} // konstruktor

		   void FindLocalMax(int ind){
		   		 int minMax = -1;
		   		 int ant= a.length/antTr?der;   // antall elementer per tr?d
		   		 int num = ant;

		   		 if (ind == antTr?der-1) num = ant + (a.length % antTr?der) ;

		   		  for (int i = 0; i< num; i++) {
		   		 	  if (a[ant*ind+i] > minMax) minMax = a[ant*ind+i];
		   		  }
		   		  lokalMax[ind] = minMax;  // lev?r svar
		   } // end FindLocalMax


	        public void run() { // Her er det som kj?res i parallell:
	            while (! stop ) {
				  try {  // wait on all other threads + main
					 vent.await();
				  } catch (Exception e) {return;}

				   FindLocalMax(ind);

				   try {  // wait on all other threads + main
					   ferdig.await();
				   } catch (Exception e) {return;}
			   } // not stop
			} // end run

     } // end class Para

	 /** sort double-array a to find median */
	 void insertSort(double a[],int left, int right) {
				int i,k;
				double 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
	 } // end insertSort
}// END class Parallell