/** 
 * 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 for the logN
 *    merge stages)  
 *  
 * 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 pop 2 push 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);
            }
        } 
} 
 
/** 
 * Partition the input bitonic sequence of length L into two bitonic
 * sequences of length L/2, with all numbers in the first sequence <=
 * all numbers in the second sequence if sortdir is UP (similar case
 * for DOWN sortdir)
 * 
 * Graphically, it is a bunch of CompareExchanges with same sortdir,
 * clustered together in the sort network at a particular step (of
 * some merge stage).
 */ 
int->int splitjoin PartitionBitonicSequence(int L, boolean sortdir)
{
    /* Each CompareExchange examines keys that are L/2 elements apart */  
    split roundrobin;
    for (int i=0; i<(L/2); i++) 
        add CompareExchange(sortdir); 
    join roundrobin;
} 

/** 
 * One step of a particular merge stage (used by all merge stages
 * except the last)
 * 
 * dircnt determines which step we are in the current merge stage 
 * (which in turn is determined by <L, numseqp>) 
 */  
int->int splitjoin StepOfMerge(int L, int numseqp, int dircnt)
{ 
    boolean curdir;   
    split roundrobin(L);
    for (int j=0; j<numseqp; j++) 
    {
      /* finding out the curdir is a bit tricky - the direction
       * depends only on the subsequence number during the FIRST
       * step. So to determine the FIRST step subsequence to which
       * this sequence belongs, divide this sequence's number j by
       * dircnt (bcoz 'dircnt' tells how many subsequences of the
       * current step make up one subsequence of the FIRST
       * step). Then, test if that result is even or odd to determine
       * if curdir is UP or DOWN respec.
       */   
      curdir = ( (j/dircnt)%2 == 0 );
      /* The last step needs special care to avoid splitjoins with
       * just one branch. */  
      if (L > 2)  
        add PartitionBitonicSequence(L, curdir); 
      else /* PartitionBitonicSequence of the last step (L=2) is
            * simply a CompareExchange */   
        add CompareExchange(curdir); 
    }
    join roundrobin(L);
} 

/** 
 * One step of the last merge stage  
 *
 * Main difference form StepOfMerge is the direction of sort. It is
 * always in the same direction - sortdir.
 */  
int->int splitjoin StepOfLastMerge(int L, int numseqp, boolean sortdir)
{ 
    split roundrobin(L);
    for (int j=0; j<numseqp; j++) 
    {  
      /* The last step needs special care to avoid splitjoins with
       * just one branch. */  
      if (L > 2)  
        add PartitionBitonicSequence(L, sortdir); 
      else /* PartitionBitonicSequence of the last step (L=2) is
            * simply a CompareExchange */   
        add CompareExchange(sortdir); 
    } 
    join roundrobin(L);
} 

/* Divide the input sequence of length N into subsequences of length P
 * and sort each of them (either UP or DOWN depending on what
 * subsequence number [0 to N/P-1] they get - All even subsequences
 * are sorted UP and all odd subsequences are sorted DOWN) In short, a
 * MergeStage is N/P Bitonic Sorters of order P each.
 * 
 * But, this MergeStage is implemented *iteratively* as logP STEPS. 
 */ 
int->int pipeline MergeStage(int P, int N)
{
    int L, numseqp, dircnt;   
    /* for each of the lopP steps (except the last step) of this merge
     * stage */  
    for (int i=1; i<P; i=i*2) 
    {
      /* length of each sequence for the current step - goes like
       * P,P/2,...,2 */ 
      L = P/i;
      /* numseqp is the number of PartitionBitonicSequence-rs in this step */ 
      numseqp = (N/P)*i;
      dircnt = i;  

      add StepOfMerge(L, numseqp, dircnt);
    } 
} 
  
/**  
 * The LastMergeStage is basically one Bitonic Sorter of order N i.e.,
 * it takes the bitonic sequence produced by the previous merge stages
 * and applies a bitonic merge on it to produce the final sorted
 * sequence.
 *  
 * This is implemented iteratively as logN steps
 */ 
int->int pipeline LastMergeStage(int N, boolean sortdir)
{
    int L, numseqp;   
    /* for each of the logN steps (except the last step) of this merge
     * stage */  
    for (int i=1; i<N; i=i*2) 
    {
      /* length of each sequence for the current step - goes like
       * N,N/2,...,2 */ 
      L = N/i;
      /* numseqp is the number of PartitionBitonicSequence-rs in this step */ 
      numseqp = i; 

      add StepOfLastMerge(L, numseqp, sortdir);
    }
} 

/** 
 * The top-level kernel of bitonic-sort (iterative version) - It has
 * logN merge stages and all merge stages except the last
 * progressively builds a bitonic sequence out of the input
 * sequence. The last merge stage acts on the resultant bitonic
 * sequence to produce the final sorted sequence (sortdir determines
 * if it is UP or DOWN).
 */  
int->int pipeline BitonicSortKernel(int N, boolean sortdir)
{
    for (int i=2; i<=(N/2); i=2*i)
        add MergeStage(i, N); 
    add LastMergeStage(N, sortdir); 
} 

/**
 * Creates N keys and sends it out  
 */
void->int filter KeySource(int N)
{
    int[N] A;
 
    init {
        /* Initialize the input. In future, might
         * want to read from file or generate a random 
         * permutation.
         */
        for (int i=0; i<N; i++)
            A[i] = (N-i);
    }

    work push N 
        {
            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 pop N
        {
            for (int i=0; i<(N-1); i++)
            {
                /* verifies if it is UP sorted */  
                // ASSERT(peek(0) <= peek(1));
                /* verifies if it is DOWN sorted */  
                // ASSERT(peek(0) >= peek(1));
                println(pop());
            } 
            println(pop());
  }                          
}
 
/** 
 * The driver class 
 */ 
void->void pipeline BitonicSort
{
    /* Make sure N is a power_of_2 */  
    int N = 32; //16;
    /* true for UP sort and false for DOWN sort */ 
    boolean sortdir = true;  
 
    add KeySource(N); 
    add BitonicSortKernel(N, sortdir); 
    //add BitonicSortKernel(N, !sortdir); 
    add KeyPrinter(N); 
}