/*

 * Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.  Oracle designates this

 * particular file as subject to the "Classpath" exception as provided

 * by Oracle in the LICENSE file that accompanied this code.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 */

package java.util;

import java.util.concurrent.RecursiveAction;

/**

 * Helper utilities for the parallel sort methods in Arrays.parallelSort.

 *

 * For each primitive type, plus Object, we define a static class to

 * contain the Sorter and Merger implementations for that type:

 *

 * Sorter classes based mainly on CilkSort

 * <A href="http://supertech.lcs.mit.edu/cilk/"> Cilk</A>:

 * Basic algorithm:

 * if array size is small, just use a sequential quicksort (via Arrays.sort)

 *         Otherwise:

 *         1. Break array in half.

 *         2. For each half,

 *             a. break the half in half (i.e., quarters),

 *             b. sort the quarters

 *             c. merge them together

 *         3. merge together the two halves.

 *

 * One reason for splitting in quarters is that this guarantees

 * that the final sort is in the main array, not the workspace

 * array.  (workspace and main swap roles on each subsort step.)

 * Leaf-level sorts use a Sequential quicksort, that in turn uses

 * insertion sort if under threshold.  Otherwise it uses median of

 * three to pick pivot, and loops rather than recurses along left

 * path.

 *

 *

 * Merger classes perform merging for Sorter. If big enough, splits Left

 * partition in half; finds the greatest point in Right partition

 * less than the beginning of the second half of Left via binary

 * search; and then, in parallel, merges left half of Left with

 * elements of Right up to split point, and merges right half of

 * Left with elements of R past split point. At leaf, it just

 * sequentially merges. This is all messy to code; sadly we need

 * distinct versions for each type.

 *

 */

