jsr166z.forkjoin
Class ParallelArray<T>

java.lang.Object
  jsr166z.forkjoin.ParallelArray<T>

All Implemented Interfaces:

java.lang.Iterable<T>

public class ParallelArray<T>
extends java.lang.Object
implements java.lang.Iterable<T>

An array supporting parallel operations.

A ParallelArray encapsulates a ForkJoinExecutor and an array in order to provide parallel aggregate operations. The main operations are to apply some procedure to each element, to map each element to a new element, to replace each element, to select a subset of elements based on matching a predicate or ranges of indices, and to reduce all elements into a single value such as a sum.

A ParallelArray is not a List, but can be viewed as one, via method asList(), or created from one, by constructing from array returned by a list's toArray method. Arrays differ from lists in that they do not incrementally grow or shrink. Random accessiblity across all elements permits efficient parallel operation. ParallelArrays also support element-by-element access (via methods get and /set), but are normally manipulated using aggregate operations on all or selected elements.

Many operations can be prefixed with range bounds, filters, and mappings using withBounds, withFilter, and withMapping, respectively. For example, aParallelArray.withFilter(aPredicate).newArray() creates a new ParallelArray containing only those elements matching the predicate. As illustrated below, a mapping often represents accessing some field or invoking some method of an element. These versions are typically more efficient than performing selections, then mappings, then other operations in multiple (parallel) steps. However, not all operations are available under all combinations, either because they wouldn't make sense, or because they would not usually be more efficient than stepwise processing.

While ParallelArrays can be based on any kind of an object array, including "boxed" types such as Integer, parallel operations on scalar "unboxed" type are likely to be substantially more efficient. For this reason, classes ParallelIntArray, ParallelLongArray, and ParallelDoubleArray are also supplied, and designed to smoothly interoperate with ParallelArrays. (Other scalar types such as short are not useful often enough to further integrate them.)

The methods in this class are designed to perform efficiently with both large and small pools, even with single-thread pools on uniprocessors. However, there is some overhead in parallelizing operations, so short computations on small arrays might not execute faster than sequential versions, and might even be slower.

Accesses by other threads of the elements of a ParallelArray while an aggregate operation is in progress have undefined effects. Don't do that.

Sample usages. The main difference between programming with plain arrays and programming with aggregates is that you must separately define each of the component functions on elements. For example, the following returns the maximum Grade Point Average across all senior students, given a (fictional) Student class:

 import static Ops.*;
 class StudentStatistics {
   ParallelArray<Student> students = ...
   // ...
   public double getMaxSeniorGpa() {
     return students.withFilter(isSenior).withMapping(gpaField).max();
   }

   // helpers:
   static final class IsSenior implements { Student => boolean } {
     public boolean invoke(Student s) { return s.credits > 90; }
   }
   static final IsSenior isSenior = new IsSenior();
   static final class GpaField implements { T => double } {
     public double invoke(Student s) { return s.gpa; }
   }
   static final GpaField gpaField = new GpaField();
 }
 

Nested Class Summary

static class	ParallelArray.WithBounds<T> A restriction of parallel array operations to apply only within a given range of indices.
static class	ParallelArray.WithDoubleMapping<T> A modifier for parallel array operations to apply to mappings of elements to doubles, not to the elements themselves
static class	ParallelArray.WithFilter<T> A restriction of parallel array operations to apply only to elements for which a selector returns true
static class	ParallelArray.WithIntMapping<T> A modifier for parallel array operations to apply to mappings of elements to ints, not to the elements themselves
static class	ParallelArray.WithLongMapping<T> A modifier for parallel array operations to apply to mappings of elements to longs, not to the elements themselves
static class	ParallelArray.WithMapping<T,U> A modifier for parallel array operations to apply to mappings of elements, not to the elements themselves

Constructor Summary

ParallelArray(ForkJoinExecutor executor, int size, java.lang.Class<? super T> elementType)
Creates a new ParallelArray using the given executor and an array of the given size constructed using the indicated base element type.

ParallelArray(ForkJoinExecutor executor, int size, T[] sourceToCopy)
Creates a new ParallelArray using the given executor and an array of the given size, initially holding copies of the given source truncated or padded with nulls to obtain the specified length.

ParallelArray(ForkJoinExecutor executor, T[] handoff)
Creates a new ParallelArray using the given executor and array.

Method Summary

