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


class Oppgave7{
// Administration, common routines and output
	int [] a;
	int numThreads;
	int n;
	int numIter;
	String fil;
	Out ut;

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

				for (k = 1 ; k < a.length; 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 median

	synchronized void println(String s) {
		ut = new Out(fil, true);
		System.out.println(s);
		ut.outln(s);
		ut.close();
	}

	public static void main (String [] args) {
		if ( args.length < 3 )	{
			System.out.println("use: >java Oblig4 <length of array> <num iterations> <file>");
	    } else {
		    new Oppgave7().doTest(args);
	    }
	 } // end main



	void  doTest (String [] args) {
		// initiate
		n = Integer.parseInt(args[0]);
		numIter = Integer.parseInt(args[1]);
		fil = args[2];


		 Random r = new Random(1337);
		 double [] seqTime = new double [numIter];
		 double [] seqTime2 = new double [numIter];
		 double [] parTime = new double [numIter];
		 double [] parTime2 = new double [numIter];
		 double [] qckTime = new double [numIter];

	     for (int j = 0; j < numIter; j++) {
			long t ;
            // ***************** Parallel Radix ******************
             a= new int[n]; // oekende lengde med oekende numThreadsint[] b = new int [n];
        	 for (int i =0; i< a.length;i++){
			 	 a[i] = r.nextInt(a.length); // random fill >=0
			 }

			 t = System.nanoTime();       // start timer
			 new ParaRadix().sort(a);
			 t = (System.nanoTime()-t);

			 parTime[j] = t/1000000.0;
			 testA(a,"ParallellRadix ");

			 System.out.println("Run no: "+j+", num cores:"+ numThreads + ", numThreads:" + numThreads);
			 System.out.println("  Parallel Radix sorting in : "+  parTime[j]+ " millisec. " );

           // ***************** Parallel Atomic Radix ******************
             a= new int[n]; // oekende lengde med oekende numThreadsint[] b = new int [n];
        	 for (int i =0; i< a.length;i++){
			 	 a[i] = r.nextInt(a.length); // random fill >=0
			 }

			 t = System.nanoTime();       // start timer
             new ParaAtomicRadix().paraRadix(a);
			 parTime2[j] = (System.nanoTime()-t)/1000000.0;

			 testA(a,"ParallellAtomic ");

			// System.out.println("Run no: "+j+", num cores:"+ numThreads + ", numThreads:" + numThreads);
			 System.out.println("  Parallel Atomic sort in : "+  parTime2[j]+ " millisec. " );

          // ***************** Sequential Radix ******************
             for (int i =0; i< a.length;i++){
			 	 a[i] = r.nextInt(a.length); // random fill >=0
			 }
			 t = System.nanoTime();
			 new SeqRadix().radix2(a);
			 seqTime[j] =(System.nanoTime()-t)/1000000.0;

			 testA(a,"Sequential Radix ");

			  System.out.println("  Sequential sorting in   : "+  seqTime[j]+ " millisec.");

          // ***************** AtomicSequential Radix ******************
             for (int i =0; i< a.length;i++){
			 	 a[i] = r.nextInt(a.length); // random fill >=0
			 }
			 t = System.nanoTime();
			 new SeqAtomicRadix().radix2(a);
			 seqTime2[j] =(System.nanoTime()-t)/1000000.0;
			  testA(a,"AtomicSequential");

			  System.out.println("  Sequential atomic  in   : "+  seqTime2[j]+ " millisec.");

			// *************** compare with Arrays.sort (quicksort)****************
			 for (int i =0; i< a.length;i++){
				 a[i] = r.nextInt(a.length); // random fill >=0
			 }
			 t = System.nanoTime();
			 Arrays.sort(a);
			 qckTime[j] =(System.nanoTime()-t)/1000000.0;
			 testA(a,"Arrays.sort ");

		     System.out.println("  Quicksort sequential in   : "+  qckTime[j]+ " millisec.");
        } // end for j

        println( "\nn= "+Format.align(n,10)+
        "\nMedian Sequential Radix time:"+Format.align(median(seqTime),10,3)+
        "\nMedian Seq Atomic       time:"     + Format.align(median(seqTime2),10,3)+
        "\nMedian Quick  seq       time:"     + Format.align(median(qckTime),10,3)+
        "\nMedian Radix parallel   time:"     + Format.align(median(parTime),10,3)+
        "\nMedian Atomic parallel  time:"     + Format.align(median(parTime2),10,3)+
        ",\n Speedup Atom :"+ Format.align(median(seqTime2)/median(parTime2),7,3)+
        ",\n Speedup Radix:"+ Format.align(median(seqTime)/median(parTime),7,3)+
        "\n Speedup: SeqQuicksort/ParaRadix:"+ Format.align(median(qckTime)/median(parTime),7,3)+
         "\n Speedup:SeqQuicksort/AtomicParaRadix:"+ Format.align(median(qckTime)/median(parTime2),7,3));


	 } // doTest

	 void testA (int [] a, String s) {
		 for (int i = 1; i < a.length; i++) {
			 if (a[i-1] > a[i] ) {
				 System.out.println ("FEIL::" + s + ", a["+(i-1) + "]: "+
				 a[i-1]+" > a["+i+"]:"+a[i]);
				 In n = new In();
				 String l = n.inLine();
				 return;
			 } //
		 } // end for i
      }// end testA
} // end class Oblig4

// **************************************** ParaRadix ******************************************

class ParaRadix{
	int [] a,b;
	int n ;
	int numThreads;
    int[]localMax ;
    CyclicBarrier sync;
    int allCount[][];

