src/extra166y/PAS.java

/*
 * Written by Doug Lea with assistance from members of JCP JSR-166
 * Expert Group and released to the public domain, as explained at
 * http://creativecommons.org/publicdomain/zero/1.0/
 */

package extra166y;
import jsr166y.*;
import static extra166y.Ops.*;
import java.util.*;
import java.util.concurrent.atomic.*;
import java.lang.reflect.Array;

/**
 * Shared internal execution support for ParallelArray and
 * specializations.
 */
class PAS {
    private PAS() {} // all-static, non-instantiable

    /** Global default executor */
    private static volatile ForkJoinPool defaultExecutor;
    /** Lock for on-demand initialization of defaultExecutor */
    private static final Object poolLock = new Object();

    static ForkJoinPool defaultExecutor() {
        ForkJoinPool p = defaultExecutor; // double-check
        if (p == null) {
            synchronized (poolLock) {
                p = defaultExecutor;
                if (p == null) {
                    // use ceil(7/8 * ncpus)
                    int nprocs = Runtime.getRuntime().availableProcessors();
                    int nthreads = nprocs - (nprocs >>> 3);
                    defaultExecutor = p = new ForkJoinPool(nthreads);
                }
            }
        }
        return p;
    }

    /**
     * Base for most divide-and-conquer tasks used for computing
     * ParallelArray operations. Rather than pure recursion, it links
     * right-hand-sides and then joins up the tree, exploiting cases
     * where tasks aren't stolen.  This generates and joins tasks with
     * a bit less overhead than pure recursive style -- there are only
     * as many tasks as leaves (no strictly internal nodes).
     *
     * Split control relies on pap.getThreshold(), which is
     * expected to err on the side of generating too many tasks. To
     * counterbalance, if a task pops off its own smallest subtask, it
     * directly runs its leaf action rather than possibly resplitting.
     *
     * There are, with a few exceptions, three flavors of each FJBase
     * subclass, prefixed FJO (object reference), FJD (double) and FJL
     * (long).
     */
    static abstract class FJBase extends RecursiveAction {
        final AbstractParallelAnyArray pap;
        final int lo;
        final int hi;
        final FJBase next; // the next task that creator should join
        FJBase(AbstractParallelAnyArray pap, int lo, int hi, FJBase next) {
            this.pap = pap;
            this.lo = lo;
            this.hi = hi;
            this.next = next;
        }

        public final void compute() {
            int g = pap.getThreshold();
            int l = lo;
            int h = hi;
            if (h - l > g)
                internalCompute(l, h, g);
            else
                atLeaf(l, h);
        }

        final void internalCompute(int l, int h, int g) {
            FJBase r = null;
            do {
                int rh = h;
                h = (l + h) >>> 1;
                (r = newSubtask(h, rh, r)).fork();
            } while (h - l > g);
            atLeaf(l, h);
            do {
                if (r.tryUnfork()) r.atLeaf(r.lo, r.hi); else r.join();
                onReduce(r);
                r = r.next;
            } while (r != null);
        }

        /** Leaf computation */
        abstract void atLeaf(int l, int h);
        /** Operation performed after joining right subtask -- default noop */
        void onReduce(FJBase right) {}
        /** Factory method to create new subtask, normally of current type */
        abstract FJBase newSubtask(int l, int h, FJBase r);
    }

    // apply

    static final class FJOApply extends FJBase {
        final Procedure procedure;
        FJOApply(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
                 Procedure procedure) {
            super(pap, lo, hi, next);
            this.procedure = procedure;
        }
        FJBase newSubtask(int l, int h, FJBase r) {
            return new FJOApply(pap, l, h, r, procedure);
        }
        void atLeaf(int l, int h) {
            pap.leafApply(l, h, procedure);
        }
    }

    static final class FJDApply extends FJBase {
        final DoubleProcedure procedure;
        FJDApply(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
                 DoubleProcedure procedure) {
            super(pap, lo, hi, next);
            this.procedure = procedure;
        }
        FJBase newSubtask(int l, int h, FJBase r) {
            return new FJDApply(pap, l, h, r, procedure);
        }
        void atLeaf(int l, int h) {
            pap.leafApply(l, h, procedure);
        }
    }

    static final class FJLApply extends FJBase {
        final LongProcedure procedure;
        FJLApply(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
                 LongProcedure procedure) {
            super(pap, lo, hi, next);
            this.procedure = procedure;
        }
        FJBase newSubtask(int l, int h, FJBase r) {
            return new FJLApply(pap, l, h, r, procedure);
        }
        void atLeaf(int l, int h) {
            pap.leafApply(l, h, procedure);
        }
    }

    // reduce

    static final class FJOReduce extends FJBase {
        final Reducer reducer;
        Object result;
        FJOReduce(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
                  Reducer reducer, Object base) {
            super(pap, lo, hi, next);
            this.reducer = reducer;
            this.result = base;
        }
        FJBase newSubtask(int l, int h, FJBase r) {
            return new FJOReduce(pap, l, h, r, reducer, result);
        }
        void atLeaf(int l, int h) {
            result = pap.leafReduce(l, h, reducer, result);
        }
        void onReduce(FJBase right) {
            result = reducer.op(result, ((FJOReduce)right).result);
        }
    }

    static final class FJDReduce extends FJBase {
        final DoubleReducer reducer;
        double result;
        FJDReduce(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
                  DoubleReducer reducer, double base) {
            super(pap, lo, hi, next);
            this.reducer = reducer;
            this.result = base;
        }
        FJBase newSubtask(int l, int h, FJBase r) {
            return new FJDReduce(pap, l, h, r, reducer, result);
        }
        void atLeaf(int l, int h) {
            result = pap.leafReduce(l, h, reducer, result);
        }
        void onReduce(FJBase right) {
            result = reducer.op(result, ((FJDReduce)right).result);
        }
    }

    static final class FJLReduce extends FJBase {
        final LongReducer reducer;
        long result;
        FJLReduce(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
                  LongReducer reducer, long base) {
            super(pap, lo, hi, next);
            this.reducer = reducer;
            this.result = base;
        }
        FJBase newSubtask(int l, int h, FJBase r) {
            return new FJLReduce(pap, l, h, r, reducer, result);
        }
        void atLeaf(int l, int h) {
            result = pap.leafReduce(l, h, reducer, result);
        }
        void onReduce(FJBase right) {
            result = reducer.op(result, ((FJLReduce)right).result);
        }
    }

    // map

    static final class FJOMap extends FJBase {
        final Object[] dest;
        final int offset;
        FJOMap(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
               Object[] dest, int offset) {
            super(pap, lo, hi, next);
            this.dest = dest;
            this.offset = offset;
        }
        FJBase newSubtask(int l, int h, FJBase r) {
            return new FJOMap(pap, l, h, r, dest, offset);
        }
        void atLeaf(int l, int h) {
            pap.leafTransfer(l, h, dest, l + offset);
        }
    }

    static final class FJDMap extends FJBase {
        final double[] dest;
        final int offset;
        FJDMap(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
               double[] dest, int offset) {
            super(pap, lo, hi, next);
            this.dest = dest;
            this.offset = offset;
        }
        FJBase newSubtask(int l, int h, FJBase r) {
            return new FJDMap(pap, l, h, r, dest, offset);
        }
        void atLeaf(int l, int h) {
            pap.leafTransfer(l, h, dest, l + offset);
        }
    }

    static final class FJLMap extends FJBase {
        final long[] dest;
        final int offset;
        FJLMap(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
               long[] dest, int offset) {
            super(pap, lo, hi, next);
            this.dest = dest;
            this.offset = offset;
        }
        FJBase newSubtask(int l, int h, FJBase r) {
            return new FJLMap(pap, l, h, r, dest, offset);
        }
        void atLeaf(int l, int h) {
            pap.leafTransfer(l, h, dest, l + offset);
        }
    }

    // transform

    static final class FJOTransform extends FJBase {
        final Op op;
        FJOTransform(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
                     Op op) {
            super(pap, lo, hi, next);
            this.op = op;
        }
        FJBase newSubtask(int l, int h, FJBase r) {
            return new FJOTransform(pap, l, h, r, op);
        }
        void atLeaf(int l, int h) {
            pap.leafTransform(l, h, op);
        }
    }

    static final class FJDTransform extends FJBase {
        final DoubleOp op;
        FJDTransform(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
                     DoubleOp op) {
            super(pap, lo, hi, next);
            this.op = op;
        }
        FJBase newSubtask(int l, int h, FJBase r) {
            return new FJDTransform(pap, l, h, r, op);
        }
        void atLeaf(int l, int h) {
            pap.leafTransform(l, h, op);
        }
    }

    static final class FJLTransform extends FJBase {
        final LongOp op;
        FJLTransform(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
                     LongOp op) {
            super(pap, lo, hi, next);
            this.op = op;
        }
        FJBase newSubtask(int l, int h, FJBase r) {
            return new FJLTransform(pap, l, h, r, op);
        }
        void atLeaf(int l, int h) {
            pap.leafTransform(l, h, op);
        }
    }

    // index map

    static final class FJOIndexMap extends FJBase {
        final IntToObject op;
        FJOIndexMap(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
                    IntToObject op) {
            super(pap, lo, hi, next);
            this.op = op;
        }
        FJBase newSubtask(int l, int h, FJBase r) {
            return new FJOIndexMap(pap, l, h, r, op);
        }
        void atLeaf(int l, int h) {
            pap.leafIndexMap(l, h, op);
        }
    }

    static final class FJDIndexMap extends FJBase {
        final IntToDouble op;
        FJDIndexMap(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
                    IntToDouble op) {
            super(pap, lo, hi, next);
            this.op = op;
        }
        FJBase newSubtask(int l, int h, FJBase r) {
            return new FJDIndexMap(pap, l, h, r, op);
        }
        void atLeaf(int l, int h) {
            pap.leafIndexMap(l, h, op);
        }
    }

    static final class FJLIndexMap extends FJBase {
        final IntToLong op;
        FJLIndexMap(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
                    IntToLong op) {
            super(pap, lo, hi, next);
            this.op = op;
        }
        FJBase newSubtask(int l, int h, FJBase r) {
            return new FJLIndexMap(pap, l, h, r, op);
        }
        void atLeaf(int l, int h) {
            pap.leafIndexMap(l, h, op);
        }
    }

    // binary index map

    static final class FJOBinaryIndexMap extends FJBase {
        final IntAndObjectToObject op;
        FJOBinaryIndexMap(AbstractParallelAnyArray pap, int lo, int hi,
                          FJBase next, IntAndObjectToObject op) {
            super(pap, lo, hi, next);
            this.op = op;
        }
        FJBase newSubtask(int l, int h, FJBase r) {
            return new FJOBinaryIndexMap(pap, l, h, r, op);
        }
        void atLeaf(int l, int h) {
            pap.leafBinaryIndexMap(l, h, op);
        }
    }

    static final class FJDBinaryIndexMap extends FJBase {
        final IntAndDoubleToDouble op;
        FJDBinaryIndexMap(AbstractParallelAnyArray pap, int lo, int hi,
                          FJBase next, IntAndDoubleToDouble op) {
            super(pap, lo, hi, next);
            this.op = op;
        }
        FJBase newSubtask(int l, int h, FJBase r) {
            return new FJDBinaryIndexMap(pap, l, h, r, op);
        }
        void atLeaf(int l, int h) {
            pap.leafBinaryIndexMap(l, h, op);
        }
    }