void	apply({T=>void} procedure) Applies the given procedure to elements
java.util.List<T>	asList() Returns a fixed-size list backed by the underlying array.
<U,V> ParallelArray<V>	combine(ParallelArray<U> other, {T,U=>V} combiner) Returns a ParallelArray containing results of applying combine(thisElement, otherElement) for each element.
<U,V> ParallelArray<V>	combine(ParallelArray<U> other, {T,U=>V} combiner, java.lang.Class<? super V> elementType) Returns a ParallelArray containing results of applying combine(thisElement, otherElement) for each element.
<U,V> ParallelArray<V>	combine(U[] other, {T,U=>V} combiner) Returns a ParallelArray containing results of applying combine(thisElement, otherElement) for each element.
<U,V> ParallelArray<V>	combine(U[] other, {T,U=>V} combiner, java.lang.Class<? super V> elementType) Returns a ParallelArray containing results of applying combine(thisElement, otherElement) for each element.
void	cumulate({T,T=>T} reducer, T base) Replaces each element with the running cumulation of applying the given reducer.
T	get(int i) Returns the element of the array at the given index
T[]	getArray() Returns the underlying array used for computations
ForkJoinExecutor	getExecutor() Returns the executor used for computations
int	indexOfMax() Returns the index of the greatest element , or -1 if empty assuming that all elements are Comparables
int	indexOfMax(java.util.Comparator<? super T> comparator) Returns the index of the greatest element , or -1 if empty
int	indexOfMin() Returns the index of the least element , or -1 if empty assuming that all elements are Comparables
int	indexOfMin(java.util.Comparator<? super T> comparator) Returns the index of the least element , or -1 if empty
java.util.Iterator<T>	iterator() Returns an iterator stepping through each element of the array.
T	max() Returns the maximum element, or null if empty assuming that all elements are Comparables
T	max(java.util.Comparator<? super T> comparator) Returns the maximum element, or null if empty
T	min() Returns the minimum element, or null if empty, assuming that all elements are Comparables
T	min(java.util.Comparator<? super T> comparator) Returns the minimum element, or null if empty
ParallelArray<T>	newArray() Returns a new ParallelArray holding elements
ParallelArray<T>	newArray(java.lang.Class<? super T> elementType) Returns a new ParallelArray with the given element type holding elements
T	precumulate({T,T=>T} reducer, T base) Replaces each element with the cumulation of applying the given reducer to all previous values, and returns the total reduction.
T	reduce({T,T=>T} reducer, T base) Returns reduction of elements
void	replaceWithCombination(ParallelArray<? extends T> other, {T,T=>T} combiner) Replaces elements with results of applying combine(thisElement, otherElement)
void	replaceWithCombination(T[] other, {T,T=>T} combiner) Replaces elements with results of applying combine(thisElement, otherElement)
void	replaceWithGeneratedValue({=>T} generator) Replaces elements with the results of applying the given generator.
void	replaceWithMappedIndex({int=>T} mapper) Replaces elements with the results of applying the given mapper to their indices.
void	replaceWithTransform({T=>T} mapper) Replaces elements with the results of applying the given mapper to their current values.
void	replaceWithValue(T value) Replaces elements with the given value.
void	set(int i, T x) Sets the element of the array at the given index to the given value
int	size() Returns the length of the underlying array
void	sort() Sorts the array, assuming all elements are Comparable.
void	sort(java.util.Comparator<? super T> comparator) Sorts the array.
ParallelArray.WithBounds<T>	withBounds(int firstIndex, int upperBound) Returns an operation prefix that causes a method to operate only on the elements of the array between firstIndex (inclusive) and upperBound (exclusive).
ParallelArray.WithFilter<T>	withFilter({T=>boolean} selector) Returns an operation prefix that causes a method to operate only on the elements of the array for which the given selector returns true
ParallelArray.WithDoubleMapping<T>	withMapping({T=>double} mapper) Returns an operation prefix that causes a method to operate on mapped elements of the array using the given mapper.
ParallelArray.WithIntMapping<T>	withMapping({T=>int} mapper) Returns an operation prefix that causes a method to operate on mapped elements of the array using the given mapper.
ParallelArray.WithLongMapping<T>	withMapping({T=>long} mapper) Returns an operation prefix that causes a method to operate on mapped elements of the array using the given mapper.
<U> ParallelArray.WithMapping<T,U>	withMapping({T=>U} mapper) Returns an operation prefix that causes a method to operate on mapped elements of the array using the given mapper.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

ParallelArray

public ParallelArray(ForkJoinExecutor executor,
                     T[] handoff)

Creates a new ParallelArray using the given executor and array. In general, the handed off array should not be used for other purposes once constructing this ParallelArray.

Parameters:

executor - the executor

handoff - the array

ParallelArray