	void sort(int [] a) {
		     this.a =a;
		     n = a.length;
			 b = new int [a.length];

			numThreads = Runtime.getRuntime().availableProcessors();
			localMax = new int[numThreads];
			Thread[] tt = new Thread[numThreads];
			sync = new CyclicBarrier(numThreads);
			allCount= new int[numThreads][];
			 // start Radix threads
				 for (int i = 0; i< numThreads; i++){
					tt[i]= new Thread(new Para(i));
					tt[i].start();
				}

				for (int i = 0; i< numThreads; i++){
					try{
					   tt[i].join();
					}catch (Exception e) { return;}
		}
	 }

	 class Para implements Runnable{
		   int ind;
		   Para(int i) { ind =i;} // constructor
		   int [] localCount;
		   int myMax ;
		   int left, right;
		   int bit1, bit2;

		   void findLocalMax(){
		   		  int num= (a.length/numThreads);   // antall elementer per traad
		   		  left = num*ind;
		   		   myMax = a[left];
		   		  right= left +num;
		   		  if (ind == numThreads -1) right = a.length;

		   		  for (int i = left+1; i < right; i++) {
		   		 	  if (a[i] > myMax) myMax = a[i];
		   		  }
		   		  localMax[ind] =myMax;
	       } // end FindLocalMax

	        void paraRadix(int [] a, int [] b) {
		         // 2 digit radixSort: a[]
		         int  numBit = 2, n =a.length;
		         while (myMax >= (1<<numBit) )numBit++; // antall siffer i max

		         // bestem antall bit i siffer1 og siffer2
		         bit1 = numBit/2;
		         bit2 = numBit-bit1;

		         paraRadixSort( a,b, bit1, 0);    // first digit sort a[] to b[]

		         try{ // start all treads  ------------- Sync 3 --------------------
				 			sync.await();
				 } catch (Exception e) {return;}

		         paraRadixSort( b,a, bit2, bit1);// second digit sort b[] to a[]
		   } // end

