| /* |
| * Copyright (c) 2012, 2013, 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; |
| import java.util.concurrent.CountedCompleter; |
| |
| /** |
| * 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 the associated sequential sort. |
| * |
| * Merger classes perform merging for Sorter. They are structured |
| * such that if the underlying sort is stable (as is true for |
| * TimSort), then so is the full sort. If big enough, they split the |
| * largest of the two partitions in half, find the greatest point in |
| * smaller partition less than the beginning of the second half of |
| * larger via binary search; and then merge in parallel the two |
| * partitions. In part to ensure tasks are triggered in |
| * stability-preserving order, the current CountedCompleter design |
| * 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.) |
| */ |
| /*package*/ class ArraysParallelSortHelpers { |
| |
| /* |
| * Style note: The task classes have a lot of parameters, that are |
| * stored as task fields and copied to local variables and used in |
| * compute() methods, We pack these into as few lines as possible, |
| * and hoist consistency checks among them before main loops, to |
| * reduce distraction. |
| */ |
| |
| /** |
| * A placeholder task for Sorters, used for the lowest |
| * quartile task, that does not need to maintain array state. |
| */ |
| static final class EmptyCompleter extends CountedCompleter<Void> { |
| static final long serialVersionUID = 2446542900576103244L; |
| EmptyCompleter(CountedCompleter<?> p) { super(p); } |
| public final void compute() { } |
| } |
| |
| /** |
| * A trigger for secondary merge of two merges |
| */ |
| static final class Relay extends CountedCompleter<Void> { |
| static final long serialVersionUID = 2446542900576103244L; |
| final CountedCompleter<?> task; |
| Relay(CountedCompleter<?> task) { |
| super(null, 1); |
| this.task = task; |
| } |
| public final void compute() { } |
| public final void onCompletion(CountedCompleter<?> t) { |
| task.compute(); |
| } |
| } |
| |
| /** Object + Comparator support class */ |
| static final class FJObject { |
| static final class Sorter<T> extends CountedCompleter<Void> { |
| static final long serialVersionUID = 2446542900576103244L; |
| final T[] a, w; |
| final int base, size, wbase, gran; |
| Comparator<? super T> comparator; |
| Sorter(CountedCompleter<?> par, T[] a, T[] w, int base, int size, |
| int wbase, int gran, |
| Comparator<? super T> comparator) { |
| super(par); |
| this.a = a; this.w = w; this.base = base; this.size = size; |
| this.wbase = wbase; this.gran = gran; |
| this.comparator = comparator; |
| } |
| public final void compute() { |
| CountedCompleter<?> s = this; |
| Comparator<? super T> c = this.comparator; |
| T[] 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<T>(s, w, a, wb, h, |
| wb+h, n-h, b, g, c)); |
| Relay rc = new Relay(new Merger<T>(fc, a, w, b+h, q, |
| b+u, n-u, wb+h, g, c)); |
| new Sorter<T>(rc, a, w, b+u, n-u, wb+u, g, c).fork(); |
| new Sorter<T>(rc, a, w, b+h, q, wb+h, g, c).fork();; |
| Relay bc = new Relay(new Merger<T>(fc, a, w, b, q, |
| b+q, h-q, wb, g, c)); |
| new Sorter<T>(bc, a, w, b+q, h-q, wb+q, g, c).fork(); |
| s = new EmptyCompleter(bc); |
| n = q; |
| } |
| TimSort.sort(a, b, b + n, c, w, wb, n); |
| s.tryComplete(); |
| } |
| } |
| |
| static final class Merger<T> extends CountedCompleter<Void> { |
| static final long serialVersionUID = 2446542900576103244L; |
| final T[] a, w; // main and workspace arrays |
| final int lbase, lsize, rbase, rsize, wbase, gran; |
| Comparator<? super T> comparator; |
| Merger(CountedCompleter<?> par, T[] a, T[] w, |
| int lbase, int lsize, int rbase, |
| int rsize, int wbase, int gran, |
| Comparator<? super T> comparator) { |
| 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; |
| this.comparator = comparator; |
| } |
| |
| public final void compute() { |
| Comparator<? super T> c = this.comparator; |
| T[] 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 || |
| c == null) |
| throw new IllegalStateException(); // hoist checks |
| for (int lh, rh;;) { // split larger, find point in smaller |
| if (ln >= rn) { |
| if (ln <= g) |
| break; |
| rh = rn; |
| T split = a[(lh = ln >>> 1) + lb]; |
| for (int lo = 0; lo < rh; ) { |
| int rm = (lo + rh) >>> 1; |
| if (c.compare(split, a[rm + rb]) <= 0) |
| rh = rm; |
| else |
| lo = rm + 1; |
| } |
| } |
| else { |
| if (rn <= g) |
| break; |
| lh = ln; |
| T split = a[(rh = rn >>> 1) + rb]; |
| for (int lo = 0; lo < lh; ) { |
| int lm = (lo + lh) >>> 1; |
| if (c.compare(split, a[lm + lb]) <= 0) |
| lh = lm; |
| else |
| lo = lm + 1; |
| } |
| } |
| Merger<T> m = new Merger<T>(this, a, w, lb + lh, ln - lh, |
| rb + rh, rn - rh, |
| k + lh + rh, g, c); |
| rn = rh; |
| ln = lh; |
| addToPendingCount(1); |
| m.fork(); |
| } |
| |
| int lf = lb + ln, rf = rb + rn; // index bounds |
| while (lb < lf && rb < rf) { |
| T t, al, ar; |
| if (c.compare((al = a[lb]), (ar = a[rb])) <= 0) { |
| 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(); |
| } |
| |
| } |
| } // 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 |
| |
| } |
