/*
 * @author Ranides Atterwim <ranides@gmail.com>
 * @copyright Ranides Atterwim
 * @license WTFPL
 * @url http://ranides.net/projects/assira
 */
package net.ranides.assira.collection.arrays;

import net.ranides.assira.collection.Swapper;
import java.util.Comparator;
import net.ranides.assira.collection.IntComparator;
import net.ranides.assira.collection.arrays.NativeArray.NativeComparator;
import net.ranides.assira.collection.arrays.NativeArray.NativeMove;
import net.ranides.assira.generic.CompareUtils;

@SuppressWarnings({
    "PMD.AvoidReassigningParameters"
})
public final class NativeArraySort {
    
    private static final int SMALL = 7;
    
    private static final int MEDIUM = 50;

    private NativeArraySort() {
        // utility class
    }
   
    /**
     * Sorts an array according to the order induced by the specified comparator
     * using quicksort.
     *
     * <p>The sorting algorithm is a tuned quicksort adapted from Jon L. Bentley
     * and M. Douglas McIlroy, &ldquo;Engineering a Sort Function&rdquo;,
     * <i>Software: Practice and Experience</i>, 23(11), pages 1249&minus;1265,
     * 1993.
     *
     * @param array the array to be sorted.
     * @param comp the comparator to determine the sorting order.
     *
     */
    public static <T> void quickSort(NativeArray array, Comparator<T> comp) {
        quickSort(array, 0, array.size(), comp);
    }
    
    /**
     * Sorts the specified range of elements according to the order induced by
     * the specified comparator using quicksort.
     *
     * <p>The sorting algorithm is a tuned quicksort adapted from Jon L. Bentley
     * and M. Douglas McIlroy, &ldquo;Engineering a Sort Function&rdquo;,
     * <i>Software: Practice and Experience</i>, 23(11), pages 1249&minus;1265,
     * 1993.
     *
     * @param array the array to be sorted.
     * @param begin the index of the first element (inclusive) to be sorted.
     * @param end the index of the last element (exclusive) to be sorted.
     * @param comp the comparator to determine the sorting order.
     *
     */
    public static <T> void quickSort(NativeArray array, int begin, int end, Comparator<T> comp) {
        quickSort(begin, end, array.comparator(comp), array);
    }
    
    /**
     * Sorts the specified range of elements using the specified swapper and
     * according to the order induced by the specified comparator using
     * quicksort.
     *
     * <p>The sorting algorithm is a tuned quicksort adapted from Jon L. Bentley
     * and M. Douglas McIlroy, &ldquo;Engineering a Sort Function&rdquo;,
     * <i>Software: Practice and Experience</i>, 23(11), pages 1249&minus;1265,
     * 1993.
     *
     * @param begin the index of the first element (inclusive) to be sorted.
     * @param end the index of the last element (exclusive) to be sorted.
     * @param comp the comparator to determine the order of the generic data.
     * @param swapper an object that knows how to swap the elements at any two
     * positions.
     *
     */
    @SuppressWarnings("PMD")
    public static void quickSort(int begin, int end, IntComparator comp, Swapper swapper) {
        int len = end - begin;
        // Insertion sort on smallest arrays
        if (len < SMALL) {
            for (int i = begin; i < end; i++) {
                for (int j = i; j > begin && (comp.compare(j - 1, j) > 0); j--) {
                    swapper.swap(j, j - 1);
                }
            }
            return;
        }

        // Choose a partition element, v
        int m = begin + len / 2; // Small arrays, middle element
        if (len > SMALL) {
            int l = begin;
            int n = end - 1;
            if (len > MEDIUM) { // Big arrays, pseudomedian of 9
                int s = len / 8;
                l = med3(l, l + s, l + 2 * s, comp);
                m = med3(m - s, m, m + s, comp);
                n = med3(n - 2 * s, n - s, n, comp);
            }
            m = med3(l, m, n, comp); // Mid-size, med of 3
        }
        // int v = x[m];

        int a = begin;
        int b = a;
        int c = end - 1;
        // Establish Invariant: v* (<v)* (>v)* v*
        int d = c;
        while (true) {
            int comparison;
            while (b <= c && ((comparison = comp.compare(b, m)) <= 0)) {
                if (comparison == 0) {
                    if (a == m) {
                        m = b; // moving target; DELTA to JDK !!!
                    } else if (b == m) {
                        m = a; // moving target; DELTA to JDK !!!
                    }
                    swapper.swap(a++, b);
                }
                b++;
            }
            while (c >= b && ((comparison = comp.compare(c, m)) >= 0)) {
                if (comparison == 0) {
                    if (c == m) {
                        m = d; // moving target; DELTA to JDK !!!
                    } else if (d == m) {
                        m = c; // moving target; DELTA to JDK !!!
                    }
                    swapper.swap(c, d--);
                }
                c--;
            }
            if (b > c) {
                break;
            }
            if (b == m) {
                m = d; // moving target; DELTA to JDK !!!
            } else if (c == m) {
                m = c; // moving target; DELTA to JDK !!!
            }
            swapper.swap(b++, c--);
        }

        // Swap partition elements back to middle
        int s;
        int n = end;
        s = Math.min(a - begin, b - a);
        vecSwap(swapper, begin, b - s, s);
        s = Math.min(d - c, n - d - 1);
        vecSwap(swapper, b, n - s, s);

        // Recursively sort non-partition-elements
        if ((s = b - a) > 1) {
            quickSort(begin, begin + s, comp, swapper);
        }
        if ((s = d - c) > 1) {
            quickSort(n - s, n, comp, swapper);
        }
    }
    