		    void paraRadixSort ( int [] a, int [] b, int maskLen, int shift){
		         int  acumVal = 0,t, n = a.length;
		         int mask = (1<<maskLen) -1;
		         localCount = new int [mask+1];
		         int num, sumC =0;

		        // b) count=the frequency of each radix value in a
		         for (int i = left; i < right; i++) {
		            localCount[(a[i]>> shift) & mask]++;
		         }
		         allCount[ind] = localCount;

			     try{ // start all threads ---------------- Sync 2 and 4 -------------------
						sync.await();
				 } catch (Exception e) {return;}

			     localCount = new int[localCount.length];

		        // c) Add up in 'count' - accumulated values in NEW localCount
		        for (int val = 0; val < mask+1; val++) {
					 for (int i = 0; i < ind; i++) {
						   sumC += allCount[i][val];
					  }
					  localCount [val] = sumC;
					  for (int i = ind; i < numThreads; i++) {
					  	   sumC += allCount[i][val];
					  }
			    }

			    // no need to sync between c) and d) - only local variables

		        // d) move numbers in sorted order a to b
		         for (int i = left; i < right; i++) {
		            b[localCount[(a[i]>>shift) & mask]++] = a[i];
		         }
           }// end paraRadixSort


	       public void run() { // Her er det som kjoeres i parallell:

					   findLocalMax();

					   try{ // start all treads  ----------- Sync 1 ----------------
							sync.await();
					   } catch (Exception e) {return;}

					   // all threads calculate the same max
					   for (int i = 0; i < numThreads; i++)
					   if (myMax < localMax[i]) myMax = localMax[i];

                       paraRadix(a,b);


			} // end run
     } // end class Para
} // end class ParaRadix



// **************************************** SeqRadix ******************************************

class SeqRadix{
   static final int INSERT_LIM = 100,
                    ONE_BIT = 8000;

   void radix2(int [] a) {
	   if ( a.length < INSERT_LIM ) innstikkSort(a);
	   else {
		  // 2 digit radixSort: a[]
		  int max = a[0], numBit = 2, n =a.length;
		 // a) finn max verdi i a[]
		  for (int i = 1 ; i < n ; i++)
			if (a[i] > max) max = a[i];
		  while (max >= (1<<numBit) )numBit++; // antall siffer i max

		  // bestem antall bit i siffer1 og siffer2
			int bit1 = numBit/2,
				  bit2 = numBit-bit1;
		  int[] b = new int [n];
		  radixSort( a,b, bit1, 0);    // første siffer fra a[] til b[]
		  radixSort( b,a, bit2, bit1);// andre siffer, tilbake fra b[] til a[]
    }
   } // end radix2


    /** Sort a[] on one digit ; number of bits = maskLen, shiftet up ‘shift’ bits */
    void radixSort ( int [] a, int [] b, int maskLen, int shift){
      int  acumVal = 0, j, n = a.length;
      int mask = (1<<maskLen) -1;
      int [] count = new int [mask+1];

     // b) count=the frequency of each radix value in a
      for (int i = 0; i < n; i++) {
         count[(a[i]>> shift) & mask]++;
      }

     // c) Add up in 'count' - accumulated values
      for (int i = 0; i <= mask; i++) {
           j = count[i];
            count[i] = acumVal;
            acumVal += j;
       }
     // d) move numbers in sorted order a to b
      for (int i = 0; i < n; i++) {
         b[count[(a[i]>>shift) & mask]++] = a[i];
      }
   }// end radixSort


     void innstikkSort(int a[]) {//,int l, int r)
         int i, t, r = a.length-1;

         for (int k = 0 ; k < r ; k++){
            t = a[k+1];
            i = k;

            while (i >= 0 && a[i] > t)
            { a[i+1] = a[i]; i--;}

             a[i+1] = t;
          } // end for k
    } // end innstikk


} // end class SeqRadix





// ********************************* ParaAtomicRadix **************************

class ParaAtomicRadix{
	CyclicBarrier  trSync ;
	int [] a, b;
	int numThreads;
	ReentrantLock lock = new ReentrantLock();
	AtomicIntegerArray count;
	int n,bit1,bit2;
	int numIter,numBit =2;
	int allMax =0;
	Thread[] tr ;