    static final class FJLBinaryIndexMap extends FJBase {
        final IntAndLongToLong op;
        FJLBinaryIndexMap(AbstractParallelAnyArray pap, int lo, int hi,
                          FJBase next, IntAndLongToLong op) {
            super(pap, lo, hi, next);
            this.op = op;
        }
        FJBase newSubtask(int l, int h, FJBase r) {
            return new FJLBinaryIndexMap(pap, l, h, r, op);
        }
        void atLeaf(int l, int h) {
            pap.leafBinaryIndexMap(l, h, op);
        }
    }


    // generate

    static final class FJOGenerate extends FJBase {
        final Generator generator;
        FJOGenerate(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
                    Generator generator) {
            super(pap, lo, hi, next);
            this.generator = generator;
        }
        FJBase newSubtask(int l, int h, FJBase r) {
            return new FJOGenerate(pap, l, h, r, generator);
        }
        void atLeaf(int l, int h) {
            pap.leafGenerate(l, h, generator);
        }
    }

    static final class FJDGenerate extends FJBase {
        final DoubleGenerator generator;
        FJDGenerate(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
                    DoubleGenerator generator) {
            super(pap, lo, hi, next);
            this.generator = generator;
        }
        FJBase newSubtask(int l, int h, FJBase r) {
            return new FJDGenerate(pap, l, h, r, generator);
        }
        void atLeaf(int l, int h) {
            pap.leafGenerate(l, h, generator);
        }
    }

    static final class FJLGenerate extends FJBase {
        final LongGenerator generator;
        FJLGenerate(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
                    LongGenerator generator) {
            super(pap, lo, hi, next);
            this.generator = generator;
        }
        FJBase newSubtask(int l, int h, FJBase r) {
            return new FJLGenerate(pap, l, h, r, generator);
        }
        void atLeaf(int l, int h) {
            pap.leafGenerate(l, h, generator);
        }
    }

    // fill

    static final class FJOFill extends FJBase {
        final Object value;
        FJOFill(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
                Object value) {
            super(pap, lo, hi, next);
            this.value = value;
        }
        FJBase newSubtask(int l, int h, FJBase r) {
            return new FJOFill(pap, l, h, r, value);
        }
        void atLeaf(int l, int h) {
            pap.leafFill(l, h, value);
        }
    }

    static final class FJDFill extends FJBase {
        final double value;
        FJDFill(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
                double value) {
            super(pap, lo, hi, next);
            this.value = value;
        }
        FJBase newSubtask(int l, int h, FJBase r) {
            return new FJDFill(pap, l, h, r, value);
        }
        void atLeaf(int l, int h) {
            pap.leafFill(l, h, value);
        }
    }

    static final class FJLFill extends FJBase {
        final long value;
        FJLFill(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
                long value) {
            super(pap, lo, hi, next);
            this.value = value;
        }
        FJBase newSubtask(int l, int h, FJBase r) {
            return new FJLFill(pap, l, h, r, value);
        }
        void atLeaf(int l, int h) {
            pap.leafFill(l, h, value);
        }
    }

    // combine in place

    static final class FJOCombineInPlace extends FJBase {
        final Object[] other;
        final int otherOffset;
        final BinaryOp combiner;
        FJOCombineInPlace(AbstractParallelAnyArray pap, int lo, int hi,
                          FJBase next, Object[] other, int otherOffset,
                          BinaryOp combiner) {
            super(pap, lo, hi, next);
            this.other = other;
            this.otherOffset = otherOffset;
            this.combiner = combiner;
        }
        FJBase newSubtask(int l, int h, FJBase r) {
            return new FJOCombineInPlace
                (pap, l, h, r, other, otherOffset, combiner);
        }
        void atLeaf(int l, int h) {
            pap.leafCombineInPlace(l, h, other, otherOffset, combiner);
        }
    }

    static final class FJDCombineInPlace extends FJBase {
        final double[] other;
        final int otherOffset;
        final BinaryDoubleOp combiner;
        FJDCombineInPlace(AbstractParallelAnyArray pap, int lo, int hi,
                          FJBase next, double[] other, int otherOffset,
                          BinaryDoubleOp combiner) {
            super(pap, lo, hi, next);
            this.other = other;
            this.otherOffset = otherOffset;
            this.combiner = combiner;
        }
        FJBase newSubtask(int l, int h, FJBase r) {
            return new FJDCombineInPlace
                (pap, l, h, r, other, otherOffset, combiner);
        }
        void atLeaf(int l, int h) {
            pap.leafCombineInPlace(l, h, other, otherOffset, combiner);
        }
    }

    static final class FJLCombineInPlace extends FJBase {
        final long[] other;
        final int otherOffset;
        final BinaryLongOp combiner;
        FJLCombineInPlace(AbstractParallelAnyArray pap, int lo, int hi,
                          FJBase next, long[] other, int otherOffset,
                          BinaryLongOp combiner) {
            super(pap, lo, hi, next);
            this.other = other;
            this.otherOffset = otherOffset;
            this.combiner = combiner;
        }
        FJBase newSubtask(int l, int h, FJBase r) {
            return new FJLCombineInPlace
                (pap, l, h, r, other, otherOffset, combiner);
        }
        void atLeaf(int l, int h) {
            pap.leafCombineInPlace(l, h, other, otherOffset, combiner);
        }
    }

    static final class FJOPACombineInPlace extends FJBase {
        final ParallelArrayWithMapping other;
        final int otherOffset;
        final BinaryOp combiner;
        FJOPACombineInPlace(AbstractParallelAnyArray pap, int lo, int hi,
                            FJBase next,
                            ParallelArrayWithMapping other, int otherOffset,
                            BinaryOp combiner) {
            super(pap, lo, hi, next);
            this.other = other;
            this.otherOffset = otherOffset;
            this.combiner = combiner;
        }
        FJBase newSubtask(int l, int h, FJBase r) {
            return new FJOPACombineInPlace
                (pap, l, h, r, other, otherOffset, combiner);
        }
        void atLeaf(int l, int h) {
            pap.leafCombineInPlace(l, h, other, otherOffset, combiner);
        }
    }

    static final class FJDPACombineInPlace extends FJBase {
        final ParallelDoubleArrayWithDoubleMapping other;
        final int otherOffset;
        final BinaryDoubleOp combiner;
        FJDPACombineInPlace(AbstractParallelAnyArray pap, int lo, int hi,
                            FJBase next,
                            ParallelDoubleArrayWithDoubleMapping other,
                            int otherOffset, BinaryDoubleOp combiner) {
            super(pap, lo, hi, next);
            this.other = other;
            this.otherOffset = otherOffset;
            this.combiner = combiner;
        }
        FJBase newSubtask(int l, int h, FJBase r) {
            return new FJDPACombineInPlace
                (pap, l, h, r, other, otherOffset, combiner);
        }
        void atLeaf(int l, int h) {
            pap.leafCombineInPlace(l, h, other, otherOffset, combiner);
        }
    }

    static final class FJLPACombineInPlace extends FJBase {
        final ParallelLongArrayWithLongMapping other;
        final int otherOffset;
        final BinaryLongOp combiner;
        FJLPACombineInPlace(AbstractParallelAnyArray pap, int lo, int hi,
                            FJBase next,
                            ParallelLongArrayWithLongMapping other,
                            int otherOffset, BinaryLongOp combiner) {
            super(pap, lo, hi, next);
            this.other = other;
            this.otherOffset = otherOffset;
            this.combiner = combiner;
        }
        FJBase newSubtask(int l, int h, FJBase r) {
            return new FJLPACombineInPlace
                (pap, l, h, r, other, otherOffset, combiner);
        }
        void atLeaf(int l, int h) {
            pap.leafCombineInPlace(l, h, other, otherOffset, combiner);
        }
    }

    // stats

    static final class FJOStats extends FJBase
        implements ParallelArray.SummaryStatistics {
        final Comparator comparator;
        public int size() { return size; }
        public Object min() { return min; }
        public Object max() { return max; }
        public int indexOfMin() { return indexOfMin; }
        public int indexOfMax() { return indexOfMax; }
        int size;
        Object min;
        Object max;
        int indexOfMin;
        int indexOfMax;
        FJOStats(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
                 Comparator comparator) {
            super(pap, lo, hi, next);
            this.comparator = comparator;
            this.indexOfMin = -1;
            this.indexOfMax = -1;
        }
        FJBase newSubtask(int l, int h, FJBase r) {
            return new FJOStats(pap, l, h, r, comparator);
        }
        void onReduce(FJBase right) {
            FJOStats r = (FJOStats)right;
            size += r.size;
            updateMin(r.indexOfMin, r.min);
            updateMax(r.indexOfMax, r.max);
        }
        void updateMin(int i, Object x) {
            if (i >= 0 &&
                (indexOfMin < 0 || comparator.compare(min, x) > 0)) {
                min = x;
                indexOfMin = i;
            }
        }
        void updateMax(int i, Object x) {
            if (i >= 0 &&
                (indexOfMax < 0 || comparator.compare(max, x) < 0)) {
                max = x;
                indexOfMax = i;
            }
        }

        void  atLeaf(int l, int h) {
            if (pap.hasFilter())
                filteredAtLeaf(l, h);
            else {
                size = h - l;
                for (int i = l; i < h; ++i) {
                    Object x = pap.oget(i);
                    updateMin(i, x);
                    updateMax(i, x);
                }
            }
        }

        void  filteredAtLeaf(int l, int h) {
            for (int i = l; i < h; ++i) {
                if (pap.isSelected(i)) {
                    Object x = pap.oget(i);
                    ++size;
                    updateMin(i, x);
                    updateMax(i, x);
                }
            }
        }

        public String toString() {
            return
                "size: " + size +
                " min: " + min + " (index " + indexOfMin +
                ") max: " + max + " (index " + indexOfMax + ")";
        }

    }