    /**
     * Sorts an array according to the natural ascending order using mergesort.
     *
     * <p>This sort is guaranteed to be <i>stable</i>: equal elements will not
     * be reordered as a result of the sort. An array as large as
     * <code>array</code> will be allocated by this method.
     *
     * @param array the array to be sorted.
     */
    public static void mergeSort(NativeArray array) {
        mergeSort(array, 0, array.size());
    }
    
    /**
     * Sorts the specified range of elements according to the natural ascending
     * order using mergesort.
     *
     * <p>This sort is guaranteed to be <i>stable</i>: equal elements will not
     * be reordered as a result of the sort. An array as large as
     * <code>array</code> will be allocated by this method.
     *
     * @param array the array to be sorted.
     * @param begin the index of the first element (inclusive) to be sorted.
     * @param end the index of the last element (exclusive) to be sorted.
     */
    public static void mergeSort(NativeArray array, int begin, int end) {
        mergeSort(array, begin, end, array.clone());
    }
    
    /**
     * Sorts the specified range of elements according to the natural ascending
     * order using mergesort, using a given support array.
     *
     * <p>This sort is guaranteed to be <i>stable</i>: equal elements will not
     * be reordered as a result of the sort. Moreover, no support arrays will be
     * allocated.
     *
     *
     * @param array the array to be sorted.
     * @param begin the index of the first element (inclusive) to be sorted.
     * @param end the index of the last element (exclusive) to be sorted.
     * @param supp a support array containing at least <code>end</code> elements.
     */
    private static void mergeSort(NativeArray array, int begin, int end, NativeArray supp) {
        MergeArray a = new MergeArray(array, supp);
        MergeArray s = new MergeArray(supp, array);
        mergeSort(begin, end, CompareUtils.comparator(array.component()), a, s);
    }

    /**
     * Sorts an array according to the order induced by the specified comparator
     * using mergesort.
     *
     * <p>This sort is guaranteed to be <i>stable</i>: equal elements will not
     * be reordered as a result of the sort. An array as large as
     * <code>array</code> will be allocated by this method.
     *
     * @param array the array to be sorted.
     * @param comp the comparator to determine the sorting order.
     */
    public static <T> void mergeSort(NativeArray array, Comparator<T> comp) {
        mergeSort(array, 0, array.size(), comp);
    }
    
    /**
     * Sorts the specified range of elements according to the order induced by
     * the specified comparator using mergesort.
     *
     * <p>This sort is guaranteed to be <i>stable</i>: equal elements will not
     * be reordered as a result of the sort. An array as large as
     * <code>array</code> will be allocated by this method.
     *
     * @param array the array to be sorted.
     * @param begin the index of the first element (inclusive) to be sorted.
     * @param end the index of the last element (exclusive) to be sorted.
     * @param comp the comparator to determine the sorting order.
     */
    public static <T>void mergeSort(NativeArray array, int begin, int end, Comparator<T> comp) {
        NativeArray supp = array.clone();
        MergeArray a = new MergeArray(array, supp, comp);
        MergeArray s = new MergeArray(supp, array, comp);
        mergeSort(begin, end, comp, a, s);
    }
    
