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

class FinnMaxMulti{
	CyclicBarrier vent, ventM5,ferdig ;
	int [] a;
	int antMetoder =6;
	int antTr?der;
	int antKjerner;
	int[]lokalMax ;
	int globalMax=0, globalMaxSeq =0;
	int metode =0;
	static int aLen;
	static int numIter;
	volatile boolean stop = false;
	double [] seqTime;
	double [][] parT;
	ReentrantLock lock = new ReentrantLock();

	// Testing muliple 6 ways of finding the GlobalMax

	void intitier(int [] param) {
		 antKjerner = Runtime.getRuntime().availableProcessors();
		 antTr?der = antKjerner;
		 vent   = new CyclicBarrier(antTr?der+1); //+1, ogs? main
		 ventM5 = new CyclicBarrier(antTr?der);
		 ferdig = new CyclicBarrier(antTr?der+1); //+1, ogs? main
		 lokalMax = new int [antTr?der];
		 parT = new double [antMetoder][numIter];
		 a = param;
System.out.println("AntTr?der:"+antTr?der);
		 // 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 FinnMaxMulti <length of array> <num iterations>");
   	    } else {
   		    aLen = Integer.parseInt(args[0]);
   		    numIter = Integer.parseInt(args[1]);
   		    new FinnMaxMulti().utf?rTest(aLen);
   	    }
	 } // end main

	 void initPara (int m) {
		 metode =m;
		 globalMax =0;
	 } // end initPara

	 void print(int metode,double[] t1, double[] t2) {
	 	 insertSort(t1, 0, numIter-1);
	     insertSort(t2, 0, numIter-1);
		 System.out.println("Met:"+metode+", Para: "
		   + Format.align(t1[numIter/2],10,2)+ " ms; Sekv:"
		   + Format.align(t2[numIter/2],7,3)+ " ms."
           +  ", SUp:"+ Format.align(t2[numIter/2]/t1[numIter/2],8,3));
     }

     void print2(String s) {
        System.out.println(s+"Metode:"+metode+", GlobalMax:"+globalMax+", globalMaxSeq:"+globalMaxSeq);
	  }


	 void  utf?rTest (int n) {
	    a= new int[n]; // ?kende lengde med ?kende antTr?der
	    if (vent == null) intitier(a);
		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

		 seqTime = new double [numIter];

		 System.out.println("Kj?ring: ant kjerner:"+
		 antKjerner + ", antTr?der:" + antTr?der +", n:"+n);

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

	 	     if (vent == null) intitier (a);
			 // sammenlign med sekvensiell utf?ring av finnMax
			 t = System.nanoTime();
			 for (int i=0;i < a.length;i++){
				   if(a[i] > globalMaxSeq) globalMaxSeq = a[i];
			 }
			 t = (System.nanoTime()-t);
			 seqTime[m] =t/1000000.0;


			 //----- Parallell FinnMaks -----------------

			 // metode 0 - GAL -ikke synkronisert
			 initPara(0);  //metode 0
			 t = System.nanoTime();       // start klokke
			     finnMaxPara(a,metode);   // start tr?der og beregn resultatet
			 t = (System.nanoTime()-t);
			 parT[metode][m] = t/1000000.0;
			 if ( globalMax != globalMaxSeq ) print2("FEIL: " );


			 // metode 1 - synkronisert metode
			 initPara(1);  //metode 1
			 t = System.nanoTime();       // start klokke
			     finnMaxPara(a,metode);   // start tr?der og beregn resultatet
			 t = (System.nanoTime()-t);
		     parT[metode][m] = t/1000000.0;
			// 	 print2("");

			 // metode 2 - Locked metode
			 initPara(2);  //metode 2
			 t = System.nanoTime();       // start klokke
			    finnMaxPara(a,metode);   // start tr?der og beregn resultatet
			 t = (System.nanoTime()-t);
			 parT[metode][m] = t/1000000.0;
			// 	 print2("");

			 // metode 3 - if (max> global Max) kall sync metode
			 initPara(3);  //metode 3
			 t = System.nanoTime();       // start klokke
			    finnMaxPara(a,metode);   // start tr?der og beregn resultatet
			 t = (System.nanoTime()-t);
	    	 parT[metode][m] = t/1000000.0;
			// 	 print2("");

			 // metode 4 - lokal max + sync metode
			 initPara(4);  //metode 4
			 t = System.nanoTime();       // start klokke
			    finnMaxPara(a,metode);   // start tr?der og beregn resultatet
			 t = (System.nanoTime()-t);
	    	 parT[metode][m] = t/1000000.0;
			// 	 print2("");

			 // metode 5 - tr?d 0 ordner det
			 initPara(5);                   //metode 5
			 t = System.nanoTime();       // start klokke
			    finnMaxPara(a,metode);   // start tr?der og beregn resultatet
			 t = (System.nanoTime()-t);
	    	 parT[metode][m] = t/1000000.0;
			// 	 print2("");

        } // end for m

        for (int met = 0; met < antMetoder; met++) print(met, parT[met], seqTime);

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

	 } // utf?r

	 void finnMaxPara (int [] a, int metode) {
		 // denne g?r p? main-tr?den - bare ett eks.
	 	   try{ // start all treads
	 			vent.await();
	 		} catch (Exception e) {return;}

            // --- her g?r alle tr?dene ?n runde til i sine run()-metoder -----

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

     synchronized void updateGlobalMax1 (int val){
		 if (val > globalMax )  globalMax=val;
	 } // end updateGlobalMax1

     void updateGlobalMax2 (int val){
	//	System.out.println("   updateGlobalMax2, val:" +val+", met:"+metode);
		lock.lock();
			try{
			  if (val > globalMax )  globalMax=val;
		//	  System.out.println("   --   updateGlobalMax2, val:" +val+", met:"+metode+", globalMax:"+globalMax);
			} finally {
		    lock.unlock();
		}
	 } // end updateGlobalMax2


	 class Para implements Runnable{
		   int ind,ant,num, start, threadMax =0;

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

	        public void run() { // Her er det som kj?res i parallell:
	             ant = a.length/antTr?der;   // antall elementer per tr?d
				 num = ant;   // antall elementer per tr?d
				 if (ind == antTr?der-1) num += (a.length % antTr?der) ;
				 start = ant*ind;
			//	 System.out.println("tr?d:"+ind+", ant:"+ant+", num:"+num+ ", start:"+ start);

	            while (! stop ) {
				  try {  // wait on all other threads + main
					 vent.await();
				  } catch (Exception e) {return;}

                  if (! stop) {
					   if (metode == 0) {
						   // GAL - ikke synkronisert
						   for (int i = 0; i < num; i++) {
							 if (a[start+i] > globalMax) globalMax = a[start+i];
						   }

					   } else if (metode == 1) {
						   // sync metode - meget treig
						   for (int i = 0; i< num; i++) {
								updateGlobalMax1(a[start+i]);
						   }

						} else if (metode == 2) {
						   // Locked metode, treig ca 4 x raskere enn metode 1
							   for (int i = 0; i< num; i++) {
								   updateGlobalMax2(a[start+i]);
								}

						} else if (metode == 3) {
							 // test f?r kall lock metode
								for (int i = 0; i< num; i++) {
									 if (a[start+i] > globalMax ){
										   updateGlobalMax2(a[start+i]);
									 }
								}

						} else if (metode == 4) {
							 // Lokal max + locked metode til sist
							  for (int i = 0; i< num; i++) {
								  if (a[start+i] > threadMax ) threadMax = a[start+i];
							  }
							   updateGlobalMax2(threadMax);

						} else if (metode == 5) {
							// Lokal max + tr?d 0 gj?r det med lokal max
							 for (int i = 0; i < num; i++) {
								 if (a[start+i] > threadMax ) threadMax = a[start+i];
							  }
							 lokalMax[ind] = threadMax;
							 try {  // wait on all other threads
								 ventM5.await();
							 } catch (Exception e) {return;}
							 if (ind == 0) {
								 for (int j = 0; j < antTr?der; j++){
									 if (lokalMax[j] > globalMax) globalMax = lokalMax[j];
								 }
							 }
						 }

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

				   } // end 2re test p? stop

			   } // while 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