< prev index next >

src/java.base/share/classes/java/util/ArraysParallelSortHelpers.java

Print this page

        

@@ -1,7 +1,7 @@
 /*
- * Copyright (c) 2012, 2013, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2012, 2019, 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

@@ -22,11 +22,10 @@
  * or visit www.oracle.com if you need additional information or have any
  * questions.
  */
 package java.util;
 
-import java.util.concurrent.RecursiveAction;
 import java.util.concurrent.CountedCompleter;
 
 /**
  * Helper utilities for the parallel sort methods in Arrays.parallelSort.
  *

@@ -34,11 +33,11 @@
  * 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)
+ * if array size is small, just use a sequential sort (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

@@ -61,18 +60,14 @@
  * requires some little tasks to serve as place holders for triggering
  * completion tasks.  These classes (EmptyCompleter and Relay) don't
  * need to keep track of the arrays, and are never themselves forked,
  * so don't hold any task state.
  *
- * The primitive class versions (FJByte... FJDouble) are
- * identical to each other except for type declarations.
- *
  * The base sequential sorts rely on non-public versions of TimSort,
- * ComparableTimSort, and DualPivotQuicksort sort methods that accept
- * temp workspace array slices that we will have already allocated, so
- * avoids redundant allocation. (Except for DualPivotQuicksort byte[]
- * sort, that does not ever use a workspace array.)
+ * ComparableTimSort sort methods that accept temp workspace array
+ * slices that we will have already allocated, so avoids redundant
+ * allocation.
  */
 /*package*/ class ArraysParallelSortHelpers {
 
     /*
      * Style note: The task classes have a lot of parameters, that are

@@ -133,11 +128,11 @@
                     Relay fc = new Relay(new Merger<>(s, w, a, wb, h,
                                                       wb+h, n-h, b, g, c));
                     Relay rc = new Relay(new Merger<>(fc, a, w, b+h, q,
                                                       b+u, n-u, wb+h, g, c));
                     new Sorter<>(rc, a, w, b+u, n-u, wb+u, g, c).fork();
-                    new Sorter<>(rc, a, w, b+h, q, wb+h, g, c).fork();;
+                    new Sorter<>(rc, a, w, b+h, q, wb+h, g, c).fork();
                     Relay bc = new Relay(new Merger<>(fc, a, w, b, q,
                                                       b+q, h-q, wb, g, c));
                     new Sorter<>(bc, a, w, b+q, h-q, wb+q, g, c).fork();
                     s = new EmptyCompleter(bc);
                     n = q;

@@ -224,787 +219,8 @@
                 else if (lb < lf)
                     System.arraycopy(a, lb, w, k, lf - lb);
 
                 tryComplete();
             }
-
-        }
-    } // FJObject
-
-    /** byte support class */
-    static final class FJByte {
-        static final class Sorter extends CountedCompleter<Void> {
-            static final long serialVersionUID = 2446542900576103244L;
-            final byte[] a, w;
-            final int base, size, wbase, gran;
-            Sorter(CountedCompleter<?> par, byte[] a, byte[] w, int base,
-                   int size, int wbase, int gran) {
-                super(par);
-                this.a = a; this.w = w; this.base = base; this.size = size;
-                this.wbase = wbase; this.gran = gran;
-            }
-            public final void compute() {
-                CountedCompleter<?> s = this;
-                byte[] a = this.a, w = this.w; // localize all params
-                int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
-                while (n > g) {
-                    int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
-                    Relay fc = new Relay(new Merger(s, w, a, wb, h,
-                                                    wb+h, n-h, b, g));
-                    Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
-                                                    b+u, n-u, wb+h, g));
-                    new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
-                    new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
-                    Relay bc = new Relay(new Merger(fc, a, w, b, q,
-                                                    b+q, h-q, wb, g));
-                    new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
-                    s = new EmptyCompleter(bc);
-                    n = q;
-                }
-                DualPivotQuicksort.sort(a, b, b + n - 1);
-                s.tryComplete();
-            }
-        }
-
-        static final class Merger extends CountedCompleter<Void> {
-            static final long serialVersionUID = 2446542900576103244L;
-            final byte[] a, w; // main and workspace arrays
-            final int lbase, lsize, rbase, rsize, wbase, gran;
-            Merger(CountedCompleter<?> par, byte[] a, byte[] w,
-                   int lbase, int lsize, int rbase,
-                   int rsize, int wbase, int gran) {
-                super(par);
-                this.a = a; this.w = w;
-                this.lbase = lbase; this.lsize = lsize;
-                this.rbase = rbase; this.rsize = rsize;
-                this.wbase = wbase; this.gran = gran;
-            }
-
-            public final void compute() {
-                byte[] a = this.a, w = this.w; // localize all params
-                int lb = this.lbase, ln = this.lsize, rb = this.rbase,
-                    rn = this.rsize, k = this.wbase, g = this.gran;
-                if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
-                    throw new IllegalStateException(); // hoist checks
-                for (int lh, rh;;) {  // split larger, find point in smaller
-                    if (ln >= rn) {
-                        if (ln <= g)
-                            break;
-                        rh = rn;
-                        byte split = a[(lh = ln >>> 1) + lb];
-                        for (int lo = 0; lo < rh; ) {
-                            int rm = (lo + rh) >>> 1;
-                            if (split <= a[rm + rb])
-                                rh = rm;
-                            else
-                                lo = rm + 1;
-                        }
-                    }
-                    else {
-                        if (rn <= g)
-                            break;
-                        lh = ln;
-                        byte split = a[(rh = rn >>> 1) + rb];
-                        for (int lo = 0; lo < lh; ) {
-                            int lm = (lo + lh) >>> 1;
-                            if (split <= a[lm + lb])
-                                lh = lm;
-                            else
-                                lo = lm + 1;
-                        }
-                    }
-                    Merger m = new Merger(this, a, w, lb + lh, ln - lh,
-                                          rb + rh, rn - rh,
-                                          k + lh + rh, g);
-                    rn = rh;
-                    ln = lh;
-                    addToPendingCount(1);
-                    m.fork();
-                }
-
-                int lf = lb + ln, rf = rb + rn; // index bounds
-                while (lb < lf && rb < rf) {
-                    byte t, al, ar;
-                    if ((al = a[lb]) <= (ar = a[rb])) {
-                        lb++; t = al;
-                    }
-                    else {
-                        rb++; t = ar;
-                    }
-                    w[k++] = t;
-                }
-                if (rb < rf)
-                    System.arraycopy(a, rb, w, k, rf - rb);
-                else if (lb < lf)
-                    System.arraycopy(a, lb, w, k, lf - lb);
-                tryComplete();
-            }
-        }
-    } // FJByte
-
-    /** char support class */
-    static final class FJChar {
-        static final class Sorter extends CountedCompleter<Void> {
-            static final long serialVersionUID = 2446542900576103244L;
-            final char[] a, w;
-            final int base, size, wbase, gran;
-            Sorter(CountedCompleter<?> par, char[] a, char[] w, int base,
-                   int size, int wbase, int gran) {
-                super(par);
-                this.a = a; this.w = w; this.base = base; this.size = size;
-                this.wbase = wbase; this.gran = gran;
-            }
-            public final void compute() {
-                CountedCompleter<?> s = this;
-                char[] a = this.a, w = this.w; // localize all params
-                int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
-                while (n > g) {
-                    int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
-                    Relay fc = new Relay(new Merger(s, w, a, wb, h,
-                                                    wb+h, n-h, b, g));
-                    Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
-                                                    b+u, n-u, wb+h, g));
-                    new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
-                    new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
-                    Relay bc = new Relay(new Merger(fc, a, w, b, q,
-                                                    b+q, h-q, wb, g));
-                    new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
-                    s = new EmptyCompleter(bc);
-                    n = q;
-                }
-                DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
-                s.tryComplete();
-            }
-        }
-
-        static final class Merger extends CountedCompleter<Void> {
-            static final long serialVersionUID = 2446542900576103244L;
-            final char[] a, w; // main and workspace arrays
-            final int lbase, lsize, rbase, rsize, wbase, gran;
-            Merger(CountedCompleter<?> par, char[] a, char[] w,
-                   int lbase, int lsize, int rbase,
-                   int rsize, int wbase, int gran) {
-                super(par);
-                this.a = a; this.w = w;
-                this.lbase = lbase; this.lsize = lsize;
-                this.rbase = rbase; this.rsize = rsize;
-                this.wbase = wbase; this.gran = gran;
-            }
-
-            public final void compute() {
-                char[] a = this.a, w = this.w; // localize all params
-                int lb = this.lbase, ln = this.lsize, rb = this.rbase,
-                    rn = this.rsize, k = this.wbase, g = this.gran;
-                if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
-                    throw new IllegalStateException(); // hoist checks
-                for (int lh, rh;;) {  // split larger, find point in smaller
-                    if (ln >= rn) {
-                        if (ln <= g)
-                            break;
-                        rh = rn;
-                        char split = a[(lh = ln >>> 1) + lb];
-                        for (int lo = 0; lo < rh; ) {
-                            int rm = (lo + rh) >>> 1;
-                            if (split <= a[rm + rb])
-                                rh = rm;
-                            else
-                                lo = rm + 1;
-                        }
-                    }
-                    else {
-                        if (rn <= g)
-                            break;
-                        lh = ln;
-                        char split = a[(rh = rn >>> 1) + rb];
-                        for (int lo = 0; lo < lh; ) {
-                            int lm = (lo + lh) >>> 1;
-                            if (split <= a[lm + lb])
-                                lh = lm;
-                            else
-                                lo = lm + 1;
-                        }
-                    }
-                    Merger m = new Merger(this, a, w, lb + lh, ln - lh,
-                                          rb + rh, rn - rh,
-                                          k + lh + rh, g);
-                    rn = rh;
-                    ln = lh;
-                    addToPendingCount(1);
-                    m.fork();
-                }
-
-                int lf = lb + ln, rf = rb + rn; // index bounds
-                while (lb < lf && rb < rf) {
-                    char t, al, ar;
-                    if ((al = a[lb]) <= (ar = a[rb])) {
-                        lb++; t = al;
-                    }
-                    else {
-                        rb++; t = ar;
-                    }
-                    w[k++] = t;
-                }
-                if (rb < rf)
-                    System.arraycopy(a, rb, w, k, rf - rb);
-                else if (lb < lf)
-                    System.arraycopy(a, lb, w, k, lf - lb);
-                tryComplete();
-            }
-        }
-    } // FJChar
-
-    /** short support class */
-    static final class FJShort {
-        static final class Sorter extends CountedCompleter<Void> {
-            static final long serialVersionUID = 2446542900576103244L;
-            final short[] a, w;
-            final int base, size, wbase, gran;
-            Sorter(CountedCompleter<?> par, short[] a, short[] w, int base,
-                   int size, int wbase, int gran) {
-                super(par);
-                this.a = a; this.w = w; this.base = base; this.size = size;
-                this.wbase = wbase; this.gran = gran;
-            }
-            public final void compute() {
-                CountedCompleter<?> s = this;
-                short[] a = this.a, w = this.w; // localize all params
-                int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
-                while (n > g) {
-                    int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
-                    Relay fc = new Relay(new Merger(s, w, a, wb, h,
-                                                    wb+h, n-h, b, g));
-                    Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
-                                                    b+u, n-u, wb+h, g));
-                    new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
-                    new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
-                    Relay bc = new Relay(new Merger(fc, a, w, b, q,
-                                                    b+q, h-q, wb, g));
-                    new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
-                    s = new EmptyCompleter(bc);
-                    n = q;
-                }
-                DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
-                s.tryComplete();
-            }
-        }
-
-        static final class Merger extends CountedCompleter<Void> {
-            static final long serialVersionUID = 2446542900576103244L;
-            final short[] a, w; // main and workspace arrays
-            final int lbase, lsize, rbase, rsize, wbase, gran;
-            Merger(CountedCompleter<?> par, short[] a, short[] w,
-                   int lbase, int lsize, int rbase,
-                   int rsize, int wbase, int gran) {
-                super(par);
-                this.a = a; this.w = w;
-                this.lbase = lbase; this.lsize = lsize;
-                this.rbase = rbase; this.rsize = rsize;
-                this.wbase = wbase; this.gran = gran;
-            }
-
-            public final void compute() {
-                short[] a = this.a, w = this.w; // localize all params
-                int lb = this.lbase, ln = this.lsize, rb = this.rbase,
-                    rn = this.rsize, k = this.wbase, g = this.gran;
-                if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
-                    throw new IllegalStateException(); // hoist checks
-                for (int lh, rh;;) {  // split larger, find point in smaller
-                    if (ln >= rn) {
-                        if (ln <= g)
-                            break;
-                        rh = rn;
-                        short split = a[(lh = ln >>> 1) + lb];
-                        for (int lo = 0; lo < rh; ) {
-                            int rm = (lo + rh) >>> 1;
-                            if (split <= a[rm + rb])
-                                rh = rm;
-                            else
-                                lo = rm + 1;
-                        }
-                    }
-                    else {
-                        if (rn <= g)
-                            break;
-                        lh = ln;
-                        short split = a[(rh = rn >>> 1) + rb];
-                        for (int lo = 0; lo < lh; ) {
-                            int lm = (lo + lh) >>> 1;
-                            if (split <= a[lm + lb])
-                                lh = lm;
-                            else
-                                lo = lm + 1;
-                        }
-                    }
-                    Merger m = new Merger(this, a, w, lb + lh, ln - lh,
-                                          rb + rh, rn - rh,
-                                          k + lh + rh, g);
-                    rn = rh;
-                    ln = lh;
-                    addToPendingCount(1);
-                    m.fork();
-                }
-
-                int lf = lb + ln, rf = rb + rn; // index bounds
-                while (lb < lf && rb < rf) {
-                    short t, al, ar;
-                    if ((al = a[lb]) <= (ar = a[rb])) {
-                        lb++; t = al;
-                    }
-                    else {
-                        rb++; t = ar;
-                    }
-                    w[k++] = t;
-                }
-                if (rb < rf)
-                    System.arraycopy(a, rb, w, k, rf - rb);
-                else if (lb < lf)
-                    System.arraycopy(a, lb, w, k, lf - lb);
-                tryComplete();
-            }
-        }
-    } // FJShort
-
-    /** int support class */
-    static final class FJInt {
-        static final class Sorter extends CountedCompleter<Void> {
-            static final long serialVersionUID = 2446542900576103244L;
-            final int[] a, w;
-            final int base, size, wbase, gran;
-            Sorter(CountedCompleter<?> par, int[] a, int[] w, int base,
-                   int size, int wbase, int gran) {
-                super(par);
-                this.a = a; this.w = w; this.base = base; this.size = size;
-                this.wbase = wbase; this.gran = gran;
-            }
-            public final void compute() {
-                CountedCompleter<?> s = this;
-                int[] a = this.a, w = this.w; // localize all params
-                int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
-                while (n > g) {
-                    int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
-                    Relay fc = new Relay(new Merger(s, w, a, wb, h,
-                                                    wb+h, n-h, b, g));
-                    Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
-                                                    b+u, n-u, wb+h, g));
-                    new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
-                    new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
-                    Relay bc = new Relay(new Merger(fc, a, w, b, q,
-                                                    b+q, h-q, wb, g));
-                    new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
-                    s = new EmptyCompleter(bc);
-                    n = q;
-                }
-                DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
-                s.tryComplete();
-            }
         }
