/**
 *  
 * BitonicSort.java - Batcher's bitonic sort network 
 *                    Implementation works only for power-of-2 sizes starting from 2. 
 * 
 * Note: 
 * 1. Each input element is also referred to as a key in the comments in this file.  
 * 2. BitonicSort of N keys is done using logN merge stages and each merge stage is made up of 
 *    lopP steps (P goes like 2, 4, ... N)  
 *  
 * See Knuth "The Art of Computer Programming" Section 5.3.4 - "Networks for Sorting" (particularly 
 * the diagram titled "A nonstandard sorting network based on bitonic sorting" in the First Set of 
 * Exercises - Fig 56 in second edition)
 * Here is an online reference: http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/bitonic/bitonicen.htm 
 */ 


/**
 * Compares the two input keys and exchanges their order if they are not 
 * sorted.  
 * 
 * sortdir determines if the sort is nondecreasing (UP) or nonincreasing (DOWN).  
 * 'true' indicates UP sort and 'false' indicates DOWN sort.  
 */ 


int->int filter CompareExchange(boolean sortdir) {

 work push 2 pop 2 {

/* the input keys and min,max keys */ 
	int k1, k2, mink, maxk; 

	k1 = pop(); 
	k2 = pop(); 
	if (k1 <= k2)
	    {  
		mink = k1; 
		maxk = k2; 
	    } 
	else /* k1 > k2 */ 
	    { 
		mink = k2; 
		maxk = k1; 
	    } 
 
	if (sortdir == true) 
	    { 
		/* UP sort */ 
		push(mink); 
		push(maxk); 
	    } 
	else /* sortdir == false */ 
	    { 
		/* DOWN sort */ 
		push(maxk); 
		push(mink); 
	    } 
    } 
}


/**
 * Creates N keys and sends it out  
 */
void->int filter KeySource(int N) {

  int[N] A;

  init {
    for (int i=0; i<N; i++)
      A[i] = (N-i);
  }

  work push N pop 0 {

    for (int i=0; i<N; i++)
      push(A[i]);
  }                          
}


/**
 * Prints out the sorted keys and verifies if they 
 * are sorted.  
 */
int->void filter KeyPrinter(int N) {

  work push 0 pop N {
    for(int i=0; i<N; i++)
      println(pop());
  }
}


/** 
 * The top-level kernel of bitonic-sort (recursive version) -  
 * First produces a bitonic sequence by recursively sorting its two halves in 
 * opposite directions and then uses BitonicMerge to merge them into one 
 * sorted sequence. 
 */  


int->int pipeline BitonicSortKernelRecursive(int L, boolean sortdir) {

  if(L > 1) {
//produce a bitonic sequence

    add int->int splitjoin {
      split roundrobin(L/2,L/2);
      add BitonicSortKernelRecursive(L/2, sortdir);
      add BitonicSortKernelRecursive(L/2, !sortdir);
      join roundrobin(L/2,L/2);
    }
/* BitonicMerge the resulting bitonic sequence */ 
    add BitonicMergeRecursive(L, sortdir);  
  }
  else {
    add Identity<int>; 
  }
}


/** 
 * BitonicMerge recursively sorts a bitonic sequence of length L.    
 * It sorts UP if the sortdir is true and sorts DOWN otherwise.  
 */ 

int->int pipeline BitonicMergeRecursive(int L, boolean sortdir) {

/* Partition the bitonic sequence into two bitonic sequences 
	 * with all numbers in the first sequence <= all numbers in the 
	 * second sequence if sortdir is UP (similar case for DOWN sortdir)  
	 */ 

  add int->int splitjoin {

    split roundrobin();
    for(int i=0; i<L/2; i++)
      add CompareExchange(sortdir);
    join roundrobin();
  }

/* Recursively sort the two bitonic sequences obtained from  
	 * the PartitionBitonicSequence step  
	 */
	if (L>2) {
	   add int->int splitjoin { 

	     split roundrobin(L/2, L/2);  
	     add BitonicMergeRecursive(L/2, sortdir); 
	     add BitonicMergeRecursive(L/2, sortdir); 
	     join roundrobin(L/2, L/2);  
	   } 
        }
}


/** 
 * The driver class 
 */ 

void->void pipeline BitonicSortRecursive() {
  /* Make sure N is a power_of_2 */  
  int N = 32; 
 
  add KeySource(N); 
  add BitonicSortKernelRecursive(N, true); /* true for UP sort */ 
  add KeyPrinter(N); 
}