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


class Oppgave4{

	   int [][] a;
	   long [] radSum;
	   int n, antT;
	   CyclicBarrier sync;

		public static void main (String [] args) {
			if ( args.length < 1 )	{
				System.out.println("use: >java Oppg4 <length of array> ");
		    } else {
			    new Oppgave4().doTest(args);
		    }
		 } // end main

	    long sumRad (int [] a ) {
		 	 		long sum =0;
		 	     	for (int j = 0 ; j < a.length; j++)
		 	 			 sum += a[j];
		 	 	     return sum;
	    } // end sumRad

       void  doTest (String [] args) {
			// initiate
			n = Integer.parseInt(args[0]);
			antT =   Runtime.getRuntime().availableProcessors();
			sync = new CyclicBarrier(antT);

			a = new int[n][n];
			radSum = new long[n];

			Random r = new Random(1337);
			long tid ;
			int k;

			// ***************** Sekvensiell RadSort ******************
			 int sum =0;

			 // -- init a[][] -----
			 for (int i =0; i< a.length;i++){
				 for (int j =0; j < n; j++) {
				   a[i][j] = r.nextInt(n);// random fill
			     }
			 } // end initarray

			 tid = System.nanoTime();       // start timer
			 for (int i =0; i< a.length;i++){
			     radSum[i] = sumRad(a[i]);
			 } // end initarray

			 quicksortSek( a, radSum,0,n-1);
			 double  tt = (System.nanoTime()-tid)/1000000.0;
			 testRS(radSum, "Sekv ");

			 System.out.println("n: "+n+", num cores:"+ antT );
			 System.out.println("  Sequental  sorting in : "+  tt+ " ms. " );

			// ***************** Parallell RadSort ******************
			 for (int i =0; i< a.length;i++){
					 radSum[i] = 0;
		     } // end initarray

            // a) regn ut radsum i parallell
			tid = System.nanoTime();       // start timer
			 Thread [ ] tr = new Thread[antT];
			 for (int i =0; i< antT;i++){
			     (tr[i] = new Thread(new Arbeider(i))).start();;
			 } // end initarray
			 try{
				 for (int i =0; i< antT;i++)
				 	 tr[i].join();
			  }catch(Exception e) {return;}

			  // sorter i parallell
              // finn level = parallellisering i toppen av treet
              int level = 0;
              while ( (antT >> level) > 0 ) level++;

			  quicksortPara( a, radSum, 0,n-1, level) ;

			   double ttt = (System.nanoTime()-tid)/1000000.0;
			    testRS(radSum, "Para ");

			 System.out.println("n: "+n+", num cores:"+ antT + ", level:"+level );
			 System.out.println("  Parallel   sorting  in: "+  ttt+ " ms., speedup: "
			                     +Format.align (tt/ttt, 5,2) );

	    } // end doTest

	    void testRS(long [] rs, String s) {
			for (int i =1; i < rs.length; i++)
			    if (rs[i-1] > rs[i]) {
					System.out.println("ERROR:" + s+ ", at i ="+i);
				}
		} // end testRS


	  // Parallell Kvikksort uten insertSort
		void quicksortPara(int[][] a, long [] rs, int left, int right, int level) {
				   int piv = partition (a,rs, left, right);   // del i to
				   int piv2 = piv-1;
				   long pivotVal = rs[piv];
				   while (piv2 > left  && rs[piv2] == pivotVal) {
						 piv2--;      // skip like elementer i midten
					}
				   if (level-- > 0){
					   Thread t1= new Thread (new Arbeider2(a,rs,left, piv2, level)),
					          t2 =new Thread (new Arbeider2(a,rs,piv+1, right, level));
					          t1.start();
					          t2.start();
					   try{
						   t1.join();
						   t2.join();
					   }catch (Exception e) {return;}
				   } else {
				        if ( piv2-left > 0) quicksortSek(a,rs, left,  piv2);
				        if ( right-piv > 0) quicksortSek(a, rs, piv + 1, right);
					}
		} // end quicksortSek

		// sekvensiell Kvikksort uten insertSort
		void quicksortSek(int[][] a, long [] rs, int left, int right) {
				   int piv = partition (a,rs, left, right);   // del i to
				   int piv2 = piv-1;
				   long pivotVal = rs[piv];
				   while (piv2 > left  && rs[piv2] == pivotVal) {
						 piv2--;      // skip like elementer i midten
					}
				   if ( piv2-left > 0) quicksortSek(a,rs, left,  piv2);
				   if ( right-piv > 0) quicksortSek(a, rs, piv + 1, right);
		} // end quicksortSek

		// del opp a[] i to: smaa og storre
		int partition (int [][]a,long[] rs, int left, int right) {
			 long pivVal = rs[(left + right) / 2];
			 int index = left;
				// plasser pivot-element helt til h?yre
				swap(a,rs, (left + right) / 2, right);
				 for (int i = left; i < right; i++) {
					  if (rs[i] <= pivVal) {
						swap(a, rs, i, index);
						index++;
					  }
			  }
			  swap(a, rs,index, right); // sett pivot tilbake
			  return index;
		  } // end partition

		 void swap(int [][] a, long [] rs, int l, int r) {
			   int []temp1 = a[l];
			   long temp2 = rs[l];
			   a[l] = a[r];
			   rs[l] = rs[r];
			   a[r] = temp1;
			   rs[r] = temp2;
		 } // end swap

		class Arbeider2 implements Runnable {
			   int[][] a;
			   long [] rs;
			   int left, right, level;

				Arbeider2 (int[][] a, long [] rs, int left, int right, int level) {
					this.a =a;
					this.rs = rs;
					this.left = left;
					this.right = right;
					this.level =level;
				}
				public void run( ) {
				//	System.out.println("Arbeider2, level:"+level);
                    quicksortPara(a, rs, left, right, level);

				} // end run
		 } // end indre klasse Arbeider2



		class Arbeider implements Runnable {
			   int ind; // lokale data og metoder B
			   int part, left,right;

				Arbeider ( int in) {
					ind = in;
					part = n/antT;
					left = ind*part;
					if (ind == antT-1) right = n;
					else right = left + part;
				}
				public void run( ) {
					// kalles n?r tr?den er startet
					for (int i = left; i < right; i++)
					   radSum[i] = sumRad(a[i]);

				} // end run
		 } // end indre klasse Arbeider

} // end Oppg.4