    static final class FJDStats extends FJBase
        implements ParallelDoubleArray.SummaryStatistics {
        final DoubleComparator comparator;
        public int size() { return size; }
        public double min() { return min; }
        public double max() { return max; }
        public double sum() { return sum; }
        public double average() { return sum / size; }
        public int indexOfMin() { return indexOfMin; }
        public int indexOfMax() { return indexOfMax; }
        int size;
        double min;
        double max;
        double sum;
        int indexOfMin;
        int indexOfMax;
        FJDStats(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
                 DoubleComparator comparator) {
            super(pap, lo, hi, next);
            this.comparator = comparator;
            this.indexOfMin = -1;
            this.indexOfMax = -1;
            this.min = Double.MAX_VALUE;
            this.max = -Double.MAX_VALUE;
        }
        FJBase newSubtask(int l, int h, FJBase r) {
            return new FJDStats(pap, l, h, r, comparator);
        }
        void onReduce(FJBase right) {
            FJDStats r = (FJDStats)right;
            size += r.size;
            sum += r.sum;
            updateMin(r.indexOfMin, r.min);
            updateMax(r.indexOfMax, r.max);
        }
        void updateMin(int i, double x) {
            if (i >= 0 &&
                (indexOfMin < 0 || comparator.compare(min, x) > 0)) {
                min = x;
                indexOfMin = i;
            }
        }
        void updateMax(int i, double x) {
            if (i >= 0 &&
                (indexOfMax < 0 || comparator.compare(max, x) < 0)) {
                max = x;
                indexOfMax = i;
            }
        }
        void atLeaf(int l, int h) {
            if (pap.hasFilter())
                filteredAtLeaf(l, h);
            else {
                size = h - l;
                for (int i = l; i < h; ++i) {
                    double x = pap.dget(i);
                    sum += x;
                    updateMin(i, x);
                    updateMax(i, x);
                }
            }
        }

        void  filteredAtLeaf(int l, int h) {
            for (int i = l; i < h; ++i) {
                if (pap.isSelected(i)) {
                    double x = pap.dget(i);
                    ++size;
                    sum += x;
                    updateMin(i, x);
                    updateMax(i, x);
                }
            }
        }

        public String toString() {
            return
                "size: " + size +
                " min: " + min + " (index " + indexOfMin +
                ") max: " + max + " (index " + indexOfMax +
                ") sum: " + sum;
        }
    }

    static final class FJLStats extends FJBase
        implements ParallelLongArray.SummaryStatistics {
        final LongComparator comparator;
        public int size() { return size; }
        public long min() { return min; }
        public long max() { return max; }
        public long sum() { return sum; }
        public double average() { return (double)sum / size; }
        public int indexOfMin() { return indexOfMin; }
        public int indexOfMax() { return indexOfMax; }
        int size;
        long min;
        long max;
        long sum;
        int indexOfMin;
        int indexOfMax;
        FJLStats(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
                 LongComparator comparator) {
            super(pap, lo, hi, next);
            this.comparator = comparator;
            this.indexOfMin = -1;
            this.indexOfMax = -1;
            this.min = Long.MAX_VALUE;
            this.max = Long.MIN_VALUE;
        }
        FJBase newSubtask(int l, int h, FJBase r) {
            return new FJLStats(pap, l, h, r, comparator);
        }
        void onReduce(FJBase right) {
            FJLStats r = (FJLStats)right;
            size += r.size;
            sum += r.sum;
            updateMin(r.indexOfMin, r.min);
            updateMax(r.indexOfMax, r.max);
        }
        void updateMin(int i, long x) {
            if (i >= 0 &&
                (indexOfMin < 0 || comparator.compare(min, x) > 0)) {
                min = x;
                indexOfMin = i;
            }
        }
        void updateMax(int i, long x) {
            if (i >= 0 &&
                (indexOfMax < 0 || comparator.compare(max, x) < 0)) {
                max = x;
                indexOfMax = i;
            }
        }

        void  atLeaf(int l, int h) {
            if (pap.hasFilter())
                filteredAtLeaf(l, h);
            else {
                size = h - l;
                for (int i = l; i < h; ++i) {
                    long x = pap.lget(i);
                    sum += x;
                    updateMin(i, x);
                    updateMax(i, x);
                }
            }
        }

        void  filteredAtLeaf(int l, int h) {
            for (int i = l; i < h; ++i) {
                if (pap.isSelected(i)) {
                    long x = pap.lget(i);
                    ++size;
                    sum += x;
                    updateMin(i, x);
                    updateMax(i, x);
                }
            }
        }

        public String toString() {
            return
                "size: " + size +
                " min: " + min + " (index " + indexOfMin +
                ") max: " + max + " (index " + indexOfMax +
                ") sum: " + sum;
        }
    }

    // count

    static final class FJCountSelected extends FJBase {
        int count;
        FJCountSelected(AbstractParallelAnyArray pap, int lo, int hi,
                        FJBase next) {
            super(pap, lo, hi, next);
        }
        FJBase newSubtask(int l, int h, FJBase r) {
            return new FJCountSelected(pap, l, h, r);
        }
        void onReduce(FJBase right) {
            count += ((FJCountSelected)right).count;
        }
        void atLeaf(int l, int h) {
            int n = 0;
            for (int i = l; i < h; ++i) {
                if (pap.isSelected(i))
                    ++n;
            }
            count = n;
        }
    }

    /**
     * Base for cancellable search tasks. Same idea as FJBase
     * but cancels tasks when result nonnegative.
     */
    static abstract class FJSearchBase extends RecursiveAction {
        final AbstractParallelAnyArray pap;
        final int lo;
        final int hi;
        final FJSearchBase next;
        final AtomicInteger result;

        FJSearchBase(AbstractParallelAnyArray pap, int lo, int hi,
                     FJSearchBase next,
                     AtomicInteger result) {
            this.pap = pap;
            this.lo = lo;
            this.hi = hi;
            this.next = next;
            this.result = result;
        }

        public void compute() {
            if (result.get() >= 0)
                return;
            FJSearchBase r = null;
            int l = lo;
            int h = hi;
            int g = pap.getThreshold();
            while (h - l > g) {
                int rh = h;
                h = (l + h) >>> 1;
                (r = newSubtask(h, rh, r)).fork();
            }
            atLeaf(l, h);
            boolean stopping = false;
            while (r != null) {
                stopping |= result.get() >= 0;
                if (r.tryUnfork()) {
                    if (!stopping)
                        r.atLeaf(r.lo, r.hi);
                }
                else if (stopping)
                    r.cancel(false);
                else
                    r.join();
                r = r.next;
            }
        }
        abstract FJSearchBase newSubtask(int l, int h, FJSearchBase r);
        abstract void atLeaf(int l, int h);
    }

    // select any

    static final class FJSelectAny extends FJSearchBase {
        FJSelectAny(AbstractParallelAnyArray pap, int lo, int hi,
                    FJSearchBase next, AtomicInteger result) {
            super(pap, lo, hi, next, result);
        }
        FJSearchBase newSubtask(int l, int h, FJSearchBase r) {
            return new FJSelectAny(pap, l, h, r, result);
        }
        void atLeaf(int l, int h) {
            for (int i = l; i < h; ++i) {
                if (pap.isSelected(i)) {
                    result.compareAndSet(-1, i);
                    break;
                }
                else if (result.get() >= 0)
                    break;
            }
        }
    }

    // index of

    static final class FJOIndexOf extends FJSearchBase {
        final Object target;
        FJOIndexOf(AbstractParallelAnyArray pap, int lo, int hi,
                   FJSearchBase next, AtomicInteger result, Object target) {
            super(pap, lo, hi, next, result);
            this.target = target;
        }
        FJSearchBase newSubtask(int l, int h, FJSearchBase r) {
            return new FJOIndexOf(pap, l, h, r, result, target);
        }
        void atLeaf(int l, int h) {
            final Object[] array = pap.ogetArray();
            if (array == null) return;
            for (int i = l; i < h; ++i) {
                if (target.equals(array[i])) {
                    result.compareAndSet(-1, i);
                    break;
                }
                else if (result.get() >= 0)
                    break;
            }
        }
    }

    static final class FJDIndexOf extends FJSearchBase {
        final double target;
        FJDIndexOf(AbstractParallelAnyArray pap, int lo, int hi,
                   FJSearchBase next, AtomicInteger result, double target) {
            super(pap, lo, hi, next, result);
            this.target = target;
        }
        FJSearchBase newSubtask(int l, int h, FJSearchBase r) {
            return new FJDIndexOf(pap, l, h, r, result, target);
        }
        void atLeaf(int l, int h) {
            final double[] array = pap.dgetArray();
            if (array == null) return;
            for (int i = l; i < h; ++i) {
                if (target == (array[i])) {
                    result.compareAndSet(-1, i);
                    break;
                }
                else if (result.get() >= 0)
                    break;
            }
        }
    }

    static final class FJLIndexOf extends FJSearchBase {
        final long target;
        FJLIndexOf(AbstractParallelAnyArray pap, int lo, int hi,
                   FJSearchBase next, AtomicInteger result, long target) {
            super(pap, lo, hi, next, result);
            this.target = target;
        }
        FJSearchBase newSubtask(int l, int h, FJSearchBase r) {
            return new FJLIndexOf(pap, l, h, r, result, target);
        }
        void atLeaf(int l, int h) {
            final long[] array = pap.lgetArray();
            if (array == null) return;
            for (int i = l; i < h; ++i) {
                if (target == (array[i])) {
                    result.compareAndSet(-1, i);
                    break;
                }
                else if (result.get() >= 0)
                    break;
            }
        }
    }

    // select all

    /**
     * SelectAll proceeds in two passes. In the first phase, indices
     * of matching elements are recorded in indices array.  In second
     * pass, once the size of results is known and result array is
     * constructed in driver, the matching elements are placed into
     * corresponding result positions.
     */
    static final class FJSelectAll extends RecursiveAction {
        final FJSelectAllDriver driver;
        FJSelectAll left, right;
        final int lo;
        final int hi;
        int count;  // number of matching elements
        int offset;
        boolean isInternal; // true if this is a non-leaf node
        final int threshold;

        FJSelectAll(FJSelectAllDriver driver, int lo, int hi) {
            this.driver = driver;
            this.lo = lo;
            this.hi = hi;
            this.threshold = driver.pap.getThreshold();
        }

        public void compute() {
            int l = lo;
            int h = hi;
            FJSelectAllDriver d = driver;
            if (d.phase == 0) {
                AbstractParallelAnyArray p = d.pap;
                if (isInternal = (h - l > threshold))
                    internalPhase0();
                else
                    count = p.leafIndexSelected(l, h, true, d.indices);
            }
            else if (count != 0) {
                if (isInternal)
                    internalPhase1();
                else
                    d.leafPhase1(l, l+count, offset);
            }
        }

        void internalPhase0() {
            int mid = (lo + hi) >>> 1;
            FJSelectAll l = new FJSelectAll(driver, lo, mid);
            FJSelectAll r = new FJSelectAll(driver, mid, hi);
            r.fork();
            l.compute();
            if (r.tryUnfork()) r.compute(); else r.join();
            int ln = l.count;
            if (ln != 0)
                left = l;
            int rn = r.count;
            if (rn != 0)
                right = r;
            count = ln + rn;
        }

        void internalPhase1() {
            int k = offset;
            if (left != null) {
                int ln = left.count;
                left.offset = k;
                left.reinitialize();
                if (right != null) {
                    right.offset = k + ln;
                    right.reinitialize();
                    right.fork();
                    left.compute();
                    if (right.tryUnfork()) right.compute(); else right.join();
                }
                else
                    left.compute();
            }
            else if (right != null) {
                right.offset = k;
                right.compute();
            }
        }
    }

    static abstract class FJSelectAllDriver extends RecursiveAction {
        final int[] indices;
        final AbstractParallelAnyArray pap;
        final int initialOffset;
        int phase;
        int resultSize;
        FJSelectAllDriver(AbstractParallelAnyArray pap, int initialOffset) {
            this.pap = pap;
            this.initialOffset = initialOffset;
            int n = pap.fence - pap.origin;
            indices = new int[n];
        }
        public final void compute() {
            FJSelectAll r = new FJSelectAll(this, pap.origin, pap.fence);
            r.offset = initialOffset;
            r.compute();
            createResults(resultSize = r.count);
            phase = 1;
            r.compute();
        }
        abstract void createResults(int size);
        abstract void leafPhase1(int loIdx, int hiIdx, int offset);
    }

