ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/extra166y/ParallelArray.java

Comparing jsr166/src/extra166y/ParallelArray.java (file contents):
Revision 1.4 by jsr166, Tue Feb 21 01:54:03 2012 UTC vs.
Revision 1.18 by jsr166, Sun Jan 18 20:17:32 2015 UTC

#	Line 5 | Line 5
5		*/
6
7		package extra166y;
8	+
9		import jsr166y.*;
10		import static extra166y.Ops.*;
11		import java.util.*;
#	Line 22 | Line 23 | import java.lang.reflect.Array;
23		* matching a predicate or ranges of indices, and to <em>reduce</em>
24		* all elements into a single value such as a sum.
25		*
26	<	* <p> A ParallelArray is constructed by allocating, using, or copying
26	>	* <p>A ParallelArray is constructed by allocating, using, or copying
27		* an array, using one of the static factory methods {@link #create},
28		* {@link #createEmpty}, {@link #createUsingHandoff} and {@link
29		* #createFromCopy}. Upon construction, the encapsulated array managed
#	Line 31 | Line 32 | import java.lang.reflect.Array;
32		* array, access by another thread of an element of a ParallelArray
33		* while another operation is in progress has undefined effects.
34		*
35	<	* <p> The ForkJoinPool used to construct a ParallelArray can be
35	>	* <p>The ForkJoinPool used to construct a ParallelArray can be
36		* shared safely by other threads (and used in other
37		* ParallelArrays). To avoid the overhead associated with creating
38		* multiple executors, it is often a good idea to use the {@link
#	Line 42 | Line 43 | import java.lang.reflect.Array;
43		* <p>A ParallelArray is not a List. It relies on random access across
44		* array elements to support efficient parallel operations.  However,
45		* a ParallelArray can be viewed and manipulated as a List, via method
46	<	* {@link ParallelArray#asList}. The <tt>asList</tt> view allows
46	>	* {@link ParallelArray#asList}. The {@code asList} view allows
47		* incremental insertion and modification of elements while setting up
48		* a ParallelArray, generally before using it for parallel
49		* operations. Similarly, the list view may be useful when accessing
50		* the results of computations in sequential contexts.  A
51		* ParallelArray may also be created using the elements of any other
52		* Collection, by constructing from the array returned by the
53	<	* Collection's <tt>toArray</tt> method. The effects of mutative
54	<	* <tt>asList</tt> operations may also be achieved directly using
53	>	* Collection's {@code toArray} method. The effects of mutative
54	>	* {@code asList} operations may also be achieved directly using
55		* method {@link #setLimit} along with element-by-element access
56		* methods {@link #get}</tt> and {@link #set}.
57		*
#	Line 61 | Line 62 | import java.lang.reflect.Array;
62		* {@link ParallelDoubleArray} are also supplied, and designed to
63		* smoothly interoperate with ParallelArrays. You should also use a
64		* ParallelLongArray for processing other integral scalar data
65	<	* (<tt>int</tt>, <tt>short</tt>, etc).  And similarly use a
66	<	* ParallelDoubleArray for <tt>float</tt> data.  (Further
65	>	* ({@code int}, {@code short}, etc).  And similarly use a
66	>	* ParallelDoubleArray for {@code float} data.  (Further
67		* specializations for these other types would add clutter without
68		* significantly improving performance beyond that of the Long and
69		* Double versions.)
70		*
71	<	* <p> Most usages of ParallelArray involve sets of operations prefixed
71	>	* <p>Most usages of ParallelArray involve sets of operations prefixed
72		* with range bounds, filters, and mappings (including mappings that
73		* combine elements from other ParallelArrays), using
74	<	* <tt>withBounds</tt>, <tt>withFilter</tt>, and <tt>withMapping</tt>,
74	>	* {@code withBounds}, {@code withFilter}, and {@code withMapping},
75		* respectively. For example,
76	<	* <tt>aParallelArray.withFilter(aPredicate).all()</tt> creates a new
76	>	* {@code aParallelArray.withFilter(aPredicate).all()} creates a new
77		* ParallelArray containing only those elements matching the
78		* predicate. And for ParallelLongArrays a, b, and c,
79	<	* <tt>a.withMapping(CommonOps.longAdder(),b).withMapping(CommonOps.longAdder(),c).min()</tt>
79	>	* {@code a.withMapping(CommonOps.longAdder(),b).withMapping(CommonOps.longAdder(),c).min()}
80		* returns the minimum value of a[i]+b[i]+c[i] for all i.  As
81		* illustrated below, a <em>mapping</em> often represents accessing
82		* some field or invoking some method of an element.  These versions
#	Line 87 | Line 88 | import java.lang.reflect.Array;
88		* be cascaded, but all filter prefixes must precede all mapping
89		* prefixes, to ensure efficient execution in a single parallel step.
90		* In cases of combined mapping expressions, this rule is only
91	<	* dynamically enforced. For example, <tt>pa.withMapping(op,
92	<	* pb.withFilter(f))</tt> will compile but throw an exception upon
91	>	* dynamically enforced. For example, {@code pa.withMapping(op,
92	>	* pb.withFilter(f))} will compile but throw an exception upon
93		* execution because the filter precedes the mapping.
94		*
95		* <p>While series of filters and mappings are allowed, it is
96		* usually more efficient to combine them into single filters or
97		* mappings when possible. For example
98	<	* <tt>pa.withMapping(addOne).withMapping(addOne)</tt> is generally
99	<	* less efficient than <tt>pa.withMapping(addTwo)</tt>. Methods
100	<	* <tt>withIndexedFilter</tt> and <tt>withIndexedMapping</tt> may be
98	>	* {@code pa.withMapping(addOne).withMapping(addOne)} is generally
99	>	* less efficient than {@code pa.withMapping(addTwo)}. Methods
100	>	* {@code withIndexedFilter} and {@code withIndexedMapping} may be
101		* useful when combining such expressions.
102		*
103	<	* <p>This class includes some reductions, such as <tt>min</tt>, that
103	>	* <p>This class includes some reductions, such as {@code min}, that
104		* are commonly useful for most element types, as well as a combined
105	<	* version, <tt>summary</tt>, that computes all of them in a single
105	>	* version, {@code summary}, that computes all of them in a single
106		* parallel step, which is normally more efficient than computing each
107		* in turn.
108		*
#	Line 117 | Line 118 | import java.lang.reflect.Array;
118		* programming with aggregates is that you must separately define each
119		* of the component functions on elements. For example, the following
120		* returns the maximum Grade Point Average across all senior students,
121	<	* given a (fictional) <tt>Student</tt> class:
121	>	* given a (fictional) {@code Student} class:
122		*
123		* <pre>
124		* import static Ops.*;
#	Line 133 | Line 134 | import java.lang.reflect.Array;
134		*     public boolean op(Student s) { return s.credits &gt; 90; }
135		*   }
136		*   static final IsSenior isSenior = new IsSenior();
137	<	*   static final class GpaField implements ObjectToDouble&lt;Student&gt {
137	>	*   static final class GpaField implements ObjectToDouble&lt;Student&gt; {
138		*     public double op(Student s) { return s.gpa; }
139		*   }
140		*   static final GpaField gpaField = new GpaField();
141		* }
142		* </pre>
142	–	*
143		*/
144		public class ParallelArray<T> extends AbstractParallelAnyArray.OUPap<T> implements Iterable<T> {
145		/*
#	Line 292 | Line 292 | public class ParallelArray<T> extends Ab
292		public ForkJoinPool getExecutor() { return ex; }
293
294		/**
295	<	* Applies the given procedure to elements
295	>	* Applies the given procedure to elements.
296		* @param procedure the procedure
297		*/
298		public void apply(Procedure<? super T> procedure) {
#	Line 300 | Line 300 | public class ParallelArray<T> extends Ab
300		}
301
302		/**
303	<	* Returns reduction of elements
303	>	* Returns reduction of elements.
304		* @param reducer the reducer
305		* @param base the result for an empty array
306		* @return reduction
#	Line 310 | Line 310 | public class ParallelArray<T> extends Ab
310		}
311
312		/**
313	<	* Returns a new ParallelArray holding all elements
313	>	* Returns a new ParallelArray holding all elements.
314		* @return a new ParallelArray holding all elements
315		*/
316		public ParallelArray<T> all() {
#	Line 319 | Line 319 | public class ParallelArray<T> extends Ab
319
320		/**
321		* Returns a new ParallelArray with the given element type holding
322	<	* all elements
322	>	* all elements.
323		* @param elementType the type of the elements
324		* @return a new ParallelArray holding all elements
325		*/
#	Line 353 | Line 353 | public class ParallelArray<T> extends Ab
353
354		/**
355		* Replaces elements with the results of applying the given
356	<	* mapping to each index and current element value
356	>	* mapping to each index and current element value.
357		* @param op the op
358		* @return this (to simplify use in expressions)
359		*/
#	Line 387 | Line 387 | public class ParallelArray<T> extends Ab
387
388		/**
389		* Replaces elements with results of applying
390	<	* <tt>op(thisElement, otherElement)</tt>
390	>	* {@code op(thisElement, otherElement)}.
391		* @param other the other array
392		* @param combiner the combiner
393		* @return this (to simplify use in expressions)
#	Line 401 | Line 401 | public class ParallelArray<T> extends Ab
401
402		/**
403		* Replaces elements with results of applying
404	<	* <tt>op(thisElement, otherElement)</tt>
404	>	* {@code op(thisElement, otherElement)}.
405		* @param other the other array
406		* @param combiner the combiner
407		* @return this (to simplify use in expressions)
#	Line 414 | Line 414 | public class ParallelArray<T> extends Ab
414
415		/**
416		* Returns the index of some element equal to given target,
417	<	* or -1 if not present
417	>	* or -1 if not present.
418		* @param target the element to search for
419		* @return the index or -1 if not present
420		*/
#	Line 451 | Line 451 | public class ParallelArray<T> extends Ab
451		* to locate minimum and maximum elements.
452		* @param comparator the comparator to use for
453		* locating minimum and maximum elements
454	<	* @return the summary.
454	>	* @return the summary
455		*/
456		public ParallelArray.SummaryStatistics<T> summary
457		(Comparator<? super T> comparator) {
#	Line 460 | Line 460 | public class ParallelArray<T> extends Ab
460
461		/**
462		* Returns summary statistics, assuming that all elements are
463	<	* Comparables
464	<	* @return the summary.
463	>	* Comparables.
464	>	* @return the summary
465		*/
466		public ParallelArray.SummaryStatistics<T> summary() {
467		return super.summary();
468		}
469
470		/**
471	<	* Returns the minimum element, or null if empty
471	>	* Returns the minimum element, or null if empty.
472		* @param comparator the comparator
473		* @return minimum element, or null if empty
474		*/
#	Line 478 | Line 478 | public class ParallelArray<T> extends Ab
478
479		/**
480		* Returns the minimum element, or null if empty,
481	<	* assuming that all elements are Comparables
481	>	* assuming that all elements are Comparables.
482		* @return minimum element, or null if empty
483	<	* @throws ClassCastException if any element is not Comparable.
483	>	* @throws ClassCastException if any element is not Comparable
484		*/
485		public T min() {
486		return super.min();
487		}
488
489		/**
490	<	* Returns the maximum element, or null if empty
490	>	* Returns the maximum element, or null if empty.
491		* @param comparator the comparator
492		* @return maximum element, or null if empty
493		*/
#	Line 496 | Line 496 | public class ParallelArray<T> extends Ab
496		}
497
498		/**
499	<	* Returns the maximum element, or null if empty
500	<	* assuming that all elements are Comparables
499	>	* Returns the maximum element, or null if empty,
500	>	* assuming that all elements are Comparables.
501		* @return maximum element, or null if empty
502	<	* @throws ClassCastException if any element is not Comparable.
502	>	* @throws ClassCastException if any element is not Comparable
503		*/
504		public T max() {
505		return super.max();
#	Line 508 | Line 508 | public class ParallelArray<T> extends Ab
508		/**
509		* Replaces each element with the running cumulation of applying
510		* the given reducer. For example, if the contents are the numbers
511	<	* <tt>1, 2, 3</tt>, and the reducer operation adds numbers, then
512	<	* after invocation of this method, the contents would be <tt>1,
513	<	* 3, 6</tt> (that is, <tt>1, 1+2, 1+2+3</tt>);
511	>	* {@code 1, 2, 3}, and the reducer operation adds numbers, then
512	>	* after invocation of this method, the contents would be {@code 1,
513	>	* 3, 6} (that is, {@code 1, 1+2, 1+2+3}).
514		* @param reducer the reducer
515		* @param base the result for an empty array
516		* @return this (to simplify use in expressions)
#	Line 523 | Line 523 | public class ParallelArray<T> extends Ab
523		/**
524		* Replaces each element with the cumulation of applying the given
525		* reducer to all previous values, and returns the total
526	<	* reduction. For example, if the contents are the numbers <tt>1,
527	<	* 2, 3</tt>, and the reducer operation adds numbers, then after
528	<	* invocation of this method, the contents would be <tt>0, 1,
529	<	* 3</tt> (that is, <tt>0, 0+1, 0+1+2</tt>, and the return value
530	<	* would be 6 (that is, <tt> 1+2+3</tt>);
526	>	* reduction. For example, if the contents are the numbers {@code 1,
527	>	* 2, 3}, and the reducer operation adds numbers, then after
528	>	* invocation of this method, the contents would be {@code 0, 1,
529	>	* 3} (that is, {@code 0, 0+1, 0+1+2}, and the return value
530	>	* would be 6 (that is, {@code 1+2+3}).
531		* @param reducer the reducer
532		* @param base the result for an empty array
533		* @return the total reduction
534		*/
535		public T precumulate(Reducer<T> reducer, T base) {
536	<	return (T)(super.precumulate(reducer, base));
536	>	return super.precumulate(reducer, base);
537		}
538
539		/**
#	Line 552 | Line 552 | public class ParallelArray<T> extends Ab
552		* Sorts the array, assuming all elements are Comparable. Unlike
553		* Arrays.sort, this sort does not guarantee that elements
554		* with equal keys maintain their relative position in the array.
555	–	* @throws ClassCastException if any element is not Comparable.
555		* @return this (to simplify use in expressions)
556	+	* @throws ClassCastException if any element is not Comparable
557		*/
558		public ParallelArray<T> sort() {
559		super.sort();
#	Line 563 | Line 563 | public class ParallelArray<T> extends Ab
563		/**
564		* Returns a new ParallelArray containing only the non-null unique
565		* elements of this array (that is, without any duplicates), using
566	<	* each element's <tt>equals</tt> method to test for duplication.
566	>	* each element's {@code equals} method to test for duplication.
567		* @return the new ParallelArray
568		*/
569		public ParallelArray<T> allUniqueElements() {
#	Line 658 | Line 658 | public class ParallelArray<T> extends Ab
658		}
659
660		/**
661	<	* Equivalent to <tt>asList().addAll</tt> but specialized for array
661	>	* Equivalent to {@code asList().addAll} but specialized for array
662		* arguments and likely to be more efficient.
663		* @param other the elements to add
664		* @return this (to simplify use in expressions)
#	Line 716 | Line 716 | public class ParallelArray<T> extends Ab
716		/**
717		* Returns an operation prefix that causes a method to operate
718		* only on the elements of the array for which the given selector
719	<	* returns true
719	>	* returns true.
720		* @param selector the selector
721		* @return operation prefix
722		*/
#	Line 728 | Line 728 | public class ParallelArray<T> extends Ab
728		/**
729		* Returns an operation prefix that causes a method to operate
730		* only on elements for which the given binary selector returns
731	<	* true
731	>	* true.
732		* @param selector the selector
733		* @return operation prefix
734		*/
#	Line 741 | Line 741 | public class ParallelArray<T> extends Ab
741		/**
742		* Returns an operation prefix that causes a method to operate
743		* only on elements for which the given indexed selector returns
744	<	* true
744	>	* true.
745		* @param selector the selector
746		* @return operation prefix
747		*/
#	Line 756 | Line 756 | public class ParallelArray<T> extends Ab
756		* @param op the op
757		* @return operation prefix
758		*/
759	<	public <U> ParallelArrayWithMapping<T, U> withMapping
759	>	public <U> ParallelArrayWithMapping<T,U> withMapping
760		(Op<? super T, ? extends U> op) {
761		return super.withMapping(op);
762		}
#	Line 790 | Line 790 | public class ParallelArray<T> extends Ab
790		* @param other the other array
791		* @return operation prefix
792		* @throws IllegalArgumentException if other array is a
793	<	* filtered view (all filters must precede all mappings).
793	>	* filtered view (all filters must precede all mappings)
794		*/
795		public <U,V,W> ParallelArrayWithMapping<T,V> withMapping
796		(BinaryOp<? super T, ? super U, ? extends V> combiner,
#	Line 805 | Line 805 | public class ParallelArray<T> extends Ab
805		* @param other the other array
806		* @return operation prefix
807		* @throws IllegalArgumentException if other array is a
808	<	* filtered view (all filters must precede all mappings).
808	>	* filtered view (all filters must precede all mappings)
809		*/
810		public <V> ParallelArrayWithMapping<T,V> withMapping
811		(ObjectAndDoubleToObject<? super T, ? extends V> combiner,
#	Line 820 | Line 820 | public class ParallelArray<T> extends Ab
820		* @param other the other array
821		* @return operation prefix
822		* @throws IllegalArgumentException if other array is a
823	<	* filtered view (all filters must precede all mappings).
823	>	* filtered view (all filters must precede all mappings)
824		*/
825		public <V> ParallelArrayWithMapping<T,V> withMapping
826		(ObjectAndLongToObject<? super T, ? extends V> combiner,
#	Line 835 | Line 835 | public class ParallelArray<T> extends Ab
835		* @param other the other array
836		* @return operation prefix
837		* @throws IllegalArgumentException if other array is a
838	<	* filtered view (all filters must precede all mappings).
838	>	* filtered view (all filters must precede all mappings)
839		*/
840		public <U,W> ParallelArrayWithDoubleMapping<T> withMapping
841		(ObjectAndObjectToDouble<? super T, ? super U> combiner,
#	Line 850 | Line 850 | public class ParallelArray<T> extends Ab
850		* @param other the other array
851		* @return operation prefix
852		* @throws IllegalArgumentException if other array is a
853	<	* filtered view (all filters must precede all mappings).
853	>	* filtered view (all filters must precede all mappings)
854		*/
855		public ParallelArrayWithDoubleMapping<T> withMapping
856		(ObjectAndDoubleToDouble<? super T> combiner,
#	Line 865 | Line 865 | public class ParallelArray<T> extends Ab
865		* @param other the other array
866		* @return operation prefix
867		* @throws IllegalArgumentException if other array is a
868	<	* filtered view (all filters must precede all mappings).
868	>	* filtered view (all filters must precede all mappings)
869		*/
870		public ParallelArrayWithDoubleMapping<T> withMapping
871		(ObjectAndLongToDouble<? super T> combiner,
#	Line 880 | Line 880 | public class ParallelArray<T> extends Ab
880		* @param other the other array
881		* @return operation prefix
882		* @throws IllegalArgumentException if other array is a
883	<	* filtered view (all filters must precede all mappings).
883	>	* filtered view (all filters must precede all mappings)
884		*/
885		public <U,W> ParallelArrayWithLongMapping<T> withMapping
886		(ObjectAndObjectToLong<? super T, ? super U> combiner,
#	Line 895 | Line 895 | public class ParallelArray<T> extends Ab
895		* @param other the other array
896		* @return operation prefix
897		* @throws IllegalArgumentException if other array is a
898	<	* filtered view (all filters must precede all mappings).
898	>	* filtered view (all filters must precede all mappings)
899		*/
900		public ParallelArrayWithLongMapping<T> withMapping
901		(ObjectAndDoubleToLong<? super T> combiner,
#	Line 910 | Line 910 | public class ParallelArray<T> extends Ab
910		* @param other the other array
911		* @return operation prefix
912		* @throws IllegalArgumentException if other array is a
913	<	* filtered view (all filters must precede all mappings).
913	>	* filtered view (all filters must precede all mappings)
914		*/
915		public ParallelArrayWithLongMapping<T> withMapping
916		(ObjectAndLongToLong<? super T> combiner,
#	Line 964 | Line 964 | public class ParallelArray<T> extends Ab
964		* Returns an iterator stepping through each element of the array
965		* up to the current limit. This iterator does <em>not</em>
966		* support the remove operation. However, a full
967	<	* <tt>ListIterator</tt> supporting add, remove, and set
967	>	* {@code ListIterator} supporting add, remove, and set
968		* operations is available via {@link #asList}.
969	<	* @return an iterator stepping through each element.
969	>	* @return an iterator stepping through each element
970		*/
971		public Iterator<T> iterator() {
972		return new ParallelArrayIterator<T>(array, fence);
#	Line 1018 | Line 1018 | public class ParallelArray<T> extends Ab
1018		public int size() { return fence; }
1019
1020		/**
1021	<	* Returns the element of the array at the given index
1021	>	* Returns the element of the array at the given index.
1022		* @param i the index
1023		* @return the element of the array at the given index
1024		*/
1025		public T get(int i) { return array[i]; }
1026
1027		/**
1028	<	* Sets the element of the array at the given index to the given value
1028	>	* Sets the element of the array at the given index to the given value.
1029		* @param i the index
1030		* @param x the value
1031		*/
1032		public void set(int i, T x) { array[i] = x; }
1033
1034		/**
1035	<	* Returns the underlying array used for computations
1035	>	* Returns the underlying array used for computations.
1036		* @return the array
1037		*/
1038		public T[] getArray() { return array; }
1039
1040		/**
1041	<	* Equivalent to <tt>asList().toString()</tt>
1041	>	* Equivalent to {@code asList().toString()}.
1042		* @return a string representation
1043		*/
1044		public String toString() {
#	Line 1053 | Line 1053 | public class ParallelArray<T> extends Ab
1053		* than the length of the underlying array, causes computations to
1054		* ignore elements past the given limit.
1055		* @param newLimit the new upper bound
1056	<	* @throws IllegalArgumentException if newLimit less than zero.
1056	>	* @throws IllegalArgumentException if newLimit less than zero
1057		*/
1058		public final void setLimit(int newLimit) {
1059		if (newLimit < 0)
#	Line 1353 | Line 1353 | public class ParallelArray<T> extends Ab
1353		return a;
1354		}
1355
1356	<	public <V> V[] toArray(V a[]) {
1356	>	public <V> V[] toArray(V[] a) {
1357		int len = fence;
1358		if (a.length < len) {
1359		Class elementType = a.getClass().getComponentType();

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines
>	Changed lines