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.1 by dl, Tue Jan 6 14:30:57 2009 UTC vs.
Revision 1.17 by jsr166, Mon Nov 4 00:00:39 2013 UTC

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

Diff Legend

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