    static final class FJOSelectAllDriver extends FJSelectAllDriver {
        final Class elementType;
        Object[] results;
        FJOSelectAllDriver(AbstractParallelAnyArray pap, Class elementType) {
            super(pap, 0);
            this.elementType = elementType;
        }
        void createResults(int size) {
            results = (Object[])Array.newInstance(elementType, size);
        }
        void leafPhase1(int loIdx, int hiIdx, int offset) {
            pap.leafTransferByIndex(indices, loIdx, hiIdx, results, offset);
        }
    }

    static final class FJDSelectAllDriver extends FJSelectAllDriver {
        double[] results;
        FJDSelectAllDriver(AbstractParallelAnyArray pap) {
            super(pap, 0);
        }
        void createResults(int size) {
            results = new double[size];
        }
        void leafPhase1(int loIdx, int hiIdx, int offset) {
            pap.leafTransferByIndex(indices, loIdx, hiIdx, results, offset);
        }
    }

    static final class FJLSelectAllDriver extends FJSelectAllDriver {
        long[] results;
        FJLSelectAllDriver(AbstractParallelAnyArray pap) {
            super(pap, 0);
        }
        void createResults(int size) {
            results = new long[size];
        }
        void leafPhase1(int loIdx, int hiIdx, int offset) {
            pap.leafTransferByIndex(indices, loIdx, hiIdx, results, offset);
        }
    }

    static final class FJOAppendAllDriver extends FJSelectAllDriver {
        Object[] results;
        FJOAppendAllDriver(AbstractParallelAnyArray pap, int initialOffset,
                           Object[] results) {
            super(pap, 0);
            this.results = results;
        }
        void createResults(int size) {
            int newSize = initialOffset + size;
            int oldLength = results.length;
            if (newSize > oldLength) {
                Class elementType = results.getClass().getComponentType();
                Object[] r = (Object[])Array.newInstance(elementType, newSize);
                System.arraycopy(results, 0, r, 0, oldLength);
                results = r;
            }
        }
        void leafPhase1(int loIdx, int hiIdx, int offset) {
            pap.leafTransferByIndex(indices, loIdx, hiIdx, results, offset);
        }
    }

    static final class FJDAppendAllDriver extends FJSelectAllDriver {
        double[] results;
        FJDAppendAllDriver(AbstractParallelAnyArray pap, int initialOffset,
                           double[] results) {
            super(pap, initialOffset);
            this.results = results;
        }
        void createResults(int size) {
            int newSize = initialOffset + size;
            int oldLength = results.length;
            if (newSize > oldLength) {
                double[] r = new double[newSize];
                System.arraycopy(results, 0, r, 0, oldLength);
                results = r;
            }
        }
        void leafPhase1(int loIdx, int hiIdx, int offset) {
            pap.leafTransferByIndex(indices, loIdx, hiIdx, results, offset);
        }
    }

    static final class FJLAppendAllDriver extends FJSelectAllDriver {
        long[] results;
        FJLAppendAllDriver(AbstractParallelAnyArray pap, int initialOffset,
                           long[] results) {
            super(pap, initialOffset);
            this.results = results;
        }
        void createResults(int size) {
            int newSize = initialOffset + size;
            int oldLength = results.length;
            if (newSize > oldLength) {
                long[] r = new long[newSize];
                System.arraycopy(results, 0, r, 0, oldLength);
                results = r;
            }
        }
        void leafPhase1(int loIdx, int hiIdx, int offset) {
            pap.leafTransferByIndex(indices, loIdx, hiIdx, results, offset);
        }
    }


    /**
     * Root node for FJRemoveAll. Spawns subtasks and shifts elements
     * as indices become available, bypassing index array creation
     * when offsets are known. This differs from SelectAll mainly in
     * that data movement is all done by the driver rather than in a
     * second parallel pass.
     */
    static final class FJRemoveAllDriver extends RecursiveAction {
        final AbstractParallelAnyArray pap;
        final int lo;
        final int hi;
        final int[] indices;
        int offset;
        final int threshold;
        FJRemoveAllDriver(AbstractParallelAnyArray pap, int lo, int hi) {
            this.pap = pap;
            this.lo = lo;
            this.hi = hi;
            this.indices = new int[hi - lo];
            this.threshold = pap.getThreshold();
        }

        public void compute() {
            FJRemoveAll r = null;
            int l = lo;
            int h = hi;
            int g = threshold;
            while (h - l > g) {
                int rh = h;
                h = (l + h) >>> 1;
                (r = new FJRemoveAll(pap, h, rh, r, indices)).fork();
            }
            int k = pap.leafMoveSelected(l, h, l, false);
            while (r != null) {
                if (r.tryUnfork())
                    k = pap.leafMoveSelected(r.lo, r.hi, k, false);
                else {
                    r.join();
                    int n = r.count;
                    if (n != 0)
                        pap.leafMoveByIndex(indices, r.lo, r.lo+n, k);
                    k += n;
                    FJRemoveAll rr = r.right;
                    if (rr != null)
                        k = inorderMove(rr, k);
                }
                r = r.next;
            }
            offset = k;
        }

        /**
         * Inorder traversal to move indexed elements across reachable
         * nodes.  This guarantees that element shifts don't overwrite
         * those still being used by active subtasks.
         */
        static int inorderMove(FJRemoveAll t, int index) {
            while (t != null) {
                int n = t.count;
                if (n != 0)
                    t.pap.leafMoveByIndex(t.indices, t.lo, t.lo+n, index);
                index += n;
                FJRemoveAll p = t.next;
                if (p != null)
                    index = inorderMove(p, index);
                t = t.right;
            }
            return index;
        }
    }

    /**
     * Basic FJ task for non-root FJRemoveAll nodes. Differs from
     * FJBase because it requires maintaining explicit right pointers so
     * FJRemoveAllDriver can traverse them
     */
    static final class FJRemoveAll extends RecursiveAction {
        final AbstractParallelAnyArray pap;
        final int lo;
        final int hi;
        final FJRemoveAll next;
        final int[] indices;
        int count;
        FJRemoveAll right;
        final int threshold;
        FJRemoveAll(AbstractParallelAnyArray pap, int lo, int hi,
                    FJRemoveAll next, int[] indices) {
            this.pap = pap;
            this.lo = lo;
            this.hi = hi;
            this.next = next;
            this.indices = indices;
            this.threshold = pap.getThreshold();
        }

        public void compute() {
            FJRemoveAll r = null;
            int l = lo;
            int h = hi;
            int g = threshold;
            while (h - l > g) {
                int rh = h;
                h = (l + h) >>> 1;
                (r = new FJRemoveAll(pap, h, rh, r, indices)).fork();
            }
            right = r;
            count = pap.leafIndexSelected(l, h, false, indices);
            while (r != null) {
                if (r.tryUnfork())
                    r.count = pap.leafIndexSelected
                        (r.lo, r.hi, false, indices);
                else
                    r.join();
                r = r.next;
            }
        }
    }

    // unique elements

    static final class FJOUniquifier extends FJBase {
        final UniquifierTable table;
        int count;
        FJOUniquifier(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
                     UniquifierTable table) {
            super(pap, lo, hi, next);
            this.table = table;
        }
        FJBase newSubtask(int l, int h, FJBase r) {
            return new FJOUniquifier(pap, l, h, r, table);
        }
        void atLeaf(int l, int h) {
            count = table.addObjects(l, h);
        }
        void onReduce(FJBase right) {
            count += ((FJOUniquifier)right).count;
        }
    }

    static final class FJDUniquifier extends FJBase {
        final UniquifierTable table;
        int count;
        FJDUniquifier(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
                     UniquifierTable table) {
            super(pap, lo, hi, next);
            this.table = table;
        }
        FJBase newSubtask(int l, int h, FJBase r) {
            return new FJDUniquifier(pap, l, h, r, table);
        }
        void atLeaf(int l, int h) {
            count = table.addDoubles(l, h);
        }
        void onReduce(FJBase right) {
            count += ((FJDUniquifier)right).count;
        }
    }

    static final class FJLUniquifier extends FJBase {
        final UniquifierTable table;
        int count;
        FJLUniquifier(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
                      UniquifierTable table) {
            super(pap, lo, hi, next);
            this.table = table;
        }
        FJBase newSubtask(int l, int h, FJBase r) {
            return new FJLUniquifier(pap, l, h, r, table);
        }
        void atLeaf(int l, int h) {
            count = table.addLongs(l, h);
        }
        void onReduce(FJBase right) {
            count += ((FJLUniquifier)right).count;
        }
    }

    /**
     * Base class of fixed-size hash tables for
     * uniquification. Opportunistically subclasses
     * AtomicLongArray. The high word of each slot is the cached
     * massaged hash of an element, and the low word contains its
     * index, plus one, to ensure that a zero tab entry means
     * empty. The mechanics for this are just folded into the
     * main addElements method.
     * Each leaf step places source array elements into table,
     * Even though this table undergoes a lot of contention when
     * elements are concurrently inserted by parallel threads, it is
     * generally faster to do this than to have separate tables and
     * then merge them.
     */
    static final class UniquifierTable extends AtomicLongArray {
        final AbstractParallelAnyArray pap;
        final boolean byIdentity;
        UniquifierTable(int size, AbstractParallelAnyArray pap,
                        boolean byIdentity) {
            super(tableSizeFor(size));
            this.pap = pap;
            this.byIdentity = byIdentity;
        }

        /** Returns a good size for table */
        static int tableSizeFor(int n) {
            int padded = n + (n >>> 1) + 1;
            if (padded < n) // int overflow
                throw new OutOfMemoryError();
            int s = 8;
            while (s < padded) s <<= 1;
            return s;
        }

        // Same hashcode conditioning as HashMap
        static int hash(int h) {
            h ^= (h >>> 20) ^ (h >>> 12);
            return h ^ (h >>> 7) ^ (h >>> 4);
        }

        int addObjects(int lo, int hi) {
            boolean filtered = pap.hasFilter();
            Object[] src = pap.ogetArray();
            final int mask = length() - 1;
            int count = 0;
            for (int k = lo; k < hi; ++k) {
                Object x;
                if ((filtered && !pap.isSelected(k)) ||
                    (x = src[k]) == null)
                    continue;
                int hc = byIdentity ? System.identityHashCode(x) : x.hashCode();
                int hash = hash(hc);
                long entry = (((long)hash) << 32) + (k + 1);
                int idx = hash & mask;
                for (;;) {
                    long d = get(idx);
                    if (d != 0) {
                        if ((int)(d >>> 32) == hash) {
                            Object y = src[(int)((d-1) & 0x7fffffffL)];
                            if (x == y || (!byIdentity && x.equals(y)))
                                break;
                        }
                        idx = (idx + 1) & mask;
                    }
                    else if (compareAndSet(idx, 0, entry)) {
                        ++count;
                        break;
                    }
                }
            }
            return count;
        }