-
-        static final class Merger extends CountedCompleter<Void> {
-            static final long serialVersionUID = 2446542900576103244L;
-            final int[] a, w; // main and workspace arrays
-            final int lbase, lsize, rbase, rsize, wbase, gran;
-            Merger(CountedCompleter<?> par, int[] a, int[] w,
-                   int lbase, int lsize, int rbase,
-                   int rsize, int wbase, int gran) {
-                super(par);
-                this.a = a; this.w = w;
-                this.lbase = lbase; this.lsize = lsize;
-                this.rbase = rbase; this.rsize = rsize;
-                this.wbase = wbase; this.gran = gran;
-            }
-
-            public final void compute() {
-                int[] a = this.a, w = this.w; // localize all params
-                int lb = this.lbase, ln = this.lsize, rb = this.rbase,
-                    rn = this.rsize, k = this.wbase, g = this.gran;
-                if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
-                    throw new IllegalStateException(); // hoist checks
-                for (int lh, rh;;) {  // split larger, find point in smaller
-                    if (ln >= rn) {
-                        if (ln <= g)
-                            break;
-                        rh = rn;
-                        int split = a[(lh = ln >>> 1) + lb];
-                        for (int lo = 0; lo < rh; ) {
-                            int rm = (lo + rh) >>> 1;
-                            if (split <= a[rm + rb])
-                                rh = rm;
-                            else
-                                lo = rm + 1;
-                        }
-                    }
-                    else {
-                        if (rn <= g)
-                            break;
-                        lh = ln;
-                        int split = a[(rh = rn >>> 1) + rb];
-                        for (int lo = 0; lo < lh; ) {
-                            int lm = (lo + lh) >>> 1;
-                            if (split <= a[lm + lb])
-                                lh = lm;
-                            else
-                                lo = lm + 1;
-                        }
-                    }
-                    Merger m = new Merger(this, a, w, lb + lh, ln - lh,
-                                          rb + rh, rn - rh,
-                                          k + lh + rh, g);
-                    rn = rh;
-                    ln = lh;
-                    addToPendingCount(1);
-                    m.fork();
-                }
-
-                int lf = lb + ln, rf = rb + rn; // index bounds
-                while (lb < lf && rb < rf) {
-                    int t, al, ar;
-                    if ((al = a[lb]) <= (ar = a[rb])) {
-                        lb++; t = al;
-                    }
-                    else {
-                        rb++; t = ar;
-                    }
-                    w[k++] = t;
-                }
-                if (rb < rf)
-                    System.arraycopy(a, rb, w, k, rf - rb);
-                else if (lb < lf)
-                    System.arraycopy(a, lb, w, k, lf - lb);
-                tryComplete();
-            }
-        }
-    } // FJInt
-
-    /** long support class */
-    static final class FJLong {
-        static final class Sorter extends CountedCompleter<Void> {
-            static final long serialVersionUID = 2446542900576103244L;
-            final long[] a, w;
-            final int base, size, wbase, gran;
-            Sorter(CountedCompleter<?> par, long[] a, long[] w, int base,
-                   int size, int wbase, int gran) {
-                super(par);
-                this.a = a; this.w = w; this.base = base; this.size = size;
-                this.wbase = wbase; this.gran = gran;
-            }
-            public final void compute() {
-                CountedCompleter<?> s = this;
-                long[] a = this.a, w = this.w; // localize all params
-                int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
-                while (n > g) {
-                    int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
-                    Relay fc = new Relay(new Merger(s, w, a, wb, h,
-                                                    wb+h, n-h, b, g));
-                    Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
-                                                    b+u, n-u, wb+h, g));
-                    new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
-                    new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
-                    Relay bc = new Relay(new Merger(fc, a, w, b, q,
-                                                    b+q, h-q, wb, g));
-                    new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
-                    s = new EmptyCompleter(bc);
-                    n = q;
-                }
-                DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
-                s.tryComplete();
-            }
-        }
-
-        static final class Merger extends CountedCompleter<Void> {
-            static final long serialVersionUID = 2446542900576103244L;
-            final long[] a, w; // main and workspace arrays
-            final int lbase, lsize, rbase, rsize, wbase, gran;
-            Merger(CountedCompleter<?> par, long[] a, long[] w,
-                   int lbase, int lsize, int rbase,
-                   int rsize, int wbase, int gran) {
-                super(par);
-                this.a = a; this.w = w;
-                this.lbase = lbase; this.lsize = lsize;
-                this.rbase = rbase; this.rsize = rsize;
-                this.wbase = wbase; this.gran = gran;
-            }
-
-            public final void compute() {
-                long[] a = this.a, w = this.w; // localize all params
-                int lb = this.lbase, ln = this.lsize, rb = this.rbase,
-                    rn = this.rsize, k = this.wbase, g = this.gran;
-                if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
-                    throw new IllegalStateException(); // hoist checks
-                for (int lh, rh;;) {  // split larger, find point in smaller
-                    if (ln >= rn) {
-                        if (ln <= g)
-                            break;
-                        rh = rn;
-                        long split = a[(lh = ln >>> 1) + lb];
-                        for (int lo = 0; lo < rh; ) {
-                            int rm = (lo + rh) >>> 1;
-                            if (split <= a[rm + rb])
-                                rh = rm;
-                            else
-                                lo = rm + 1;
-                        }
-                    }
-                    else {
-                        if (rn <= g)
-                            break;
-                        lh = ln;
-                        long split = a[(rh = rn >>> 1) + rb];
-                        for (int lo = 0; lo < lh; ) {
-                            int lm = (lo + lh) >>> 1;
-                            if (split <= a[lm + lb])
-                                lh = lm;
-                            else
-                                lo = lm + 1;
-                        }
-                    }
-                    Merger m = new Merger(this, a, w, lb + lh, ln - lh,
-                                          rb + rh, rn - rh,
-                                          k + lh + rh, g);
-                    rn = rh;
-                    ln = lh;
-                    addToPendingCount(1);
-                    m.fork();
-                }
-
-                int lf = lb + ln, rf = rb + rn; // index bounds
-                while (lb < lf && rb < rf) {
-                    long t, al, ar;
-                    if ((al = a[lb]) <= (ar = a[rb])) {
-                        lb++; t = al;
-                    }
-                    else {
-                        rb++; t = ar;
-                    }
-                    w[k++] = t;
-                }
-                if (rb < rf)
-                    System.arraycopy(a, rb, w, k, rf - rb);
-                else if (lb < lf)
-                    System.arraycopy(a, lb, w, k, lf - lb);
-                tryComplete();
-            }
-        }
-    } // FJLong
-
-    /** float support class */
-    static final class FJFloat {
-        static final class Sorter extends CountedCompleter<Void> {
-            static final long serialVersionUID = 2446542900576103244L;
-            final float[] a, w;
-            final int base, size, wbase, gran;
-            Sorter(CountedCompleter<?> par, float[] a, float[] w, int base,
-                   int size, int wbase, int gran) {
-                super(par);
-                this.a = a; this.w = w; this.base = base; this.size = size;
-                this.wbase = wbase; this.gran = gran;
-            }
-            public final void compute() {
-                CountedCompleter<?> s = this;
-                float[] a = this.a, w = this.w; // localize all params
-                int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
-                while (n > g) {
-                    int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
-                    Relay fc = new Relay(new Merger(s, w, a, wb, h,
-                                                    wb+h, n-h, b, g));
-                    Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
-                                                    b+u, n-u, wb+h, g));
-                    new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
-                    new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
-                    Relay bc = new Relay(new Merger(fc, a, w, b, q,
-                                                    b+q, h-q, wb, g));
-                    new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
-                    s = new EmptyCompleter(bc);
-                    n = q;
-                }
-                DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
-                s.tryComplete();
-            }
-        }
-
-        static final class Merger extends CountedCompleter<Void> {
-            static final long serialVersionUID = 2446542900576103244L;
-            final float[] a, w; // main and workspace arrays
-            final int lbase, lsize, rbase, rsize, wbase, gran;
-            Merger(CountedCompleter<?> par, float[] a, float[] w,
-                   int lbase, int lsize, int rbase,
-                   int rsize, int wbase, int gran) {
-                super(par);
-                this.a = a; this.w = w;
-                this.lbase = lbase; this.lsize = lsize;
-                this.rbase = rbase; this.rsize = rsize;
-                this.wbase = wbase; this.gran = gran;
-            }
-
-            public final void compute() {
-                float[] a = this.a, w = this.w; // localize all params
-                int lb = this.lbase, ln = this.lsize, rb = this.rbase,
-                    rn = this.rsize, k = this.wbase, g = this.gran;
-                if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
-                    throw new IllegalStateException(); // hoist checks
-                for (int lh, rh;;) {  // split larger, find point in smaller
-                    if (ln >= rn) {
-                        if (ln <= g)
-                            break;
-                        rh = rn;
-                        float split = a[(lh = ln >>> 1) + lb];
-                        for (int lo = 0; lo < rh; ) {
-                            int rm = (lo + rh) >>> 1;
-                            if (split <= a[rm + rb])
-                                rh = rm;
-                            else
-                                lo = rm + 1;
-                        }
-                    }
-                    else {
-                        if (rn <= g)
-                            break;
-                        lh = ln;
-                        float split = a[(rh = rn >>> 1) + rb];
-                        for (int lo = 0; lo < lh; ) {
-                            int lm = (lo + lh) >>> 1;
-                            if (split <= a[lm + lb])
-                                lh = lm;
-                            else
-                                lo = lm + 1;
-                        }
-                    }
-                    Merger m = new Merger(this, a, w, lb + lh, ln - lh,
-                                          rb + rh, rn - rh,
-                                          k + lh + rh, g);
-                    rn = rh;
-                    ln = lh;
-                    addToPendingCount(1);
-                    m.fork();
-                }
-
-                int lf = lb + ln, rf = rb + rn; // index bounds
-                while (lb < lf && rb < rf) {
-                    float t, al, ar;
-                    if ((al = a[lb]) <= (ar = a[rb])) {
-                        lb++; t = al;
-                    }
-                    else {
-                        rb++; t = ar;
-                    }
-                    w[k++] = t;
-                }
-                if (rb < rf)
-                    System.arraycopy(a, rb, w, k, rf - rb);
-                else if (lb < lf)
-                    System.arraycopy(a, lb, w, k, lf - lb);
-                tryComplete();
-            }
-        }
-    } // FJFloat
-
-    /** double support class */
-    static final class FJDouble {
-        static final class Sorter extends CountedCompleter<Void> {
-            static final long serialVersionUID = 2446542900576103244L;
-            final double[] a, w;
-            final int base, size, wbase, gran;
-            Sorter(CountedCompleter<?> par, double[] a, double[] w, int base,
-                   int size, int wbase, int gran) {
-                super(par);
-                this.a = a; this.w = w; this.base = base; this.size = size;
-                this.wbase = wbase; this.gran = gran;
-            }
-            public final void compute() {
-                CountedCompleter<?> s = this;
-                double[] a = this.a, w = this.w; // localize all params
-                int b = this.base, n = this.size, wb = this.wbase, g = this.gran;
-                while (n > g) {
-                    int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
-                    Relay fc = new Relay(new Merger(s, w, a, wb, h,
-                                                    wb+h, n-h, b, g));
-                    Relay rc = new Relay(new Merger(fc, a, w, b+h, q,
-                                                    b+u, n-u, wb+h, g));
-                    new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
-                    new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
-                    Relay bc = new Relay(new Merger(fc, a, w, b, q,
-                                                    b+q, h-q, wb, g));
-                    new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
-                    s = new EmptyCompleter(bc);
-                    n = q;
-                }
-                DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
-                s.tryComplete();
-            }
-        }
-
-        static final class Merger extends CountedCompleter<Void> {
-            static final long serialVersionUID = 2446542900576103244L;
-            final double[] a, w; // main and workspace arrays
-            final int lbase, lsize, rbase, rsize, wbase, gran;
-            Merger(CountedCompleter<?> par, double[] a, double[] w,
-                   int lbase, int lsize, int rbase,
-                   int rsize, int wbase, int gran) {
-                super(par);
-                this.a = a; this.w = w;
-                this.lbase = lbase; this.lsize = lsize;
-                this.rbase = rbase; this.rsize = rsize;
-                this.wbase = wbase; this.gran = gran;
-            }
-
-            public final void compute() {
-                double[] a = this.a, w = this.w; // localize all params
-                int lb = this.lbase, ln = this.lsize, rb = this.rbase,
-                    rn = this.rsize, k = this.wbase, g = this.gran;
-                if (a == null || w == null || lb < 0 || rb < 0 || k < 0)
-                    throw new IllegalStateException(); // hoist checks
-                for (int lh, rh;;) {  // split larger, find point in smaller
-                    if (ln >= rn) {
-                        if (ln <= g)
-                            break;
-                        rh = rn;
-                        double split = a[(lh = ln >>> 1) + lb];
-                        for (int lo = 0; lo < rh; ) {
-                            int rm = (lo + rh) >>> 1;
-                            if (split <= a[rm + rb])
-                                rh = rm;
-                            else
-                                lo = rm + 1;
-                        }
-                    }
-                    else {
-                        if (rn <= g)
-                            break;
-                        lh = ln;
-                        double split = a[(rh = rn >>> 1) + rb];
-                        for (int lo = 0; lo < lh; ) {
-                            int lm = (lo + lh) >>> 1;
-                            if (split <= a[lm + lb])
-                                lh = lm;
-                            else
-                                lo = lm + 1;
-                        }
-                    }
-                    Merger m = new Merger(this, a, w, lb + lh, ln - lh,
-                                          rb + rh, rn - rh,
-                                          k + lh + rh, g);
-                    rn = rh;
-                    ln = lh;
-                    addToPendingCount(1);
-                    m.fork();
-                }
-
-                int lf = lb + ln, rf = rb + rn; // index bounds
-                while (lb < lf && rb < rf) {
-                    double t, al, ar;
-                    if ((al = a[lb]) <= (ar = a[rb])) {
-                        lb++; t = al;
-                    }
-                    else {
-                        rb++; t = ar;
-                    }
-                    w[k++] = t;
-                }
-                if (rb < rf)
-                    System.arraycopy(a, rb, w, k, rf - rb);
-                else if (lb < lf)
-                    System.arraycopy(a, lb, w, k, lf - lb);
-                tryComplete();
-            }
-        }
-    } // FJDouble
-
+    }
 }
< prev index next >