    /**
     * Sorts the specified range of elements according to the order induced by
     * the specified comparator using mergesort, using a given support array.
     *
     * <p>This sort is guaranteed to be <i>stable</i>: equal elements will not
     * be reordered as a result of the sort. Moreover, no support arrays will be
     * allocated.
     *
     * @param array the array to be sorted.
     * @param begin the index of the first element (inclusive) to be sorted.
     * @param end the index of the last element (exclusive) to be sorted.
     * @param comp the comparator to determine the sorting order.
     * @param supp a support array containing at least <code>end</code> elements.
     */
    private static <T> void mergeSort(int begin, int end, Comparator<T> comp, MergeArray a, MergeArray s) {
        int len = end - begin;
        // Insertion sort on smallest arrays
        if (len < SMALL) {
            insertionSort(a.array, begin, end, comp);
            return;
        }
        
        // Recursively sort halves of a into supp
        int mid = (begin + end) >>> 1;
        mergeSort(begin, mid, comp, s, a);
        mergeSort(mid, end, comp, s, a);
        // If list is already sorted, just copy from supp to a.  This is an
        // optimization that results in faster sorts for nearly ordered lists.
        
        if (s.icmp.compare(mid - 1, mid) <= 0) {
            NativeArrayUtils.copy(s.array, begin, a.array, begin, len);
            return;
        }
        
//        NativeArray.NativeMove imov = array.move(supp);
        
        // Merge sorted halves (now in supp) into a
        for (int i = begin, p = begin, q = mid; i < end; i++) {
            if (q >= end || p < mid && s.icmp.compare(p, q) <= 0) {
                a.imov.move(i, p++);
            } else {
                a.imov.move(i, q++);
            }
        }
    }
        
    /**
     * Sorts the specified range of elements using the specified swapper and
     * according to the order induced by the specified comparator using
     * mergesort.
     *
     * <p>This sort is guaranteed to be <i>stable</i>: equal elements will not
     * be reordered as a result of the sort. The sorting algorithm is an
     * in-place mergesort that is significantly slower than a standard
     * mergesort, as its running time is
     * <i>O</i>(<var>n</var>&nbsp;(log&nbsp;<var>n</var>)<sup>2</sup>), but it
     * does not allocate additional memory; as a result, it can be used as a
     * generic sorting algorithm.
     *
     * @param begin the index of the first element (inclusive) to be sorted.
     * @param end the index of the last element (exclusive) to be sorted.
     * @param comp the comparator to determine the order of the generic data
     * (arguments are positions).
     * @param swapper an object that knows how to swap the elements at any two
     * positions.
     */
    public static void mergeSort(int begin, int end, IntComparator comp, Swapper swapper) {
        /*
         * We retain the same method signature as quickSort. Given only a comparator and swapper we
         * do not know how to copy and move elements from/to temporary arrays. Hence, in contrast to
         * the JDK mergesorts this is an "in-place" mergesort, i.e. does not allocate any temporary
         * arrays. A non-inplace mergesort would perhaps be faster in most cases, but would require
         * non-intuitive delegate objects...
         */
        int length = end - begin;

        // Insertion sort on smallest arrays
        if (length < SMALL) {
            for (int i = begin; i < end; i++) {
                for (int j = i; j > begin && (comp.compare(j - 1, j) > 0); j--) {
                    swapper.swap(j, j - 1);
                }
            }
            return;
        }

        // Recursively sort halves
        int mid = (begin + end) >>> 1;
        mergeSort(begin, mid, comp, swapper);
        mergeSort(mid, end, comp, swapper);

        // If list is already sorted, nothing left to do. This is an
        // optimization that results in faster sorts for nearly ordered lists.
        if (comp.compare(mid - 1, mid) <= 0) {
            return;
        }

        // Merge sorted halves
        inPlaceMerge(begin, mid, end, comp, swapper);
    }

    private static <T> void insertionSort(NativeArray array, int begin, int end, Comparator<T> comp) {
        for (int i = begin; ++i < end;) {
            Object item = array.get(i);
            NativeComparator icmp = array.lcmp(item, comp);
            int j = i;
            for (; icmp.compare(j-1) < 0; j--) {
                array.move(j,j-1);
                if (begin == j - 1) {
                    --j;
                    break;
                }
            }
            array.set(j,item);
        }
    }
            