        int addDoubles(int lo, int hi) {
            boolean filtered = pap.hasFilter();
            double[] src = pap.dgetArray();
            final int mask = length() - 1;
            int count = 0;
            for (int k = lo; k < hi; ++k) {
                if (filtered && !pap.isSelected(k))
                    continue;
                double x = src[k];
                long bits = Double.doubleToLongBits(x);
                int hash = hash((int)(bits ^ (bits >>> 32)));
                long entry = (((long)hash) << 32) + (k + 1);
                int idx = hash & mask;
                for (;;) {
                    long d = get(idx);
                    if (d != 0) {
                        if ((int)(d >>> 32) == hash &&
                            x == src[(int)((d - 1) & 0x7fffffffL)])
                            break;
                        idx = (idx + 1) & mask;
                    }
                    else if (compareAndSet(idx, 0, entry)) {
                        ++count;
                        break;
                    }
                }
            }
            return count;
        }

        int addLongs(int lo, int hi) {
            boolean filtered = pap.hasFilter();
            long[] src = pap.lgetArray();
            final int mask = length() - 1;
            int count = 0;
            for (int k = lo; k < hi; ++k) {
                if (filtered && !pap.isSelected(k))
                    continue;
                long x = src[k];
                int hash = hash((int)(x ^ (x >>> 32)));
                long entry = (((long)hash) << 32) + (k + 1);
                int idx = hash & mask;
                for (;;) {
                    long d = get(idx);
                    if (d != 0) {
                        if ((int)(d >>> 32) == hash &&
                            x == src[(int)((d - 1) & 0x7fffffffL)])
                            break;
                        idx = (idx + 1) & mask;
                    }
                    else if (compareAndSet(idx, 0, entry)) {
                        ++count;
                        break;
                    }
                }
            }
            return count;
        }

        /**
         * Return new array holding all elements.
         */
        Object[] uniqueObjects(int size) {
            Object[] src = pap.ogetArray();
            Class sclass = src.getClass().getComponentType();
            Object[] res = (Object[])Array.newInstance(sclass, size);
            int k = 0;
            int n = length();
            for (int i = 0; i < n && k < size; ++i) {
                long d = get(i);
                if (d != 0)
                    res[k++] = src[((int)((d - 1) & 0x7fffffffL))];
            }
            return res;
        }

        double[] uniqueDoubles(int size) {
            double[] src = pap.dgetArray();
            double[] res = new double[size];
            int k = 0;
            int n = length();
            for (int i = 0; i < n && k < size; ++i) {
                long d = get(i);
                if (d != 0)
                    res[k++] = src[((int)((d - 1) & 0x7fffffffL))];
            }
            return res;
        }

        long[] uniqueLongs(int size) {
            long[] src = pap.lgetArray();
            long[] res = new long[size];
            int k = 0;
            int n = length();
            for (int i = 0; i < n && k < size; ++i) {
                long d = get(i);
                if (d != 0)
                    res[k++] = src[((int)((d - 1) & 0x7fffffffL))];
            }
            return res;
        }
    }

    /**
     * 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
     *         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.
     *
     * It is sad but true that sort and merge performance are
     * sensitive enough to inner comparison overhead to warrant
     * creating 6 versions (not just 3) -- one each for natural
     * comparisons vs supplied comparators.
     */
    static final class FJOSorter extends RecursiveAction {
        final Comparator cmp;
        final Object[] a;     // array to be sorted.
        final Object[] 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
        FJOSorter(Comparator cmp,
                  Object[] a, Object[] w, int origin, int n, int gran) {
            this.cmp = cmp;
            this.a = a; this.w = w; this.origin = origin; this.n = n;
            this.gran = gran;
        }

        public void compute() {
            int l = origin;
            int g = gran;
            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 FJOSorter(cmp, a, w, l,   q,   g),
                     new FJOSorter(cmp, a, w, l+q, h-q, g),
                     new FJOMerger(cmp, a, w, l,   q,
                                   l+q, h-q, l, g, null));
                FJSubSorter rs = new FJSubSorter
                    (new FJOSorter(cmp, a, w, l+h, q,   g),
                     new FJOSorter(cmp, a, w, l+u, n-u, g),
                     new FJOMerger(cmp, 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 FJOMerger(cmp, w, a, l, h,
                              l+h, n-h, l, g, null).compute();
            }
            else
                Arrays.sort(a, l, l+n, cmp);
        }
    }