public ParallelArray(ForkJoinExecutor executor,
                     int size,
                     T[] sourceToCopy)

Creates a new ParallelArray using the given executor and an array of the given size, initially holding copies of the given source truncated or padded with nulls to obtain the specified length.

Parameters:

executor - the executor

size - the array size

sourceToCopy - the source of initial elements

ParallelArray

public ParallelArray(ForkJoinExecutor executor,
                     int size,
                     java.lang.Class<? super T> elementType)

Creates a new ParallelArray using the given executor and an array of the given size constructed using the indicated base element type.

Parameters:

executor - the executor

size - the array size

elementType - the type of the elements

Method Detail

getExecutor

public ForkJoinExecutor getExecutor()

Returns the executor used for computations

Returns:

the executor

getArray

public T[] getArray()

Returns the underlying array used for computations

Returns:

the array

size

public int size()

Returns the length of the underlying array

Returns:

the length of the underlying array

get

public T get(int i)

Returns the element of the array at the given index

Parameters:

i - the index

Returns:

the element of the array at the given index

set

public void set(int i,
                T x)

Sets the element of the array at the given index to the given value

Parameters:

i - the index

x - the value

asList

public java.util.List<T> asList()

Returns a fixed-size list backed by the underlying array.

Returns:

a list view of the specified array

iterator

public java.util.Iterator<T> iterator()

Returns an iterator stepping through each element of the array. This iterator does not support the remove operation.

Specified by:

iterator in interface java.lang.Iterable<T>

Returns:

an iterator stepping through each element of the array.

apply

public void apply({T=>void} procedure)

Applies the given procedure to elements

Parameters:

procedure - the procedure

reduce

public T reduce({T,T=>T} reducer,
                T base)

Returns reduction of elements

Parameters:

reducer - the reducer

base - the result for an empty array

Returns:

reduction

newArray

public ParallelArray<T> newArray()

Returns a new ParallelArray holding elements

Returns:

a new ParallelArray holding elements

newArray

public ParallelArray<T> newArray(java.lang.Class<? super T> elementType)

Returns a new ParallelArray with the given element type holding elements

Parameters:

elementType - the type of the elements

Returns:

a new ParallelArray holding elements

combine

public <U,V> ParallelArray<V> combine(U[] other,
                                      {T,U=>V} combiner)

Returns a ParallelArray containing results of applying combine(thisElement, otherElement) for each element.

Parameters:

other - the other array

combiner - the combiner

Returns:

the array of mappings

Throws:

java.lang.ArrayIndexOutOfBoundsException - if other array is shorter than this array.

combine

public <U,V> ParallelArray<V> combine(ParallelArray<U> other,
                                      {T,U=>V} combiner)

Returns a ParallelArray containing results of applying combine(thisElement, otherElement) for each element.

Parameters:

other - the other array

combiner - the combiner

Returns:

the array of mappings

Throws:

java.lang.ArrayIndexOutOfBoundsException - if other array is not the same length as this array.

combine

public <U,V> ParallelArray<V> combine(U[] other,
                                      {T,U=>V} combiner,
                                      java.lang.Class<? super V> elementType)

Returns a ParallelArray containing results of applying combine(thisElement, otherElement) for each element.

Parameters:

other - the other array

combiner - the combiner

elementType - the type of elements of returned array

Returns:

the array of mappings

Throws:

java.lang.ArrayIndexOutOfBoundsException - if other array is shorter than this array.

combine

public <U,V> ParallelArray<V> combine(ParallelArray<U> other,
                                      {T,U=>V} combiner,
                                      java.lang.Class<? super V> elementType)

Returns a ParallelArray containing results of applying combine(thisElement, otherElement) for each element.

Parameters:

other - the other array

combiner - the combiner

elementType - the type of elements of returned array

Returns:

the array of mappings

Throws:

java.lang.ArrayIndexOutOfBoundsException - if other array is not the same length as this array.

replaceWithTransform

public void replaceWithTransform({T=>T} mapper)

Replaces elements with the results of applying the given mapper to their current values.

Parameters:

mapper - the mapper

replaceWithMappedIndex

public void replaceWithMappedIndex({int=>T} mapper)

Replaces elements with the results of applying the given mapper to their indices.

Parameters:

mapper - the mapper

replaceWithGeneratedValue

public void replaceWithGeneratedValue({=>T} generator)

Replaces elements with the results of applying the given generator.

Parameters:

generator - the generator

replaceWithValue

public void replaceWithValue(T value)

Replaces elements with the given value.

Parameters:

value - the value

replaceWithCombination

