/*
Copyright 2011, 2012 Frederic Langlet
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
you may obtain a copy of the License at

                http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
*/

package kanzi.util.sort;

import kanzi.IntSorter;


// See http://www.tools-of-computing.com/tc/CS/Sorts/bitonic_sort.htm
// or http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/bitonic/bitonicen.htm
// Bitonic sort performs best when implemented as a parallel algorithm (not here)
public class BitonicSort implements IntSorter
{
    private static final int[] POWER_OF_TWO =
    {
        0,  0,  1,  2,  2,  4,  4,  4,  4,  8,  8,  8,  8,  8,  8,  8,
        8, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
       16, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32,
       32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32
    };

    private final int size;


    public BitonicSort()
    {
        this.size = 0;
    }


    public BitonicSort(int size)
    {
        if (size < 0)
            throw new IllegalArgumentException("The size parameter must be at least 0");

        this.size = size;
    }


    // Thread safe
    // all input data must be smaller than 1 << logDataSize
    @Override
    public void sort(int[] input, int blkptr)
    {
        final int sz = (this.size == 0) ? input.length : this.size;

        if (sz > 1)
           sort(input, blkptr, blkptr+sz, true);
    }


    private static void sort(int[] array, int lo, int n, boolean up)
    {
        int m = n >> 1;

        if (m > 1)
          sort(array, lo, m, !up);

        if (n - m > 1)
           sort(array, lo+m, n-m, up);

        if (n > 1)
          merge(array, lo, n, up);
    }


    private static void merge(int[] array, int lo, int n, boolean up)
    {
       // Find greatest power of two smaller than n
       int m;

       if (n < POWER_OF_TWO.length)
       {
            m = POWER_OF_TWO[n];
       }
       else
       {
         m = 1;

         while (m < n)
            m <<= 1;

          m >>= 1;
        }

        final int end = lo + n - m;

        for (int i=lo; i<end; i++)
        {
            if ((array[i] > array[i+m]) == up)
            {
                int tmp = array[i];
                array[i] = array[i+m];
                array[i+m] = tmp;
            }
        }

        if (m > 1)
           merge(array, lo, m, up);

        if (n-m > 1)
           merge(array, lo+m, n-m, up);
    }
}
@@ -1801,15 +1801,8 @@
 tr, 
-blkptr+
 sz, 
@@ -2274,16 +2274,17 @@
 .length)
+ 
 %0A       
@@ -2291,26 +2291,24 @@
 %7B%0A          
-  
 m = POWER_OF
@@ -2316,32 +2316,33 @@
 TWO%5Bn%5D;%0A       %7D
+ 
 %0A       else%0A   
@@ -2337,16 +2337,17 @@
     else
+ 
 %0A       
@@ -2361,16 +2361,17 @@
     
+ 
 m = 1;%0A%0A
     
@@ -2362,24 +2362,25 @@
     m = 1;%0A%0A
+ 
          whi
@@ -2390,16 +2390,17 @@
 (m %3C n)%0A
+ 
         
@@ -2432,17 +2432,16 @@
  %3E%3E= 1;%0A
- 
        %7D

Fix bug when offset 'blkptr' is not 0