/*package*/ class ArraysParallelSortHelpers {

    // RFE: we should only need a working array as large as the subarray

    //      to be sorted, but the logic assumes that indices in the two

    //      arrays always line-up

    /** byte support class */

    static final class FJByte {

        static final class Sorter extends RecursiveAction {

            static final long serialVersionUID = 749471161188027634L;

            final byte[] a;     // array to be sorted.

            final byte[] w;     // workspace for merge

            final int origin;   // origin of the part of array we deal with

            final int n;        // Number of elements in (sub)arrays.

            final int gran;     // split control

            Sorter(byte[] a, byte[] w, int origin, int n, int gran) {

                this.a = a;

                this.w = w;

                this.origin = origin;

                this.n = n;

                this.gran = gran;

            }

            public void compute() {

                final int l = origin;

                final int g = gran;

                final int n = this.n;

                final byte[] a = this.a;

                final byte[] w = this.w;

                if (n > g) {

                    int h = n >>> 1; // half

                    int q = n >>> 2; // lower quarter index

                    int u = h + q;   // upper quarter

                    FJSubSorter ls = new FJSubSorter(new Sorter(a, w, l, q,  g),

                                                     new Sorter(a, w, l+q, h-q, g),

                                                     new Merger(a, w, l,   q,

                                                                l+q, h-q, l, g, null));

                    FJSubSorter rs = new FJSubSorter(new Sorter(a, w, l+h, q,   g),

                                                     new Sorter(a, w, l+u, n-u, g),

                                                     new Merger(a, w, l+h, q,

                                                                l+u, n-u, l+h, g, null));

                    rs.fork();

                    ls.compute();

                    if (rs.tryUnfork()) rs.compute(); else rs.join();

                    new Merger(w, a, l, h,

                               l+h, n-h, l, g, null).compute();

                } else {

                    DualPivotQuicksort.sort(a, l, l+n-1);   //skip rangeCheck

                }

            }

        }

        static final class Merger extends RecursiveAction {

            static final long serialVersionUID = -9090258248781844470L;

            final byte[] a;

            final byte[] w;

            final int lo;

            final int ln;

            final int ro;

            final int rn;

            final int wo;

            final int gran;

            final Merger next;

            Merger(byte[] a, byte[] w, int lo, int ln, int ro, int rn, int wo,

                   int gran, Merger next) {

                this.a = a;

                this.w = w;

                this.lo = lo;

                this.ln = ln;

                this.ro = ro;

                this.rn = rn;

                this.wo = wo;

                this.gran = gran;

                this.next = next;

            }

            public void compute() {

                final byte[] a = this.a;

                final byte[] w = this.w;

                Merger rights = null;

                int nleft = ln;

                int nright = rn;

                while (nleft > gran) {

                    int lh = nleft >>> 1;

                    int splitIndex = lo + lh;

                    byte split = a[splitIndex];

                    int rl = 0;

                    int rh = nright;

                    while (rl < rh) {

                        int mid = (rl + rh) >>> 1;

                        if (split <= a[ro + mid])

                            rh = mid;

                        else

                            rl = mid + 1;

                    }

                    (rights = new Merger(a, w, splitIndex, nleft-lh, ro+rh,

                                         nright-rh, wo+lh+rh, gran, rights)).fork();

                    nleft = lh;

                    nright = rh;

                }

                int l = lo;

                int lFence = l + nleft;

                int r = ro;

                int rFence = r + nright;

                int k = wo;

                while (l < lFence && r < rFence) {

                    byte al = a[l];

                    byte ar = a[r];

                    byte t;

                    if (al <= ar) {++l; t=al;} else {++r; t = ar;}

                    w[k++] = t;

                }

                while (l < lFence)

                    w[k++] = a[l++];

                while (r < rFence)

                    w[k++] = a[r++];

                while (rights != null) {

                    if (rights.tryUnfork())

                        rights.compute();

                    else

                        rights.join();

                    rights = rights.next;

                }

            }

        }

    } // FJByte

    /** char support class */

    static final class FJChar {

        static final class Sorter extends RecursiveAction {

            static final long serialVersionUID = 8723376019074596641L;

            final char[] a;     // array to be sorted.

            final char[] w;     // workspace for merge

            final int origin;   // origin of the part of array we deal with

            final int n;        // Number of elements in (sub)arrays.

            final int gran;     // split control

            Sorter(char[] a, char[] w, int origin, int n, int gran) {

                this.a = a;

                this.w = w;

                this.origin = origin;

                this.n = n;

                this.gran = gran;

            }

            public void compute() {

                final int l = origin;

                final int g = gran;

                final int n = this.n;

                final char[] a = this.a;

                final char[] w = this.w;

                if (n > g) {

                    int h = n >>> 1; // half

                    int q = n >>> 2; // lower quarter index

                    int u = h + q;   // upper quarter

                    FJSubSorter ls = new FJSubSorter(new Sorter(a, w, l, q,   g),

                                                     new Sorter(a, w, l+q, h-q, g),

                                                     new Merger(a, w, l,   q,

                                                                l+q, h-q, l, g, null));

                    FJSubSorter rs = new FJSubSorter(new Sorter(a, w, l + h, q,   g),

                                                     new Sorter(a, w, l+u, n-u, g),

                                                     new Merger(a, w, l+h, q,

                                                                l+u, n-u, l+h, g, null));

                    rs.fork();

                    ls.compute();

                    if (rs.tryUnfork()) rs.compute(); else rs.join();

                    new Merger(w, a, l, h, l + h, n - h, l, g, null).compute();

                } else {

                    DualPivotQuicksort.sort(a, l, l+n-1);   // skip rangeCheck

                }

            }

        }

        static final class Merger extends RecursiveAction {

            static final long serialVersionUID = -1383975444621698926L;

            final char[] a;

            final char[] w;

            final int lo;

            final int ln;

            final int ro;

            final int rn;

            final int wo;

            final int gran;

            final Merger next;

            Merger(char[] a, char[] w, int lo, int ln, int ro, int rn, int wo,

                   int gran, Merger next) {

                this.a = a;

                this.w = w;

                this.lo = lo;

                this.ln = ln;

                this.ro = ro;

                this.rn = rn;

                this.wo = wo;

                this.gran = gran;

                this.next = next;

            }

            public void compute() {

                final char[] a = this.a;

                final char[] w = this.w;

                Merger rights = null;

                int nleft = ln;

                int nright = rn;

                while (nleft > gran) {

                    int lh = nleft >>> 1;

                    int splitIndex = lo + lh;

                    char split = a[splitIndex];

                    int rl = 0;

                    int rh = nright;

                    while (rl < rh) {

                        int mid = (rl + rh) >>> 1;

                        if (split <= a[ro + mid])

                            rh = mid;

                        else

                            rl = mid + 1;

                    }

                    (rights = new Merger(a, w, splitIndex, nleft-lh, ro+rh,

                                         nright-rh, wo+lh+rh, gran, rights)).fork();

                    nleft = lh;

                    nright = rh;

                }

                int l = lo;

                int lFence = l + nleft;

                int r = ro;

                int rFence = r + nright;

                int k = wo;

                while (l < lFence && r < rFence) {

                    char al = a[l];

                    char ar = a[r];

                    char t;

                    if (al <= ar) {++l; t=al;} else {++r; t = ar;}

                    w[k++] = t;

                }

                while (l < lFence)

                    w[k++] = a[l++];

                while (r < rFence)

                    w[k++] = a[r++];

                while (rights != null) {

                    if (rights.tryUnfork())

                        rights.compute();

                    else

                        rights.join();

                    rights = rights.next;

                }

            }

        }

    } // FJChar

    /** short support class */

    static final class FJShort {

        static final class Sorter extends RecursiveAction {

            static final long serialVersionUID = -7886754793730583084L;

            final short[] a;    // array to be sorted.

            final short[] w;    // workspace for merge

            final int origin;   // origin of the part of array we deal with

            final int n;        // Number of elements in (sub)arrays.

            final int gran;     // split control

            Sorter(short[] a, short[] w, int origin, int n, int gran) {

                this.a = a;

                this.w = w;

                this.origin = origin;

                this.n = n;

                this.gran = gran;

            }

            public void compute() {

                final int l = origin;

                final int g = gran;

                final int n = this.n;

                final short[] a = this.a;

                final short[] w = this.w;

                if (n > g) {

                    int h = n >>> 1; // half

                    int q = n >>> 2; // lower quarter index

                    int u = h + q;   // upper quarter

                    FJSubSorter ls = new FJSubSorter(new Sorter(a, w, l, q,   g),

                                                     new Sorter(a, w, l+q, h-q, g),

                                                     new Merger(a, w, l,   q,

                                                                l+q, h-q, l, g, null));

                    FJSubSorter rs = new FJSubSorter(new Sorter(a, w, l + h, q,   g),

                                                     new Sorter(a, w, l+u, n-u, g),

                                                     new Merger(a, w, l+h, q,

                                                                l+u, n-u, l+h, g, null));

                    rs.fork();

                    ls.compute();

                    if (rs.tryUnfork()) rs.compute(); else rs.join();

                    new Merger(w, a, l, h, l + h, n - h, l, g, null).compute();

                } else {

                    DualPivotQuicksort.sort(a, l, l+n-1);   // skip rangeCheck

                }

            }

        }

        static final class Merger extends RecursiveAction {

            static final long serialVersionUID = 3895749408536700048L;

            final short[] a;

            final short[] w;

            final int lo;

            final int ln;

            final int ro;

            final int rn;

            final int wo;

            final int gran;

            final Merger next;

            Merger(short[] a, short[] w, int lo, int ln, int ro, int rn, int wo,

                   int gran, Merger next) {

                this.a = a;

                this.w = w;

                this.lo = lo;

                this.ln = ln;

                this.ro = ro;

                this.rn = rn;

                this.wo = wo;

                this.gran = gran;

                this.next = next;

            }

            public void compute() {

                final short[] a = this.a;

                final short[] w = this.w;

                Merger rights = null;

                int nleft = ln;

                int nright = rn;

                while (nleft > gran) {

                    int lh = nleft >>> 1;

                    int splitIndex = lo + lh;

                    short split = a[splitIndex];

                    int rl = 0;

                    int rh = nright;

                    while (rl < rh) {

                        int mid = (rl + rh) >>> 1;

                        if (split <= a[ro + mid])

                            rh = mid;

                        else

                            rl = mid + 1;

                    }

                    (rights = new Merger(a, w, splitIndex, nleft-lh, ro+rh,

                                         nright-rh, wo+lh+rh, gran, rights)).fork();

                    nleft = lh;

                    nright = rh;

                }

                int l = lo;

                int lFence = l + nleft;

                int r = ro;

                int rFence = r + nright;

                int k = wo;

                while (l < lFence && r < rFence) {

                    short al = a[l];

                    short ar = a[r];

                    short t;

                    if (al <= ar) {++l; t=al;} else {++r; t = ar;}

                    w[k++] = t;

                }

                while (l < lFence)

                    w[k++] = a[l++];

                while (r < rFence)

                    w[k++] = a[r++];

                while (rights != null) {

                    if (rights.tryUnfork())

                        rights.compute();

                    else

                        rights.join();

                    rights = rights.next;

                }

            }

        }

    } // FJShort

    /** int support class */

    static final class FJInt {

        static final class Sorter extends RecursiveAction {

            static final long serialVersionUID = 4263311808957292729L;

            final int[] a;     // array to be sorted.

            final int[] w;     // workspace for merge

            final int origin;  // origin of the part of array we deal with

            final int n;       // Number of elements in (sub)arrays.

            final int gran;    // split control

            Sorter(int[] a, int[] w, int origin, int n, int gran) {

                this.a = a;

                this.w = w;

                this.origin = origin;

                this.n = n;

                this.gran = gran;

            }

            public void compute() {

                final int l = origin;

                final int g = gran;

                final int n = this.n;

                final int[] a = this.a;

                final int[] w = this.w;

                if (n > g) {

                    int h = n >>> 1; // half

                    int q = n >>> 2; // lower quarter index

                    int u = h + q;   // upper quarter

                    FJSubSorter ls = new FJSubSorter(new Sorter(a, w, l, q,   g),

                                                     new Sorter(a, w, l+q, h-q, g),

                                                     new Merger(a, w, l,   q,

                                                                l+q, h-q, l, g, null));

                    FJSubSorter rs = new FJSubSorter(new Sorter(a, w, l + h, q,   g),

                                                     new Sorter(a, w, l+u, n-u, g),

                                                     new Merger(a, w, l+h, q,

                                                                l+u, n-u, l+h, g, null));

                    rs.fork();

                    ls.compute();

                    if (rs.tryUnfork()) rs.compute(); else rs.join();

                    new Merger(w, a, l, h, l + h, n - h, l, g, null).compute();

                } else {

                    DualPivotQuicksort.sort(a, l, l+n-1);   // skip rangeCheck

                }

            }

        }

        static final class Merger extends RecursiveAction {

            static final long serialVersionUID = -8727507284219982792L;

            final int[] a;

            final int[] w;

            final int lo;

            final int ln;

            final int ro;

            final int rn;

            final int wo;

            final int gran;

            final Merger next;

            Merger(int[] a, int[] w, int lo, int ln, int ro, int rn, int wo,

                   int gran, Merger next) {

                this.a = a;

                this.w = w;

                this.lo = lo;

                this.ln = ln;

                this.ro = ro;

                this.rn = rn;

                this.wo = wo;

                this.gran = gran;

                this.next = next;

            }

            public void compute() {

                final int[] a = this.a;

                final int[] w = this.w;

                Merger rights = null;

                int nleft = ln;

                int nright = rn;

                while (nleft > gran) {

                    int lh = nleft >>> 1;

                    int splitIndex = lo + lh;

                    int split = a[splitIndex];

                    int rl = 0;

                    int rh = nright;

                    while (rl < rh) {

                        int mid = (rl + rh) >>> 1;

                        if (split <= a[ro + mid])

                            rh = mid;