    void updateMax(int m) {
	   lock.lock();
	   try{
		 if (m > allMax) allMax = m;
	   }finally { lock.unlock();}
	 } // end updateMax


	 ParaAtomicRadix() {
		numThreads = Runtime.getRuntime().availableProcessors();
		trSync  = new CyclicBarrier(numThreads);
	 } // end constructor

	 void paraRadix(int[] a) {
		// called from main-tread
		this.a = a;
		this.n = a.length;
		b = new int[a.length];
		tr = new Thread[numThreads];
//printArr(a, "Input a:", 0, a.length);
		for (int i = 0; i< numThreads; i++) {
			(tr[i] = new Arbeider(i)).start();
		}

		//---  completed whan return
		for (int i = 0; i< numThreads; i++)
		try{
		   tr[i].join();
		}catch (Exception e) { return;}

//printArr(a, "Etter siffer2 a:", 0, a.length);

	 } // end paraRadix



     class Arbeider extends Thread {
	      int left, right, myMax,ind;

	      Arbeider(int in) {
			ind = in;
			int num= (a.length/numThreads);   // antall elementer per traad
			left = num*ind;
			right= left+num;
			if (ind == numThreads-1) right = a.length;
	      } // end konstruktor Arbeider

	      void paraAtomicRadixSort ( int [] a, int [] b, int maskLen, int shift){
		   // called from run
			  int  acumVal = 0, j, n = a.length;
			  int mask = (1<<maskLen) -1;
	//	 System.out.println("B ind:"+ind+", mask:"+mask);

			 // b) count=the frequency of each radix value in a
			  for (int i = left; i < right; i++) {
				 count.getAndIncrement((a[i]>> shift) & mask);
			  }
			  try{ // sync all treads  ------------- Sync 3 & 7--------------------
					trSync.await();
			  } catch (Exception e) {return;}


	//	  System.out.println("c ind:"+ind);
			  // c) Add up in 'count' - accumulated values - done in main-tr
			  if (ind == 0) {
	// printAtomic(count, "MaskLen:"+maskLen+", count Post:", 0, count.length() );
				 // Add up in 'count' - accumulated values digit 2
				 for (int i = 0; i <= mask; i++) {
					 j = count.get(i);
					 count.set(i,acumVal);
					 acumVal += j;
				 }
			   } // thread 0
	//	  System.out.println("D ind:"+ind);
			  try{ // sync all treads  ------------- Sync 4 %8 --------------------
					trSync.await();
			   } catch (Exception e) {return;}
	//	  System.out.println("E ind:"+ind);
			 // d) move numbers in sorted order a to b
			 if (ind == 0) {
				  for (int i = 0; i < a.length; i++) {
					 b[count.getAndIncrement((a[i]>>shift) & mask)] = a[i];
				  }
			  }

	//    System.out.println("F ind:"+ind);
		  }// end atomicRadixSort

		  public void run() {
			myMax = a[left];
			for (int i = left+1; i < right; i++) {
				if (a[i] > myMax) myMax = a[i];
			}
			updateMax(myMax);                    // loop a)

			try{ // sync all treads  ------------- Sync 1 --------------------
					trSync.await();
			} catch (Exception e) {return;}

			if (ind == 0) {
				 while (allMax >= (1L<<numBit) )numBit++; // antall siffer i max
				 // bestem antall bit i siffer1 og siffer2
				 bit1 = numBit/2;
				 bit2 = numBit-bit1;
				 count = new AtomicIntegerArray(1<<bit1);
			 }

			  try{ // sync all treads  ------------- Sync 2 --------------------
					trSync.await();
			  } catch (Exception e) {return;}

			  paraAtomicRadixSort ( a,  b,  bit1, 0);  // loop b), ( &c) i main) og d)

			  try{ // sync all treads  ------------- Sync 5 --------------------
					trSync.await();
			  } catch (Exception e) {return;}
//if (ind == 0) printArr(b, "Etter f?rste siffer a:", 0, a.length );

			  if (ind == 0) count = new AtomicIntegerArray(1<<bit2);

			  try{ // sync all treads  ------------- Sync 6 --------------------
						trSync.await();
			  } catch (Exception e) {return;}

			   paraAtomicRadixSort ( b,  a,  bit2, bit1);

		 } // end run

	  } // end lokal class Arbeider