    static final class FJOCSorter extends RecursiveAction {
        final Comparable[] a; final Comparable[] w;
        final int origin; final int n; final int gran;
        FJOCSorter(Comparable[] a, Comparable[] 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() {
            int l = origin;
            int g = gran;
            if (n > g) {
                int h = n >>> 1;
                int q = n >>> 2;
                int u = h + q;
                FJSubSorter ls = new FJSubSorter
                    (new FJOCSorter(a, w, l,   q,   g),
                     new FJOCSorter(a, w, l+q, h-q, g),
                     new FJOCMerger(a, w, l,   q,
                                   l+q, h-q, l, g, null));
                FJSubSorter rs = new FJSubSorter
                    (new FJOCSorter(a, w, l+h, q,   g),
                     new FJOCSorter(a, w, l+u, n-u, g),
                     new FJOCMerger(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 FJOCMerger(w, a, l, h,
                               l+h, n-h, l, g, null).compute();
            }
            else
                Arrays.sort(a, l, l+n);
        }
    }

    static final class FJDSorter extends RecursiveAction {
        final DoubleComparator cmp; final double[] a; final double[] w;
        final int origin; final int n; final int gran;
        FJDSorter(DoubleComparator cmp,
                  double[] a, double[] w, int origin, int n, int gran) {
            this.cmp = cmp;
            this.a = a; this.w = w; this.origin = origin; this.n = n;
            this.gran = gran;
        }
        public void compute() {
            int l = origin;
            int g = gran;
            if (n > g) {
                int h = n >>> 1;
                int q = n >>> 2;
                int u = h + q;
                FJSubSorter ls = new FJSubSorter
                    (new FJDSorter(cmp, a, w, l,   q,   g),
                     new FJDSorter(cmp, a, w, l+q, h-q, g),
                     new FJDMerger(cmp, a, w, l,   q,
                                   l+q, h-q, l, g, null));
                FJSubSorter rs = new FJSubSorter
                    (new FJDSorter(cmp, a, w, l+h, q,   g),
                     new FJDSorter(cmp, a, w, l+u, n-u, g),
                     new FJDMerger(cmp, 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 FJDMerger(cmp, w, a, l, h,
                              l+h, n-h, l, g, null).compute();
            }
            else
                dquickSort(a, cmp, l, l+n-1);
        }
    }

    static final class FJDCSorter extends RecursiveAction {
        final double[] a; final double[] w;
        final int origin; final int n; final int gran;
        FJDCSorter(double[] a, double[] 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() {
            int l = origin;
            int g = gran;
            if (n > g) {
                int h = n >>> 1;
                int q = n >>> 2;
                int u = h + q;
                FJSubSorter ls = new FJSubSorter
                    (new FJDCSorter(a, w, l,   q,   g),
                     new FJDCSorter(a, w, l+q, h-q, g),
                     new FJDCMerger(a, w, l,   q,
                                    l+q, h-q, l, g, null));
                FJSubSorter rs = new FJSubSorter
                    (new FJDCSorter(a, w, l+h, q,   g),
                     new FJDCSorter(a, w, l+u, n-u, g),
                     new FJDCMerger(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 FJDCMerger(w, a, l, h,
                               l+h, n-h, l, g, null).compute();
            }
            else
                Arrays.sort(a, l, l+n);
        }
    }

    static final class FJLSorter extends RecursiveAction {
        final LongComparator cmp; final long[] a; final long[] w;
        final int origin; final int n; final int gran;
        FJLSorter(LongComparator cmp,
                  long[] a, long[] w, int origin, int n, int gran) {
            this.cmp = cmp;
            this.a = a; this.w = w; this.origin = origin; this.n = n;
            this.gran = gran;
        }

        public void compute() {
            int l = origin;
            int g = gran;
            if (n > g) {
                int h = n >>> 1;
                int q = n >>> 2;
                int u = h + q;
                FJSubSorter ls = new FJSubSorter
                    (new FJLSorter(cmp, a, w, l,   q,   g),
                     new FJLSorter(cmp, a, w, l+q, h-q, g),
                     new FJLMerger(cmp, a, w, l,   q,
                                   l+q, h-q, l, g, null));
                FJSubSorter rs = new FJSubSorter
                    (new FJLSorter(cmp, a, w, l+h, q,   g),
                     new FJLSorter(cmp, a, w, l+u, n-u, g),
                     new FJLMerger(cmp, 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 FJLMerger(cmp, w, a, l, h,
                              l+h, n-h, l, g, null).compute();
            }
            else
                lquickSort(a, cmp, l, l+n-1);
        }
    }

    static final class FJLCSorter extends RecursiveAction {
        final long[] a; final long[] w;
        final int origin; final int n; final int gran;
        FJLCSorter(long[] a, long[] 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() {
            int l = origin;
            int g = gran;
            if (n > g) {
                int h = n >>> 1;
                int q = n >>> 2;
                int u = h + q;
                FJSubSorter ls = new FJSubSorter
                    (new FJLCSorter(a, w, l,   q,   g),
                     new FJLCSorter(a, w, l+q, h-q, g),
                     new FJLCMerger(a, w, l,   q,
                                    l+q, h-q, l, g, null));

                FJSubSorter rs = new FJSubSorter
                    (new FJLCSorter(a, w, l+h, q,   g),
                     new FJLCSorter(a, w, l+u, n-u, g),
                     new FJLCMerger(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 FJLCMerger(w, a, l, h,
                               l+h, n-h, l, g, null).compute();
            }
            else
                Arrays.sort(a, l, l+n);
        }
    }

    /** Utility class to sort half a partitioned array */
    static final class FJSubSorter extends RecursiveAction {
        final RecursiveAction left;
        final RecursiveAction right;
        final RecursiveAction merger;
        FJSubSorter(RecursiveAction left, RecursiveAction right,
                    RecursiveAction merger) {
            this.left = left; this.right = right; this.merger = merger;
        }
        public void compute() {
            right.fork();
            left.invoke();
            right.join();
            merger.invoke();
        }
    }

    /**
     * Perform merging for FJSorter. 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
     * six versions.
     */
    static final class FJOMerger extends RecursiveAction {
        final Comparator cmp;
        final Object[] a;      // partitioned  array.
        final Object[] w;      // Output array.
        final int lo;          // relative origin of left side of a
        final int ln;          // number of elements on left of a
        final int ro;          // relative origin of right side of a
        final int rn;          // number of elements on right of a
        final int wo;          // origin for output
        final int gran;
        final FJOMerger next;

        FJOMerger(Comparator cmp, Object[] a, Object[] w,
                  int lo, int ln, int ro, int rn, int wo,
                  int gran, FJOMerger next) {
            this.cmp = cmp;
            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() {
            // spawn right subtasks
            FJOMerger rights = null;
            int nleft = ln;
            int nright = rn;
            while (nleft > gran) {
                int lh = nleft >>> 1;
                int splitIndex = lo + lh;
                Object split = a[splitIndex];
                // binary search r for split
                int rl = 0;
                int rh = nright;
                while (rl < rh) {
                    int mid = (rl + rh) >>> 1;
                    if (cmp.compare(split, a[ro + mid]) <= 0)
                        rh = mid;
                    else
                        rl = mid + 1;
                }
                (rights = new FJOMerger
                 (cmp, a, w, splitIndex, nleft-lh, ro+rh,
                  nright-rh, wo+lh+rh, gran, rights)).fork();
                nleft = lh;
                nright = rh;
            }

            // sequentially merge
            int l = lo;
            int lFence = lo + nleft;
            int r = ro;
            int rFence = ro + nright;
            int k = wo;
            while (l < lFence && r < rFence) {
                Object al = a[l];
                Object ar = a[r];
                Object t;
                if (cmp.compare(al, ar) <= 0) {++l; t=al;} else {++r; t=ar;}
                w[k++] = t;
            }
            while (l < lFence)
                w[k++] = a[l++];
            while (r < rFence)
                w[k++] = a[r++];

            // join subtasks
            while (rights != null) {
                if (rights.tryUnfork())
                    rights.compute();
                else
                    rights.join();
                rights = rights.next;
            }
        }
    }

    static final class FJOCMerger extends RecursiveAction {
        final Comparable[] a; final Comparable[] w;
        final int lo; final int ln; final int ro;  final int rn; final int wo;
        final int gran;
        final FJOCMerger next;
        FJOCMerger(Comparable[] a, Comparable[] w, int lo,
                   int ln, int ro, int rn, int wo,
                   int gran, FJOCMerger 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() {
            FJOCMerger rights = null;
            int nleft = ln;
            int nright = rn;
            while (nleft > gran) {
                int lh = nleft >>> 1;
                int splitIndex = lo + lh;
                Comparable split = a[splitIndex];
                int rl = 0;
                int rh = nright;
                while (rl < rh) {
                    int mid = (rl + rh) >>> 1;
                    if (split.compareTo(a[ro + mid]) <= 0)
                        rh = mid;
                    else
                        rl = mid + 1;
                }
                (rights = new FJOCMerger
                 (a, w, splitIndex, nleft-lh, ro+rh,
                  nright-rh, wo+lh+rh, gran, rights)).fork();
                nleft = lh;
                nright = rh;
            }

            int l = lo;
            int lFence = lo + nleft;
            int r = ro;
            int rFence = ro + nright;
            int k = wo;
            while (l < lFence && r < rFence) {
                Comparable al = a[l];
                Comparable ar = a[r];
                Comparable t;
                if (al.compareTo(ar) <= 0) {++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;
            }
        }
    }

    static final class FJDMerger extends RecursiveAction {
        final DoubleComparator cmp; final double[] a; final double[] w;
        final int lo; final int ln; final int ro; final int rn; final int wo;
        final int gran;
        final FJDMerger next;
        FJDMerger(DoubleComparator cmp, double[] a, double[] w,
                  int lo, int ln, int ro, int rn, int wo,
                  int gran, FJDMerger next) {
            this.cmp = cmp;
            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() {
            FJDMerger rights = null;
            int nleft = ln;
            int nright = rn;
            while (nleft > gran) {
                int lh = nleft >>> 1;
                int splitIndex = lo + lh;
                double split = a[splitIndex];
                int rl = 0;
                int rh = nright;
                while (rl < rh) {
                    int mid = (rl + rh) >>> 1;
                    if (cmp.compare(split, a[ro + mid]) <= 0)
                        rh = mid;
                    else
                        rl = mid + 1;
                }
                (rights = new FJDMerger
                 (cmp, a, w, splitIndex, nleft-lh, ro+rh,
                  nright-rh, wo+lh+rh, gran, rights)).fork();
                nleft = lh;
                nright = rh;
            }

            int l = lo;
            int lFence = lo + nleft;
            int r = ro;
            int rFence = ro + nright;
            int k = wo;
            while (l < lFence && r < rFence) {
                double al = a[l];
                double ar = a[r];
                double t;
                if (cmp.compare(al, ar) <= 0) {++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;
            }
        }
    }

    static final class FJDCMerger extends RecursiveAction {
        final double[] a; final double[] w;
        final int lo; final int ln; final int ro; final int rn; final int wo;
        final int gran;
        final FJDCMerger next;
        FJDCMerger(double[] a, double[] w, int lo,
                   int ln, int ro, int rn, int wo,
                   int gran, FJDCMerger 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() {
            FJDCMerger rights = null;
            int nleft = ln;
            int nright = rn;
            while (nleft > gran) {
                int lh = nleft >>> 1;
                int splitIndex = lo + lh;
                double 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 FJDCMerger
                 (a, w, splitIndex, nleft-lh, ro+rh,
                  nright-rh, wo+lh+rh, gran, rights)).fork();
                nleft = lh;
                nright = rh;
            }

            int l = lo;
            int lFence = lo + nleft;
            int r = ro;
            int rFence = ro + nright;
            int k = wo;
            while (l < lFence && r < rFence) {
                double al = a[l];
                double ar = a[r];
                double 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;
            }
        }
    }

    static final class FJLMerger extends RecursiveAction {
        final LongComparator cmp; final long[] a; final long[] w;
        final int lo; final int ln; final int ro; final int rn; final int wo;
        final int gran;
        final FJLMerger next;
        FJLMerger(LongComparator cmp, long[] a, long[] w,
                  int lo, int ln, int ro, int rn, int wo,
                  int gran, FJLMerger next) {
            this.cmp = cmp;
            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() {
            FJLMerger rights = null;
            int nleft = ln;
            int nright = rn;
            while (nleft > gran) {
                int lh = nleft >>> 1;
                int splitIndex = lo + lh;
                long split = a[splitIndex];
                int rl = 0;
                int rh = nright;
                while (rl < rh) {
                    int mid = (rl + rh) >>> 1;
                    if (cmp.compare(split, a[ro + mid]) <= 0)
                        rh = mid;
                    else
                        rl = mid + 1;
                }
                (rights = new FJLMerger
                 (cmp, a, w, splitIndex, nleft-lh, ro+rh,
                  nright-rh, wo+lh+rh, gran, rights)).fork();
                nleft = lh;
                nright = rh;
            }

            int l = lo;
            int lFence = lo + nleft;
            int r = ro;
            int rFence = ro + nright;
            int k = wo;
            while (l < lFence && r < rFence) {
                long al = a[l];
                long ar = a[r];
                long t;
                if (cmp.compare(al, ar) <= 0) {++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;
            }
        }
    }

    static final class FJLCMerger extends RecursiveAction {
        final long[] a; final long[] w;
        final int lo; final int ln; final int ro; final int rn; final int wo;
        final int gran;
        final FJLCMerger next;
        FJLCMerger(long[] a, long[] w, int lo,
                   int ln, int ro, int rn, int wo,
                   int gran, FJLCMerger 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() {
            FJLCMerger rights = null;
            int nleft = ln;
            int nright = rn;
            while (nleft > gran) {
                int lh = nleft >>> 1;
                int splitIndex = lo + lh;
                long 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 FJLCMerger
                 (a, w, splitIndex, nleft-lh, ro+rh,
                  nright-rh, wo+lh+rh, gran, rights)).fork();
                nleft = lh;
                nright = rh;
            }

            int l = lo;
            int lFence = lo + nleft;
            int r = ro;
            int rFence = ro + nright;
            int k = wo;
            while (l < lFence && r < rFence) {
                long al = a[l];
                long ar = a[r];
                long 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;
            }
        }
    }

    /** Cutoff for when to use insertion-sort instead of quicksort */
    static final int INSERTION_SORT_THRESHOLD = 8;

    // versions of quicksort with comparators


    static void dquickSort(double[] a, DoubleComparator cmp, int lo, int hi) {
        for (;;) {
            if (hi - lo <= INSERTION_SORT_THRESHOLD) {
                for (int i = lo + 1; i <= hi; i++) {
                    double t = a[i];
                    int j = i - 1;
                    while (j >= lo && cmp.compare(t, a[j]) < 0) {
                        a[j+1] = a[j];
                        --j;
                    }
                    a[j+1] = t;
                }
                return;
            }

            int mid = (lo + hi) >>> 1;
            if (cmp.compare(a[lo], a[mid]) > 0) {
                double t = a[lo]; a[lo] = a[mid]; a[mid] = t;
            }
            if (cmp.compare(a[mid], a[hi]) > 0) {
                double t = a[mid]; a[mid] = a[hi]; a[hi] = t;
                if (cmp.compare(a[lo], a[mid]) > 0) {
                    double u = a[lo]; a[lo] = a[mid]; a[mid] = u;
                }
            }

            double pivot = a[mid];
            int left = lo+1;
            int right = hi-1;
            boolean sameLefts = true;
            for (;;) {
                while (cmp.compare(pivot, a[right]) < 0)
                    --right;
                int c;
                while (left < right &&
                       (c = cmp.compare(pivot, a[left])) >= 0) {
                    if (c != 0)
                        sameLefts = false;
                    ++left;
                }
                if (left < right) {
                    double t = a[left]; a[left] = a[right]; a[right] = t;
                    --right;
                }
                else break;
            }

            if (sameLefts && right == hi - 1)
                return;
            if (left - lo <= hi - right) {
                dquickSort(a, cmp, lo, left);
                lo = left + 1;
            }
            else {
                dquickSort(a, cmp, right, hi);
                hi = left;
            }
        }
    }

    static void lquickSort(long[] a, LongComparator cmp, int lo, int hi) {
        for (;;) {
            if (hi - lo <= INSERTION_SORT_THRESHOLD) {
                for (int i = lo + 1; i <= hi; i++) {
                    long t = a[i];
                    int j = i - 1;
                    while (j >= lo && cmp.compare(t, a[j]) < 0) {
                        a[j+1] = a[j];
                        --j;
                    }
                    a[j+1] = t;
                }
                return;
            }

            int mid = (lo + hi) >>> 1;
            if (cmp.compare(a[lo], a[mid]) > 0) {
                long t = a[lo]; a[lo] = a[mid]; a[mid] = t;
            }
            if (cmp.compare(a[mid], a[hi]) > 0) {
                long t = a[mid]; a[mid] = a[hi]; a[hi] = t;
                if (cmp.compare(a[lo], a[mid]) > 0) {
                    long u = a[lo]; a[lo] = a[mid]; a[mid] = u;
                }
            }

            long pivot = a[mid];
            int left = lo+1;
            int right = hi-1;
            boolean sameLefts = true;
            for (;;) {
                while (cmp.compare(pivot, a[right]) < 0)
                    --right;
                int c;
                while (left < right &&
                       (c = cmp.compare(pivot, a[left])) >= 0) {
                    if (c != 0)
                        sameLefts = false;
                    ++left;
                }
                if (left < right) {
                    long t = a[left]; a[left] = a[right]; a[right] = t;
                    --right;
                }
                else break;
            }

            if (sameLefts && right == hi - 1)
                return;
            if (left - lo <= hi - right) {
                lquickSort(a, cmp, lo, left);
                lo = left + 1;
            }
            else {
                lquickSort(a, cmp, right, hi);
                hi = left;
            }
        }
    }

    /**
     * Cumulative scan
     *
     * A basic version of scan is straightforward.
     *  Keep dividing by two to threshold segment size, and then:
     *   Pass 1: Create tree of partial sums for each segment
     *   Pass 2: For each segment, cumulate with offset of left sibling
     * See G. Blelloch's http://www.cs.cmu.edu/~scandal/alg/scan.html
     *
     * This version improves performance within FJ framework mainly by
     * allowing second pass of ready left-hand sides to proceed even
     * if some right-hand side first passes are still executing.  It
     * also combines first and second pass for leftmost segment, and
     * for cumulate (not precumulate) also skips first pass for
     * rightmost segment (whose result is not needed for second pass).
     *
     * To manage this, it relies on "phase" phase/state control field
     * maintaining bits CUMULATE, SUMMED, and FINISHED. CUMULATE is
     * main phase bit. When false, segments compute only their sum.
     * When true, they cumulate array elements. CUMULATE is set at
     * root at beginning of second pass and then propagated down. But
     * it may also be set earlier for subtrees with lo==origin (the
     * left spine of tree). SUMMED is a one bit join count. For leafs,
     * set when summed. For internal nodes, becomes true when one
     * child is summed.  When second child finishes summing, it then
     * moves up tree to trigger cumulate phase. FINISHED is also a one
     * bit join count. For leafs, it is set when cumulated. For
     * internal nodes, it becomes true when one child is cumulated.
     * When second child finishes cumulating, it then moves up tree,
     * executing complete() at the root.
     *
     * This class maintains only the basic control logic.  Subclasses
     * maintain the "in" and "out" fields, and *Ops classes perform
     * computations
     */
    static abstract class FJScan extends ForkJoinTask<Void> {
        static final short CUMULATE = (short)1;
        static final short SUMMED   = (short)2;
        static final short FINISHED = (short)4;

        final FJScan parent;
        final FJScanOp op;
        FJScan left, right;
        volatile int phase;  // phase/state
        final int lo;
        final int hi;

        static final AtomicIntegerFieldUpdater<FJScan> phaseUpdater =
            AtomicIntegerFieldUpdater.newUpdater(FJScan.class, "phase");

        FJScan(FJScan parent, FJScanOp op, int lo, int hi) {
            this.parent = parent;
            this.op = op;
            this.lo = lo;
            this.hi = hi;
        }

        public final Void getRawResult() { return null; }
        protected final void setRawResult(Void mustBeNull) { }

        /** Returns true if can CAS CUMULATE bit true */
        final boolean transitionToCumulate() {
            int c;
            while (((c = phase) & CUMULATE) == 0)
                if (phaseUpdater.compareAndSet(this, c, c | CUMULATE))
                    return true;
            return false;
        }

        public final boolean exec() {
            if (hi - lo > op.threshold) {
                if (left == null) { // first pass
                    int mid = (lo + hi) >>> 1;
                    left =  op.newSubtask(this, lo, mid);
                    right = op.newSubtask(this, mid, hi);
                }

                boolean cumulate = (phase & CUMULATE) != 0;
                if (cumulate)
                    op.pushDown(this, left, right);

                if (!cumulate || right.transitionToCumulate())
                    right.fork();
                if (!cumulate || left.transitionToCumulate())
                    left.exec();
            }
            else {
                int cb;
                for (;;) { // Establish action: sum, cumulate, or both
                    int b = phase;
                    if ((b & FINISHED) != 0) // already done
                        return false;
                    if ((b & CUMULATE) != 0)
                        cb = FINISHED;
                    else if (lo == op.origin) // combine leftmost
                        cb = (SUMMED|FINISHED);
                    else
                        cb = SUMMED;
                    if (phaseUpdater.compareAndSet(this, b, b|cb))
                        break;
                }

                if (cb == SUMMED)
                    op.sumLeaf(lo, hi, this);
                else if (cb == FINISHED)
                    op.cumulateLeaf(lo, hi, this);
                else if (cb == (SUMMED|FINISHED))
                    op.sumAndCumulateLeaf(lo, hi, this);

                // propagate up
                FJScan ch = this;
                FJScan par = parent;
                for (;;) {
                    if (par == null) {
                        if ((cb & FINISHED) != 0)
                            ch.complete(null);
                        break;
                    }
                    int pb = par.phase;
                    if ((pb & cb & FINISHED) != 0) { // both finished
                        ch = par;
                        par = par.parent;
                    }
                    else if ((pb & cb & SUMMED) != 0) { // both summed
                        op.pushUp(par, par.left, par.right);
                        int refork =
                            ((pb & CUMULATE) == 0 &&
                             par.lo == op.origin) ? CUMULATE : 0;
                        int nextPhase = pb|cb|refork;
                        if (pb == nextPhase ||
                            phaseUpdater.compareAndSet(par, pb, nextPhase)) {
                            if (refork != 0)
                                par.fork();
                            cb = SUMMED; // drop finished bit
                            ch = par;
                            par = par.parent;
                        }
                    }
                    else if (phaseUpdater.compareAndSet(par, pb, pb|cb))
                        break;
                }
            }
            return false;
        }

        // no-op versions of methods to get/set in/out, overridden as
        // appropriate in subclasses
        Object ogetIn() { return null; }
        Object ogetOut() { return null; }
        void rsetIn(Object x) { }
        void rsetOut(Object x) { }

        double dgetIn() { return 0; }
        double dgetOut() { return 0; }
        void dsetIn(double x) { }
        void dsetOut(double x) { }

        long lgetIn() { return 0; }
        long lgetOut() { return 0; }
        void lsetIn(long x) { }
        void lsetOut(long x) { }
    }

    // Subclasses adding in/out fields of the appropriate type
    static final class FJOScan extends FJScan {
        Object in;
        Object out;
        FJOScan(FJScan parent, FJScanOp op, int lo, int hi) {
            super(parent, op, lo, hi);
        }
        Object ogetIn() { return in; }
        Object ogetOut() { return out; }
        void rsetIn(Object x) { in = x; }
        void rsetOut(Object x) { out = x; }
    }

    static final class FJDScan extends FJScan {
        double in;
        double out;
        FJDScan(FJScan parent, FJScanOp op, int lo, int hi) {
            super(parent, op, lo, hi);
        }
        double dgetIn() { return in; }
        double dgetOut() { return out; }
        void dsetIn(double x) { in = x; }
        void dsetOut(double x) { out = x; }

    }

    static final class FJLScan extends FJScan {
        long in;
        long out;
        FJLScan(FJScan parent, FJScanOp op, int lo, int hi) {
            super(parent, op, lo, hi);
        }
        long lgetIn() { return in; }
        long lgetOut() { return out; }
        void lsetIn(long x) { in = x; }
        void lsetOut(long x) { out = x; }
    }

    /**
     * Computational operations for FJScan
     */
    static abstract class FJScanOp {
        final int threshold;
        final int origin;
        final int fence;
        FJScanOp(AbstractParallelAnyArray pap) {
            this.origin = pap.origin;
            this.fence = pap.fence;
            this.threshold = pap.computeThreshold();
        }
        abstract void pushDown(FJScan parent, FJScan left, FJScan right);
        abstract void pushUp(FJScan parent, FJScan left, FJScan right);
        abstract void sumLeaf(int lo, int hi, FJScan f);
        abstract void cumulateLeaf(int lo, int hi, FJScan f);
        abstract void sumAndCumulateLeaf(int lo, int hi, FJScan f);
        abstract FJScan newSubtask(FJScan parent, int lo, int hi);
    }

    static abstract class FJOScanOp extends FJScanOp {
        final Object[] array;
        final Reducer reducer;
        final Object base;
        FJOScanOp(AbstractParallelAnyArray.OPap pap,
                  Reducer reducer, Object base) {
            super(pap);
            this.array = pap.array;
            this.reducer = reducer;
            this.base = base;
        }
        final void pushDown(FJScan parent, FJScan left, FJScan right) {
            Object pin = parent.ogetIn();
            left.rsetIn(pin);
            right.rsetIn(reducer.op(pin, left.ogetOut()));
        }
        final void pushUp(FJScan parent, FJScan left, FJScan right) {
            parent.rsetOut(reducer.op(left.ogetOut(),
                                           right.ogetOut()));
        }
        final FJScan newSubtask(FJScan parent, int lo, int hi) {
            FJOScan f = new FJOScan(parent, this, lo, hi);
            f.in = base;
            f.out = base;
            return f;
        }
    }

    static final class FJOCumulateOp extends FJOScanOp {
        FJOCumulateOp(AbstractParallelAnyArray.OPap pap,
                      Reducer reducer, Object base) {
            super(pap, reducer, base);
        }
        void sumLeaf(int lo, int hi, FJScan f) {
            Object sum = base;
            if (hi != fence) {
                Object[] arr = array;
                for (int i = lo; i < hi; ++i)
                    sum = reducer.op(sum, arr[i]);
            }
            f.rsetOut(sum);
        }
        void cumulateLeaf(int lo, int hi, FJScan f) {
            Object[] arr = array;
            Object sum = f.ogetIn();
            for (int i = lo; i < hi; ++i)
                arr[i] = sum = reducer.op(sum, arr[i]);
        }
        void sumAndCumulateLeaf(int lo, int hi, FJScan f) {
            Object[] arr = array;
            Object sum = base;
            for (int i = lo; i < hi; ++i)
                arr[i] = sum = reducer.op(sum, arr[i]);
            f.rsetOut(sum);
        }
    }

    static final class FJOPrecumulateOp extends FJOScanOp {
        FJOPrecumulateOp(AbstractParallelAnyArray.OPap pap,
                         Reducer reducer, Object base) {
            super(pap, reducer, base);
        }
        void sumLeaf(int lo, int hi, FJScan f) {
            Object[] arr = array;
            Object sum = base;
            for (int i = lo; i < hi; ++i)
                sum = reducer.op(sum, arr[i]);
            f.rsetOut(sum);
        }
        void cumulateLeaf(int lo, int hi, FJScan f) {
            Object[] arr = array;
            Object sum = f.ogetIn();
            for (int i = lo; i < hi; ++i) {
                Object x = arr[i];
                arr[i] = sum;
                sum = reducer.op(sum, x);
            }
        }
        void sumAndCumulateLeaf(int lo, int hi, FJScan f) {
            Object[] arr = array;
            Object sum = base;
            for (int i = lo; i < hi; ++i) {
                Object x = arr[i];
                arr[i] = sum;
                sum = reducer.op(sum, x);
            }
            f.rsetOut(sum);
        }
    }

    static abstract class FJDScanOp extends FJScanOp {
        final double[] array;
        final DoubleReducer reducer;
        final double base;
        FJDScanOp(AbstractParallelAnyArray.DPap pap,
                  DoubleReducer reducer, double base) {
            super(pap);
            this.array = pap.array;
            this.reducer = reducer;
            this.base = base;
        }
        final void pushDown(FJScan parent, FJScan left, FJScan right) {
            double pin = parent.dgetIn();
            left.dsetIn(pin);
            right.dsetIn(reducer.op(pin, left.dgetOut()));
        }
        final void pushUp(FJScan parent, FJScan left, FJScan right) {
            parent.dsetOut(reducer.op(left.dgetOut(),
                                           right.dgetOut()));
        }
        final FJScan newSubtask(FJScan parent, int lo, int hi) {
            FJDScan f = new FJDScan(parent, this, lo, hi);
            f.in = base;
            f.out = base;
            return f;
        }
    }

    static final class FJDCumulateOp extends FJDScanOp {
        FJDCumulateOp(AbstractParallelAnyArray.DPap pap,
                      DoubleReducer reducer, double base) {
            super(pap, reducer, base);
        }
        void sumLeaf(int lo, int hi, FJScan f) {
            double sum = base;
            if (hi != fence) {
                double[] arr = array;
                for (int i = lo; i < hi; ++i)
                    sum = reducer.op(sum, arr[i]);
            }
            f.dsetOut(sum);
        }
        void cumulateLeaf(int lo, int hi, FJScan f) {
            double[] arr = array;
            double sum = f.dgetIn();
            for (int i = lo; i < hi; ++i)
                arr[i] = sum = reducer.op(sum, arr[i]);
        }
        void sumAndCumulateLeaf(int lo, int hi, FJScan f) {
            double[] arr = array;
            double sum = base;
            for (int i = lo; i < hi; ++i)
                arr[i] = sum = reducer.op(sum, arr[i]);
            f.dsetOut(sum);
        }
    }

    static final class FJDPrecumulateOp extends FJDScanOp {
        FJDPrecumulateOp(AbstractParallelAnyArray.DPap pap,
                         DoubleReducer reducer, double base) {
            super(pap, reducer, base);
        }
        void sumLeaf(int lo, int hi, FJScan f) {
            double[] arr = array;
            double sum = base;
            for (int i = lo; i < hi; ++i)
                sum = reducer.op(sum, arr[i]);
            f.dsetOut(sum);
        }
        void cumulateLeaf(int lo, int hi, FJScan f) {
            double[] arr = array;
            double sum = f.dgetIn();
            for (int i = lo; i < hi; ++i) {
                double x = arr[i];
                arr[i] = sum;
                sum = reducer.op(sum, x);
            }
        }
        void sumAndCumulateLeaf(int lo, int hi, FJScan f) {
            double[] arr = array;
            double sum = base;
            for (int i = lo; i < hi; ++i) {
                double x = arr[i];
                arr[i] = sum;
                sum = reducer.op(sum, x);
            }
            f.dsetOut(sum);
        }
    }

    static abstract class FJLScanOp extends FJScanOp {
        final long[] array;
        final LongReducer reducer;
        final long base;
        FJLScanOp(AbstractParallelAnyArray.LPap pap,
                  LongReducer reducer, long base) {
            super(pap);
            this.array = pap.array;
            this.reducer = reducer;
            this.base = base;
        }
        final void pushDown(FJScan parent, FJScan left, FJScan right) {
            long pin = parent.lgetIn();
            left.lsetIn(pin);
            right.lsetIn(reducer.op(pin, left.lgetOut()));
        }
        final void pushUp(FJScan parent, FJScan left, FJScan right) {
            parent.lsetOut(reducer.op(left.lgetOut(),
                                           right.lgetOut()));
        }
        final FJScan newSubtask(FJScan parent, int lo, int hi) {
            FJLScan f = new FJLScan(parent, this, lo, hi);
            f.in = base;
            f.out = base;
            return f;
        }
    }

    static final class FJLCumulateOp extends FJLScanOp {
        FJLCumulateOp(AbstractParallelAnyArray.LPap pap,
                      LongReducer reducer, long base) {
            super(pap, reducer, base);
        }
        void sumLeaf(int lo, int hi, FJScan f) {
            long sum = base;
            if (hi != fence) {
                long[] arr = array;
                for (int i = lo; i < hi; ++i)
                    sum = reducer.op(sum, arr[i]);
            }
            f.lsetOut(sum);
        }
        void cumulateLeaf(int lo, int hi, FJScan f) {
            long[] arr = array;
            long sum = f.lgetIn();
            for (int i = lo; i < hi; ++i)
                arr[i] = sum = reducer.op(sum, arr[i]);
        }
        void sumAndCumulateLeaf(int lo, int hi, FJScan f) {
            long[] arr = array;
            long sum = base;
            for (int i = lo; i < hi; ++i)
                arr[i] = sum = reducer.op(sum, arr[i]);
            f.lsetOut(sum);
        }
    }

    static final class FJLPrecumulateOp extends FJLScanOp {
        FJLPrecumulateOp(AbstractParallelAnyArray.LPap pap,
                         LongReducer reducer, long base) {
            super(pap, reducer, base);
        }
        void sumLeaf(int lo, int hi, FJScan f) {
            long[] arr = array;
            long sum = base;
            for (int i = lo; i < hi; ++i)
                sum = reducer.op(sum, arr[i]);
            f.lsetOut(sum);
        }
        void cumulateLeaf(int lo, int hi, FJScan f) {
            long[] arr = array;
            long sum = f.lgetIn();
            for (int i = lo; i < hi; ++i) {
                long x = arr[i];
                arr[i] = sum;
                sum = reducer.op(sum, x);
            }
        }
        void sumAndCumulateLeaf(int lo, int hi, FJScan f) {
            long[] arr = array;
            long sum = base;
            for (int i = lo; i < hi; ++i) {
                long x = arr[i];
                arr[i] = sum;
                sum = reducer.op(sum, x);
            }
            f.lsetOut(sum);
        }
    }

    // specialized versions for plus

    static abstract class FJDScanPlusOp extends FJScanOp {
        final double[] array;
        FJDScanPlusOp(AbstractParallelAnyArray.DPap pap) {
            super(pap);
            this.array = pap.array;
        }
        final void pushDown(FJScan parent, FJScan left, FJScan right) {
            double pin = parent.dgetIn();
            left.dsetIn(pin);
            right.dsetIn(pin + left.dgetOut());
        }
        final void pushUp(FJScan parent, FJScan left, FJScan right) {
            parent.dsetOut(left.dgetOut() + right.dgetOut());
        }
        final FJScan newSubtask(FJScan parent, int lo, int hi) {
            FJDScan f = new FJDScan(parent, this, lo, hi);
            f.in = 0.0;
            f.out = 0.0;
            return f;
        }
    }

    static final class FJDCumulatePlusOp extends FJDScanPlusOp {
        FJDCumulatePlusOp(AbstractParallelAnyArray.DPap pap) {
            super(pap);
        }
        void sumLeaf(int lo, int hi, FJScan f) {
            double sum = 0.0;
            if (hi != fence) {
                double[] arr = array;
                for (int i = lo; i < hi; ++i)
                    sum += arr[i];
            }
            f.dsetOut(sum);
        }
        void cumulateLeaf(int lo, int hi, FJScan f) {
            double[] arr = array;
            double sum = f.dgetIn();
            for (int i = lo; i < hi; ++i)
                arr[i] = sum += arr[i];
        }
        void sumAndCumulateLeaf(int lo, int hi, FJScan f) {
            double[] arr = array;
            double sum = 0.0;
            for (int i = lo; i < hi; ++i)
                arr[i] = sum += arr[i];
            f.dsetOut(sum);
        }
    }

    static final class FJDPrecumulatePlusOp extends FJDScanPlusOp {
        FJDPrecumulatePlusOp(AbstractParallelAnyArray.DPap pap) {
            super(pap);
        }
        void sumLeaf(int lo, int hi, FJScan f) {
            double[] arr = array;
            double sum = 0.0;
            for (int i = lo; i < hi; ++i)
                sum += arr[i];
            f.dsetOut(sum);
        }
        void cumulateLeaf(int lo, int hi, FJScan f) {
            double[] arr = array;
            double sum = f.dgetIn();
            for (int i = lo; i < hi; ++i) {
                double x = arr[i];
                arr[i] = sum;
                sum += x;
            }
        }
        void sumAndCumulateLeaf(int lo, int hi, FJScan f) {
            double[] arr = array;
            double sum = 0.0;
            for (int i = lo; i < hi; ++i) {
                double x = arr[i];
                arr[i] = sum;
                sum += x;
            }
            f.dsetOut(sum);
        }
    }

    static abstract class FJLScanPlusOp extends FJScanOp {
        final long[] array;
        FJLScanPlusOp(AbstractParallelAnyArray.LPap pap) {
            super(pap);
            this.array = pap.array;
        }
        final void pushDown(FJScan parent, FJScan left, FJScan right) {
            long pin = parent.lgetIn();
            left.lsetIn(pin);
            right.lsetIn(pin + left.lgetOut());
        }

        final void pushUp(FJScan parent, FJScan left, FJScan right) {
            parent.lsetOut(left.lgetOut() + right.lgetOut());
        }

        final FJScan newSubtask(FJScan parent, int lo, int hi) {
            FJLScan f = new FJLScan(parent, this, lo, hi);
            f.in = 0L;
            f.out = 0L;
            return f;
        }
    }

    static final class FJLCumulatePlusOp extends FJLScanPlusOp {
        FJLCumulatePlusOp(AbstractParallelAnyArray.LPap pap) {
            super(pap);
        }
        void sumLeaf(int lo, int hi, FJScan f) {
            long sum = 0L;
            if (hi != fence) {
                long[] arr = array;
                for (int i = lo; i < hi; ++i)
                    sum += arr[i];
            }
            f.lsetOut(sum);
        }
        void cumulateLeaf(int lo, int hi, FJScan f) {
            long[] arr = array;
            long sum = f.lgetIn();
            for (int i = lo; i < hi; ++i)
                arr[i] = sum += arr[i];
        }
        void sumAndCumulateLeaf(int lo, int hi, FJScan f) {
            long[] arr = array;
            long sum = 0L;
            for (int i = lo; i < hi; ++i)
                arr[i] = sum += arr[i];
            f.lsetOut(sum);
        }
    }

    static final class FJLPrecumulatePlusOp extends FJLScanPlusOp {
        FJLPrecumulatePlusOp(AbstractParallelAnyArray.LPap pap) {
            super(pap);
        }
        void sumLeaf(int lo, int hi, FJScan f) {
            long[] arr = array;
            long sum = 0L;
            for (int i = lo; i < hi; ++i)
                sum += arr[i];
            f.lsetOut(sum);
        }
        void cumulateLeaf(int lo, int hi, FJScan f) {
            long[] arr = array;
            long sum = f.lgetIn();
            for (int i = lo; i < hi; ++i) {
                long x = arr[i];
                arr[i] = sum;
                sum += x;
            }
        }
        void sumAndCumulateLeaf(int lo, int hi, FJScan f) {
            long[] arr = array;
            long sum = 0L;
            for (int i = lo; i < hi; ++i) {
                long x = arr[i];
                arr[i] = sum;
                sum += x;
            }
            f.lsetOut(sum);
        }
    }

}
Revision:	1.14
Committed:	Tue Mar 15 19:47:02 2011 UTC (13 years, 2 months ago) by jsr166
Branch:	MAIN
CVS Tags:	jdk7-compat, release-1_7_0
Changes since 1.13:	+1 -1 lines
Log Message:	Update Creative Commons license URL in legal notices