    /**
     * Transforms two consecutive sorted ranges into a single sorted range. The
     * initial ranges are
     * <code>[first..middle)</code> and
     * <code>[middle..last)</code>, and the resulting range is
     * <code>[first..last)</code>. Elements in the first input range will
     * precede equal elements in the second.
     */
    @SuppressWarnings("PMD")
    private static void inPlaceMerge(int begin, int mid, int end, IntComparator comp, Swapper swapper) {
        if (begin >= mid || mid >= end) {
            return;
        }
        if (end - begin == 2) {
            if (comp.compare(mid, begin) < 0) {
                swapper.swap(begin, mid);
            }
            return;
        }

        int firstCut;
        int secondCut;

        if (mid - begin > end - mid) {
            firstCut = begin + (mid - begin) / 2;
            secondCut = lowerBound(mid, end, firstCut, comp);
        } else {
            secondCut = mid + (end - mid) / 2;
            firstCut = upperBound(begin, mid, secondCut, comp);
        }

        int first2 = firstCut;
        int middle2 = mid;
        int last2 = secondCut;
        if (middle2 != first2 && middle2 != last2) {
            int first1 = first2;
            int last1 = middle2;
            while (first1 < --last1) {
                swapper.swap(first1++, last1);
            }
            first1 = middle2;
            last1 = last2;
            while (first1 < --last1) {
                swapper.swap(first1++, last1);
            }
            first1 = first2;
            last1 = last2;
            while (first1 < --last1) {
                swapper.swap(first1++, last1);
            }
        }

        mid = firstCut + (secondCut - mid);
        inPlaceMerge(begin, firstCut, mid, comp, swapper);
        inPlaceMerge(mid, secondCut, end, comp, swapper);
    }

    /**
     * Performs a binary search on an already-sorted range: finds the first
     * position where an element can be inserted without violating the ordering.
     * Sorting is by a user-supplied comparison function.
     *
     * @param begin the index of the first element (inclusive) to be included in
     * the binary search.
     * @param end the index of the last element (exclusive) to be included in the
     * binary search.
     * @param pos the position of the element to be searched for.
     * @param comp the comparison function.
     * @return the largest index i such that, for every j in the *      * range <code>[first..i)</code>, <code>comp.compare(j, pos)</code> *
     * is <code>true</code>.
     */
    private static int lowerBound(int begin, int end, int pos, IntComparator comp) {
        // if (comp==null) throw new NullPointerException();
        int len = end - begin;
        while (len > 0) {
            int half = len / 2;
            int middle = begin + half;
            if (comp.compare(middle, pos) < 0) {
                begin = middle + 1;
                len -= half + 1;
            } else {
                len = half;
            }
        }
        return begin;
    }

    /**
     * Performs a binary search on an already sorted range: finds the last
     * position where an element can be inserted without violating the ordering.
     * Sorting is by a user-supplied comparison function.
     *
     * @param begin the index of the first element (inclusive) to be included in
     * the binary search.
     * @param to the index of the last element (exclusive) to be included in the
     * binary search.
     * @param pos the position of the element to be searched for.
     * @param comp the comparison function.
     * @return The largest index i such that, for every j in the *      * range <code>[first..i)</code>, <code>comp.compare(pos, j)</code> *
     * is <code>false</code>.
     */
    private static int upperBound(int begin, int mid, int pos, IntComparator comp) {
        int len = mid - begin;
        while (len > 0) {
            int half = len / 2;
            int middle = begin + half;
            if (comp.compare(pos, middle) < 0) {
                len = half;
            } else {
                begin = middle + 1;
                len -= half + 1;
            }
        }
        return begin;
    }
    
    /**
     * Returns the index of the median of the three indexed chars.
     */
    private static int med3(int a, int b, int c, IntComparator comp) {
        int ab = comp.compare(a, b);
        int ac = comp.compare(a, c);
        int bc = comp.compare(b, c);
        return (ab < 0
                ? (bc < 0 ? b : ac < 0 ? c : a)
                : (bc > 0 ? b : ac > 0 ? c : a));
    }

    private static void vecSwap(Swapper swapper, int begin, int end, int count) {
        for (int i = 0; i < count; i++, begin++, end++) {
            swapper.swap(begin, end);
        }
    }
    
    private static final class MergeArray {
        public final NativeArray array;
        public final IntComparator icmp;
        public final NativeMove imov;
        
        public MergeArray(NativeArray array, NativeArray supp, Comparator comp) {
            this.array = array;
            this.icmp = array.comparator(comp);
            this.imov = array.move(supp);
        }
        
        public MergeArray(NativeArray array, NativeArray supp) {
            this.array = array;
            this.icmp = array.comparator();
            this.imov = array.move(supp);
        }
    }
}