	  static void printArr(int [] arr, String s, int start, int num2 ) {
		 //------------------------------------------------
		 // Print num2 tall i arr,  10 per  linje
		 //*------------------------------------------------*/
		   int i;
		   System.out.println(s);
		   System.out.print(Format.align(start,6)+" |");
		   for (i = 0; i< num2; i++) {
			System.out.print(Format.align(arr[i+start],6)+" ");
			 if (( (i+1) % 10) == 0 && (i+1) < num2) {
			   System.out.println("");
				 System.out.print( Format.align((start+i+1),6)+" |");
			 }
			}
			System.out.println("");
     }// end printArr

      static void printAtomic(AtomicIntegerArray arr, String s, int start, int num2 ) {
		 //------------------------------------------------
		 // Print num2 tall i arr,  10 per  linje
		 //*------------------------------------------------*/
		   int i;
		   System.out.println(s);
		   System.out.print(Format.align(start,6)+" |");
		   for (i = 0; i< num2; i++) {
			System.out.print(Format.align(arr.get(i+start),6)+" ");
			 if (( (i+1) % 10) == 0 && (i+1) < num2) {
			   System.out.println("");
				 System.out.print( Format.align((start+i+1),6)+" |");
			 }
			}
			System.out.println("");
     }// end printArr


 }// end class ParaAtomicRadix

// ********************************* SeqAtomicRadix **************************


class SeqAtomicRadix{
   // sequental ver using AtomicIntegerArray

   void radix2(int [] a) {
      // 2 digit radixSort: a[]
      int max = a[0], numBit = 2, n =a.length;
     // a) finn max verdi i a[]
      for (int i = 1 ; i < n ; i++)
        if (a[i] > max) max = a[i];

      while (max >= (1<<numBit) )numBit++; // antall siffer i max

      // bestem antall bit i siffer1 og siffer2
        int bit1 = numBit/2,
              bit2 = numBit-bit1;
      int[] b = new int [n];
      atomicRadixSort( a,b, bit1, 0);    // første siffer fra a[] til b[]
// ParaAtomicRadix.printArr(b, "Seq siffer1 a:", 0, a.length);
      atomicRadixSort( b,a, bit2, bit1);// andre siffer, tilbake fra b[] til a[]
//  ParaAtomicRadix.printArr(a, "Seq siffer2 a:", 0, a.length);

    } // end  radix2


    /** Sort a[] on one digit ; number of bits = maskLen, shiftet up ‘shift’ bits */
    void atomicRadixSort ( int [] a, int [] b, int maskLen, int shift){
      int  acumVal = 0, j, n = a.length;
      int mask = (1<<maskLen) -1;
      AtomicIntegerArray count = new AtomicIntegerArray (mask+1);;

     // b) count=the frequency of each radix value in a
      for (int i = 0; i < n; i++) {
         count.getAndIncrement((a[i]>> shift) & mask);
      }

     // c) Add up in 'count' - accumulated values
      for (int i = 0; i <= mask; i++) {
            j = count.get(i);
            count.set(i,acumVal);
            acumVal += j;
       }
     // d) move numbers in sorted order a to b
      for (int i = 0; i < n; i++) {
         b[count.getAndIncrement((a[i]>>shift) & mask)] = a[i];
      }


   }// end atomicRadixSort
} // end class SeqAtomicRadix