ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/jsr166y/forkjoin/PAS.java
Revision: 1.10
Committed: Tue Jan 6 14:34:59 2009 UTC (15 years, 5 months ago) by dl
Branch: MAIN
CVS Tags: HEAD
Changes since 1.9: +0 -0 lines
State: FILE REMOVED
Log Message: 
Repackaging

File Contents

# User Rev Content
1 dl 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
5     */
6    
7     package jsr166y.forkjoin;
8     import static jsr166y.forkjoin.Ops.*;
9     import java.util.*;
10     import java.util.concurrent.atomic.*;
11     import java.lang.reflect.Array;
12    
13     /**
14 dl 1.4 * Shared internal execution support for ParallelArray and
15     * specializations.
16 dl 1.1 */
17     class PAS {
18     private PAS() {} // all-static, non-instantiable
19    
20     /** Global default executor */
21 dl 1.3 private static volatile ForkJoinPool defaultExecutor;
22 dl 1.1 /** Lock for on-demand initialization of defaultExecutor */
23     private static final Object poolLock = new Object();
24 jsr166 1.7
25 dl 1.1 static ForkJoinExecutor defaultExecutor() {
26 dl 1.3 ForkJoinPool p = defaultExecutor; // double-check
27     if (p == null) {
28     synchronized(poolLock) {
29     p = defaultExecutor;
30     if (p == null) {
31     // use ceil(7/8 * ncpus)
32     int nprocs = Runtime.getRuntime().availableProcessors();
33     int nthreads = nprocs - (nprocs >>> 3);
34     defaultExecutor = p = new ForkJoinPool(nthreads);
35     }
36 dl 1.1 }
37     }
38 dl 1.3 return p;
39 dl 1.1 }
40    
41     /**
42     * Base for most divide-and-conquer tasks used for computing
43     * ParallelArray operations. Rather than pure recursion, it links
44     * right-hand-sides and then joins up the tree, exploiting cases
45     * where tasks aren't stolen. This generates and joins tasks with
46     * a bit less overhead than pure recursive style -- there are only
47     * as many tasks as leaves (no strictly internal nodes).
48     *
49 dl 1.4 * Split control relies on pap.getThreshold(), which is
50 dl 1.3 * expected to err on the side of generating too many tasks. To
51 dl 1.6 * counterbalance, if a task pops off its own smallest subtask, it
52     * directly runs its leaf action rather than possibly resplitting.
53 dl 1.1 *
54     * There are, with a few exceptions, three flavors of each FJBase
55 dl 1.2 * subclass, prefixed FJO (object reference), FJD (double) and FJL
56 jsr166 1.7 * (long).
57 dl 1.1 */
58     static abstract class FJBase extends RecursiveAction {
59 dl 1.4 final AbstractParallelAnyArray pap;
60 dl 1.1 final int lo;
61     final int hi;
62     final FJBase next; // the next task that creator should join
63 dl 1.4 FJBase(AbstractParallelAnyArray pap, int lo, int hi, FJBase next) {
64     this.pap = pap;
65 dl 1.1 this.lo = lo;
66     this.hi = hi;
67     this.next = next;
68     }
69    
70     public final void compute() {
71 dl 1.4 int g = pap.getThreshold();
72 dl 1.1 int l = lo;
73     int h = hi;
74 jsr166 1.7 if (h - l > g)
75 dl 1.3 internalCompute(l, h, g);
76     else
77     atLeaf(l, h);
78     }
79    
80     final void internalCompute(int l, int h, int g) {
81     FJBase r = null;
82     do {
83 dl 1.1 int rh = h;
84     h = (l + h) >>> 1;
85     (r = newSubtask(h, rh, r)).fork();
86 dl 1.3 } while (h - l > g);
87 dl 1.1 atLeaf(l, h);
88 dl 1.9 while (ForkJoinWorkerThread.removeIfNextLocalTask(r)) {
89     r.atLeaf(r.lo, r.hi);
90     onReduce(r);
91     if ((r = r.next) == null)
92     return;
93     }
94 dl 1.3 do {
95 dl 1.9 r.join();
96 dl 1.1 onReduce(r);
97     r = r.next;
98 dl 1.3 } while (r != null);
99 dl 1.1 }
100    
101     /** Leaf computation */
102     abstract void atLeaf(int l, int h);
103     /** Operation performed after joining right subtask -- default noop */
104     void onReduce(FJBase right) {}
105     /** Factory method to create new subtask, normally of current type */
106     abstract FJBase newSubtask(int l, int h, FJBase r);
107     }
108    
109     // apply
110    
111 dl 1.2 static final class FJOApply extends FJBase {
112 dl 1.1 final Procedure procedure;
113 dl 1.4 FJOApply(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
114 dl 1.1 Procedure procedure) {
115 dl 1.4 super(pap, lo, hi, next);
116 dl 1.1 this.procedure = procedure;
117     }
118     FJBase newSubtask(int l, int h, FJBase r) {
119 dl 1.4 return new FJOApply(pap, l, h, r, procedure);
120 dl 1.1 }
121     void atLeaf(int l, int h) {
122 dl 1.4 pap.leafApply(l, h, procedure);
123 dl 1.1 }
124     }
125    
126     static final class FJDApply extends FJBase {
127     final DoubleProcedure procedure;
128 dl 1.4 FJDApply(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
129 dl 1.1 DoubleProcedure procedure) {
130 dl 1.4 super(pap, lo, hi, next);
131 dl 1.1 this.procedure = procedure;
132     }
133     FJBase newSubtask(int l, int h, FJBase r) {
134 dl 1.4 return new FJDApply(pap, l, h, r, procedure);
135 dl 1.1 }
136     void atLeaf(int l, int h) {
137 dl 1.4 pap.leafApply(l, h, procedure);
138 dl 1.1 }
139     }
140    
141     static final class FJLApply extends FJBase {
142     final LongProcedure procedure;
143 dl 1.4 FJLApply(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
144 dl 1.1 LongProcedure procedure) {
145 dl 1.4 super(pap, lo, hi, next);
146 dl 1.1 this.procedure = procedure;
147     }
148     FJBase newSubtask(int l, int h, FJBase r) {
149 dl 1.4 return new FJLApply(pap, l, h, r, procedure);
150 dl 1.1 }
151     void atLeaf(int l, int h) {
152 dl 1.4 pap.leafApply(l, h, procedure);
153 dl 1.1 }
154     }
155    
156     // reduce
157    
158 dl 1.2 static final class FJOReduce extends FJBase {
159 dl 1.1 final Reducer reducer;
160     Object result;
161 dl 1.4 FJOReduce(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
162 dl 1.1 Reducer reducer, Object base) {
163 dl 1.4 super(pap, lo, hi, next);
164 dl 1.1 this.reducer = reducer;
165     this.result = base;
166     }
167     FJBase newSubtask(int l, int h, FJBase r) {
168 dl 1.4 return new FJOReduce(pap, l, h, r, reducer, result);
169 dl 1.1 }
170     void atLeaf(int l, int h) {
171 dl 1.4 result = pap.leafReduce(l, h, reducer, result);
172 dl 1.1 }
173     void onReduce(FJBase right) {
174 dl 1.2 result = reducer.op(result, ((FJOReduce)right).result);
175 dl 1.1 }
176     }
177    
178     static final class FJDReduce extends FJBase {
179     final DoubleReducer reducer;
180     double result;
181 dl 1.4 FJDReduce(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
182 dl 1.1 DoubleReducer reducer, double base) {
183 dl 1.4 super(pap, lo, hi, next);
184 dl 1.1 this.reducer = reducer;
185     this.result = base;
186     }
187     FJBase newSubtask(int l, int h, FJBase r) {
188 dl 1.4 return new FJDReduce(pap, l, h, r, reducer, result);
189 dl 1.1 }
190     void atLeaf(int l, int h) {
191 dl 1.4 result = pap.leafReduce(l, h, reducer, result);
192 dl 1.1 }
193     void onReduce(FJBase right) {
194 dl 1.2 result = reducer.op(result, ((FJDReduce)right).result);
195 dl 1.1 }
196     }
197    
198     static final class FJLReduce extends FJBase {
199     final LongReducer reducer;
200     long result;
201 dl 1.4 FJLReduce(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
202 dl 1.1 LongReducer reducer, long base) {
203 dl 1.4 super(pap, lo, hi, next);
204 dl 1.1 this.reducer = reducer;
205     this.result = base;
206     }
207     FJBase newSubtask(int l, int h, FJBase r) {
208 dl 1.4 return new FJLReduce(pap, l, h, r, reducer, result);
209 dl 1.1 }
210     void atLeaf(int l, int h) {
211 dl 1.4 result = pap.leafReduce(l, h, reducer, result);
212 dl 1.1 }
213     void onReduce(FJBase right) {
214 dl 1.2 result = reducer.op(result, ((FJLReduce)right).result);
215 dl 1.1 }
216     }
217    
218     // map
219    
220 dl 1.2 static final class FJOMap extends FJBase {
221 dl 1.1 final Object[] dest;
222     final int offset;
223 dl 1.4 FJOMap(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
224     Object[] dest, int offset) {
225     super(pap, lo, hi, next);
226 dl 1.1 this.dest = dest;
227     this.offset = offset;
228     }
229     FJBase newSubtask(int l, int h, FJBase r) {
230 dl 1.4 return new FJOMap(pap, l, h, r, dest, offset);
231 dl 1.1 }
232     void atLeaf(int l, int h) {
233 dl 1.5 pap.leafTransfer(l, h, dest, l + offset);
234 dl 1.1 }
235     }
236    
237     static final class FJDMap extends FJBase {
238     final double[] dest;
239     final int offset;
240 jsr166 1.7 FJDMap(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
241 dl 1.4 double[] dest, int offset) {
242     super(pap, lo, hi, next);
243 dl 1.1 this.dest = dest;
244     this.offset = offset;
245     }
246     FJBase newSubtask(int l, int h, FJBase r) {
247 dl 1.4 return new FJDMap(pap, l, h, r, dest, offset);
248 dl 1.1 }
249     void atLeaf(int l, int h) {
250 dl 1.5 pap.leafTransfer(l, h, dest, l + offset);
251 dl 1.1 }
252     }
253    
254     static final class FJLMap extends FJBase {
255     final long[] dest;
256     final int offset;
257 jsr166 1.7 FJLMap(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
258 dl 1.4 long[] dest, int offset) {
259     super(pap, lo, hi, next);
260 dl 1.1 this.dest = dest;
261     this.offset = offset;
262     }
263     FJBase newSubtask(int l, int h, FJBase r) {
264 dl 1.4 return new FJLMap(pap, l, h, r, dest, offset);
265 dl 1.1 }
266     void atLeaf(int l, int h) {
267 dl 1.5 pap.leafTransfer(l, h, dest, l + offset);
268 dl 1.1 }
269     }
270    
271     // transform
272    
273 dl 1.2 static final class FJOTransform extends FJBase {
274     final Op op;
275 dl 1.4 FJOTransform(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
276 dl 1.2 Op op) {
277 dl 1.4 super(pap, lo, hi, next);
278 dl 1.2 this.op = op;
279 dl 1.1 }
280     FJBase newSubtask(int l, int h, FJBase r) {
281 dl 1.4 return new FJOTransform(pap, l, h, r, op);
282 dl 1.1 }
283     void atLeaf(int l, int h) {
284 dl 1.4 pap.leafTransform(l, h, op);
285 dl 1.1 }
286     }
287    
288     static final class FJDTransform extends FJBase {
289 dl 1.2 final DoubleOp op;
290 dl 1.4 FJDTransform(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
291 dl 1.2 DoubleOp op) {
292 dl 1.4 super(pap, lo, hi, next);
293 dl 1.2 this.op = op;
294 dl 1.1 }
295     FJBase newSubtask(int l, int h, FJBase r) {
296 dl 1.4 return new FJDTransform(pap, l, h, r, op);
297 dl 1.1 }
298     void atLeaf(int l, int h) {
299 dl 1.4 pap.leafTransform(l, h, op);
300 dl 1.1 }
301     }
302    
303     static final class FJLTransform extends FJBase {
304 dl 1.2 final LongOp op;
305 dl 1.4 FJLTransform(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
306 dl 1.2 LongOp op) {
307 dl 1.4 super(pap, lo, hi, next);
308 dl 1.2 this.op = op;
309 dl 1.1 }
310     FJBase newSubtask(int l, int h, FJBase r) {
311 dl 1.4 return new FJLTransform(pap, l, h, r, op);
312 dl 1.1 }
313     void atLeaf(int l, int h) {
314 dl 1.4 pap.leafTransform(l, h, op);
315 dl 1.1 }
316     }
317    
318     // index map
319    
320 dl 1.2 static final class FJOIndexMap extends FJBase {
321     final IntToObject op;
322 dl 1.4 FJOIndexMap(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
323 dl 1.2 IntToObject op) {
324 dl 1.4 super(pap, lo, hi, next);
325 dl 1.2 this.op = op;
326 dl 1.1 }
327     FJBase newSubtask(int l, int h, FJBase r) {
328 dl 1.4 return new FJOIndexMap(pap, l, h, r, op);
329 dl 1.1 }
330     void atLeaf(int l, int h) {
331 dl 1.4 pap.leafIndexMap(l, h, op);
332 dl 1.1 }
333     }
334    
335     static final class FJDIndexMap extends FJBase {
336 dl 1.2 final IntToDouble op;
337 dl 1.4 FJDIndexMap(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
338 dl 1.2 IntToDouble op) {
339 dl 1.4 super(pap, lo, hi, next);
340 dl 1.2 this.op = op;
341 dl 1.1 }
342     FJBase newSubtask(int l, int h, FJBase r) {
343 dl 1.4 return new FJDIndexMap(pap, l, h, r, op);
344 dl 1.1 }
345     void atLeaf(int l, int h) {
346 dl 1.4 pap.leafIndexMap(l, h, op);
347 dl 1.1 }
348     }
349    
350     static final class FJLIndexMap extends FJBase {
351 dl 1.2 final IntToLong op;
352 dl 1.4 FJLIndexMap(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
353 dl 1.2 IntToLong op) {
354 dl 1.4 super(pap, lo, hi, next);
355 dl 1.2 this.op = op;
356 dl 1.1 }
357     FJBase newSubtask(int l, int h, FJBase r) {
358 dl 1.4 return new FJLIndexMap(pap, l, h, r, op);
359 dl 1.1 }
360     void atLeaf(int l, int h) {
361 dl 1.4 pap.leafIndexMap(l, h, op);
362 dl 1.1 }
363     }
364    
365 dl 1.3 // binary index map
366    
367     static final class FJOBinaryIndexMap extends FJBase {
368     final IntAndObjectToObject op;
369 jsr166 1.7 FJOBinaryIndexMap(AbstractParallelAnyArray pap, int lo, int hi,
370 dl 1.4 FJBase next, IntAndObjectToObject op) {
371     super(pap, lo, hi, next);
372 dl 1.3 this.op = op;
373     }
374     FJBase newSubtask(int l, int h, FJBase r) {
375 dl 1.4 return new FJOBinaryIndexMap(pap, l, h, r, op);
376 dl 1.3 }
377     void atLeaf(int l, int h) {
378 dl 1.4 pap.leafBinaryIndexMap(l, h, op);
379 dl 1.3 }
380     }
381    
382     static final class FJDBinaryIndexMap extends FJBase {
383     final IntAndDoubleToDouble op;
384 jsr166 1.7 FJDBinaryIndexMap(AbstractParallelAnyArray pap, int lo, int hi,
385 dl 1.4 FJBase next, IntAndDoubleToDouble op) {
386     super(pap, lo, hi, next);
387 dl 1.3 this.op = op;
388     }
389     FJBase newSubtask(int l, int h, FJBase r) {
390 dl 1.4 return new FJDBinaryIndexMap(pap, l, h, r, op);
391 dl 1.3 }
392     void atLeaf(int l, int h) {
393 dl 1.4 pap.leafBinaryIndexMap(l, h, op);
394 dl 1.3 }
395     }
396    
397     static final class FJLBinaryIndexMap extends FJBase {
398     final IntAndLongToLong op;
399 jsr166 1.7 FJLBinaryIndexMap(AbstractParallelAnyArray pap, int lo, int hi,
400 dl 1.4 FJBase next, IntAndLongToLong op) {
401     super(pap, lo, hi, next);
402 dl 1.3 this.op = op;
403     }
404     FJBase newSubtask(int l, int h, FJBase r) {
405 dl 1.4 return new FJLBinaryIndexMap(pap, l, h, r, op);
406 dl 1.3 }
407     void atLeaf(int l, int h) {
408 dl 1.4 pap.leafBinaryIndexMap(l, h, op);
409 dl 1.3 }
410     }
411    
412    
413 dl 1.1 // generate
414    
415 dl 1.2 static final class FJOGenerate extends FJBase {
416 dl 1.1 final Generator generator;
417 dl 1.4 FJOGenerate(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
418 dl 1.1 Generator generator) {
419 dl 1.4 super(pap, lo, hi, next);
420 dl 1.1 this.generator = generator;
421     }
422     FJBase newSubtask(int l, int h, FJBase r) {
423 dl 1.4 return new FJOGenerate(pap, l, h, r, generator);
424 dl 1.1 }
425     void atLeaf(int l, int h) {
426 dl 1.4 pap.leafGenerate(l, h, generator);
427 dl 1.1 }
428     }
429    
430     static final class FJDGenerate extends FJBase {
431     final DoubleGenerator generator;
432 dl 1.4 FJDGenerate(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
433 dl 1.1 DoubleGenerator generator) {
434 dl 1.4 super(pap, lo, hi, next);
435 dl 1.1 this.generator = generator;
436     }
437     FJBase newSubtask(int l, int h, FJBase r) {
438 dl 1.4 return new FJDGenerate(pap, l, h, r, generator);
439 dl 1.1 }
440     void atLeaf(int l, int h) {
441 dl 1.4 pap.leafGenerate(l, h, generator);
442 dl 1.1 }
443     }
444    
445     static final class FJLGenerate extends FJBase {
446     final LongGenerator generator;
447 dl 1.4 FJLGenerate(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
448 dl 1.1 LongGenerator generator) {
449 dl 1.4 super(pap, lo, hi, next);
450 dl 1.1 this.generator = generator;
451     }
452     FJBase newSubtask(int l, int h, FJBase r) {
453 dl 1.4 return new FJLGenerate(pap, l, h, r, generator);
454 dl 1.1 }
455     void atLeaf(int l, int h) {
456 dl 1.4 pap.leafGenerate(l, h, generator);
457 dl 1.1 }
458     }
459    
460     // fill
461    
462 dl 1.2 static final class FJOFill extends FJBase {
463 dl 1.1 final Object value;
464 jsr166 1.7 FJOFill(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
465 dl 1.4 Object value) {
466     super(pap, lo, hi, next);
467 dl 1.1 this.value = value;
468     }
469     FJBase newSubtask(int l, int h, FJBase r) {
470 dl 1.4 return new FJOFill(pap, l, h, r, value);
471 dl 1.1 }
472     void atLeaf(int l, int h) {
473 dl 1.4 pap.leafFill(l, h, value);
474 dl 1.1 }
475     }
476    
477     static final class FJDFill extends FJBase {
478     final double value;
479 jsr166 1.7 FJDFill(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
480 dl 1.4 double value) {
481     super(pap, lo, hi, next);
482 dl 1.1 this.value = value;
483     }
484     FJBase newSubtask(int l, int h, FJBase r) {
485 dl 1.4 return new FJDFill(pap, l, h, r, value);
486 dl 1.1 }
487     void atLeaf(int l, int h) {
488 dl 1.4 pap.leafFill(l, h, value);
489 dl 1.1 }
490     }
491    
492     static final class FJLFill extends FJBase {
493     final long value;
494 jsr166 1.7 FJLFill(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
495 dl 1.4 long value) {
496     super(pap, lo, hi, next);
497 dl 1.1 this.value = value;
498     }
499     FJBase newSubtask(int l, int h, FJBase r) {
500 dl 1.4 return new FJLFill(pap, l, h, r, value);
501 dl 1.1 }
502     void atLeaf(int l, int h) {
503 dl 1.4 pap.leafFill(l, h, value);
504 dl 1.1 }
505     }
506    
507     // combine in place
508    
509 dl 1.2 static final class FJOCombineInPlace extends FJBase {
510 dl 1.1 final Object[] other;
511     final int otherOffset;
512 dl 1.2 final BinaryOp combiner;
513 jsr166 1.7 FJOCombineInPlace(AbstractParallelAnyArray pap, int lo, int hi,
514 dl 1.4 FJBase next, Object[] other, int otherOffset,
515 dl 1.2 BinaryOp combiner) {
516 dl 1.4 super(pap, lo, hi, next);
517 dl 1.1 this.other = other;
518     this.otherOffset = otherOffset;
519     this.combiner = combiner;
520     }
521     FJBase newSubtask(int l, int h, FJBase r) {
522 dl 1.2 return new FJOCombineInPlace
523 dl 1.4 (pap, l, h, r, other, otherOffset, combiner);
524 dl 1.1 }
525     void atLeaf(int l, int h) {
526 dl 1.4 pap.leafCombineInPlace(l, h, other, otherOffset, combiner);
527 dl 1.1 }
528     }
529    
530     static final class FJDCombineInPlace extends FJBase {
531     final double[] other;
532     final int otherOffset;
533 dl 1.2 final BinaryDoubleOp combiner;
534 jsr166 1.7 FJDCombineInPlace(AbstractParallelAnyArray pap, int lo, int hi,
535 dl 1.4 FJBase next, double[] other, int otherOffset,
536 dl 1.2 BinaryDoubleOp combiner) {
537 dl 1.4 super(pap, lo, hi, next);
538 dl 1.1 this.other = other;
539     this.otherOffset = otherOffset;
540     this.combiner = combiner;
541     }
542     FJBase newSubtask(int l, int h, FJBase r) {
543     return new FJDCombineInPlace
544 dl 1.4 (pap, l, h, r, other, otherOffset, combiner);
545 dl 1.1 }
546     void atLeaf(int l, int h) {
547 dl 1.4 pap.leafCombineInPlace(l, h, other, otherOffset, combiner);
548 dl 1.1 }
549     }
550    
551     static final class FJLCombineInPlace extends FJBase {
552     final long[] other;
553     final int otherOffset;
554 dl 1.2 final BinaryLongOp combiner;
555 jsr166 1.7 FJLCombineInPlace(AbstractParallelAnyArray pap, int lo, int hi,
556 dl 1.4 FJBase next, long[] other, int otherOffset,
557 dl 1.2 BinaryLongOp combiner) {
558 dl 1.4 super(pap, lo, hi, next);
559 dl 1.1 this.other = other;
560     this.otherOffset = otherOffset;
561     this.combiner = combiner;
562     }
563     FJBase newSubtask(int l, int h, FJBase r) {
564     return new FJLCombineInPlace
565 dl 1.4 (pap, l, h, r, other, otherOffset, combiner);
566 dl 1.1 }
567     void atLeaf(int l, int h) {
568 dl 1.4 pap.leafCombineInPlace(l, h, other, otherOffset, combiner);
569 dl 1.1 }
570     }
571    
572 dl 1.3 static final class FJOPACombineInPlace extends FJBase {
573 dl 1.4 final ParallelArrayWithMapping other;
574 dl 1.3 final int otherOffset;
575     final BinaryOp combiner;
576 jsr166 1.7 FJOPACombineInPlace(AbstractParallelAnyArray pap, int lo, int hi,
577 dl 1.4 FJBase next,
578     ParallelArrayWithMapping other, int otherOffset,
579     BinaryOp combiner) {
580     super(pap, lo, hi, next);
581 dl 1.3 this.other = other;
582     this.otherOffset = otherOffset;
583     this.combiner = combiner;
584     }
585     FJBase newSubtask(int l, int h, FJBase r) {
586     return new FJOPACombineInPlace
587 dl 1.4 (pap, l, h, r, other, otherOffset, combiner);
588 dl 1.3 }
589     void atLeaf(int l, int h) {
590 dl 1.4 pap.leafCombineInPlace(l, h, other, otherOffset, combiner);
591 dl 1.3 }
592     }
593    
594     static final class FJDPACombineInPlace extends FJBase {
595 dl 1.4 final ParallelDoubleArrayWithDoubleMapping other;
596 dl 1.3 final int otherOffset;
597     final BinaryDoubleOp combiner;
598 jsr166 1.7 FJDPACombineInPlace(AbstractParallelAnyArray pap, int lo, int hi,
599     FJBase next,
600     ParallelDoubleArrayWithDoubleMapping other,
601 dl 1.4 int otherOffset, BinaryDoubleOp combiner) {
602     super(pap, lo, hi, next);
603 dl 1.3 this.other = other;
604     this.otherOffset = otherOffset;
605     this.combiner = combiner;
606     }
607     FJBase newSubtask(int l, int h, FJBase r) {
608     return new FJDPACombineInPlace
609 dl 1.4 (pap, l, h, r, other, otherOffset, combiner);
610 dl 1.3 }
611     void atLeaf(int l, int h) {
612 dl 1.4 pap.leafCombineInPlace(l, h, other, otherOffset, combiner);
613 dl 1.3 }
614     }
615    
616     static final class FJLPACombineInPlace extends FJBase {
617 dl 1.4 final ParallelLongArrayWithLongMapping other;
618 dl 1.3 final int otherOffset;
619     final BinaryLongOp combiner;
620 jsr166 1.7 FJLPACombineInPlace(AbstractParallelAnyArray pap, int lo, int hi,
621 dl 1.4 FJBase next,
622 jsr166 1.7 ParallelLongArrayWithLongMapping other,
623 dl 1.4 int otherOffset, BinaryLongOp combiner) {
624     super(pap, lo, hi, next);
625 dl 1.3 this.other = other;
626     this.otherOffset = otherOffset;
627     this.combiner = combiner;
628     }
629     FJBase newSubtask(int l, int h, FJBase r) {
630     return new FJLPACombineInPlace
631 dl 1.4 (pap, l, h, r, other, otherOffset, combiner);
632 dl 1.3 }
633     void atLeaf(int l, int h) {
634 dl 1.4 pap.leafCombineInPlace(l, h, other, otherOffset, combiner);
635 dl 1.3 }
636     }
637    
638 dl 1.1 // stats
639    
640 dl 1.2 static final class FJOStats extends FJBase
641 dl 1.1 implements ParallelArray.SummaryStatistics {
642     final Comparator comparator;
643     public int size() { return size; }
644     public Object min() { return min; }
645     public Object max() { return max; }
646     public int indexOfMin() { return indexOfMin; }
647     public int indexOfMax() { return indexOfMax; }
648     int size;
649     Object min;
650     Object max;
651     int indexOfMin;
652     int indexOfMax;
653 dl 1.4 FJOStats(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
654 dl 1.1 Comparator comparator) {
655 dl 1.4 super(pap, lo, hi, next);
656 dl 1.1 this.comparator = comparator;
657     this.indexOfMin = -1;
658     this.indexOfMax = -1;
659     }
660     FJBase newSubtask(int l, int h, FJBase r) {
661 dl 1.4 return new FJOStats(pap, l, h, r, comparator);
662 dl 1.1 }
663     void onReduce(FJBase right) {
664 dl 1.2 FJOStats r = (FJOStats)right;
665 dl 1.1 size += r.size;
666     updateMin(r.indexOfMin, r.min);
667     updateMax(r.indexOfMax, r.max);
668     }
669     void updateMin(int i, Object x) {
670     if (i >= 0 &&
671     (indexOfMin < 0 || comparator.compare(min, x) > 0)) {
672     min = x;
673     indexOfMin = i;
674     }
675     }
676     void updateMax(int i, Object x) {
677     if (i >= 0 &&
678     (indexOfMax < 0 || comparator.compare(max, x) < 0)) {
679     max = x;
680     indexOfMax = i;
681     }
682     }
683    
684 dl 1.2 void atLeaf(int l, int h) {
685 jsr166 1.7 if (pap.hasFilter())
686 dl 1.2 filteredAtLeaf(l, h);
687 dl 1.4 else {
688     size = h - l;
689     for (int i = l; i < h; ++i) {
690     Object x = pap.oget(i);
691     updateMin(i, x);
692     updateMax(i, x);
693     }
694 dl 1.2 }
695     }
696    
697     void filteredAtLeaf(int l, int h) {
698     for (int i = l; i < h; ++i) {
699 dl 1.4 if (pap.isSelected(i)) {
700     Object x = pap.oget(i);
701 dl 1.2 ++size;
702     updateMin(i, x);
703     updateMax(i, x);
704     }
705     }
706     }
707    
708 dl 1.1 public String toString() {
709     return
710     "size: " + size +
711     " min: " + min + " (index " + indexOfMin +
712     ") max: " + max + " (index " + indexOfMax + ")";
713     }
714    
715     }
716    
717     static final class FJDStats extends FJBase
718     implements ParallelDoubleArray.SummaryStatistics {
719     final DoubleComparator comparator;
720     public int size() { return size; }
721     public double min() { return min; }
722     public double max() { return max; }
723     public double sum() { return sum; }
724     public double average() { return sum / size; }
725     public int indexOfMin() { return indexOfMin; }
726     public int indexOfMax() { return indexOfMax; }
727     int size;
728     double min;
729     double max;
730     double sum;
731     int indexOfMin;
732     int indexOfMax;
733 dl 1.4 FJDStats(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
734 dl 1.1 DoubleComparator comparator) {
735 dl 1.4 super(pap, lo, hi, next);
736 dl 1.1 this.comparator = comparator;
737     this.indexOfMin = -1;
738     this.indexOfMax = -1;
739     this.min = Double.MAX_VALUE;
740     this.max = -Double.MAX_VALUE;
741     }
742     FJBase newSubtask(int l, int h, FJBase r) {
743 dl 1.4 return new FJDStats(pap, l, h, r, comparator);
744 dl 1.1 }
745     void onReduce(FJBase right) {
746     FJDStats r = (FJDStats)right;
747     size += r.size;
748     sum += r.sum;
749     updateMin(r.indexOfMin, r.min);
750     updateMax(r.indexOfMax, r.max);
751     }
752     void updateMin(int i, double x) {
753     if (i >= 0 &&
754     (indexOfMin < 0 || comparator.compare(min, x) > 0)) {
755     min = x;
756     indexOfMin = i;
757     }
758     }
759     void updateMax(int i, double x) {
760     if (i >= 0 &&
761     (indexOfMax < 0 || comparator.compare(max, x) < 0)) {
762     max = x;
763     indexOfMax = i;
764     }
765     }
766 dl 1.4 void atLeaf(int l, int h) {
767 jsr166 1.7 if (pap.hasFilter())
768 dl 1.2 filteredAtLeaf(l, h);
769 dl 1.4 else {
770     size = h - l;
771     for (int i = l; i < h; ++i) {
772     double x = pap.dget(i);
773     sum += x;
774     updateMin(i, x);
775     updateMax(i, x);
776     }
777 dl 1.2 }
778     }
779    
780     void filteredAtLeaf(int l, int h) {
781     for (int i = l; i < h; ++i) {
782 dl 1.4 if (pap.isSelected(i)) {
783     double x = pap.dget(i);
784 dl 1.2 ++size;
785     sum += x;
786     updateMin(i, x);
787     updateMax(i, x);
788     }
789     }
790     }
791    
792 dl 1.1 public String toString() {
793     return
794     "size: " + size +
795     " min: " + min + " (index " + indexOfMin +
796     ") max: " + max + " (index " + indexOfMax +
797     ") sum: " + sum;
798     }
799     }
800    
801     static final class FJLStats extends FJBase
802     implements ParallelLongArray.SummaryStatistics {
803     final LongComparator comparator;
804     public int size() { return size; }
805     public long min() { return min; }
806     public long max() { return max; }
807     public long sum() { return sum; }
808     public double average() { return (double)sum / size; }
809     public int indexOfMin() { return indexOfMin; }
810     public int indexOfMax() { return indexOfMax; }
811     int size;
812     long min;
813     long max;
814     long sum;
815     int indexOfMin;
816     int indexOfMax;
817 dl 1.4 FJLStats(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
818 dl 1.1 LongComparator comparator) {
819 dl 1.4 super(pap, lo, hi, next);
820 dl 1.1 this.comparator = comparator;
821     this.indexOfMin = -1;
822     this.indexOfMax = -1;
823     this.min = Long.MAX_VALUE;
824     this.max = Long.MIN_VALUE;
825     }
826     FJBase newSubtask(int l, int h, FJBase r) {
827 dl 1.4 return new FJLStats(pap, l, h, r, comparator);
828 dl 1.1 }
829     void onReduce(FJBase right) {
830     FJLStats r = (FJLStats)right;
831     size += r.size;
832     sum += r.sum;
833     updateMin(r.indexOfMin, r.min);
834     updateMax(r.indexOfMax, r.max);
835     }
836     void updateMin(int i, long x) {
837     if (i >= 0 &&
838     (indexOfMin < 0 || comparator.compare(min, x) > 0)) {
839     min = x;
840     indexOfMin = i;
841     }
842     }
843     void updateMax(int i, long x) {
844     if (i >= 0 &&
845     (indexOfMax < 0 || comparator.compare(max, x) < 0)) {
846     max = x;
847     indexOfMax = i;
848     }
849     }
850    
851 dl 1.2 void atLeaf(int l, int h) {
852 jsr166 1.7 if (pap.hasFilter())
853 dl 1.2 filteredAtLeaf(l, h);
854 dl 1.4 else {
855     size = h - l;
856     for (int i = l; i < h; ++i) {
857     long x = pap.lget(i);
858     sum += x;
859     updateMin(i, x);
860     updateMax(i, x);
861     }
862 dl 1.2 }
863     }
864    
865     void filteredAtLeaf(int l, int h) {
866     for (int i = l; i < h; ++i) {
867 dl 1.4 if (pap.isSelected(i)) {
868     long x = pap.lget(i);
869 dl 1.2 ++size;
870     sum += x;
871     updateMin(i, x);
872     updateMax(i, x);
873     }
874     }
875     }
876    
877 dl 1.1 public String toString() {
878     return
879     "size: " + size +
880     " min: " + min + " (index " + indexOfMin +
881     ") max: " + max + " (index " + indexOfMax +
882     ") sum: " + sum;
883     }
884     }
885    
886     // count
887    
888 dl 1.4 static final class FJCountSelected extends FJBase {
889 dl 1.1 int count;
890 jsr166 1.7 FJCountSelected(AbstractParallelAnyArray pap, int lo, int hi,
891 dl 1.4 FJBase next) {
892     super(pap, lo, hi, next);
893 dl 1.1 }
894     FJBase newSubtask(int l, int h, FJBase r) {
895 dl 1.4 return new FJCountSelected(pap, l, h, r);
896 dl 1.1 }
897     void onReduce(FJBase right) {
898 dl 1.4 count += ((FJCountSelected)right).count;
899 dl 1.1 }
900     void atLeaf(int l, int h) {
901 dl 1.4 int n = 0;
902     for (int i = l; i < h; ++i) {
903     if (pap.isSelected(i))
904     ++n;
905 dl 1.1 }
906 dl 1.4 count = n;
907 dl 1.1 }
908     }
909    
910     /**
911     * Base for cancellable search tasks. Same idea as FJBase
912     * but cancels tasks when result nonnegative.
913     */
914     static abstract class FJSearchBase extends RecursiveAction {
915 dl 1.4 final AbstractParallelAnyArray pap;
916 dl 1.1 final int lo;
917     final int hi;
918     final FJSearchBase next;
919     final AtomicInteger result;
920    
921 dl 1.4 FJSearchBase(AbstractParallelAnyArray pap, int lo, int hi,
922 dl 1.1 FJSearchBase next,
923     AtomicInteger result) {
924 dl 1.4 this.pap = pap;
925 dl 1.1 this.lo = lo;
926     this.hi = hi;
927     this.next = next;
928     this.result = result;
929     }
930    
931     public void compute() {
932     if (result.get() >= 0)
933     return;
934     FJSearchBase r = null;
935     int l = lo;
936     int h = hi;
937 dl 1.4 int g = pap.getThreshold();
938 dl 1.3 while (h - l > g) {
939 dl 1.1 int rh = h;
940     h = (l + h) >>> 1;
941     (r = newSubtask(h, rh, r)).fork();
942     }
943     atLeaf(l, h);
944     boolean stopping = false;
945 dl 1.9 boolean pop = true;
946 dl 1.1 while (r != null) {
947     stopping |= result.get() >= 0;
948 dl 1.9 if (pop &&
949     (pop = ForkJoinWorkerThread.removeIfNextLocalTask(r))) {
950 dl 1.1 if (!stopping)
951     r.atLeaf(r.lo, r.hi);
952     }
953     else if (stopping)
954     r.cancel();
955     else
956     r.join();
957     r = r.next;
958     }
959     }
960     abstract FJSearchBase newSubtask(int l, int h, FJSearchBase r);
961     abstract void atLeaf(int l, int h);
962     }
963    
964     // select any
965    
966 dl 1.4 static final class FJSelectAny extends FJSearchBase {
967 jsr166 1.7 FJSelectAny(AbstractParallelAnyArray pap, int lo, int hi,
968 dl 1.4 FJSearchBase next, AtomicInteger result) {
969     super(pap, lo, hi, next, result);
970 dl 1.1 }
971     FJSearchBase newSubtask(int l, int h, FJSearchBase r) {
972 dl 1.4 return new FJSelectAny(pap, l, h, r, result);
973 dl 1.1 }
974     void atLeaf(int l, int h) {
975     for (int i = l; i < h; ++i) {
976 dl 1.4 if (pap.isSelected(i)) {
977 dl 1.1 result.compareAndSet(-1, i);
978     break;
979     }
980     else if (result.get() >= 0)
981     break;
982     }
983     }
984     }
985    
986     // index of
987    
988 dl 1.2 static final class FJOIndexOf extends FJSearchBase {
989 dl 1.1 final Object target;
990 jsr166 1.7 FJOIndexOf(AbstractParallelAnyArray pap, int lo, int hi,
991 dl 1.4 FJSearchBase next, AtomicInteger result, Object target) {
992     super(pap, lo, hi, next, result);
993 dl 1.1 this.target = target;
994     }
995     FJSearchBase newSubtask(int l, int h, FJSearchBase r) {
996 dl 1.4 return new FJOIndexOf(pap, l, h, r, result, target);
997 dl 1.1 }
998     void atLeaf(int l, int h) {
999 dl 1.4 final Object[] array = pap.ogetArray();
1000 dl 1.1 if (array == null) return;
1001     for (int i = l; i < h; ++i) {
1002     if (target.equals(array[i])) {
1003     result.compareAndSet(-1, i);
1004     break;
1005     }
1006     else if (result.get() >= 0)
1007     break;
1008     }
1009     }
1010     }
1011    
1012     static final class FJDIndexOf extends FJSearchBase {
1013     final double target;
1014 jsr166 1.7 FJDIndexOf(AbstractParallelAnyArray pap, int lo, int hi,
1015 dl 1.4 FJSearchBase next, AtomicInteger result, double target) {
1016     super(pap, lo, hi, next, result);
1017 dl 1.1 this.target = target;
1018     }
1019     FJSearchBase newSubtask(int l, int h, FJSearchBase r) {
1020 dl 1.4 return new FJDIndexOf(pap, l, h, r, result, target);
1021 dl 1.1 }
1022     void atLeaf(int l, int h) {
1023 dl 1.4 final double[] array = pap.dgetArray();
1024 dl 1.1 if (array == null) return;
1025     for (int i = l; i < h; ++i) {
1026     if (target == (array[i])) {
1027     result.compareAndSet(-1, i);
1028     break;
1029     }
1030     else if (result.get() >= 0)
1031     break;
1032     }
1033     }
1034     }
1035    
1036     static final class FJLIndexOf extends FJSearchBase {
1037     final long target;
1038 jsr166 1.7 FJLIndexOf(AbstractParallelAnyArray pap, int lo, int hi,
1039 dl 1.4 FJSearchBase next, AtomicInteger result, long target) {
1040     super(pap, lo, hi, next, result);
1041 dl 1.1 this.target = target;
1042     }
1043     FJSearchBase newSubtask(int l, int h, FJSearchBase r) {
1044 dl 1.4 return new FJLIndexOf(pap, l, h, r, result, target);
1045 dl 1.1 }
1046     void atLeaf(int l, int h) {
1047 dl 1.4 final long[] array = pap.lgetArray();
1048 dl 1.1 if (array == null) return;
1049     for (int i = l; i < h; ++i) {
1050     if (target == (array[i])) {
1051     result.compareAndSet(-1, i);
1052     break;
1053     }
1054     else if (result.get() >= 0)
1055     break;
1056     }
1057     }
1058     }
1059    
1060     // select all
1061    
1062     /**
1063 dl 1.2 * SelectAll proceeds in two passes. In the first phase, indices
1064     * of matching elements are recorded in indices array. In second
1065     * pass, once the size of results is known and result array is
1066 dl 1.1 * constructed in driver, the matching elements are placed into
1067     * corresponding result positions.
1068     */
1069     static final class FJSelectAll extends RecursiveAction {
1070     final FJSelectAllDriver driver;
1071     FJSelectAll left, right;
1072     final int lo;
1073     final int hi;
1074     int count; // number of matching elements
1075     int offset;
1076     boolean isInternal; // true if this is a non-leaf node
1077 dl 1.9 final int threshold;
1078 dl 1.1
1079     FJSelectAll(FJSelectAllDriver driver, int lo, int hi) {
1080     this.driver = driver;
1081     this.lo = lo;
1082     this.hi = hi;
1083 dl 1.9 this.threshold = driver.pap.getThreshold();
1084 dl 1.1 }
1085    
1086     public void compute() {
1087 dl 1.3 int l = lo;
1088     int h = hi;
1089 dl 1.1 FJSelectAllDriver d = driver;
1090     if (d.phase == 0) {
1091 dl 1.4 AbstractParallelAnyArray p = d.pap;
1092 dl 1.9 if (isInternal = (h - l > threshold))
1093 dl 1.1 internalPhase0();
1094     else
1095 dl 1.3 count = p.leafIndexSelected(l, h, true, d.indices);
1096 dl 1.1 }
1097     else if (count != 0) {
1098     if (isInternal)
1099     internalPhase1();
1100     else
1101 dl 1.3 d.leafPhase1(l, l+count, offset);
1102 dl 1.1 }
1103     }
1104    
1105     void internalPhase0() {
1106     int mid = (lo + hi) >>> 1;
1107     FJSelectAll l = new FJSelectAll(driver, lo, mid);
1108     FJSelectAll r = new FJSelectAll(driver, mid, hi);
1109     forkJoin(l, r);
1110     int ln = l.count;
1111     if (ln != 0)
1112     left = l;
1113     int rn = r.count;
1114     if (rn != 0)
1115     right = r;
1116     count = ln + rn;
1117     }
1118    
1119     void internalPhase1() {
1120     int k = offset;
1121     if (left != null) {
1122     int ln = left.count;
1123     left.offset = k;
1124     left.reinitialize();
1125     if (right != null) {
1126     right.offset = k + ln;
1127     right.reinitialize();
1128     forkJoin(left, right);
1129     }
1130     else
1131     left.compute();
1132     }
1133     else if (right != null) {
1134     right.offset = k;
1135     right.compute();
1136     }
1137     }
1138     }
1139    
1140     static abstract class FJSelectAllDriver extends RecursiveAction {
1141     final int[] indices;
1142 dl 1.4 final AbstractParallelAnyArray pap;
1143     final int initialOffset;
1144 dl 1.1 int phase;
1145 dl 1.4 int resultSize;
1146     FJSelectAllDriver(AbstractParallelAnyArray pap, int initialOffset) {
1147     this.pap = pap;
1148     this.initialOffset = initialOffset;
1149     int n = pap.fence - pap.origin;
1150 dl 1.1 indices = new int[n];
1151     }
1152     public final void compute() {
1153 dl 1.4 FJSelectAll r = new FJSelectAll(this, pap.origin, pap.fence);
1154     r.offset = initialOffset;
1155 dl 1.1 r.compute();
1156 dl 1.4 createResults(resultSize = r.count);
1157 dl 1.1 phase = 1;
1158     r.compute();
1159     }
1160     abstract void createResults(int size);
1161     abstract void leafPhase1(int loIdx, int hiIdx, int offset);
1162     }
1163    
1164 dl 1.2 static final class FJOSelectAllDriver extends FJSelectAllDriver {
1165 dl 1.1 final Class elementType;
1166     Object[] results;
1167 dl 1.4 FJOSelectAllDriver(AbstractParallelAnyArray pap, Class elementType) {
1168     super(pap, 0);
1169 dl 1.1 this.elementType = elementType;
1170     }
1171     void createResults(int size) {
1172     results = (Object[])Array.newInstance(elementType, size);
1173     }
1174     void leafPhase1(int loIdx, int hiIdx, int offset) {
1175 dl 1.4 pap.leafTransferByIndex(indices, loIdx, hiIdx, results, offset);
1176 dl 1.1 }
1177     }
1178    
1179     static final class FJDSelectAllDriver extends FJSelectAllDriver {
1180     double[] results;
1181 dl 1.4 FJDSelectAllDriver(AbstractParallelAnyArray pap) {
1182     super(pap, 0);
1183 dl 1.1 }
1184     void createResults(int size) {
1185     results = new double[size];
1186     }
1187     void leafPhase1(int loIdx, int hiIdx, int offset) {
1188 dl 1.4 pap.leafTransferByIndex(indices, loIdx, hiIdx, results, offset);
1189 dl 1.1 }
1190     }
1191    
1192     static final class FJLSelectAllDriver extends FJSelectAllDriver {
1193     long[] results;
1194 dl 1.4 FJLSelectAllDriver(AbstractParallelAnyArray pap) {
1195     super(pap, 0);
1196 dl 1.1 }
1197     void createResults(int size) {
1198     results = new long[size];
1199     }
1200     void leafPhase1(int loIdx, int hiIdx, int offset) {
1201 dl 1.4 pap.leafTransferByIndex(indices, loIdx, hiIdx, results, offset);
1202     }
1203     }
1204    
1205     static final class FJOAppendAllDriver extends FJSelectAllDriver {
1206     Object[] results;
1207 jsr166 1.7 FJOAppendAllDriver(AbstractParallelAnyArray pap, int initialOffset,
1208 dl 1.4 Object[] results) {
1209     super(pap, 0);
1210     this.results = results;
1211     }
1212     void createResults(int size) {
1213     int newSize = initialOffset + size;
1214     int oldLength = results.length;
1215     if (newSize > oldLength) {
1216     Class elementType = results.getClass().getComponentType();
1217     Object[] r = (Object[])Array.newInstance(elementType, newSize);
1218     System.arraycopy(results, 0, r, 0, oldLength);
1219     results = r;
1220     }
1221     }
1222     void leafPhase1(int loIdx, int hiIdx, int offset) {
1223     pap.leafTransferByIndex(indices, loIdx, hiIdx, results, offset);
1224     }
1225     }
1226    
1227     static final class FJDAppendAllDriver extends FJSelectAllDriver {
1228     double[] results;
1229 jsr166 1.7 FJDAppendAllDriver(AbstractParallelAnyArray pap, int initialOffset,
1230 dl 1.4 double[] results) {
1231     super(pap, initialOffset);
1232     this.results = results;
1233     }
1234     void createResults(int size) {
1235     int newSize = initialOffset + size;
1236     int oldLength = results.length;
1237     if (newSize > oldLength) {
1238     double[] r = new double[newSize];
1239     System.arraycopy(results, 0, r, 0, oldLength);
1240     results = r;
1241     }
1242     }
1243     void leafPhase1(int loIdx, int hiIdx, int offset) {
1244     pap.leafTransferByIndex(indices, loIdx, hiIdx, results, offset);
1245     }
1246     }
1247    
1248     static final class FJLAppendAllDriver extends FJSelectAllDriver {
1249     long[] results;
1250 jsr166 1.7 FJLAppendAllDriver(AbstractParallelAnyArray pap, int initialOffset,
1251 dl 1.4 long[] results) {
1252     super(pap, initialOffset);
1253     this.results = results;
1254     }
1255     void createResults(int size) {
1256     int newSize = initialOffset + size;
1257     int oldLength = results.length;
1258     if (newSize > oldLength) {
1259     long[] r = new long[newSize];
1260     System.arraycopy(results, 0, r, 0, oldLength);
1261     results = r;
1262     }
1263     }
1264     void leafPhase1(int loIdx, int hiIdx, int offset) {
1265     pap.leafTransferByIndex(indices, loIdx, hiIdx, results, offset);
1266 dl 1.1 }
1267     }
1268    
1269 dl 1.4
1270 dl 1.1 /**
1271     * Root node for FJRemoveAll. Spawns subtasks and shifts elements
1272     * as indices become available, bypassing index array creation
1273     * when offsets are known. This differs from SelectAll mainly in
1274     * that data movement is all done by the driver rather than in a
1275     * second parallel pass.
1276     */
1277     static final class FJRemoveAllDriver extends RecursiveAction {
1278 dl 1.4 final AbstractParallelAnyArray pap;
1279 dl 1.1 final int lo;
1280     final int hi;
1281     final int[] indices;
1282     int offset;
1283 dl 1.9 final int threshold;
1284 dl 1.4 FJRemoveAllDriver(AbstractParallelAnyArray pap, int lo, int hi) {
1285     this.pap = pap;
1286 dl 1.1 this.lo = lo;
1287     this.hi = hi;
1288     this.indices = new int[hi - lo];
1289 dl 1.9 this.threshold = pap.getThreshold();
1290 dl 1.1 }
1291    
1292     public void compute() {
1293     FJRemoveAll r = null;
1294     int l = lo;
1295     int h = hi;
1296 dl 1.9 int g = threshold;
1297 dl 1.3 while (h - l > g) {
1298 dl 1.1 int rh = h;
1299     h = (l + h) >>> 1;
1300 dl 1.4 (r = new FJRemoveAll(pap, h, rh, r, indices)).fork();
1301 dl 1.1 }
1302 dl 1.4 int k = pap.leafMoveSelected(l, h, l, false);
1303 dl 1.9 boolean pop = true;
1304 dl 1.1 while (r != null) {
1305 dl 1.9 if (pop &&
1306     (pop = ForkJoinWorkerThread.removeIfNextLocalTask(r)))
1307 dl 1.4 k = pap.leafMoveSelected(r.lo, r.hi, k, false);
1308 dl 1.1 else {
1309     r.join();
1310     int n = r.count;
1311     if (n != 0)
1312 dl 1.4 pap.leafMoveByIndex(indices, r.lo, r.lo+n, k);
1313 dl 1.1 k += n;
1314     FJRemoveAll rr = r.right;
1315     if (rr != null)
1316     k = inorderMove(rr, k);
1317     }
1318     r = r.next;
1319     }
1320     offset = k;
1321     }
1322    
1323     /**
1324     * Inorder traversal to move indexed elements across reachable
1325     * nodes. This guarantees that element shifts don't overwrite
1326     * those still being used by active subtasks.
1327     */
1328     static int inorderMove(FJRemoveAll t, int index) {
1329     while (t != null) {
1330     int n = t.count;
1331     if (n != 0)
1332 dl 1.4 t.pap.leafMoveByIndex(t.indices, t.lo, t.lo+n, index);
1333 dl 1.1 index += n;
1334     FJRemoveAll p = t.next;
1335     if (p != null)
1336     index = inorderMove(p, index);
1337     t = t.right;
1338     }
1339     return index;
1340     }
1341     }
1342    
1343     /**
1344 jsr166 1.8 * Basic FJ task for non-root FJRemoveAll nodes. Differs from
1345     * FJBase because it requires maintaining explicit right pointers so
1346 dl 1.3 * FJRemoveAllDriver can traverse them
1347 dl 1.1 */
1348     static final class FJRemoveAll extends RecursiveAction {
1349 dl 1.4 final AbstractParallelAnyArray pap;
1350 dl 1.1 final int lo;
1351     final int hi;
1352     final FJRemoveAll next;
1353     final int[] indices;
1354     int count;
1355     FJRemoveAll right;
1356 dl 1.9 final int threshold;
1357 jsr166 1.7 FJRemoveAll(AbstractParallelAnyArray pap, int lo, int hi,
1358 dl 1.4 FJRemoveAll next, int[] indices) {
1359     this.pap = pap;
1360 dl 1.1 this.lo = lo;
1361     this.hi = hi;
1362     this.next = next;
1363     this.indices = indices;
1364 dl 1.9 this.threshold = pap.getThreshold();
1365 dl 1.1 }
1366    
1367     public void compute() {
1368     FJRemoveAll r = null;
1369     int l = lo;
1370     int h = hi;
1371 dl 1.9 int g = threshold;
1372 dl 1.3 while (h - l > g) {
1373 dl 1.1 int rh = h;
1374     h = (l + h) >>> 1;
1375 dl 1.4 (r = new FJRemoveAll(pap, h, rh, r, indices)).fork();
1376 dl 1.1 }
1377     right = r;
1378 dl 1.4 count = pap.leafIndexSelected(l, h, false, indices);
1379 dl 1.9 boolean pop = true;
1380 dl 1.1 while (r != null) {
1381 dl 1.9 if (pop &&
1382     (pop = ForkJoinWorkerThread.removeIfNextLocalTask(r)))
1383 dl 1.4 r.count = pap.leafIndexSelected
1384 dl 1.1 (r.lo, r.hi, false, indices);
1385     else
1386     r.join();
1387     r = r.next;
1388     }
1389     }
1390     }
1391    
1392     // unique elements
1393    
1394 dl 1.4 static final class FJOUniquifier extends FJBase {
1395     final UniquifierTable table;
1396     int count;
1397     FJOUniquifier(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
1398     UniquifierTable table) {
1399     super(pap, lo, hi, next);
1400     this.table = table;
1401     }
1402     FJBase newSubtask(int l, int h, FJBase r) {
1403     return new FJOUniquifier(pap, l, h, r, table);
1404     }
1405     void atLeaf(int l, int h) {
1406     count = table.addObjects(l, h);
1407     }
1408     void onReduce(FJBase right) {
1409     count += ((FJOUniquifier)right).count;
1410     }
1411     }
1412    
1413     static final class FJDUniquifier extends FJBase {
1414 dl 1.1 final UniquifierTable table;
1415     int count;
1416 dl 1.4 FJDUniquifier(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
1417 dl 1.1 UniquifierTable table) {
1418 dl 1.4 super(pap, lo, hi, next);
1419     this.table = table;
1420     }
1421     FJBase newSubtask(int l, int h, FJBase r) {
1422     return new FJDUniquifier(pap, l, h, r, table);
1423     }
1424     void atLeaf(int l, int h) {
1425     count = table.addDoubles(l, h);
1426     }
1427     void onReduce(FJBase right) {
1428     count += ((FJDUniquifier)right).count;
1429     }
1430     }
1431    
1432     static final class FJLUniquifier extends FJBase {
1433     final UniquifierTable table;
1434     int count;
1435     FJLUniquifier(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
1436     UniquifierTable table) {
1437     super(pap, lo, hi, next);
1438 dl 1.1 this.table = table;
1439     }
1440     FJBase newSubtask(int l, int h, FJBase r) {
1441 dl 1.4 return new FJLUniquifier(pap, l, h, r, table);
1442 dl 1.1 }
1443     void atLeaf(int l, int h) {
1444 dl 1.4 count = table.addLongs(l, h);
1445 dl 1.1 }
1446     void onReduce(FJBase right) {
1447 dl 1.4 count += ((FJLUniquifier)right).count;
1448 dl 1.1 }
1449     }
1450    
1451     /**
1452     * Base class of fixed-size hash tables for
1453     * uniquification. Opportunistically subclasses
1454     * AtomicLongArray. The high word of each slot is the cached
1455     * massaged hash of an element, and the low word contains its
1456     * index, plus one, to ensure that a zero tab entry means
1457     * empty. The mechanics for this are just folded into the
1458     * main addElements method.
1459     * Each leaf step places source array elements into table,
1460     * Even though this table undergoes a lot of contention when
1461     * elements are concurrently inserted by parallel threads, it is
1462     * generally faster to do this than to have separate tables and
1463     * then merge them.
1464     */
1465 dl 1.4 static final class UniquifierTable extends AtomicLongArray {
1466     final AbstractParallelAnyArray pap;
1467     final boolean byIdentity;
1468 jsr166 1.7 UniquifierTable(int size, AbstractParallelAnyArray pap,
1469 dl 1.4 boolean byIdentity) {
1470 dl 1.1 super(tableSizeFor(size));
1471 dl 1.4 this.pap = pap;
1472     this.byIdentity = byIdentity;
1473 dl 1.1 }
1474    
1475     /** Returns a good size for table */
1476     static int tableSizeFor(int n) {
1477     int padded = n + (n >>> 1) + 1;
1478     if (padded < n) // int overflow
1479     throw new OutOfMemoryError();
1480     int s = 8;
1481     while (s < padded) s <<= 1;
1482     return s;
1483     }
1484    
1485     // Same hashcode conditioning as HashMap
1486     static int hash(int h) {
1487     h ^= (h >>> 20) ^ (h >>> 12);
1488     return h ^ (h >>> 7) ^ (h >>> 4);
1489     }
1490    
1491 dl 1.4 int addObjects(int lo, int hi) {
1492     boolean filtered = pap.hasFilter();
1493     Object[] src = pap.ogetArray();
1494 dl 1.1 final int mask = length() - 1;
1495     int count = 0;
1496     for (int k = lo; k < hi; ++k) {
1497 dl 1.4 Object x;
1498     if ((filtered && !pap.isSelected(k)) ||
1499     (x = src[k]) == null)
1500 dl 1.1 continue;
1501     int hc = byIdentity? System.identityHashCode(x): x.hashCode();
1502     int hash = hash(hc);
1503     long entry = (((long)hash) << 32) + (k + 1);
1504     int idx = hash & mask;
1505     for (;;) {
1506     long d = get(idx);
1507     if (d != 0) {
1508     if ((int)(d >>> 32) == hash) {
1509 dl 1.4 Object y = src[(int)((d-1) & 0x7fffffffL)];
1510 dl 1.6 if (x == y || (!byIdentity && x.equals(y)))
1511 dl 1.1 break;
1512     }
1513     idx = (idx + 1) & mask;
1514     }
1515     else if (compareAndSet(idx, 0, entry)) {
1516     ++count;
1517     break;
1518     }
1519     }
1520     }
1521     return count;
1522     }
1523    
1524 dl 1.4 int addDoubles(int lo, int hi) {
1525     boolean filtered = pap.hasFilter();
1526     double[] src = pap.dgetArray();
1527 dl 1.1 final int mask = length() - 1;
1528     int count = 0;
1529     for (int k = lo; k < hi; ++k) {
1530 dl 1.4 if (filtered && !pap.isSelected(k))
1531     continue;
1532 dl 1.1 double x = src[k];
1533     long bits = Double.doubleToLongBits(x);
1534     int hash = hash((int)(bits ^ (bits >>> 32)));;
1535     long entry = (((long)hash) << 32) + (k + 1);
1536     int idx = hash & mask;
1537     for (;;) {
1538     long d = get(idx);
1539     if (d != 0) {
1540     if ((int)(d >>> 32) == hash &&
1541 dl 1.4 x == src[(int)((d - 1) & 0x7fffffffL)])
1542 dl 1.1 break;
1543     idx = (idx + 1) & mask;
1544     }
1545     else if (compareAndSet(idx, 0, entry)) {
1546     ++count;
1547     break;
1548     }
1549     }
1550     }
1551     return count;
1552     }
1553    
1554 dl 1.4 int addLongs(int lo, int hi) {
1555     boolean filtered = pap.hasFilter();
1556     long[] src = pap.lgetArray();
1557 dl 1.1 final int mask = length() - 1;
1558     int count = 0;
1559     for (int k = lo; k < hi; ++k) {
1560 dl 1.4 if (filtered && !pap.isSelected(k))
1561     continue;
1562 dl 1.1 long x = src[k];
1563     int hash = hash((int)(x ^ (x >>> 32)));
1564     long entry = (((long)hash) << 32) + (k + 1);
1565     int idx = hash & mask;
1566     for (;;) {
1567     long d = get(idx);
1568     if (d != 0) {
1569     if ((int)(d >>> 32) == hash &&
1570 dl 1.4 x == src[(int)((d - 1) & 0x7fffffffL)])
1571 dl 1.1 break;
1572     idx = (idx + 1) & mask;
1573     }
1574     else if (compareAndSet(idx, 0, entry)) {
1575     ++count;
1576     break;
1577     }
1578     }
1579     }
1580     return count;
1581     }
1582    
1583 dl 1.4 /**
1584     * Return new array holding all elements.
1585     */
1586     Object[] uniqueObjects(int size) {
1587     Object[] src = pap.ogetArray();
1588     Class sclass = src.getClass().getComponentType();
1589     Object[] res = (Object[])Array.newInstance(sclass, size);
1590     int k = 0;
1591     int n = length();
1592     for (int i = 0; i < n && k < size; ++i) {
1593     long d = get(i);
1594     if (d != 0)
1595     res[k++] = src[((int)((d - 1) & 0x7fffffffL))];
1596     }
1597     return res;
1598     }
1599    
1600     double[] uniqueDoubles(int size) {
1601     double[] src = pap.dgetArray();
1602     double[] res = new double[size];
1603     int k = 0;
1604     int n = length();
1605     for (int i = 0; i < n && k < size; ++i) {
1606     long d = get(i);
1607     if (d != 0)
1608     res[k++] = src[((int)((d - 1) & 0x7fffffffL))];
1609     }
1610     return res;
1611     }
1612    
1613     long[] uniqueLongs(int size) {
1614     long[] src = pap.lgetArray();
1615 dl 1.1 long[] res = new long[size];
1616     int k = 0;
1617     int n = length();
1618     for (int i = 0; i < n && k < size; ++i) {
1619     long d = get(i);
1620     if (d != 0)
1621     res[k++] = src[((int)((d - 1) & 0x7fffffffL))];
1622     }
1623     return res;
1624     }
1625     }
1626    
1627     /**
1628     * Sorter classes based mainly on CilkSort
1629     * <A href="http://supertech.lcs.mit.edu/cilk/"> Cilk</A>:
1630     * Basic algorithm:
1631     * if array size is small, just use a sequential quicksort
1632     * Otherwise:
1633     * 1. Break array in half.
1634     * 2. For each half,
1635     * a. break the half in half (i.e., quarters),
1636     * b. sort the quarters
1637     * c. merge them together
1638     * 3. merge together the two halves.
1639     *
1640     * One reason for splitting in quarters is that this guarantees
1641     * that the final sort is in the main array, not the workspace
1642     * array. (workspace and main swap roles on each subsort step.)
1643     * Leaf-level sorts use a Sequential quicksort, that in turn uses
1644     * insertion sort if under threshold. Otherwise it uses median of
1645     * three to pick pivot, and loops rather than recurses along left
1646     * path.
1647     *
1648     * It is sad but true that sort and merge performance are
1649     * sensitive enough to inner comparison overhead to warrant
1650     * creating 6 versions (not just 3) -- one each for natural
1651     * comparisons vs supplied comparators.
1652     */
1653 dl 1.2 static final class FJOSorter extends RecursiveAction {
1654 dl 1.1 final Comparator cmp;
1655     final Object[] a; // array to be sorted.
1656     final Object[] w; // workspace for merge
1657     final int origin; // origin of the part of array we deal with
1658     final int n; // Number of elements in (sub)arrays.
1659     final int gran; // split control
1660 dl 1.2 FJOSorter(Comparator cmp,
1661 dl 1.1 Object[] a, Object[] w, int origin, int n, int gran) {
1662     this.cmp = cmp;
1663     this.a = a; this.w = w; this.origin = origin; this.n = n;
1664     this.gran = gran;
1665     }
1666    
1667     public void compute() {
1668     int l = origin;
1669     int g = gran;
1670     if (n > g) {
1671     int h = n >>> 1; // half
1672     int q = n >>> 2; // lower quarter index
1673     int u = h + q; // upper quarter
1674     forkJoin(new FJSubSorter
1675 dl 1.2 (new FJOSorter(cmp, a, w, l, q, g),
1676     new FJOSorter(cmp, a, w, l+q, h-q, g),
1677     new FJOMerger(cmp, a, w, l, q,
1678 dl 1.1 l+q, h-q, l, g, null)),
1679     new FJSubSorter
1680 dl 1.2 (new FJOSorter(cmp, a, w, l+h, q, g),
1681     new FJOSorter(cmp, a, w, l+u, n-u, g),
1682     new FJOMerger(cmp, a, w, l+h, q,
1683 dl 1.1 l+u, n-u, l+h, g, null)));
1684 dl 1.2 new FJOMerger(cmp, w, a, l, h,
1685 dl 1.1 l+h, n-h, l, g, null).compute();
1686     }
1687     else
1688 dl 1.2 oquickSort(a, cmp, l, l+n-1);
1689 dl 1.1 }
1690     }
1691    
1692 dl 1.2 static final class FJOCSorter extends RecursiveAction {
1693 dl 1.1 final Comparable[] a; final Comparable[] w;
1694     final int origin; final int n; final int gran;
1695 dl 1.2 FJOCSorter(Comparable[] a, Comparable[] w,
1696 dl 1.1 int origin, int n, int gran) {
1697     this.a = a; this.w = w; this.origin = origin; this.n = n;
1698     this.gran = gran;
1699     }
1700     public void compute() {
1701     int l = origin;
1702     int g = gran;
1703     if (n > g) {
1704     int h = n >>> 1;
1705     int q = n >>> 2;
1706     int u = h + q;
1707     forkJoin(new FJSubSorter
1708 dl 1.2 (new FJOCSorter(a, w, l, q, g),
1709     new FJOCSorter(a, w, l+q, h-q, g),
1710     new FJOCMerger(a, w, l, q,
1711 dl 1.1 l+q, h-q, l, g, null)),
1712     new FJSubSorter
1713 dl 1.2 (new FJOCSorter(a, w, l+h, q, g),
1714     new FJOCSorter(a, w, l+u, n-u, g),
1715     new FJOCMerger(a, w, l+h, q,
1716 dl 1.1 l+u, n-u, l+h, g, null)));
1717 dl 1.2 new FJOCMerger(w, a, l, h,
1718 dl 1.1 l+h, n-h, l, g, null).compute();
1719     }
1720     else
1721 dl 1.2 ocquickSort(a, l, l+n-1);
1722 dl 1.1 }
1723     }
1724    
1725     static final class FJDSorter extends RecursiveAction {
1726     final DoubleComparator cmp; final double[] a; final double[] w;
1727     final int origin; final int n; final int gran;
1728     FJDSorter(DoubleComparator cmp,
1729     double[] a, double[] w, int origin, int n, int gran) {
1730     this.cmp = cmp;
1731     this.a = a; this.w = w; this.origin = origin; this.n = n;
1732     this.gran = gran;
1733     }
1734     public void compute() {
1735     int l = origin;
1736     int g = gran;
1737     if (n > g) {
1738     int h = n >>> 1;
1739     int q = n >>> 2;
1740     int u = h + q;
1741     forkJoin(new FJSubSorter
1742     (new FJDSorter(cmp, a, w, l, q, g),
1743     new FJDSorter(cmp, a, w, l+q, h-q, g),
1744     new FJDMerger(cmp, a, w, l, q,
1745     l+q, h-q, l, g, null)),
1746     new FJSubSorter
1747     (new FJDSorter(cmp, a, w, l+h, q, g),
1748     new FJDSorter(cmp, a, w, l+u, n-u, g),
1749     new FJDMerger(cmp, a, w, l+h, q,
1750     l+u, n-u, l+h, g, null)));
1751     new FJDMerger(cmp, w, a, l, h,
1752     l+h, n-h, l, g, null).compute();
1753     }
1754     else
1755     dquickSort(a, cmp, l, l+n-1);
1756     }
1757     }
1758    
1759     static final class FJDCSorter extends RecursiveAction {
1760     final double[] a; final double[] w;
1761     final int origin; final int n; final int gran;
1762     FJDCSorter(double[] a, double[] w, int origin,
1763     int n, int gran) {
1764     this.a = a; this.w = w; this.origin = origin; this.n = n;
1765     this.gran = gran;
1766     }
1767     public void compute() {
1768     int l = origin;
1769     int g = gran;
1770     if (n > g) {
1771     int h = n >>> 1;
1772     int q = n >>> 2;
1773     int u = h + q;
1774     forkJoin(new FJSubSorter
1775     (new FJDCSorter(a, w, l, q, g),
1776     new FJDCSorter(a, w, l+q, h-q, g),
1777     new FJDCMerger(a, w, l, q,
1778     l+q, h-q, l, g, null)),
1779     new FJSubSorter
1780     (new FJDCSorter(a, w, l+h, q, g),
1781     new FJDCSorter(a, w, l+u, n-u, g),
1782     new FJDCMerger(a, w, l+h, q,
1783     l+u, n-u, l+h, g, null)));
1784     new FJDCMerger(w, a, l, h,
1785     l+h, n-h, l, g, null).compute();
1786     }
1787     else
1788     dcquickSort(a, l, l+n-1);
1789     }
1790     }
1791    
1792     static final class FJLSorter extends RecursiveAction {
1793     final LongComparator cmp; final long[] a; final long[] w;
1794     final int origin; final int n; final int gran;
1795     FJLSorter(LongComparator cmp,
1796     long[] a, long[] w, int origin, int n, int gran) {
1797     this.cmp = cmp;
1798     this.a = a; this.w = w; this.origin = origin; this.n = n;
1799     this.gran = gran;
1800     }
1801    
1802     public void compute() {
1803     int l = origin;
1804     int g = gran;
1805     if (n > g) {
1806     int h = n >>> 1;
1807     int q = n >>> 2;
1808     int u = h + q;
1809     forkJoin(new FJSubSorter
1810     (new FJLSorter(cmp, a, w, l, q, g),
1811     new FJLSorter(cmp, a, w, l+q, h-q, g),
1812     new FJLMerger(cmp, a, w, l, q,
1813     l+q, h-q, l, g, null)),
1814     new FJSubSorter
1815     (new FJLSorter(cmp, a, w, l+h, q, g),
1816     new FJLSorter(cmp, a, w, l+u, n-u, g),
1817     new FJLMerger(cmp, a, w, l+h, q,
1818     l+u, n-u, l+h, g, null)));
1819     new FJLMerger(cmp, w, a, l, h,
1820     l+h, n-h, l, g, null).compute();
1821     }
1822     else
1823     lquickSort(a, cmp, l, l+n-1);
1824     }
1825     }
1826    
1827     static final class FJLCSorter extends RecursiveAction {
1828     final long[] a; final long[] w;
1829     final int origin; final int n; final int gran;
1830     FJLCSorter(long[] a, long[] w, int origin,
1831     int n, int gran) {
1832     this.a = a; this.w = w; this.origin = origin; this.n = n;
1833     this.gran = gran;
1834     }
1835     public void compute() {
1836     int l = origin;
1837     int g = gran;
1838     if (n > g) {
1839     int h = n >>> 1;
1840     int q = n >>> 2;
1841     int u = h + q;
1842     forkJoin(new FJSubSorter
1843     (new FJLCSorter(a, w, l, q, g),
1844     new FJLCSorter(a, w, l+q, h-q, g),
1845     new FJLCMerger(a, w, l, q,
1846     l+q, h-q, l, g, null)),
1847     new FJSubSorter
1848     (new FJLCSorter(a, w, l+h, q, g),
1849     new FJLCSorter(a, w, l+u, n-u, g),
1850     new FJLCMerger(a, w, l+h, q,
1851     l+u, n-u, l+h, g, null)));
1852     new FJLCMerger(w, a, l, h,
1853     l+h, n-h, l, g, null).compute();
1854     }
1855     else
1856     lcquickSort(a, l, l+n-1);
1857     }
1858     }
1859    
1860     /** Utility class to sort half a partitioned array */
1861     static final class FJSubSorter extends RecursiveAction {
1862     final RecursiveAction left;
1863     final RecursiveAction right;
1864     final RecursiveAction merger;
1865     FJSubSorter(RecursiveAction left, RecursiveAction right,
1866     RecursiveAction merger){
1867     this.left = left; this.right = right; this.merger = merger;
1868     }
1869     public void compute() {
1870     forkJoin(left, right);
1871     merger.compute();
1872     }
1873     }
1874    
1875     /**
1876     * Perform merging for FJSorter. If big enough, splits Left
1877     * partition in half; finds the greatest point in Right partition
1878     * less than the beginning of the second half of Left via binary
1879     * search; and then, in parallel, merges left half of Left with
1880     * elements of Right up to split point, and merges right half of
1881     * Left with elements of R past split point. At leaf, it just
1882     * sequentially merges. This is all messy to code; sadly we need
1883     * six versions.
1884     */
1885 dl 1.2 static final class FJOMerger extends RecursiveAction {
1886 dl 1.1 final Comparator cmp;
1887     final Object[] a; // partitioned array.
1888     final Object[] w; // Output array.
1889     final int lo; // relative origin of left side of a
1890     final int ln; // number of elements on left of a
1891     final int ro; // relative origin of right side of a
1892     final int rn; // number of elements on right of a
1893     final int wo; // origin for output
1894     final int gran;
1895 dl 1.2 final FJOMerger next;
1896 dl 1.1
1897 dl 1.2 FJOMerger(Comparator cmp, Object[] a, Object[] w,
1898 dl 1.1 int lo, int ln, int ro, int rn, int wo,
1899 dl 1.2 int gran, FJOMerger next) {
1900 dl 1.1 this.cmp = cmp;
1901     this.a = a; this.w = w;
1902     this.lo = lo; this.ln = ln;
1903     this.ro = ro; this.rn = rn;
1904     this.wo = wo;
1905     this.gran = gran;
1906     this.next = next;
1907     }
1908    
1909     public void compute() {
1910     // spawn right subtasks
1911 dl 1.2 FJOMerger rights = null;
1912 dl 1.1 int nleft = ln;
1913     int nright = rn;
1914     while (nleft > gran) {
1915     int lh = nleft >>> 1;
1916     int splitIndex = lo + lh;
1917     Object split = a[splitIndex];
1918     // binary search r for split
1919     int rl = 0;
1920     int rh = nright;
1921     while (rl < rh) {
1922     int mid = (rl + rh) >>> 1;
1923     if (cmp.compare(split, a[ro + mid]) <= 0)
1924     rh = mid;
1925     else
1926     rl = mid + 1;
1927     }
1928 dl 1.2 (rights = new FJOMerger
1929 dl 1.1 (cmp, a, w, splitIndex, nleft-lh, ro+rh,
1930     nright-rh, wo+lh+rh, gran, rights)).fork();
1931     nleft = lh;
1932     nright = rh;
1933     }
1934    
1935     // sequentially merge
1936     int l = lo;
1937     int lFence = lo + nleft;
1938     int r = ro;
1939     int rFence = ro + nright;
1940     int k = wo;
1941     while (l < lFence && r < rFence) {
1942     Object al = a[l];
1943     Object ar = a[r];
1944     Object t;
1945     if (cmp.compare(al, ar) <= 0) {++l; t=al;} else {++r; t=ar;}
1946     w[k++] = t;
1947     }
1948     while (l < lFence)
1949     w[k++] = a[l++];
1950     while (r < rFence)
1951     w[k++] = a[r++];
1952    
1953     // join subtasks
1954 dl 1.9 boolean pop = true;
1955 dl 1.1 while (rights != null) {
1956 dl 1.9 if (pop &&
1957     (pop = ForkJoinWorkerThread.removeIfNextLocalTask(rights)))
1958 dl 1.1 rights.compute();
1959     else
1960     rights.join();
1961     rights = rights.next;
1962     }
1963     }
1964     }
1965    
1966 dl 1.2 static final class FJOCMerger extends RecursiveAction {
1967 dl 1.1 final Comparable[] a; final Comparable[] w;
1968     final int lo; final int ln; final int ro; final int rn; final int wo;
1969     final int gran;
1970 dl 1.2 final FJOCMerger next;
1971     FJOCMerger(Comparable[] a, Comparable[] w, int lo,
1972 dl 1.1 int ln, int ro, int rn, int wo,
1973 dl 1.2 int gran, FJOCMerger next) {
1974 dl 1.1 this.a = a; this.w = w;
1975     this.lo = lo; this.ln = ln; this.ro = ro; this.rn = rn;
1976     this.wo = wo;
1977     this.gran = gran;
1978     this.next = next;
1979     }
1980    
1981     public void compute() {
1982 dl 1.2 FJOCMerger rights = null;
1983 dl 1.1 int nleft = ln;
1984     int nright = rn;
1985     while (nleft > gran) {
1986     int lh = nleft >>> 1;
1987     int splitIndex = lo + lh;
1988     Comparable split = a[splitIndex];
1989     int rl = 0;
1990     int rh = nright;
1991     while (rl < rh) {
1992     int mid = (rl + rh) >>> 1;
1993     if (split.compareTo(a[ro + mid]) <= 0)
1994     rh = mid;
1995     else
1996     rl = mid + 1;
1997     }
1998 dl 1.2 (rights = new FJOCMerger
1999 dl 1.1 (a, w, splitIndex, nleft-lh, ro+rh,
2000     nright-rh, wo+lh+rh, gran, rights)).fork();
2001     nleft = lh;
2002     nright = rh;
2003     }
2004    
2005     int l = lo;
2006     int lFence = lo + nleft;
2007     int r = ro;
2008     int rFence = ro + nright;
2009     int k = wo;
2010     while (l < lFence && r < rFence) {
2011     Comparable al = a[l];
2012     Comparable ar = a[r];
2013     Comparable t;
2014     if (al.compareTo(ar) <= 0) {++l; t=al;} else {++r; t=ar; }
2015     w[k++] = t;
2016     }
2017     while (l < lFence)
2018     w[k++] = a[l++];
2019     while (r < rFence)
2020     w[k++] = a[r++];
2021 dl 1.9 boolean pop = true;
2022 dl 1.1 while (rights != null) {
2023 dl 1.9 if (pop &&
2024     (pop = ForkJoinWorkerThread.removeIfNextLocalTask(rights)))
2025 dl 1.1 rights.compute();
2026     else
2027     rights.join();
2028     rights = rights.next;
2029     }
2030     }
2031     }
2032    
2033     static final class FJDMerger extends RecursiveAction {
2034     final DoubleComparator cmp; final double[] a; final double[] w;
2035     final int lo; final int ln; final int ro; final int rn; final int wo;
2036     final int gran;
2037     final FJDMerger next;
2038     FJDMerger(DoubleComparator cmp, double[] a, double[] w,
2039     int lo, int ln, int ro, int rn, int wo,
2040     int gran, FJDMerger next) {
2041     this.cmp = cmp;
2042     this.a = a; this.w = w;
2043     this.lo = lo; this.ln = ln;
2044     this.ro = ro; this.rn = rn;
2045     this.wo = wo;
2046     this.gran = gran;
2047     this.next = next;
2048     }
2049     public void compute() {
2050     FJDMerger rights = null;
2051     int nleft = ln;
2052     int nright = rn;
2053     while (nleft > gran) {
2054     int lh = nleft >>> 1;
2055     int splitIndex = lo + lh;
2056     double split = a[splitIndex];
2057     int rl = 0;
2058     int rh = nright;
2059     while (rl < rh) {
2060     int mid = (rl + rh) >>> 1;
2061     if (cmp.compare(split, a[ro + mid]) <= 0)
2062     rh = mid;
2063     else
2064     rl = mid + 1;
2065     }
2066     (rights = new FJDMerger
2067     (cmp, a, w, splitIndex, nleft-lh, ro+rh,
2068     nright-rh, wo+lh+rh, gran, rights)).fork();
2069     nleft = lh;
2070     nright = rh;
2071     }
2072    
2073     int l = lo;
2074     int lFence = lo + nleft;
2075     int r = ro;
2076     int rFence = ro + nright;
2077     int k = wo;
2078     while (l < lFence && r < rFence) {
2079     double al = a[l];
2080     double ar = a[r];
2081     double t;
2082     if (cmp.compare(al, ar) <= 0) {++l; t=al;} else {++r; t=ar; }
2083     w[k++] = t;
2084     }
2085     while (l < lFence)
2086     w[k++] = a[l++];
2087     while (r < rFence)
2088     w[k++] = a[r++];
2089 dl 1.9 boolean pop = true;
2090 dl 1.1 while (rights != null) {
2091 dl 1.9 if (pop &&
2092     (pop = ForkJoinWorkerThread.removeIfNextLocalTask(rights)))
2093 dl 1.1 rights.compute();
2094     else
2095     rights.join();
2096     rights = rights.next;
2097     }
2098     }
2099     }
2100    
2101     static final class FJDCMerger extends RecursiveAction {
2102     final double[] a; final double[] w;
2103     final int lo; final int ln; final int ro; final int rn; final int wo;
2104     final int gran;
2105     final FJDCMerger next;
2106     FJDCMerger(double[] a, double[] w, int lo,
2107     int ln, int ro, int rn, int wo,
2108     int gran, FJDCMerger next) {
2109     this.a = a; this.w = w;
2110     this.lo = lo; this.ln = ln;
2111     this.ro = ro; this.rn = rn;
2112     this.wo = wo;
2113     this.gran = gran;
2114     this.next = next;
2115     }
2116     public void compute() {
2117     FJDCMerger rights = null;
2118     int nleft = ln;
2119     int nright = rn;
2120     while (nleft > gran) {
2121     int lh = nleft >>> 1;
2122     int splitIndex = lo + lh;
2123     double split = a[splitIndex];
2124     int rl = 0;
2125     int rh = nright;
2126     while (rl < rh) {
2127     int mid = (rl + rh) >>> 1;
2128     if (split <= a[ro + mid])
2129     rh = mid;
2130     else
2131     rl = mid + 1;
2132     }
2133     (rights = new FJDCMerger
2134     (a, w, splitIndex, nleft-lh, ro+rh,
2135     nright-rh, wo+lh+rh, gran, rights)).fork();
2136     nleft = lh;
2137     nright = rh;
2138     }
2139    
2140     int l = lo;
2141     int lFence = lo + nleft;
2142     int r = ro;
2143     int rFence = ro + nright;
2144     int k = wo;
2145     while (l < lFence && r < rFence) {
2146     double al = a[l];
2147     double ar = a[r];
2148     double t;
2149     if (al <= ar) {++l; t=al;} else {++r; t=ar; }
2150     w[k++] = t;
2151     }
2152     while (l < lFence)
2153     w[k++] = a[l++];
2154     while (r < rFence)
2155     w[k++] = a[r++];
2156 dl 1.9 boolean pop = true;
2157 dl 1.1 while (rights != null) {
2158 dl 1.9 if (pop &&
2159     (pop = ForkJoinWorkerThread.removeIfNextLocalTask(rights)))
2160 dl 1.1 rights.compute();
2161     else
2162     rights.join();
2163     rights = rights.next;
2164     }
2165     }
2166     }
2167    
2168     static final class FJLMerger extends RecursiveAction {
2169     final LongComparator cmp; final long[] a; final long[] w;
2170     final int lo; final int ln; final int ro; final int rn; final int wo;
2171     final int gran;
2172     final FJLMerger next;
2173     FJLMerger(LongComparator cmp, long[] a, long[] w,
2174     int lo, int ln, int ro, int rn, int wo,
2175     int gran, FJLMerger next) {
2176     this.cmp = cmp;
2177     this.a = a; this.w = w;
2178     this.lo = lo; this.ln = ln;
2179     this.ro = ro; this.rn = rn;
2180     this.wo = wo;
2181     this.gran = gran;
2182     this.next = next;
2183     }
2184     public void compute() {
2185     FJLMerger rights = null;
2186     int nleft = ln;
2187     int nright = rn;
2188     while (nleft > gran) {
2189     int lh = nleft >>> 1;
2190     int splitIndex = lo + lh;
2191     long split = a[splitIndex];
2192     int rl = 0;
2193     int rh = nright;
2194     while (rl < rh) {
2195     int mid = (rl + rh) >>> 1;
2196     if (cmp.compare(split, a[ro + mid]) <= 0)
2197     rh = mid;
2198     else
2199     rl = mid + 1;
2200     }
2201     (rights = new FJLMerger
2202     (cmp, a, w, splitIndex, nleft-lh, ro+rh,
2203     nright-rh, wo+lh+rh, gran, rights)).fork();
2204     nleft = lh;
2205     nright = rh;
2206     }
2207    
2208     int l = lo;
2209     int lFence = lo + nleft;
2210     int r = ro;
2211     int rFence = ro + nright;
2212     int k = wo;
2213     while (l < lFence && r < rFence) {
2214     long al = a[l];
2215     long ar = a[r];
2216     long t;
2217     if (cmp.compare(al, ar) <= 0) {++l; t=al;} else {++r; t=ar;}
2218     w[k++] = t;
2219     }
2220     while (l < lFence)
2221     w[k++] = a[l++];
2222     while (r < rFence)
2223     w[k++] = a[r++];
2224 dl 1.9 boolean pop = true;
2225 dl 1.1 while (rights != null) {
2226 dl 1.9 if (pop &&
2227     (pop = ForkJoinWorkerThread.removeIfNextLocalTask(rights)))
2228 dl 1.1 rights.compute();
2229     else
2230     rights.join();
2231     rights = rights.next;
2232     }
2233     }
2234     }
2235    
2236     static final class FJLCMerger extends RecursiveAction {
2237     final long[] a; final long[] w;
2238     final int lo; final int ln; final int ro; final int rn; final int wo;
2239     final int gran;
2240     final FJLCMerger next;
2241     FJLCMerger(long[] a, long[] w, int lo,
2242     int ln, int ro, int rn, int wo,
2243     int gran, FJLCMerger next) {
2244     this.a = a; this.w = w;
2245     this.lo = lo; this.ln = ln;
2246     this.ro = ro; this.rn = rn;
2247     this.wo = wo;
2248     this.gran = gran;
2249     this.next = next;
2250     }
2251     public void compute() {
2252     FJLCMerger rights = null;
2253     int nleft = ln;
2254     int nright = rn;
2255     while (nleft > gran) {
2256     int lh = nleft >>> 1;
2257     int splitIndex = lo + lh;
2258     long split = a[splitIndex];
2259     int rl = 0;
2260     int rh = nright;
2261     while (rl < rh) {
2262     int mid = (rl + rh) >>> 1;
2263     if (split <= a[ro + mid])
2264     rh = mid;
2265     else
2266     rl = mid + 1;
2267     }
2268     (rights = new FJLCMerger
2269     (a, w, splitIndex, nleft-lh, ro+rh,
2270     nright-rh, wo+lh+rh, gran, rights)).fork();
2271     nleft = lh;
2272     nright = rh;
2273     }
2274    
2275     int l = lo;
2276     int lFence = lo + nleft;
2277     int r = ro;
2278     int rFence = ro + nright;
2279     int k = wo;
2280     while (l < lFence && r < rFence) {
2281     long al = a[l];
2282     long ar = a[r];
2283     long t;
2284     if (al <= ar) {++l; t=al;} else {++r; t = ar;}
2285     w[k++] = t;
2286     }
2287     while (l < lFence)
2288     w[k++] = a[l++];
2289     while (r < rFence)
2290     w[k++] = a[r++];
2291 dl 1.9 boolean pop = true;
2292 dl 1.1 while (rights != null) {
2293 dl 1.9 if (pop &&
2294     (pop = ForkJoinWorkerThread.removeIfNextLocalTask(rights)))
2295 dl 1.1 rights.compute();
2296     else
2297     rights.join();
2298     rights = rights.next;
2299     }
2300     }
2301     }
2302    
2303     /** Cutoff for when to use insertion-sort instead of quicksort */
2304     static final int INSERTION_SORT_THRESHOLD = 8;
2305    
2306     // Six nearly identical versions of quicksort
2307    
2308 dl 1.2 static void oquickSort(Object[] a, Comparator cmp, int lo, int hi) {
2309 dl 1.1 for (;;) {
2310     if (hi - lo <= INSERTION_SORT_THRESHOLD) {
2311     for (int i = lo + 1; i <= hi; i++) {
2312     Object t = a[i];
2313     int j = i - 1;
2314     while (j >= lo && cmp.compare(t, a[j]) < 0) {
2315     a[j+1] = a[j];
2316     --j;
2317     }
2318     a[j+1] = t;
2319     }
2320     return;
2321     }
2322    
2323     int mid = (lo + hi) >>> 1;
2324     if (cmp.compare(a[lo], a[mid]) > 0) {
2325     Object t = a[lo]; a[lo] = a[mid]; a[mid] = t;
2326     }
2327     if (cmp.compare(a[mid], a[hi]) > 0) {
2328     Object t = a[mid]; a[mid] = a[hi]; a[hi] = t;
2329     if (cmp.compare(a[lo], a[mid]) > 0) {
2330     Object u = a[lo]; a[lo] = a[mid]; a[mid] = u;
2331     }
2332     }
2333    
2334     Object pivot = a[mid];
2335     int left = lo+1;
2336     int right = hi-1;
2337     for (;;) {
2338     while (cmp.compare(pivot, a[right]) < 0)
2339     --right;
2340     while (left < right && cmp.compare(pivot, a[left]) >= 0)
2341     ++left;
2342     if (left < right) {
2343     Object t = a[left]; a[left] = a[right]; a[right] = t;
2344     --right;
2345     }
2346     else break;
2347     }
2348    
2349 dl 1.2 oquickSort(a, cmp, lo, left);
2350 dl 1.1 lo = left + 1;
2351     }
2352     }
2353    
2354 dl 1.2 static void ocquickSort(Comparable[] a, int lo, int hi) {
2355 dl 1.1 for (;;) {
2356     if (hi - lo <= INSERTION_SORT_THRESHOLD) {
2357     for (int i = lo + 1; i <= hi; i++) {
2358     Comparable t = a[i];
2359     int j = i - 1;
2360     while (j >= lo && t.compareTo(a[j]) < 0) {
2361     a[j+1] = a[j];
2362     --j;
2363     }
2364     a[j+1] = t;
2365     }
2366     return;
2367     }
2368    
2369     int mid = (lo + hi) >>> 1;
2370     if (a[lo].compareTo(a[mid]) > 0) {
2371     Comparable t = a[lo]; a[lo] = a[mid]; a[mid] = t;
2372     }
2373     if (a[mid].compareTo(a[hi]) > 0) {
2374     Comparable t = a[mid]; a[mid] = a[hi]; a[hi] = t;
2375     if (a[lo].compareTo(a[mid]) > 0) {
2376     Comparable u = a[lo]; a[lo] = a[mid]; a[mid] = u;
2377     }
2378     }
2379    
2380     Comparable pivot = a[mid];
2381     int left = lo+1;
2382     int right = hi-1;
2383     for (;;) {
2384     while (pivot.compareTo(a[right]) < 0)
2385     --right;
2386     while (left < right && pivot.compareTo(a[left]) >= 0)
2387     ++left;
2388     if (left < right) {
2389     Comparable t = a[left]; a[left] = a[right]; a[right] = t;
2390     --right;
2391     }
2392     else break;
2393     }
2394    
2395 dl 1.2 ocquickSort(a, lo, left);
2396 dl 1.1 lo = left + 1;
2397     }
2398     }
2399    
2400     static void dquickSort(double[] a, DoubleComparator cmp, int lo, int hi) {
2401     for (;;) {
2402     if (hi - lo <= INSERTION_SORT_THRESHOLD) {
2403     for (int i = lo + 1; i <= hi; i++) {
2404     double t = a[i];
2405     int j = i - 1;
2406     while (j >= lo && cmp.compare(t, a[j]) < 0) {
2407     a[j+1] = a[j];
2408     --j;
2409     }
2410     a[j+1] = t;
2411     }
2412     return;
2413     }
2414    
2415     int mid = (lo + hi) >>> 1;
2416     if (cmp.compare(a[lo], a[mid]) > 0) {
2417     double t = a[lo]; a[lo] = a[mid]; a[mid] = t;
2418     }
2419     if (cmp.compare(a[mid], a[hi]) > 0) {
2420     double t = a[mid]; a[mid] = a[hi]; a[hi] = t;
2421     if (cmp.compare(a[lo], a[mid]) > 0) {
2422     double u = a[lo]; a[lo] = a[mid]; a[mid] = u;
2423     }
2424     }
2425    
2426     double pivot = a[mid];
2427     int left = lo+1;
2428     int right = hi-1;
2429     for (;;) {
2430     while (cmp.compare(pivot, a[right]) < 0)
2431     --right;
2432     while (left < right && cmp.compare(pivot, a[left]) >= 0)
2433     ++left;
2434     if (left < right) {
2435     double t = a[left]; a[left] = a[right]; a[right] = t;
2436     --right;
2437     }
2438     else break;
2439     }
2440    
2441     dquickSort(a, cmp, lo, left);
2442     lo = left + 1;
2443     }
2444     }
2445    
2446     static void dcquickSort(double[] a, int lo, int hi) {
2447     for (;;) {
2448     if (hi - lo <= INSERTION_SORT_THRESHOLD) {
2449     for (int i = lo + 1; i <= hi; i++) {
2450     double t = a[i];
2451     int j = i - 1;
2452     while (j >= lo && t < a[j]) {
2453     a[j+1] = a[j];
2454     --j;
2455     }
2456     a[j+1] = t;
2457     }
2458     return;
2459     }
2460    
2461     int mid = (lo + hi) >>> 1;
2462     if (a[lo] > a[mid]) {
2463     double t = a[lo]; a[lo] = a[mid]; a[mid] = t;
2464     }
2465     if (a[mid] > a[hi]) {
2466     double t = a[mid]; a[mid] = a[hi]; a[hi] = t;
2467     if (a[lo] > a[mid]) {
2468     double u = a[lo]; a[lo] = a[mid]; a[mid] = u;
2469     }
2470     }
2471    
2472     double pivot = a[mid];
2473     int left = lo+1;
2474     int right = hi-1;
2475     for (;;) {
2476     while (pivot < a[right])
2477     --right;
2478     while (left < right && pivot >= a[left])
2479     ++left;
2480     if (left < right) {
2481     double t = a[left]; a[left] = a[right]; a[right] = t;
2482     --right;
2483     }
2484     else break;
2485     }
2486    
2487     dcquickSort(a, lo, left);
2488     lo = left + 1;
2489     }
2490     }
2491    
2492     static void lquickSort(long[] a, LongComparator cmp, int lo, int hi) {
2493     for (;;) {
2494     if (hi - lo <= INSERTION_SORT_THRESHOLD) {
2495     for (int i = lo + 1; i <= hi; i++) {
2496     long t = a[i];
2497     int j = i - 1;
2498     while (j >= lo && cmp.compare(t, a[j]) < 0) {
2499     a[j+1] = a[j];
2500     --j;
2501     }
2502     a[j+1] = t;
2503     }
2504     return;
2505     }
2506    
2507     int mid = (lo + hi) >>> 1;
2508     if (cmp.compare(a[lo], a[mid]) > 0) {
2509     long t = a[lo]; a[lo] = a[mid]; a[mid] = t;
2510     }
2511     if (cmp.compare(a[mid], a[hi]) > 0) {
2512     long t = a[mid]; a[mid] = a[hi]; a[hi] = t;
2513     if (cmp.compare(a[lo], a[mid]) > 0) {
2514     long u = a[lo]; a[lo] = a[mid]; a[mid] = u;
2515     }
2516     }
2517    
2518     long pivot = a[mid];
2519     int left = lo+1;
2520     int right = hi-1;
2521     for (;;) {
2522     while (cmp.compare(pivot, a[right]) < 0)
2523     --right;
2524     while (left < right && cmp.compare(pivot, a[left]) >= 0)
2525     ++left;
2526     if (left < right) {
2527     long t = a[left]; a[left] = a[right]; a[right] = t;
2528     --right;
2529     }
2530     else break;
2531     }
2532    
2533     lquickSort(a, cmp, lo, left);
2534     lo = left + 1;
2535     }
2536     }
2537    
2538     static void lcquickSort(long[] a, int lo, int hi) {
2539     for (;;) {
2540     if (hi - lo <= INSERTION_SORT_THRESHOLD) {
2541     for (int i = lo + 1; i <= hi; i++) {
2542     long t = a[i];
2543     int j = i - 1;
2544     while (j >= lo && t < a[j]) {
2545     a[j+1] = a[j];
2546     --j;
2547     }
2548     a[j+1] = t;
2549     }
2550     return;
2551     }
2552    
2553     int mid = (lo + hi) >>> 1;
2554     if (a[lo] > a[mid]) {
2555     long t = a[lo]; a[lo] = a[mid]; a[mid] = t;
2556     }
2557     if (a[mid] > a[hi]) {
2558     long t = a[mid]; a[mid] = a[hi]; a[hi] = t;
2559     if (a[lo] > a[mid]) {
2560     long u = a[lo]; a[lo] = a[mid]; a[mid] = u;
2561     }
2562     }
2563    
2564     long pivot = a[mid];
2565     int left = lo+1;
2566     int right = hi-1;
2567     for (;;) {
2568     while (pivot < a[right])
2569     --right;
2570     while (left < right && pivot >= a[left])
2571     ++left;
2572     if (left < right) {
2573     long t = a[left]; a[left] = a[right]; a[right] = t;
2574     --right;
2575     }
2576     else break;
2577     }
2578    
2579     lcquickSort(a, lo, left);
2580     lo = left + 1;
2581     }
2582     }
2583    
2584     /**
2585     * Cumulative scan
2586     *
2587     * A basic version of scan is straightforward.
2588     * Keep dividing by two to threshold segment size, and then:
2589     * Pass 1: Create tree of partial sums for each segment
2590     * Pass 2: For each segment, cumulate with offset of left sibling
2591     * See G. Blelloch's http://www.cs.cmu.edu/~scandal/alg/scan.html
2592     *
2593     * This version improves performance within FJ framework mainly by
2594     * allowing second pass of ready left-hand sides to proceed even
2595     * if some right-hand side first passes are still executing. It
2596     * also combines first and second pass for leftmost segment, and
2597     * for cumulate (not precumulate) also skips first pass for
2598     * rightmost segment (whose result is not needed for second pass).
2599     *
2600     * To manage this, it relies on "phase" phase/state control field
2601     * maintaining bits CUMULATE, SUMMED, and FINISHED. CUMULATE is
2602     * main phase bit. When false, segments compute only their sum.
2603     * When true, they cumulate array elements. CUMULATE is set at
2604     * root at beginning of second pass and then propagated down. But
2605 dl 1.4 * it may also be set earlier for subtrees with lo==origin (the
2606 dl 1.1 * left spine of tree). SUMMED is a one bit join count. For leafs,
2607     * set when summed. For internal nodes, becomes true when one
2608     * child is summed. When second child finishes summing, it then
2609     * moves up tree to trigger cumulate phase. FINISHED is also a one
2610     * bit join count. For leafs, it is set when cumulated. For
2611     * internal nodes, it becomes true when one child is cumulated.
2612     * When second child finishes cumulating, it then moves up tree,
2613 jsr166 1.8 * executing finish() at the root.
2614 dl 1.1 *
2615     * This class maintains only the basic control logic. Subclasses
2616     * maintain the "in" and "out" fields, and *Ops classes perform
2617     * computations
2618     */
2619 dl 1.9 static abstract class FJScan extends BasicAsyncAction {
2620 dl 1.1 static final int CUMULATE = 1;
2621     static final int SUMMED = 2;
2622     static final int FINISHED = 4;
2623    
2624     final FJScan parent;
2625     final FJScanOp op;
2626     FJScan left, right;
2627     final int lo;
2628     final int hi;
2629    
2630     FJScan(FJScan parent, FJScanOp op, int lo, int hi) {
2631     this.parent = parent;
2632     this.op = op;
2633     this.lo = lo;
2634     this.hi = hi;
2635     }
2636    
2637     /** Returns true if can CAS CUMULATE bit true */
2638     final boolean transitionToCumulate() {
2639     int c;
2640 dl 1.9 while (((c = getTaskState()) & CUMULATE) == 0)
2641     if (compareAndSetTaskState(c, c | CUMULATE))
2642 dl 1.1 return true;
2643     return false;
2644     }
2645    
2646     public final void compute() {
2647     if (hi - lo > op.threshold) {
2648     if (left == null) { // first pass
2649     int mid = (lo + hi) >>> 1;
2650     left = op.newSubtask(this, lo, mid);
2651     right = op.newSubtask(this, mid, hi);
2652     }
2653    
2654 dl 1.9 boolean cumulate = (getTaskState() & CUMULATE) != 0;
2655 dl 1.1 if (cumulate)
2656     op.pushDown(this, left, right);
2657    
2658     if (!cumulate || right.transitionToCumulate())
2659     right.fork();
2660     if (!cumulate || left.transitionToCumulate())
2661     left.compute();
2662     }
2663     else {
2664     int cb;
2665     for (;;) { // Establish action: sum, cumulate, or both
2666 dl 1.9 int b = getTaskState();
2667     if (b < 0 || (b & FINISHED) != 0) // already done
2668 dl 1.1 return;
2669     if ((b & CUMULATE) != 0)
2670     cb = FINISHED;
2671 dl 1.4 else if (lo == op.origin) // combine leftmost
2672 dl 1.1 cb = (SUMMED|FINISHED);
2673     else
2674     cb = SUMMED;
2675 dl 1.9 if (compareAndSetTaskState(b, b|cb))
2676 dl 1.1 break;
2677     }
2678    
2679     if (cb == SUMMED)
2680     op.sumLeaf(lo, hi, this);
2681     else if (cb == FINISHED)
2682     op.cumulateLeaf(lo, hi, this);
2683     else if (cb == (SUMMED|FINISHED))
2684     op.sumAndCumulateLeaf(lo, hi, this);
2685    
2686     // propagate up
2687     FJScan ch = this;
2688     FJScan par = parent;
2689     for (;;) {
2690     if (par == null) {
2691     if ((cb & FINISHED) != 0)
2692     ch.finish();
2693     break;
2694     }
2695 dl 1.9 int pb = par.getTaskState();
2696 dl 1.1 if ((pb & cb & FINISHED) != 0) { // both finished
2697     ch = par;
2698     par = par.parent;
2699     }
2700     else if ((pb & cb & SUMMED) != 0) { // both summed
2701     op.pushUp(par, par.left, par.right);
2702     int refork =
2703     ((pb & CUMULATE) == 0 &&
2704 dl 1.4 par.lo == op.origin)? CUMULATE : 0;
2705 dl 1.1 int nextPhase = pb|cb|refork;
2706     if (pb == nextPhase ||
2707 dl 1.9 par.compareAndSetTaskState(pb, nextPhase)) {
2708 dl 1.1 if (refork != 0)
2709     par.fork();
2710     cb = SUMMED; // drop finished bit
2711     ch = par;
2712     par = par.parent;
2713     }
2714     }
2715 dl 1.9 else if (par.compareAndSetTaskState(pb, pb|cb))
2716 dl 1.1 break;
2717     }
2718     }
2719     }
2720    
2721     // no-op versions of methods to get/set in/out, overridden as
2722     // appropriate in subclasses
2723 dl 1.2 Object ogetIn() { return null; }
2724     Object ogetOut() { return null; }
2725 dl 1.1 void rsetIn(Object x) { }
2726     void rsetOut(Object x) { }
2727    
2728     double dgetIn() { return 0; }
2729     double dgetOut() { return 0; }
2730     void dsetIn(double x) { }
2731     void dsetOut(double x) { }
2732    
2733     long lgetIn() { return 0; }
2734     long lgetOut() { return 0; }
2735     void lsetIn(long x) { }
2736     void lsetOut(long x) { }
2737     }
2738    
2739     // Subclasses adding in/out fields of the appropriate type
2740 dl 1.2 static final class FJOScan extends FJScan {
2741 dl 1.1 Object in;
2742     Object out;
2743 dl 1.2 FJOScan(FJScan parent, FJScanOp op, int lo, int hi) {
2744 dl 1.1 super(parent, op, lo, hi);
2745     }
2746 dl 1.2 Object ogetIn() { return in; }
2747     Object ogetOut() { return out; }
2748 dl 1.1 void rsetIn(Object x) { in = x; }
2749     void rsetOut(Object x) { out = x; }
2750     }
2751    
2752     static final class FJDScan extends FJScan {
2753     double in;
2754     double out;
2755     FJDScan(FJScan parent, FJScanOp op, int lo, int hi) {
2756     super(parent, op, lo, hi);
2757     }
2758     double dgetIn() { return in; }
2759     double dgetOut() { return out; }
2760     void dsetIn(double x) { in = x; }
2761     void dsetOut(double x) { out = x; }
2762    
2763     }
2764    
2765     static final class FJLScan extends FJScan {
2766     long in;
2767     long out;
2768     FJLScan(FJScan parent, FJScanOp op, int lo, int hi) {
2769     super(parent, op, lo, hi);
2770     }
2771     long lgetIn() { return in; }
2772     long lgetOut() { return out; }
2773     void lsetIn(long x) { in = x; }
2774     void lsetOut(long x) { out = x; }
2775     }
2776    
2777     /**
2778     * Computational operations for FJSCan
2779     */
2780     static abstract class FJScanOp {
2781     final int threshold;
2782 dl 1.4 final int origin;
2783     final int fence;
2784     FJScanOp(AbstractParallelAnyArray pap) {
2785     this.origin = pap.origin;
2786     this.fence = pap.fence;
2787 dl 1.9 this.threshold = pap.computeThreshold();
2788 dl 1.1 }
2789     abstract void pushDown(FJScan parent, FJScan left, FJScan right);
2790     abstract void pushUp(FJScan parent, FJScan left, FJScan right);
2791     abstract void sumLeaf(int lo, int hi, FJScan f);
2792     abstract void cumulateLeaf(int lo, int hi, FJScan f);
2793     abstract void sumAndCumulateLeaf(int lo, int hi, FJScan f);
2794     abstract FJScan newSubtask(FJScan parent, int lo, int hi);
2795     }
2796    
2797 dl 1.2 static abstract class FJOScanOp extends FJScanOp {
2798 dl 1.1 final Object[] array;
2799     final Reducer reducer;
2800     final Object base;
2801 jsr166 1.7 FJOScanOp(AbstractParallelAnyArray.OPap pap,
2802 dl 1.4 Reducer reducer, Object base) {
2803     super(pap);
2804     this.array = pap.array;
2805 dl 1.1 this.reducer = reducer;
2806     this.base = base;
2807     }
2808     final void pushDown(FJScan parent, FJScan left, FJScan right) {
2809 dl 1.2 Object pin = parent.ogetIn();
2810 dl 1.1 left.rsetIn(pin);
2811 dl 1.2 right.rsetIn(reducer.op(pin, left.ogetOut()));
2812 dl 1.1 }
2813     final void pushUp(FJScan parent, FJScan left, FJScan right) {
2814 dl 1.2 parent.rsetOut(reducer.op(left.ogetOut(),
2815     right.ogetOut()));
2816 dl 1.1 }
2817     final FJScan newSubtask(FJScan parent, int lo, int hi) {
2818 dl 1.2 FJOScan f = new FJOScan(parent, this, lo, hi);
2819 dl 1.1 f.in = base;
2820     f.out = base;
2821     return f;
2822     }
2823     }
2824    
2825 dl 1.2 static final class FJOCumulateOp extends FJOScanOp {
2826 jsr166 1.7 FJOCumulateOp(AbstractParallelAnyArray.OPap pap,
2827 dl 1.4 Reducer reducer, Object base) {
2828     super(pap, reducer, base);
2829 dl 1.1 }
2830     void sumLeaf(int lo, int hi, FJScan f) {
2831     Object sum = base;
2832 dl 1.4 if (hi != fence) {
2833 dl 1.1 Object[] arr = array;
2834     for (int i = lo; i < hi; ++i)
2835 dl 1.2 sum = reducer.op(sum, arr[i]);
2836 dl 1.1 }
2837     f.rsetOut(sum);
2838     }
2839     void cumulateLeaf(int lo, int hi, FJScan f) {
2840     Object[] arr = array;
2841 dl 1.2 Object sum = f.ogetIn();
2842 dl 1.1 for (int i = lo; i < hi; ++i)
2843 dl 1.2 arr[i] = sum = reducer.op(sum, arr[i]);
2844 dl 1.1 }
2845     void sumAndCumulateLeaf(int lo, int hi, FJScan f) {
2846     Object[] arr = array;
2847     Object sum = base;
2848     for (int i = lo; i < hi; ++i)
2849 dl 1.2 arr[i] = sum = reducer.op(sum, arr[i]);
2850 dl 1.1 f.rsetOut(sum);
2851     }
2852     }
2853    
2854 dl 1.2 static final class FJOPrecumulateOp extends FJOScanOp {
2855 jsr166 1.7 FJOPrecumulateOp(AbstractParallelAnyArray.OPap pap,
2856 dl 1.4 Reducer reducer, Object base) {
2857     super(pap, reducer, base);
2858 dl 1.1 }
2859     void sumLeaf(int lo, int hi, FJScan f) {
2860     Object[] arr = array;
2861     Object sum = base;
2862     for (int i = lo; i < hi; ++i)
2863 dl 1.2 sum = reducer.op(sum, arr[i]);
2864 dl 1.1 f.rsetOut(sum);
2865     }
2866     void cumulateLeaf(int lo, int hi, FJScan f) {
2867     Object[] arr = array;
2868 dl 1.2 Object sum = f.ogetIn();
2869 dl 1.1 for (int i = lo; i < hi; ++i) {
2870     Object x = arr[i];
2871     arr[i] = sum;
2872 dl 1.2 sum = reducer.op(sum, x);
2873 dl 1.1 }
2874     }
2875     void sumAndCumulateLeaf(int lo, int hi, FJScan f) {
2876     Object[] arr = array;
2877     Object sum = base;
2878     for (int i = lo; i < hi; ++i) {
2879     Object x = arr[i];
2880     arr[i] = sum;
2881 dl 1.2 sum = reducer.op(sum, x);
2882 dl 1.1 }
2883     f.rsetOut(sum);
2884     }
2885     }
2886    
2887     static abstract class FJDScanOp extends FJScanOp {
2888     final double[] array;
2889     final DoubleReducer reducer;
2890     final double base;
2891 jsr166 1.7 FJDScanOp(AbstractParallelAnyArray.DPap pap,
2892 dl 1.4 DoubleReducer reducer, double base) {
2893     super(pap);
2894     this.array = pap.array;
2895 dl 1.1 this.reducer = reducer;
2896     this.base = base;
2897     }
2898     final void pushDown(FJScan parent, FJScan left, FJScan right) {
2899     double pin = parent.dgetIn();
2900     left.dsetIn(pin);
2901 dl 1.2 right.dsetIn(reducer.op(pin, left.dgetOut()));
2902 dl 1.1 }
2903     final void pushUp(FJScan parent, FJScan left, FJScan right) {
2904 dl 1.2 parent.dsetOut(reducer.op(left.dgetOut(),
2905 dl 1.1 right.dgetOut()));
2906     }
2907     final FJScan newSubtask(FJScan parent, int lo, int hi) {
2908     FJDScan f = new FJDScan(parent, this, lo, hi);
2909     f.in = base;
2910     f.out = base;
2911     return f;
2912     }
2913     }
2914    
2915     static final class FJDCumulateOp extends FJDScanOp {
2916 jsr166 1.7 FJDCumulateOp(AbstractParallelAnyArray.DPap pap,
2917 dl 1.4 DoubleReducer reducer, double base) {
2918     super(pap, reducer, base);
2919 dl 1.1 }
2920     void sumLeaf(int lo, int hi, FJScan f) {
2921     double sum = base;
2922 dl 1.4 if (hi != fence) {
2923 dl 1.1 double[] arr = array;
2924     for (int i = lo; i < hi; ++i)
2925 dl 1.2 sum = reducer.op(sum, arr[i]);
2926 dl 1.1 }
2927     f.dsetOut(sum);
2928     }
2929     void cumulateLeaf(int lo, int hi, FJScan f) {
2930     double[] arr = array;
2931     double sum = f.dgetIn();
2932     for (int i = lo; i < hi; ++i)
2933 dl 1.2 arr[i] = sum = reducer.op(sum, arr[i]);
2934 dl 1.1 }
2935     void sumAndCumulateLeaf(int lo, int hi, FJScan f) {
2936     double[] arr = array;
2937     double sum = base;
2938     for (int i = lo; i < hi; ++i)
2939 dl 1.2 arr[i] = sum = reducer.op(sum, arr[i]);
2940 dl 1.1 f.dsetOut(sum);
2941     }
2942     }
2943    
2944     static final class FJDPrecumulateOp extends FJDScanOp {
2945 jsr166 1.7 FJDPrecumulateOp(AbstractParallelAnyArray.DPap pap,
2946 dl 1.4 DoubleReducer reducer, double base) {
2947     super(pap, reducer, base);
2948 dl 1.1 }
2949     void sumLeaf(int lo, int hi, FJScan f) {
2950     double[] arr = array;
2951     double sum = base;
2952     for (int i = lo; i < hi; ++i)
2953 dl 1.2 sum = reducer.op(sum, arr[i]);
2954 dl 1.1 f.dsetOut(sum);
2955     }
2956     void cumulateLeaf(int lo, int hi, FJScan f) {
2957     double[] arr = array;
2958     double sum = f.dgetIn();
2959     for (int i = lo; i < hi; ++i) {
2960     double x = arr[i];
2961     arr[i] = sum;
2962 dl 1.2 sum = reducer.op(sum, x);
2963 dl 1.1 }
2964     }
2965     void sumAndCumulateLeaf(int lo, int hi, FJScan f) {
2966     double[] arr = array;
2967     double sum = base;
2968     for (int i = lo; i < hi; ++i) {
2969     double x = arr[i];
2970     arr[i] = sum;
2971 dl 1.2 sum = reducer.op(sum, x);
2972 dl 1.1 }
2973     f.dsetOut(sum);
2974     }
2975     }
2976    
2977     static abstract class FJLScanOp extends FJScanOp {
2978     final long[] array;
2979     final LongReducer reducer;
2980     final long base;
2981 jsr166 1.7 FJLScanOp(AbstractParallelAnyArray.LPap pap,
2982 dl 1.4 LongReducer reducer, long base) {
2983     super(pap);
2984     this.array = pap.array;
2985 dl 1.1 this.reducer = reducer;
2986     this.base = base;
2987     }
2988     final void pushDown(FJScan parent, FJScan left, FJScan right) {
2989     long pin = parent.lgetIn();
2990     left.lsetIn(pin);
2991 dl 1.2 right.lsetIn(reducer.op(pin, left.lgetOut()));
2992 dl 1.1 }
2993     final void pushUp(FJScan parent, FJScan left, FJScan right) {
2994 dl 1.2 parent.lsetOut(reducer.op(left.lgetOut(),
2995 dl 1.1 right.lgetOut()));
2996     }
2997     final FJScan newSubtask(FJScan parent, int lo, int hi) {
2998     FJLScan f = new FJLScan(parent, this, lo, hi);
2999     f.in = base;
3000     f.out = base;
3001     return f;
3002     }
3003     }
3004    
3005     static final class FJLCumulateOp extends FJLScanOp {
3006 jsr166 1.7 FJLCumulateOp(AbstractParallelAnyArray.LPap pap,
3007 dl 1.4 LongReducer reducer, long base) {
3008     super(pap, reducer, base);
3009 dl 1.1 }
3010     void sumLeaf(int lo, int hi, FJScan f) {
3011     long sum = base;
3012 dl 1.4 if (hi != fence) {
3013 dl 1.1 long[] arr = array;
3014     for (int i = lo; i < hi; ++i)
3015 dl 1.2 sum = reducer.op(sum, arr[i]);
3016 dl 1.1 }
3017     f.lsetOut(sum);
3018     }
3019     void cumulateLeaf(int lo, int hi, FJScan f) {
3020     long[] arr = array;
3021     long sum = f.lgetIn();
3022     for (int i = lo; i < hi; ++i)
3023 dl 1.2 arr[i] = sum = reducer.op(sum, arr[i]);
3024 dl 1.1 }
3025     void sumAndCumulateLeaf(int lo, int hi, FJScan f) {
3026     long[] arr = array;
3027     long sum = base;
3028     for (int i = lo; i < hi; ++i)
3029 dl 1.2 arr[i] = sum = reducer.op(sum, arr[i]);
3030 dl 1.1 f.lsetOut(sum);
3031     }
3032     }
3033    
3034     static final class FJLPrecumulateOp extends FJLScanOp {
3035 jsr166 1.7 FJLPrecumulateOp(AbstractParallelAnyArray.LPap pap,
3036 dl 1.4 LongReducer reducer, long base) {
3037     super(pap, reducer, base);
3038 dl 1.1 }
3039     void sumLeaf(int lo, int hi, FJScan f) {
3040     long[] arr = array;
3041     long sum = base;
3042     for (int i = lo; i < hi; ++i)
3043 dl 1.2 sum = reducer.op(sum, arr[i]);
3044 dl 1.1 f.lsetOut(sum);
3045     }
3046     void cumulateLeaf(int lo, int hi, FJScan f) {
3047     long[] arr = array;
3048     long sum = f.lgetIn();
3049     for (int i = lo; i < hi; ++i) {
3050     long x = arr[i];
3051     arr[i] = sum;
3052 dl 1.2 sum = reducer.op(sum, x);
3053 dl 1.1 }
3054     }
3055     void sumAndCumulateLeaf(int lo, int hi, FJScan f) {
3056     long[] arr = array;
3057     long sum = base;
3058     for (int i = lo; i < hi; ++i) {
3059     long x = arr[i];
3060     arr[i] = sum;
3061 dl 1.2 sum = reducer.op(sum, x);
3062 dl 1.1 }
3063     f.lsetOut(sum);
3064     }
3065     }
3066    
3067     // specialized versions for plus
3068    
3069     static abstract class FJDScanPlusOp extends FJScanOp {
3070     final double[] array;
3071 dl 1.4 FJDScanPlusOp(AbstractParallelAnyArray.DPap pap) {
3072     super(pap);
3073     this.array = pap.array;
3074 dl 1.1 }
3075     final void pushDown(FJScan parent, FJScan left, FJScan right) {
3076     double pin = parent.dgetIn();
3077     left.dsetIn(pin);
3078     right.dsetIn(pin + left.dgetOut());
3079     }
3080     final void pushUp(FJScan parent, FJScan left, FJScan right) {
3081     parent.dsetOut(left.dgetOut() + right.dgetOut());
3082     }
3083     final FJScan newSubtask(FJScan parent, int lo, int hi) {
3084     FJDScan f = new FJDScan(parent, this, lo, hi);
3085     f.in = 0.0;
3086     f.out = 0.0;
3087     return f;
3088     }
3089     }
3090    
3091     static final class FJDCumulatePlusOp extends FJDScanPlusOp {
3092 dl 1.4 FJDCumulatePlusOp(AbstractParallelAnyArray.DPap pap) {
3093     super(pap);
3094 dl 1.1 }
3095     void sumLeaf(int lo, int hi, FJScan f) {
3096     double sum = 0.0;
3097 dl 1.4 if (hi != fence) {
3098 dl 1.1 double[] arr = array;
3099     for (int i = lo; i < hi; ++i)
3100     sum += arr[i];
3101     }
3102     f.dsetOut(sum);
3103     }
3104     void cumulateLeaf(int lo, int hi, FJScan f) {
3105     double[] arr = array;
3106     double sum = f.dgetIn();
3107     for (int i = lo; i < hi; ++i)
3108     arr[i] = sum += arr[i];
3109     }
3110     void sumAndCumulateLeaf(int lo, int hi, FJScan f) {
3111     double[] arr = array;
3112     double sum = 0.0;
3113     for (int i = lo; i < hi; ++i)
3114     arr[i] = sum += arr[i];
3115     f.dsetOut(sum);
3116     }
3117     }
3118    
3119     static final class FJDPrecumulatePlusOp extends FJDScanPlusOp {
3120 dl 1.4 FJDPrecumulatePlusOp(AbstractParallelAnyArray.DPap pap) {
3121     super(pap);
3122 dl 1.1 }
3123     void sumLeaf(int lo, int hi, FJScan f) {
3124     double[] arr = array;
3125     double sum = 0.0;
3126     for (int i = lo; i < hi; ++i)
3127     sum += arr[i];
3128     f.dsetOut(sum);
3129     }
3130     void cumulateLeaf(int lo, int hi, FJScan f) {
3131     double[] arr = array;
3132     double sum = f.dgetIn();
3133     for (int i = lo; i < hi; ++i) {
3134     double x = arr[i];
3135     arr[i] = sum;
3136     sum += x;
3137     }
3138     }
3139     void sumAndCumulateLeaf(int lo, int hi, FJScan f) {
3140     double[] arr = array;
3141     double sum = 0.0;
3142     for (int i = lo; i < hi; ++i) {
3143     double x = arr[i];
3144     arr[i] = sum;
3145     sum += x;
3146     }
3147     f.dsetOut(sum);
3148     }
3149     }
3150    
3151     static abstract class FJLScanPlusOp extends FJScanOp {
3152     final long[] array;
3153 dl 1.4 FJLScanPlusOp(AbstractParallelAnyArray.LPap pap) {
3154     super(pap);
3155     this.array = pap.array;
3156 dl 1.1 }
3157     final void pushDown(FJScan parent, FJScan left, FJScan right) {
3158     long pin = parent.lgetIn();
3159     left.lsetIn(pin);
3160     right.lsetIn(pin + left.lgetOut());
3161     }
3162    
3163     final void pushUp(FJScan parent, FJScan left, FJScan right) {
3164     parent.lsetOut(left.lgetOut() + right.lgetOut());
3165     }
3166    
3167     final FJScan newSubtask(FJScan parent, int lo, int hi) {
3168     FJLScan f = new FJLScan(parent, this, lo, hi);
3169     f.in = 0L;
3170     f.out = 0L;
3171     return f;
3172     }
3173     }
3174    
3175     static final class FJLCumulatePlusOp extends FJLScanPlusOp {
3176 dl 1.4 FJLCumulatePlusOp(AbstractParallelAnyArray.LPap pap) {
3177     super(pap);
3178 dl 1.1 }
3179     void sumLeaf(int lo, int hi, FJScan f) {
3180     long sum = 0L;
3181 dl 1.4 if (hi != fence) {
3182 dl 1.1 long[] arr = array;
3183     for (int i = lo; i < hi; ++i)
3184     sum += arr[i];
3185     }
3186     f.lsetOut(sum);
3187     }
3188     void cumulateLeaf(int lo, int hi, FJScan f) {
3189     long[] arr = array;
3190     long sum = f.lgetIn();
3191     for (int i = lo; i < hi; ++i)
3192     arr[i] = sum += arr[i];
3193     }
3194     void sumAndCumulateLeaf(int lo, int hi, FJScan f) {
3195     long[] arr = array;
3196     long sum = 0L;
3197     for (int i = lo; i < hi; ++i)
3198     arr[i] = sum += arr[i];
3199     f.lsetOut(sum);
3200     }
3201     }
3202    
3203     static final class FJLPrecumulatePlusOp extends FJLScanPlusOp {
3204 dl 1.4 FJLPrecumulatePlusOp(AbstractParallelAnyArray.LPap pap) {
3205     super(pap);
3206 dl 1.1 }
3207     void sumLeaf(int lo, int hi, FJScan f) {
3208     long[] arr = array;
3209     long sum = 0L;
3210     for (int i = lo; i < hi; ++i)
3211     sum += arr[i];
3212     f.lsetOut(sum);
3213     }
3214     void cumulateLeaf(int lo, int hi, FJScan f) {
3215     long[] arr = array;
3216     long sum = f.lgetIn();
3217     for (int i = lo; i < hi; ++i) {
3218     long x = arr[i];
3219     arr[i] = sum;
3220     sum += x;
3221     }
3222     }
3223     void sumAndCumulateLeaf(int lo, int hi, FJScan f) {
3224     long[] arr = array;
3225     long sum = 0L;
3226     for (int i = lo; i < hi; ++i) {
3227     long x = arr[i];
3228     arr[i] = sum;
3229     sum += x;
3230     }
3231     f.lsetOut(sum);
3232     }
3233     }
3234 dl 1.2
3235 dl 1.1 }