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 {
/** Return the number of elements */
public int size();
/** Return the minimum element, or Long.MAX_VALUE if empty */
public long min();
/** Return the maximum element, or Long.MIN_VALUE if empty */
public long max();
/** Return the index of the minimum element, or -1 if empty */
public int indexOfMin();
/** Return the index of the maximum element, or -1 if empty */
public int indexOfMax();
/** Return the sum of all elements */
public long sum();
/** Return 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
* 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
* 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
* 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
* 1, 2, 3, and the reducer operation adds numbers, then
* after invocation of this method, the contents would be 1,
* 3, 6 (that is, 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 1,
* 2, 3, and the reducer operation adds numbers, then after
* invocation of this method, the contents would be 0, 1,
* 3 (that is, 0, 0+1, 0+1+2, and the return value
* would be 6 (that is, 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 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 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