public void replaceWithCombination(ParallelArray<? extends T> other,
                                   {T,T=>T} combiner)

Replaces elements with results of applying combine(thisElement, otherElement)

Parameters:

other - the other array

combiner - the combiner

Throws:

java.lang.ArrayIndexOutOfBoundsException - if other array has fewer elements than this array.

replaceWithCombination

public void replaceWithCombination(T[] other,
                                   {T,T=>T} combiner)

Replaces elements with results of applying combine(thisElement, otherElement)

Parameters:

other - the other array

combiner - the combiner

Throws:

java.lang.ArrayIndexOutOfBoundsException - if other array has fewer elements than this array.

indexOfMin

public int indexOfMin(java.util.Comparator<? super T> comparator)

Returns the index of the least element , or -1 if empty

Parameters:

comparator - the comparator

Returns:

the index of least element or -1 if empty.

indexOfMax

public int indexOfMax(java.util.Comparator<? super T> comparator)

Returns the index of the greatest element , or -1 if empty

Parameters:

comparator - the comparator

Returns:

the index of greatest element or -1 if empty.

indexOfMin

public int indexOfMin()

Returns the index of the least element , or -1 if empty assuming that all elements are Comparables

Returns:

the index of least element or -1 if empty.

Throws:

java.lang.ClassCastException - if any element is not Comparable.

indexOfMax

public int indexOfMax()

Returns the index of the greatest element , or -1 if empty assuming that all elements are Comparables

Returns:

the index of greatest element or -1 if empty.

Throws:

java.lang.ClassCastException - if any element is not Comparable.

min

public T min(java.util.Comparator<? super T> comparator)

Returns the minimum element, or null if empty

Parameters:

comparator - the comparator

Returns:

minimum element, or null if empty

min

public T min()

Returns the minimum element, or null if empty, assuming that all elements are Comparables

Returns:

minimum element, or null if empty

Throws:

java.lang.ClassCastException - if any element is not Comparable.

max

public T max(java.util.Comparator<? super T> comparator)

Returns the maximum element, or null if empty

Parameters:

comparator - the comparator

Returns:

maximum element, or null if empty

max

public T max()

Returns the maximum element, or null if empty assuming that all elements are Comparables

Returns:

maximum element, or null if empty

Throws:

java.lang.ClassCastException - if any element is not Comparable.

cumulate

public void cumulate({T,T=>T} reducer,
                     T base)

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);

Parameters:

reducer - the reducer

base - the result for an empty array

precumulate

public T precumulate({T,T=>T} reducer,
                     T base)

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);

Parameters:

reducer - the reducer

base - the result for an empty array

Returns:

the total reduction

sort

public void sort(java.util.Comparator<? super T> comparator)

Sorts the array. Unlike Arrays.sort, this sort does not guarantee that elements with equal keys maintain their relative position in the array.

Parameters:

comparator - the comparator to use

sort

public void sort()

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:

java.lang.ClassCastException - if any element is not Comparable.

withBounds

public ParallelArray.WithBounds<T> withBounds(int firstIndex,
                                              int upperBound)

Returns an operation prefix that causes a method to operate only on the elements of the array between firstIndex (inclusive) and upperBound (exclusive).

Parameters:

firstIndex - the lower bound (inclusive)

upperBound - the upper bound (exclusive)

Returns:

operation prefix

withFilter

public ParallelArray.WithFilter<T> withFilter({T=>boolean} selector)

Returns an operation prefix that causes a method to operate only on the elements of the array for which the given selector returns true

Parameters:

selector - the selector

Returns:

operation prefix

withMapping

public <U> ParallelArray.WithMapping<T,U> withMapping({T=>U} mapper)

Returns an operation prefix that causes a method to operate on mapped elements of the array using the given mapper.

Parameters:

mapper - the mapper

Returns:

operation prefix

withMapping

public ParallelArray.WithDoubleMapping<T> withMapping({T=>double} mapper)

Returns an operation prefix that causes a method to operate on mapped elements of the array using the given mapper.

Parameters:

mapper - the mapper

Returns:

operation prefix

withMapping

public ParallelArray.WithLongMapping<T> withMapping({T=>long} mapper)

Returns an operation prefix that causes a method to operate on mapped elements of the array using the given mapper.

Parameters:

mapper - the mapper

Returns:

operation prefix

withMapping

public ParallelArray.WithIntMapping<T> withMapping({T=>int} mapper)

Returns an operation prefix that causes a method to operate on mapped elements of the array using the given mapper.

Parameters:

mapper - the mapper

Returns:

operation prefix