/* * 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; /** * An array of longs supporting parallel operations. This class * provides methods supporting the same operations as {@link * ParallelArray}, but specialized for scalar longs. It additionally * provides a few methods specific to numerical values. * *
Sample usages. * Here is a complete (although naive) prime filter program: *
* import java.math.BigInteger; * import jsr166y.*; * import static extra166y.Ops.*; * import static extra166y.ParallelLongArray.*; * * public class Sieve { * public static void main(String[] args) { * int n = Integer.parseInt(args[0]); * // create array of divisors * ParallelLongArray a = create(n-1, defaultExecutor()); * a.replaceWithMappedIndex(add2); * int i = 0; * long p = 2; * while (p * p < n) { // repeatedly filter * a = a.withFilter(notDivisibleBy(p)).all(); * p = a.get(++i); * } * System.out.printf("sieve(%d) = %s%n", n, a); * // check result * if (!a.withFilter(notProbablePrime).isEmpty()) * throw new Error(); * } * static IntToLong add2 = new IntToLong() { * public long op(int i) { return i + 2; } }; * static LongPredicate notDivisibleBy(final long p) { * return new LongPredicate() { * public boolean op(long n) { return n <= p || (n % p) != 0; } * }; } * static LongPredicate notProbablePrime = new LongPredicate() { * private static final int CERTAINTY = 8; * public boolean op(long n) { * return !BigInteger.valueOf(n).isProbablePrime(CERTAINTY); * } * }; * } **/ public class ParallelLongArray extends AbstractParallelAnyArray.LUPap { // Same internals as ParallelArray, but specialized for longs AsList listView; /** * Returns a common default executor for use in ParallelArrays. * This executor arranges enough parallelism to use most, but not * necessarily all, of the available processors on this system. * @return the executor */ public static ForkJoinPool defaultExecutor() { return PAS.defaultExecutor(); } /** * Constructor for use by subclasses to create a new ParallelLongArray * using the given executor, and initially using the supplied * array, with effective size bound by the given limit. This * constructor is designed to enable extensions via * subclassing. To create a ParallelLongArray, use {@link #create}, * {@link #createEmpty}, {@link #createUsingHandoff} or {@link * #createFromCopy}. * @param executor the executor * @param array the array * @param limit the upper bound limit */ protected ParallelLongArray(ForkJoinPool executor, long[] array, int limit) { super(executor, 0, limit, array); if (executor == null || array == null) throw new NullPointerException(); if (limit < 0 || limit > array.length) throw new IllegalArgumentException(); } /** * Trusted internal version of protected constructor. */ ParallelLongArray(ForkJoinPool executor, long[] array) { super(executor, 0, array.length, array); } /** * Creates a new ParallelLongArray using the given executor and * an array of the given size. * @param size the array size * @param executor the executor */ public static ParallelLongArray create (int size, ForkJoinPool executor) { long[] array = new long[size]; return new ParallelLongArray(executor, array, size); } /** * Creates a new ParallelLongArray initially using the given array and * executor. In general, the handed off array should not be used * for other purposes once constructing this ParallelLongArray. The * given array may be internally replaced by another array in the * course of methods that add or remove elements. * @param handoff the array * @param executor the executor */ public static ParallelLongArray createUsingHandoff (long[] handoff, ForkJoinPool executor) { return new ParallelLongArray(executor, handoff, handoff.length); } /** * Creates a new ParallelLongArray using the given executor and * initially holding copies of the given * source elements. * @param source the source of initial elements * @param executor the executor */ public static ParallelLongArray createFromCopy (long[] source, ForkJoinPool executor) { // For now, avoid copyOf so people can compile with Java5 int size = source.length; long[] array = new long[size]; System.arraycopy(source, 0, array, 0, size); return new ParallelLongArray(executor, array, size); } /** * Creates a new ParallelLongArray using an array of the given size, * initially holding copies of the given source truncated or * padded with zeros to obtain the specified length. * @param source the source of initial elements * @param size the array size * @param executor the executor */ public static ParallelLongArray createFromCopy (int size, long[] source, ForkJoinPool executor) { // For now, avoid copyOf so people can compile with Java5 long[] array = new long[size]; System.arraycopy(source, 0, array, 0, Math.min(source.length, size)); return new ParallelLongArray(executor, array, size); } /** * Creates a new ParallelLongArray using the given executor and * an array of the given size, but with an initial effective size * of zero, enabling incremental insertion via {@link * ParallelLongArray#asList} operations. * @param size the array size * @param executor the executor */ public static ParallelLongArray createEmpty (int size, ForkJoinPool executor) { long[] array = new long[size]; return new ParallelLongArray(executor, array, 0); } /** * Summary statistics for a possibly bounded, filtered, and/or * mapped ParallelLongArray. */ public static interface SummaryStatistics { /** Returns the number of elements */ public int size(); /** Returns the minimum element, or Long.MAX_VALUE if empty */ public long min(); /** Returns the maximum element, or Long.MIN_VALUE if empty */ public long max(); /** Returns the index of the minimum element, or -1 if empty */ public int indexOfMin(); /** Returns the index of the maximum element, or -1 if empty */ public int indexOfMax(); /** Returns the sum of all elements */ public long sum(); /** Returns the arithmetic average of all elements */ public double average(); } /** * Returns the executor used for computations. * @return the executor */ public ForkJoinPool getExecutor() { return ex; } /** * Applies the given procedure to elements. * @param procedure the procedure */ public void apply(LongProcedure procedure) { super.apply(procedure); } /** * Returns reduction of elements. * @param reducer the reducer * @param base the result for an empty array * @return reduction */ public long reduce(LongReducer reducer, long base) { return super.reduce(reducer, base); } /** * Returns a new ParallelLongArray holding all elements. * @return a new ParallelLongArray holding all elements */ public ParallelLongArray all() { return super.all(); } /** * Replaces elements with the results of applying the given op * to their current values. * @param op the op * @return this (to simplify use in expressions) */ public ParallelLongArray replaceWithMapping(LongOp op) { super.replaceWithMapping(op); return this; } /** * Replaces elements with the results of applying the given * op to their indices. * @param op the op * @return this (to simplify use in expressions) */ public ParallelLongArray replaceWithMappedIndex(IntToLong op) { super.replaceWithMappedIndex(op); return this; } /** * Replaces elements with the results of applying the given * mapping to each index and current element value. * @param op the op * @return this (to simplify use in expressions) */ public ParallelLongArray replaceWithMappedIndex(IntAndLongToLong op) { super.replaceWithMappedIndex(op); return this; } /** * Replaces elements with the results of applying the given * generator. For example, to fill the array with uniform random * values, use * {@code replaceWithGeneratedValue(Ops.longRandom())}. * @param generator the generator * @return this (to simplify use in expressions) */ public ParallelLongArray replaceWithGeneratedValue(LongGenerator generator){ super.replaceWithGeneratedValue(generator); return this; } /** * Replaces elements with the given value. * @param value the value * @return this (to simplify use in expressions) */ public ParallelLongArray replaceWithValue(long value) { super.replaceWithValue(value); return this; } /** * Replaces elements with results of applying * {@code op(thisElement, otherElement)}. * @param other the other array * @param combiner the combiner * @return this (to simplify use in expressions) */ public ParallelLongArray replaceWithMapping (BinaryLongOp combiner, ParallelLongArrayWithLongMapping other) { super.replaceWithMapping(combiner, other); return this; } /** * Replaces elements with results of applying * {@code op(thisElement, otherElement)}. * @param other the other array * @param combiner the combiner * @return this (to simplify use in expressions) * @throws ArrayIndexOutOfBoundsException if other array has * fewer elements than this array. */ public ParallelLongArray replaceWithMapping(BinaryLongOp combiner, long[] other) { super.replaceWithMapping(combiner, other); return this; } /** * Returns the index of some element equal to given target, or -1 * if not present. * @param target the element to search for * @return the index or -1 if not present */ public int indexOf(long target) { return super.indexOf(target); } /** * Assuming this array is sorted, returns the index of an element * equal to given target, or -1 if not present. If the array * is not sorted, the results are undefined. * @param target the element to search for * @return the index or -1 if not present */ public int binarySearch(long target) { return super.binarySearch(target); } /** * Assuming this array is sorted with respect to the given * comparator, returns the index of an element equal to given * target, or -1 if not present. If the array is not sorted, the * results are undefined. * @param target the element to search for * @param comparator the comparator * @return the index or -1 if not present */ public int binarySearch(long target, LongComparator comparator) { return super.binarySearch(target, comparator); } /** * Returns summary statistics, using the given comparator * to locate minimum and maximum elements. * @param comparator the comparator to use for * locating minimum and maximum elements * @return the summary */ public ParallelLongArray.SummaryStatistics summary (LongComparator comparator) { return super.summary(comparator); } /** * Returns summary statistics, using natural comparator. * @return the summary */ public ParallelLongArray.SummaryStatistics summary() { return super.summary(); } /** * Returns the minimum element, or Long.MAX_VALUE if empty. * @param comparator the comparator * @return minimum element, or Long.MAX_VALUE if empty */ public long min(LongComparator comparator) { return super.min(comparator); } /** * Returns the minimum element, or Long.MAX_VALUE if empty. * @return minimum element, or Long.MAX_VALUE if empty */ public long min() { return super.min(); } /** * Returns the maximum element, or Long.MIN_VALUE if empty. * @param comparator the comparator * @return maximum element, or Long.MIN_VALUE if empty */ public long max(LongComparator comparator) { return super.max(comparator); } /** * Returns the maximum element, or Long.MIN_VALUE if empty. * @return maximum element, or Long.MIN_VALUE if empty */ public long max() { return super.max(); } /** * Replaces each element with the running cumulation of applying * the given reducer. For example, if the contents are the numbers * {@code 1, 2, 3}, and the reducer operation adds numbers, then * after invocation of this method, the contents would be {@code 1, * 3, 6} (that is, {@code 1, 1+2, 1+2+3}). * @param reducer the reducer * @param base the result for an empty array * @return this (to simplify use in expressions) */ public ParallelLongArray cumulate(LongReducer reducer, long base) { super.cumulate(reducer, base); return this; } /** * Replaces each element with the cumulation of applying the given * reducer to all previous values, and returns the total * reduction. For example, if the contents are the numbers {@code 1, * 2, 3}, and the reducer operation adds numbers, then after * invocation of this method, the contents would be {@code 0, 1, * 3} (that is, {@code 0, 0+1, 0+1+2}, and the return value * would be 6 (that is, {@code 1+2+3}). * @param reducer the reducer * @param base the result for an empty array * @return the total reduction */ public long precumulate(LongReducer reducer, long base) { return super.precumulate(reducer, base); } /** * Sorts the array. Unlike Arrays.sort, this sort does * not guarantee that elements with equal keys maintain their * relative position in the array. * @param comparator the comparator to use * @return this (to simplify use in expressions) */ public ParallelLongArray sort(LongComparator comparator) { super.sort(comparator); return this; } /** * Sorts the array, assuming all elements are Comparable. Unlike * Arrays.sort, this sort does not guarantee that elements * with equal keys maintain their relative position in the array. * @throws ClassCastException if any element is not Comparable * @return this (to simplify use in expressions) */ public ParallelLongArray sort() { super.sort(); return this; } /** * Removes consecutive elements that are equal, * shifting others leftward, and possibly decreasing size. This * method may be used after sorting to ensure that this * ParallelLongArray contains a set of unique elements. * @return this (to simplify use in expressions) */ public ParallelLongArray removeConsecutiveDuplicates() { // Sequential implementation for now int k = 0; int n = fence; if (k < n) { long[] arr = this.array; long last = arr[k++]; for (int i = k; i < n; ++i) { long x = arr[i]; if (last != x) arr[k++] = last = x; } removeSlotsAt(k, n); } return this; } /** * Equivalent to {@code asList().addAll} but specialized for array * arguments and likely to be more efficient. * @param other the elements to add * @return this (to simplify use in expressions) */ public ParallelLongArray addAll(long[] other) { int csize = other.length; int end = fence; insertSlotsAt(end, csize); System.arraycopy(other, 0, array, end, csize); return this; } /** * Appends all (possibly bounded, filtered, or mapped) elements of * the given ParallelDoubleArray, resizing and/or reallocating this * array if necessary. * @param other the elements to add * @return this (to simplify use in expressions) */ public ParallelLongArray addAll(ParallelLongArrayWithLongMapping other) { int end = fence; if (other.hasFilter()) { PAS.FJLAppendAllDriver r = new PAS.FJLAppendAllDriver (other, end, array); ex.invoke(r); array = r.results; fence = end + r.resultSize; } else { int csize = other.size(); insertSlotsAt(end, csize); if (other.hasMap()) ex.invoke(new PAS.FJLMap(other, other.origin, other.fence, null, array, end - other.origin)); else System.arraycopy(other.array, 0, array, end, csize); } return this; } /** * Returns a new ParallelLongArray containing only the unique * elements of this array (that is, without any duplicates). * @return the new ParallelLongArray */ public ParallelLongArray allUniqueElements() { return super.allUniqueElements(); } /** * Removes from the array all elements for which the given * selector holds. * @param selector the selector * @return this (to simplify use in expressions) */ public ParallelLongArray removeAll(LongPredicate selector) { LFPap v = new LFPap(ex, 0, fence, array, selector); PAS.FJRemoveAllDriver f = new PAS.FJRemoveAllDriver(v, 0, fence); ex.invoke(f); removeSlotsAt(f.offset, fence); return this; } /** * Returns true if all elements at the same relative positions * of this and other array are equal. * @param other the other array */ public boolean hasAllEqualElements(ParallelLongArrayWithLongMapping other) { return super.hasAllEqualElements(other); } /** * Returns the sum of elements. * @return the sum of elements */ public long sum() { return super.sum(); } /** * Replaces each element with the running sum. * @return this (to simplify use in expressions) */ public ParallelLongArray cumulateSum() { super.cumulateSum(); return this; } /** * Replaces each element with its prefix sum. * @return the total sum */ public long precumulateSum() { return super.precumulateSum(); } /** * Returns an operation prefix that causes a method to * operate only on the elements of the array between * firstIndex (inclusive) and upperBound (exclusive). * @param firstIndex the lower bound (inclusive) * @param upperBound the upper bound (exclusive) * @return operation prefix */ public ParallelLongArrayWithBounds withBounds(int firstIndex, int upperBound) { return super.withBounds(firstIndex, upperBound); } /** * Returns an operation prefix that causes a method to operate * only on the elements of the array for which the given selector * returns true. * @param selector the selector * @return operation prefix */ public ParallelLongArrayWithFilter withFilter(LongPredicate selector) { return super.withFilter(selector); } /** * Returns an operation prefix that causes a method to operate * only on elements for which the given binary selector returns * true. * @param selector the selector * @return operation prefix */ public ParallelLongArrayWithFilter withFilter (BinaryLongPredicate selector, ParallelLongArrayWithLongMapping other) { return super.withFilter(selector, other); } /** * Returns an operation prefix that causes a method to operate * only on elements for which the given indexed selector returns * true. * @param selector the selector * @return operation prefix */ public ParallelLongArrayWithFilter withIndexedFilter (IntAndLongPredicate selector) { return super.withIndexedFilter(selector); } /** * Returns an operation prefix that causes a method to operate * on mapped elements of the array using the given op. * @param op the op * @return operation prefix */ public ParallelLongArrayWithMapping withMapping (LongToObject extends U> op) { return super.withMapping(op); } /** * Returns an operation prefix that causes a method to operate * on mapped elements of the array using the given op. * @param op the op * @return operation prefix */ public ParallelLongArrayWithLongMapping withMapping(LongOp op) { return super.withMapping(op); } /** * Returns an operation prefix that causes a method to operate * on mapped elements of the array using the given op. * @param op the op * @return operation prefix */ public ParallelLongArrayWithDoubleMapping withMapping(LongToDouble op) { return super.withMapping(op); } /** * Returns an operation prefix that causes a method to operate * on binary mappings of this array and the other array. * @param combiner the combiner * @param other the other array * @return operation prefix * @throws IllegalArgumentException if other array is a * filtered view (all filters must precede all mappings) */ public