1 /*
2 * Copyright (c) 2012, 2013, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25 package java.util.stream;
26
27 import java.util.ArrayDeque;
28 import java.util.Arrays;
29 import java.util.Collection;
30 import java.util.Deque;
31 import java.util.List;
32 import java.util.Objects;
33 import java.util.Spliterator;
34 import java.util.Spliterators;
35 import java.util.concurrent.CountedCompleter;
36 import java.util.function.Consumer;
37 import java.util.function.DoubleConsumer;
38 import java.util.function.IntConsumer;
39 import java.util.function.IntFunction;
40 import java.util.function.LongConsumer;
41
42 import static java.util.stream.Collectors.toStringJoiner;
43
44 /**
45 * Factory methods for constructing implementations of {@link Node} and
46 * {@link Node.Builder} and their primitive specializations. Fork/Join tasks
47 * for collecting output from a {@link PipelineHelper} to a {@link Node} and
48 * flattening {@link Node}s.
49 *
50 * @since 1.8
51 */
52 final class Nodes {
53
54 private Nodes() {
55 throw new Error("no instances");
56 }
57
58 /**
59 * The maximum size of an array that can be allocated.
60 */
61 static final long MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
62
63 private static final Node EMPTY_NODE = new EmptyNode.OfRef();
64 private static final Node.OfInt EMPTY_INT_NODE = new EmptyNode.OfInt();
65 private static final Node.OfLong EMPTY_LONG_NODE = new EmptyNode.OfLong();
66 private static final Node.OfDouble EMPTY_DOUBLE_NODE = new EmptyNode.OfDouble();
67
68 // General shape-based node creation methods
69
70 /**
71 * Produces an empty node whose count is zero, has no children and no content.
72 *
73 * @param shape the shape of the node to be created.
74 * @param <T> the type of elements of the created node.
75 * @return an empty node.
76 */
77 @SuppressWarnings("unchecked")
78 static <T> Node<T> emptyNode(StreamShape shape) {
79 switch (shape) {
80 case REFERENCE: return (Node<T>) EMPTY_NODE;
81 case INT_VALUE: return (Node<T>) EMPTY_INT_NODE;
82 case LONG_VALUE: return (Node<T>) EMPTY_LONG_NODE;
83 case DOUBLE_VALUE: return (Node<T>) EMPTY_DOUBLE_NODE;
84 default:
85 throw new IllegalStateException("Unknown shape " + shape);
86 }
87 }
88
89 /**
90 * Produces a concatenated {@link Node} that has two or more children.
91 * <p>The count of the concatenated node is equal to the sum of the count
92 * of each child. Traversal of the concatenated node traverses the content
93 * of each child in encounter order of the list of children. Splitting a
94 * spliterator obtained from the concatenated node preserves the encounter
95 * order of the list of children.
96 *
97 * <p>The result may be a concatenated node, the input sole node if the size
98 * of the list is 1, or an empty node.
99 *
100 * @param shape the shape of the concatenated node to be created
101 * @param nodes the input nodes
102 * @param <T> the type of elements of the concatenated node
103 * @return a {@code Node} covering the elements of the input nodes
104 * @throws IllegalStateException if all {@link Node} elements of the list
105 * are an not instance of type supported by this factory.
106 */
107 @SuppressWarnings("unchecked")
108 static <T> Node<T> conc(StreamShape shape, List<? extends Node<T>> nodes) {
109 int size = nodes.size();
110 if (size == 0)
111 return emptyNode(shape);
112 else if (size == 1)
113 return nodes.get(0);
114 else {
115 // Create a right-balanced tree when there are more that 2 nodes
116 switch (shape) {
117 case REFERENCE: {
118 List<Node<T>> refNodes = (List<Node<T>>) nodes;
119 ConcNode<T> c = new ConcNode<>(refNodes.get(size - 2), refNodes.get(size - 1));
120 for (int i = size - 3; i >= 0; i--) {
121 c = new ConcNode<>(refNodes.get(i), c);
122 }
123 return c;
124 }
125 case INT_VALUE: {
126 List<? extends Node.OfInt> intNodes = (List<? extends Node.OfInt>) nodes;
127 IntConcNode c = new IntConcNode(intNodes.get(size - 2), intNodes.get(size - 1));
128 for (int i = size - 3; i >= 0; i--) {
129 c = new IntConcNode(intNodes.get(i), c);
130 }
131 return (Node<T>) c;
132 }
133 case LONG_VALUE: {
134 List<? extends Node.OfLong> longNodes = (List<? extends Node.OfLong>) nodes;
135 LongConcNode c = new LongConcNode(longNodes.get(size - 2), longNodes.get(size - 1));
136 for (int i = size - 3; i >= 0; i--) {
137 c = new LongConcNode(longNodes.get(i), c);
138 }
139 return (Node<T>) c;
140 }
141 case DOUBLE_VALUE: {
142 List<? extends Node.OfDouble> doubleNodes = (List<? extends Node.OfDouble>) nodes;
143 DoubleConcNode c = new DoubleConcNode(doubleNodes.get(size - 2), doubleNodes.get(size - 1));
144 for (int i = size - 3; i >= 0; i--) {
145 c = new DoubleConcNode(doubleNodes.get(i), c);
146 }
147 return (Node<T>) c;
148 }
149 default:
150 throw new IllegalStateException("Unknown shape " + shape);
151 }
152 }
153
154 }
155
156 /**
157 * Truncate a {@link Node}, returning a node describing a subsequence of
158 * the contents of the input node.
159 *
160 * @param input the input node
161 * @param from the starting offset to include in the truncated node (inclusive)
162 * @param to the ending offset ot include in the truncated node (exclusive)
163 * @param generator the array factory (only used for reference nodes)
164 * @param <T> the type of elements of the input node and truncated node
165 * @return the truncated node
166 */
167 @SuppressWarnings("unchecked")
168 static <T> Node<T> truncateNode(Node<T> input, long from, long to, IntFunction<T[]> generator) {
169 StreamShape shape = input.getShape();
170 long size = truncatedSize(input.count(), from, to);
171 if (size == 0)
172 return emptyNode(shape);
173 else if (from == 0 && to >= input.count())
174 return input;
175
176 switch (shape) {
177 case REFERENCE: {
178 Spliterator<T> spliterator = input.spliterator();
179 Node.Builder<T> nodeBuilder = Nodes.builder(size, generator);
180 nodeBuilder.begin(size);
181 for (int i = 0; i < from && spliterator.tryAdvance(e -> { }); i++) { }
182 for (int i = 0; (i < size) && spliterator.tryAdvance(nodeBuilder); i++) { }
183 nodeBuilder.end();
184 return nodeBuilder.build();
185 }
186 case INT_VALUE: {
187 Spliterator.OfInt spliterator = ((Node.OfInt) input).spliterator();
188 Node.Builder.OfInt nodeBuilder = Nodes.intBuilder(size);
189 nodeBuilder.begin(size);
190 for (int i = 0; i < from && spliterator.tryAdvance((IntConsumer) e -> { }); i++) { }
191 for (int i = 0; (i < size) && spliterator.tryAdvance((IntConsumer) nodeBuilder); i++) { }
192 nodeBuilder.end();
193 return (Node<T>) nodeBuilder.build();
194 }
195 case LONG_VALUE: {
196 Spliterator.OfLong spliterator = ((Node.OfLong) input).spliterator();
197 Node.Builder.OfLong nodeBuilder = Nodes.longBuilder(size);
198 nodeBuilder.begin(size);
199 for (int i = 0; i < from && spliterator.tryAdvance((LongConsumer) e -> { }); i++) { }
200 for (int i = 0; (i < size) && spliterator.tryAdvance((LongConsumer) nodeBuilder); i++) { }
201 nodeBuilder.end();
202 return (Node<T>) nodeBuilder.build();
203 }
204 case DOUBLE_VALUE: {
205 Spliterator.OfDouble spliterator = ((Node.OfDouble) input).spliterator();
206 Node.Builder.OfDouble nodeBuilder = Nodes.doubleBuilder(size);
207 nodeBuilder.begin(size);
208 for (int i = 0; i < from && spliterator.tryAdvance((DoubleConsumer) e -> { }); i++) { }
209 for (int i = 0; (i < size) && spliterator.tryAdvance((DoubleConsumer) nodeBuilder); i++) { }
210 nodeBuilder.end();
211 return (Node<T>) nodeBuilder.build();
212 }
213 default:
214 throw new IllegalStateException("Unknown shape " + shape);
215 }
216 }
217
218 private static long truncatedSize(long size, long from, long to) {
219 if (from >= 0)
220 size = Math.max(0, size - from);
221 long limit = to - from;
222 if (limit >= 0)
223 size = Math.min(size, limit);
224 return size;
225 }
226
227 // Reference-based node methods
228
229 /**
230 * Produces a {@link Node} describing an array.
231 * <p>
232 * The node will hold a reference to the array and will not make a copy.
233 *
234 * @param array the array.
235 * @param <T> the type of elements held by the node
236 * @return a node holding an array
237 */
238 static<T> Node<T> node(T[] array) {
239 return new ArrayNode<>(array);
240 }
241
242 /**
243 * Produces a {@link Node} describing a {@link Collection}.
244 * <p>
245 * The node will hold a reference to the collection and will not make a copy.
246 *
247 * @param c the collection.
248 * @param <T> the type of elements held by the node.
249 * @return a node holding a collection.
250 */
251 static<T> Node<T> node(Collection<T> c) {
252 return new CollectionNode<>(c);
253 }
254
255 /**
256 * Produces a {@link Node.Builder}.
257 *
258 * @param exactSizeIfKnown -1 if a variable size builder is requested,
259 * otherwise the exact capacity desired. A fixed capacity builder will
260 * fail if the wrong number of elements are added to the builder.
261 * @param generator the array factory
262 * @param <T> the type of elements of the node builder
263 * @return a {@code Node.Builder}
264 */
265 static <T> Node.Builder<T> builder(long exactSizeIfKnown, IntFunction<T[]> generator) {
266 return (exactSizeIfKnown >= 0 && exactSizeIfKnown < MAX_ARRAY_SIZE)
267 ? new FixedNodeBuilder<>(exactSizeIfKnown, generator)
268 : builder();
269 }
270
271 /**
272 * Produces a variable size @{link Node.Builder}.
273 *
274 * @param <T> the type of elements of the node builder
275 * @return a {@code Node.Builder}
276 */
277 static <T> Node.Builder<T> builder() {
278 return new SpinedNodeBuilder<>();
279 }
280
281 // Int nodes
282
283 /**
284 * Produces a {@link Node.OfInt} describing an int[] array.
285 * <p>
286 * The node will hold a reference to the array and will not make a copy.
287 *
288 * @param array the array
289 * @return a node holding an array
290 */
291 static Node.OfInt node(int[] array) {
292 return new IntArrayNode(array);
293 }
294
295 /**
296 * Produces a {@link Node.Builder.OfInt}.
297 *
298 * @param exactSizeIfKnown -1 if a variable size builder is requested,
299 * otherwise the exact capacity desired. A fixed capacity builder will
300 * fail if the wrong number of elements are added to the builder.
301 * @return a {@code Node.Builder.OfInt}
302 */
303 static Node.Builder.OfInt intBuilder(long exactSizeIfKnown) {
304 return (exactSizeIfKnown >= 0 && exactSizeIfKnown < MAX_ARRAY_SIZE)
305 ? new IntFixedNodeBuilder(exactSizeIfKnown)
306 : intBuilder();
307 }
308
309 /**
310 * Produces a variable size @{link Node.Builder.OfInt}.
311 *
312 * @return a {@code Node.Builder.OfInt}
313 */
314 static Node.Builder.OfInt intBuilder() {
315 return new IntSpinedNodeBuilder();
316 }
317
318 // Long nodes
319
320 /**
321 * Produces a {@link Node.OfLong} describing a long[] array.
322 * <p>
323 * The node will hold a reference to the array and will not make a copy.
324 *
325 * @param array the array
326 * @return a node holding an array
327 */
328 static Node.OfLong node(final long[] array) {
329 return new LongArrayNode(array);
330 }
331
332 /**
333 * Produces a {@link Node.Builder.OfLong}.
334 *
335 * @param exactSizeIfKnown -1 if a variable size builder is requested,
336 * otherwise the exact capacity desired. A fixed capacity builder will
337 * fail if the wrong number of elements are added to the builder.
338 * @return a {@code Node.Builder.OfLong}
339 */
340 static Node.Builder.OfLong longBuilder(long exactSizeIfKnown) {
341 return (exactSizeIfKnown >= 0 && exactSizeIfKnown < MAX_ARRAY_SIZE)
342 ? new LongFixedNodeBuilder(exactSizeIfKnown)
343 : longBuilder();
344 }
345
346 /**
347 * Produces a variable size @{link Node.Builder.OfLong}.
348 *
349 * @return a {@code Node.Builder.OfLong}
350 */
351 static Node.Builder.OfLong longBuilder() {
352 return new LongSpinedNodeBuilder();
353 }
354
355 // Double nodes
356
357 /**
358 * Produces a {@link Node.OfDouble} describing a double[] array.
359 * <p>
360 * The node will hold a reference to the array and will not make a copy.
361 *
362 * @param array the array
363 * @return a node holding an array
364 */
365 static Node.OfDouble node(final double[] array) {
366 return new DoubleArrayNode(array);
367 }
368
369 /**
370 * Produces a {@link Node.Builder.OfDouble}.
371 *
372 * @param exactSizeIfKnown -1 if a variable size builder is requested,
373 * otherwise the exact capacity desired. A fixed capacity builder will
374 * fail if the wrong number of elements are added to the builder.
375 * @return a {@code Node.Builder.OfDouble}
376 */
377 static Node.Builder.OfDouble doubleBuilder(long exactSizeIfKnown) {
378 return (exactSizeIfKnown >= 0 && exactSizeIfKnown < MAX_ARRAY_SIZE)
379 ? new DoubleFixedNodeBuilder(exactSizeIfKnown)
380 : doubleBuilder();
381 }
382
383 /**
384 * Produces a variable size @{link Node.Builder.OfDouble}.
385 *
386 * @return a {@code Node.Builder.OfDouble}
387 */
388 static Node.Builder.OfDouble doubleBuilder() {
389 return new DoubleSpinedNodeBuilder();
390 }
391
392 // Parallel evaluation of pipelines to nodes
393
394 /**
395 * Collect, in parallel, elements output from a pipeline and describe those
396 * elements with a {@link Node}.
397 *
398 * @implSpec
399 * If the exact size of the output from the pipeline is known and the source
400 * {@link Spliterator} has the {@link Spliterator#SUBSIZED} characteristic,
401 * then a flat {@link Node} will be returned whose content is an array,
402 * since the size is known the array can be constructed in advance and
403 * output elements can be placed into the array concurrently by leaf
404 * tasks at the correct offsets. If the exact size is not known, output
405 * elements are collected into a conc-node whose shape mirrors that
406 * of the computation. This conc-node can then be flattened in
407 * parallel to produce a flat {@code Node} if desired.
408 *
409 * @param helper the pipeline helper describing the pipeline
410 * @param flattenTree whether a conc node should be flattened into a node
411 * describing an array before returning
412 * @param generator the array generator
413 * @return a {@link Node} describing the output elements
414 */
415 public static <P_IN, P_OUT> Node<P_OUT> collect(PipelineHelper<P_OUT> helper,
416 Spliterator<P_IN> spliterator,
417 boolean flattenTree,
418 IntFunction<P_OUT[]> generator) {
419 long size = helper.exactOutputSizeIfKnown(spliterator);
420 if (size >= 0 && spliterator.hasCharacteristics(Spliterator.SUBSIZED)) {
421 if (size >= MAX_ARRAY_SIZE)
422 throw new IllegalArgumentException("Stream size exceeds max array size");
423 P_OUT[] array = generator.apply((int) size);
424 new SizedCollectorTask.OfRef<>(spliterator, helper, array).invoke();
425 return node(array);
426 } else {
427 Node<P_OUT> node = new CollectorTask<>(helper, generator, spliterator).invoke();
428 return flattenTree ? flatten(node, generator) : node;
429 }
430 }
431
432 /**
433 * Collect, in parallel, elements output from an int-valued pipeline and
434 * describe those elements with a {@link Node.OfInt}.
435 *
436 * @implSpec
437 * If the exact size of the output from the pipeline is known and the source
438 * {@link Spliterator} has the {@link Spliterator#SUBSIZED} characteristic,
439 * then a flat {@link Node} will be returned whose content is an array,
440 * since the size is known the array can be constructed in advance and
441 * output elements can be placed into the array concurrently by leaf
442 * tasks at the correct offsets. If the exact size is not known, output
443 * elements are collected into a conc-node whose shape mirrors that
444 * of the computation. This conc-node can then be flattened in
445 * parallel to produce a flat {@code Node.OfInt} if desired.
446 *
447 * @param helper the pipeline helper describing the pipeline
448 * @param flattenTree whether a conc node should be flattened into a node
449 * describing an array before returning
450 * @return a {@link Node.OfInt} describing the output elements
451 */
452 public static <P_IN> Node.OfInt collectInt(PipelineHelper<Integer> helper,
453 Spliterator<P_IN> spliterator,
454 boolean flattenTree) {
455 long size = helper.exactOutputSizeIfKnown(spliterator);
456 if (size >= 0 && spliterator.hasCharacteristics(Spliterator.SUBSIZED)) {
457 if (size >= MAX_ARRAY_SIZE)
458 throw new IllegalArgumentException("Stream size exceeds max array size");
459 int[] array = new int[(int) size];
460 new SizedCollectorTask.OfInt<>(spliterator, helper, array).invoke();
461 return node(array);
462 }
463 else {
464 Node.OfInt node = new IntCollectorTask<>(helper, spliterator).invoke();
465 return flattenTree ? flattenInt(node) : node;
466 }
467 }
468
469 /**
470 * Collect, in parallel, elements output from a long-valued pipeline and
471 * describe those elements with a {@link Node.OfLong}.
472 *
473 * @implSpec
474 * If the exact size of the output from the pipeline is known and the source
475 * {@link Spliterator} has the {@link Spliterator#SUBSIZED} characteristic,
476 * then a flat {@link Node} will be returned whose content is an array,
477 * since the size is known the array can be constructed in advance and
478 * output elements can be placed into the array concurrently by leaf
479 * tasks at the correct offsets. If the exact size is not known, output
480 * elements are collected into a conc-node whose shape mirrors that
481 * of the computation. This conc-node can then be flattened in
482 * parallel to produce a flat {@code Node.OfLong} if desired.
483 *
484 * @param helper the pipeline helper describing the pipeline
485 * @param flattenTree whether a conc node should be flattened into a node
486 * describing an array before returning
487 * @return a {@link Node.OfLong} describing the output elements
488 */
489 public static <P_IN> Node.OfLong collectLong(PipelineHelper<Long> helper,
490 Spliterator<P_IN> spliterator,
491 boolean flattenTree) {
492 long size = helper.exactOutputSizeIfKnown(spliterator);
493 if (size >= 0 && spliterator.hasCharacteristics(Spliterator.SUBSIZED)) {
494 if (size >= MAX_ARRAY_SIZE)
495 throw new IllegalArgumentException("Stream size exceeds max array size");
496 long[] array = new long[(int) size];
497 new SizedCollectorTask.OfLong<>(spliterator, helper, array).invoke();
498 return node(array);
499 }
500 else {
501 Node.OfLong node = new LongCollectorTask<>(helper, spliterator).invoke();
502 return flattenTree ? flattenLong(node) : node;
503 }
504 }
505
506 /**
507 * Collect, in parallel, elements output from n double-valued pipeline and
508 * describe those elements with a {@link Node.OfDouble}.
509 *
510 * @implSpec
511 * If the exact size of the output from the pipeline is known and the source
512 * {@link Spliterator} has the {@link Spliterator#SUBSIZED} characteristic,
513 * then a flat {@link Node} will be returned whose content is an array,
514 * since the size is known the array can be constructed in advance and
515 * output elements can be placed into the array concurrently by leaf
516 * tasks at the correct offsets. If the exact size is not known, output
517 * elements are collected into a conc-node whose shape mirrors that
518 * of the computation. This conc-node can then be flattened in
519 * parallel to produce a flat {@code Node.OfDouble} if desired.
520 *
521 * @param helper the pipeline helper describing the pipeline
522 * @param flattenTree whether a conc node should be flattened into a node
523 * describing an array before returning
524 * @return a {@link Node.OfDouble} describing the output elements
525 */
526 public static <P_IN> Node.OfDouble collectDouble(PipelineHelper<Double> helper,
527 Spliterator<P_IN> spliterator,
528 boolean flattenTree) {
529 long size = helper.exactOutputSizeIfKnown(spliterator);
530 if (size >= 0 && spliterator.hasCharacteristics(Spliterator.SUBSIZED)) {
531 if (size >= MAX_ARRAY_SIZE)
532 throw new IllegalArgumentException("Stream size exceeds max array size");
533 double[] array = new double[(int) size];
534 new SizedCollectorTask.OfDouble<>(spliterator, helper, array).invoke();
535 return node(array);
536 }
537 else {
538 Node.OfDouble node = new DoubleCollectorTask<>(helper, spliterator).invoke();
539 return flattenTree ? flattenDouble(node) : node;
540 }
541 }
542
543 // Parallel flattening of nodes
544
545 /**
546 * Flatten, in parallel, a {@link Node}. A flattened node is one that has
547 * no children. If the node is already flat, it is simply returned.
548 *
549 * @implSpec
550 * If a new node is to be created, the generator is used to create an array
551 * whose length is {@link Node#count()}. Then the node tree is traversed
552 * and leaf node elements are placed in the array concurrently by leaf tasks
553 * at the correct offsets.
554 *
555 * @param node the node to flatten
556 * @param generator the array factory used to create array instances
557 * @param <T> type of elements contained by the node
558 * @return a flat {@code Node}
559 */
560 public static <T> Node<T> flatten(Node<T> node, IntFunction<T[]> generator) {
561 if (node.getChildCount() > 0) {
562 T[] array = generator.apply((int) node.count());
563 new ToArrayTask.OfRef<>(node, array, 0).invoke();
564 return node(array);
565 } else {
566 return node;
567 }
568 }
569
570 /**
571 * Flatten, in parallel, a {@link Node.OfInt}. A flattened node is one that
572 * has no children. If the node is already flat, it is simply returned.
573 *
574 * @implSpec
575 * If a new node is to be created, a new int[] array is created whose length
576 * is {@link Node#count()}. Then the node tree is traversed and leaf node
577 * elements are placed in the array concurrently by leaf tasks at the
578 * correct offsets.
579 *
580 * @param node the node to flatten
581 * @return a flat {@code Node.OfInt}
582 */
583 public static Node.OfInt flattenInt(Node.OfInt node) {
584 if (node.getChildCount() > 0) {
585 int[] array = new int[(int) node.count()];
586 new ToArrayTask.OfInt(node, array, 0).invoke();
587 return node(array);
588 } else {
589 return node;
590 }
591 }
592
593 /**
594 * Flatten, in parallel, a {@link Node.OfLong}. A flattened node is one that
595 * has no children. If the node is already flat, it is simply returned.
596 *
597 * @implSpec
598 * If a new node is to be created, a new long[] array is created whose length
599 * is {@link Node#count()}. Then the node tree is traversed and leaf node
600 * elements are placed in the array concurrently by leaf tasks at the
601 * correct offsets.
602 *
603 * @param node the node to flatten
604 * @return a flat {@code Node.OfLong}
605 */
606 public static Node.OfLong flattenLong(Node.OfLong node) {
607 if (node.getChildCount() > 0) {
608 long[] array = new long[(int) node.count()];
609 new ToArrayTask.OfLong(node, array, 0).invoke();
610 return node(array);
611 } else {
612 return node;
613 }
614 }
615
616 /**
617 * Flatten, in parallel, a {@link Node.OfDouble}. A flattened node is one that
618 * has no children. If the node is already flat, it is simply returned.
619 *
620 * @implSpec
621 * If a new node is to be created, a new double[] array is created whose length
622 * is {@link Node#count()}. Then the node tree is traversed and leaf node
623 * elements are placed in the array concurrently by leaf tasks at the
624 * correct offsets.
625 *
626 * @param node the node to flatten
627 * @return a flat {@code Node.OfDouble}
628 */
629 public static Node.OfDouble flattenDouble(Node.OfDouble node) {
630 if (node.getChildCount() > 0) {
631 double[] array = new double[(int) node.count()];
632 new ToArrayTask.OfDouble(node, array, 0).invoke();
633 return node(array);
634 } else {
635 return node;
636 }
637 }
638
639 // Implementations
640
641 private static abstract class EmptyNode<T, T_ARR, T_CONS> implements Node<T> {
642 EmptyNode() { }
643
644 @Override
645 public T[] asArray(IntFunction<T[]> generator) {
646 return generator.apply(0);
647 }
648
649 public void copyInto(T_ARR array, int offset) { }
650
651 @Override
652 public long count() {
653 return 0;
654 }
655
656 public void forEach(T_CONS consumer) { }
657
658 private static class OfRef<T> extends EmptyNode<T, T[], Consumer<? super T>> {
659 private OfRef() {
660 super();
661 }
662
663 @Override
664 public Spliterator<T> spliterator() {
665 return Spliterators.emptySpliterator();
666 }
667 }
668
669 private static final class OfInt
670 extends EmptyNode<Integer, int[], IntConsumer>
671 implements Node.OfInt {
672
673 OfInt() { } // Avoid creation of special accessor
674
675 @Override
676 public Spliterator.OfInt spliterator() {
677 return Spliterators.emptyIntSpliterator();
678 }
679
680 @Override
681 public int[] asIntArray() {
682 return EMPTY_INT_ARRAY;
683 }
684 }
685
686 private static final class OfLong
687 extends EmptyNode<Long, long[], LongConsumer>
688 implements Node.OfLong {
689
690 OfLong() { } // Avoid creation of special accessor
691
692 @Override
693 public Spliterator.OfLong spliterator() {
694 return Spliterators.emptyLongSpliterator();
695 }
696
697 @Override
698 public long[] asLongArray() {
699 return EMPTY_LONG_ARRAY;
700 }
701 }
702
703 private static final class OfDouble
704 extends EmptyNode<Double, double[], DoubleConsumer>
705 implements Node.OfDouble {
706
707 OfDouble() { } // Avoid creation of special accessor
708
709 @Override
710 public Spliterator.OfDouble spliterator() {
711 return Spliterators.emptyDoubleSpliterator();
712 }
713
714 @Override
715 public double[] asDoubleArray() {
716 return EMPTY_DOUBLE_ARRAY;
717 }
718 }
719 }
720
721 /** Node class for a reference array */
722 private static class ArrayNode<T> implements Node<T> {
723 final T[] array;
724 int curSize;
725
726 @SuppressWarnings("unchecked")
727 ArrayNode(long size, IntFunction<T[]> generator) {
728 if (size >= MAX_ARRAY_SIZE)
729 throw new IllegalArgumentException("Stream size exceeds max array size");
730 this.array = generator.apply((int) size);
731 this.curSize = 0;
732 }
733
734 ArrayNode(T[] array) {
735 this.array = array;
736 this.curSize = array.length;
737 }
738
739 // Node
740
741 @Override
742 public Spliterator<T> spliterator() {
743 return Arrays.spliterator(array, 0, curSize);
744 }
745
746 @Override
747 public void copyInto(T[] dest, int destOffset) {
748 System.arraycopy(array, 0, dest, destOffset, curSize);
749 }
750
751 @Override
752 public T[] asArray(IntFunction<T[]> generator) {
753 if (array.length == curSize) {
754 return array;
755 } else {
756 throw new IllegalStateException();
757 }
758 }
759
760 @Override
761 public long count() {
762 return curSize;
763 }
764
765 // Traversable
766
767 @Override
768 public void forEach(Consumer<? super T> consumer) {
769 for (int i = 0; i < curSize; i++) {
770 consumer.accept(array[i]);
771 }
772 }
773
774 //
775
776 @Override
777 public String toString() {
778 return String.format("ArrayNode[%d][%s]",
779 array.length - curSize, Arrays.toString(array));
780 }
781 }
782
783 /** Node class for a Collection */
784 private static final class CollectionNode<T> implements Node<T> {
785 private final Collection<T> c;
786
787 CollectionNode(Collection<T> c) {
788 this.c = c;
789 }
790
791 // Node
792
793 @Override
794 public Spliterator<T> spliterator() {
795 return c.stream().spliterator();
796 }
797
798 @Override
799 public void copyInto(T[] array, int offset) {
800 for (T t : c)
801 array[offset++] = t;
802 }
803
804 @Override
805 @SuppressWarnings("unchecked")
806 public T[] asArray(IntFunction<T[]> generator) {
807 return c.toArray(generator.apply(c.size()));
808 }
809
810 @Override
811 public long count() {
812 return c.size();
813 }
814
815 @Override
816 public void forEach(Consumer<? super T> consumer) {
817 c.forEach(consumer);
818 }
819
820 //
821
822 @Override
823 public String toString() {
824 return String.format("CollectionNode[%d][%s]", c.size(), c);
825 }
826 }
827
828 /** Node class for an internal node with two or more children */
829 static final class ConcNode<T> implements Node<T> {
830 private final Node<T> left;
831 private final Node<T> right;
832
833 private final long size;
834
835 ConcNode(Node<T> left, Node<T> right) {
836 this.left = left;
837 this.right = right;
838 // The Node count will be required when the Node spliterator is
839 // obtained and it is cheaper to aggressively calculate bottom up
840 // as the tree is built rather than later on from the top down
841 // traversing the tree
842 this.size = left.count() + right.count();
843 }
844
845 // Node
846
847 @Override
848 public Spliterator<T> spliterator() {
849 return new Nodes.InternalNodeSpliterator.OfRef<>(this);
850 }
851
852 @Override
853 public int getChildCount() {
854 return 2;
855 }
856
857 @Override
858 public Node<T> getChild(int i) {
859 if (i == 0) return left;
860 if (i == 1) return right;
861 throw new IndexOutOfBoundsException();
862 }
863
864 @Override
865 public void copyInto(T[] array, int offset) {
866 Objects.requireNonNull(array);
867 left.copyInto(array, offset);
868 right.copyInto(array, offset + (int) left.count());
869 }
870
871 @Override
872 public T[] asArray(IntFunction<T[]> generator) {
873 T[] array = generator.apply((int) count());
874 copyInto(array, 0);
875 return array;
876 }
877
878 @Override
879 public long count() {
880 return size;
881 }
882
883 @Override
884 public void forEach(Consumer<? super T> consumer) {
885 left.forEach(consumer);
886 right.forEach(consumer);
887 }
888
889 @Override
890 public String toString() {
891 if (count() < 32) {
892 return String.format("ConcNode[%s]",
893 Arrays.asList(left, right).stream()
894 .map(Object::toString)
895 .collect(toStringJoiner(","))
896 .toString());
897 } else {
898 return String.format("ConcNode[size=%d]", count());
899 }
900 }
901 }
902
903 /** Abstract class for spliterator for all internal node classes */
904 private static abstract class InternalNodeSpliterator<T,
905 S extends Spliterator<T>,
906 N extends Node<T>, C>
907 implements Spliterator<T> {
908 // Node we are pointing to
909 // null if full traversal has occurred
910 N curNode;
911
912 // next child of curNode to consume
913 int curChildIndex;
914
915 // The spliterator of the curNode if that node is last and has no children.
916 // This spliterator will be delegated to for splitting and traversing.
917 // null if curNode has children
918 S lastNodeSpliterator;
919
920 // spliterator used while traversing with tryAdvance
921 // null if no partial traversal has occurred
922 S tryAdvanceSpliterator;
923
924 // node stack used when traversing to search and find leaf nodes
925 // null if no partial traversal has occurred
926 Deque<N> tryAdvanceStack;
927
928 InternalNodeSpliterator(N curNode) {
929 this.curNode = curNode;
930 }
931
932 /**
933 * Initiate a stack containing, in left-to-right order, the child nodes
934 * covered by this spliterator
935 */
936 protected final Deque<N> initStack() {
937 // Bias size to the case where leaf nodes are close to this node
938 // 8 is the minimum initial capacity for the ArrayDeque implementation
939 Deque<N> stack = new ArrayDeque<>(8);
940 for (int i = curNode.getChildCount() - 1; i >= curChildIndex; i--)
941 stack.addFirst((N) curNode.getChild(i));
942 return stack;
943 }
944
945 /**
946 * Depth first search, in left-to-right order, of the node tree, using
947 * an explicit stack, to find the next non-empty leaf node.
948 */
949 protected final N findNextLeafNode(Deque<N> stack) {
950 N n = null;
951 while ((n = stack.pollFirst()) != null) {
952 if (n.getChildCount() == 0) {
953 if (n.count() > 0)
954 return n;
955 } else {
956 for (int i = n.getChildCount() - 1; i >= 0; i--)
957 stack.addFirst((N) n.getChild(i));
958 }
959 }
960
961 return null;
962 }
963
964 protected final boolean internalTryAdvance(C consumer) {
965 if (curNode == null)
966 return false;
967
968 if (tryAdvanceSpliterator == null) {
969 if (lastNodeSpliterator == null) {
970 // Initiate the node stack
971 tryAdvanceStack = initStack();
972 N leaf = findNextLeafNode(tryAdvanceStack);
973 if (leaf != null)
974 tryAdvanceSpliterator = (S) leaf.spliterator();
975 else {
976 // A non-empty leaf node was not found
977 // No elements to traverse
978 curNode = null;
979 return false;
980 }
981 }
982 else
983 tryAdvanceSpliterator = lastNodeSpliterator;
984 }
985
986 boolean hasNext = tryAdvance(tryAdvanceSpliterator, consumer);
987 if (!hasNext) {
988 if (lastNodeSpliterator == null) {
989 // Advance to the spliterator of the next non-empty leaf node
990 Node<T> leaf = findNextLeafNode(tryAdvanceStack);
991 if (leaf != null) {
992 tryAdvanceSpliterator = (S) leaf.spliterator();
993 // Since the node is not-empty the spliterator can be advanced
994 return tryAdvance(tryAdvanceSpliterator, consumer);
995 }
996 }
997 // No more elements to traverse
998 curNode = null;
999 }
1000 return hasNext;
1001 }
1002
1003 protected abstract boolean tryAdvance(S spliterator, C consumer);
1004
1005 @Override
1006 @SuppressWarnings("unchecked")
1007 public S trySplit() {
1008 if (curNode == null || tryAdvanceSpliterator != null)
1009 return null; // Cannot split if fully or partially traversed
1010 else if (lastNodeSpliterator != null)
1011 return (S) lastNodeSpliterator.trySplit();
1012 else if (curChildIndex < curNode.getChildCount() - 1)
1013 return (S) curNode.getChild(curChildIndex++).spliterator();
1014 else {
1015 curNode = (N) curNode.getChild(curChildIndex);
1016 if (curNode.getChildCount() == 0) {
1017 lastNodeSpliterator = (S) curNode.spliterator();
1018 return (S) lastNodeSpliterator.trySplit();
1019 }
1020 else {
1021 curChildIndex = 0;
1022 return (S) curNode.getChild(curChildIndex++).spliterator();
1023 }
1024 }
1025 }
1026
1027 @Override
1028 public long estimateSize() {
1029 if (curNode == null)
1030 return 0;
1031
1032 // Will not reflect the effects of partial traversal.
1033 // This is compliant with the specification
1034 if (lastNodeSpliterator != null)
1035 return lastNodeSpliterator.estimateSize();
1036 else {
1037 long size = 0;
1038 for (int i = curChildIndex; i < curNode.getChildCount(); i++)
1039 size += curNode.getChild(i).count();
1040 return size;
1041 }
1042 }
1043
1044 @Override
1045 public int characteristics() {
1046 return Spliterator.SIZED;
1047 }
1048
1049 private static final class OfRef<T>
1050 extends InternalNodeSpliterator<T, Spliterator<T>, Node<T>, Consumer<? super T>> {
1051
1052 OfRef(Node<T> curNode) {
1053 super(curNode);
1054 }
1055
1056 @Override
1057 public boolean tryAdvance(Consumer<? super T> consumer) {
1058 return internalTryAdvance(consumer);
1059 }
1060
1061 @Override
1062 protected boolean tryAdvance(Spliterator<T> spliterator,
1063 Consumer<? super T> consumer) {
1064 return spliterator.tryAdvance(consumer);
1065 }
1066
1067 @Override
1068 public void forEachRemaining(Consumer<? super T> consumer) {
1069 if (curNode == null)
1070 return;
1071
1072 if (tryAdvanceSpliterator == null) {
1073 if (lastNodeSpliterator == null) {
1074 Deque<Node<T>> stack = initStack();
1075 Node<T> leaf;
1076 while ((leaf = findNextLeafNode(stack)) != null) {
1077 leaf.forEach(consumer);
1078 }
1079 curNode = null;
1080 }
1081 else
1082 lastNodeSpliterator.forEachRemaining(consumer);
1083 }
1084 else
1085 while(tryAdvance(consumer)) { }
1086 }
1087 }
1088
1089 private static final class OfInt
1090 extends InternalNodeSpliterator<Integer, Spliterator.OfInt, Node.OfInt, IntConsumer>
1091 implements Spliterator.OfInt {
1092
1093 OfInt(Node.OfInt cur) {
1094 super(cur);
1095 }
1096
1097 @Override
1098 public boolean tryAdvance(IntConsumer consumer) {
1099 return internalTryAdvance(consumer);
1100 }
1101
1102 @Override
1103 protected boolean tryAdvance(Spliterator.OfInt spliterator,
1104 IntConsumer consumer) {
1105 return spliterator.tryAdvance(consumer);
1106 }
1107
1108 @Override
1109 public void forEachRemaining(IntConsumer consumer) {
1110 if (curNode == null)
1111 return;
1112
1113 if (tryAdvanceSpliterator == null) {
1114 if (lastNodeSpliterator == null) {
1115 Deque<Node.OfInt> stack = initStack();
1116 Node.OfInt leaf;
1117 while ((leaf = findNextLeafNode(stack)) != null) {
1118 leaf.forEach(consumer);
1119 }
1120 curNode = null;
1121 }
1122 else
1123 lastNodeSpliterator.forEachRemaining(consumer);
1124 }
1125 else
1126 while(tryAdvance(consumer)) { }
1127 }
1128 }
1129
1130 private static final class OfLong
1131 extends InternalNodeSpliterator<Long, Spliterator.OfLong, Node.OfLong, LongConsumer>
1132 implements Spliterator.OfLong {
1133
1134 OfLong(Node.OfLong cur) {
1135 super(cur);
1136 }
1137
1138 @Override
1139 public boolean tryAdvance(LongConsumer consumer) {
1140 return internalTryAdvance(consumer);
1141 }
1142
1143 @Override
1144 protected boolean tryAdvance(Spliterator.OfLong spliterator,
1145 LongConsumer consumer) {
1146 return spliterator.tryAdvance(consumer);
1147 }
1148
1149 @Override
1150 public void forEachRemaining(LongConsumer consumer) {
1151 if (curNode == null)
1152 return;
1153
1154 if (tryAdvanceSpliterator == null) {
1155 if (lastNodeSpliterator == null) {
1156 Deque<Node.OfLong> stack = initStack();
1157 Node.OfLong leaf;
1158 while ((leaf = findNextLeafNode(stack)) != null) {
1159 leaf.forEach(consumer);
1160 }
1161 curNode = null;
1162 }
1163 else
1164 lastNodeSpliterator.forEachRemaining(consumer);
1165 }
1166 else
1167 while(tryAdvance(consumer)) { }
1168 }
1169 }
1170
1171 private static final class OfDouble
1172 extends InternalNodeSpliterator<Double, Spliterator.OfDouble, Node.OfDouble, DoubleConsumer>
1173 implements Spliterator.OfDouble {
1174
1175 OfDouble(Node.OfDouble cur) {
1176 super(cur);
1177 }
1178
1179 @Override
1180 public boolean tryAdvance(DoubleConsumer consumer) {
1181 return internalTryAdvance(consumer);
1182 }
1183
1184 @Override
1185 protected boolean tryAdvance(Spliterator.OfDouble spliterator,
1186 DoubleConsumer consumer) {
1187 return spliterator.tryAdvance(consumer);
1188 }
1189
1190 @Override
1191 public void forEachRemaining(DoubleConsumer consumer) {
1192 if (curNode == null)
1193 return;
1194
1195 if (tryAdvanceSpliterator == null) {
1196 if (lastNodeSpliterator == null) {
1197 Deque<Node.OfDouble> stack = initStack();
1198 Node.OfDouble leaf;
1199 while ((leaf = findNextLeafNode(stack)) != null) {
1200 leaf.forEach(consumer);
1201 }
1202 curNode = null;
1203 }
1204 else
1205 lastNodeSpliterator.forEachRemaining(consumer);
1206 }
1207 else
1208 while(tryAdvance(consumer)) { }
1209 }
1210 }
1211 }
1212
1213 /** Fixed-sized builder class for reference nodes */
1214 private static final class FixedNodeBuilder<T>
1215 extends ArrayNode<T>
1216 implements Node.Builder<T> {
1217
1218 FixedNodeBuilder(long size, IntFunction<T[]> generator) {
1219 super(size, generator);
1220 assert size < MAX_ARRAY_SIZE;
1221 }
1222
1223 @Override
1224 public Node<T> build() {
1225 if (curSize < array.length)
1226 throw new IllegalStateException(String.format("Current size %d is less than fixed size %d",
1227 curSize, array.length));
1228 return this;
1229 }
1230
1231 @Override
1232 public void begin(long size) {
1233 if (size != array.length)
1234 throw new IllegalStateException(String.format("Begin size %d is not equal to fixed size %d",
1235 size, array.length));
1236 curSize = 0;
1237 }
1238
1239 @Override
1240 public void accept(T t) {
1241 if (curSize < array.length) {
1242 array[curSize++] = t;
1243 } else {
1244 throw new IllegalStateException(String.format("Accept exceeded fixed size of %d",
1245 array.length));
1246 }
1247 }
1248
1249 @Override
1250 public void end() {
1251 if (curSize < array.length)
1252 throw new IllegalStateException(String.format("End size %d is less than fixed size %d",
1253 curSize, array.length));
1254 }
1255
1256 @Override
1257 public String toString() {
1258 return String.format("FixedNodeBuilder[%d][%s]",
1259 array.length - curSize, Arrays.toString(array));
1260 }
1261 }
1262
1263 /** Variable-sized builder class for reference nodes */
1264 private static final class SpinedNodeBuilder<T>
1265 extends SpinedBuffer<T>
1266 implements Node<T>, Node.Builder<T> {
1267 private boolean building = false;
1268
1269 SpinedNodeBuilder() {} // Avoid creation of special accessor
1270
1271 @Override
1272 public Spliterator<T> spliterator() {
1273 assert !building : "during building";
1274 return super.spliterator();
1275 }
1276
1277 @Override
1278 public void forEach(Consumer<? super T> consumer) {
1279 assert !building : "during building";
1280 super.forEach(consumer);
1281 }
1282
1283 //
1284 @Override
1285 public void begin(long size) {
1286 assert !building : "was already building";
1287 building = true;
1288 clear();
1289 ensureCapacity(size);
1290 }
1291
1292 @Override
1293 public void accept(T t) {
1294 assert building : "not building";
1295 super.accept(t);
1296 }
1297
1298 @Override
1299 public void end() {
1300 assert building : "was not building";
1301 building = false;
1302 // @@@ check begin(size) and size
1303 }
1304
1305 @Override
1306 public void copyInto(T[] array, int offset) {
1307 assert !building : "during building";
1308 super.copyInto(array, offset);
1309 }
1310
1311 @Override
1312 public T[] asArray(IntFunction<T[]> arrayFactory) {
1313 assert !building : "during building";
1314 return super.asArray(arrayFactory);
1315 }
1316
1317 @Override
1318 public Node<T> build() {
1319 assert !building : "during building";
1320 return this;
1321 }
1322 }
1323
1324 //
1325
1326 private static final int[] EMPTY_INT_ARRAY = new int[0];
1327 private static final long[] EMPTY_LONG_ARRAY = new long[0];
1328 private static final double[] EMPTY_DOUBLE_ARRAY = new double[0];
1329
1330 private abstract static class AbstractPrimitiveConcNode<E, N extends Node<E>>
1331 implements Node<E> {
1332 final N left;
1333 final N right;
1334 final long size;
1335
1336 AbstractPrimitiveConcNode(N left, N right) {
1337 this.left = left;
1338 this.right = right;
1339 // The Node count will be required when the Node spliterator is
1340 // obtained and it is cheaper to aggressively calculate bottom up as
1341 // the tree is built rather than later on by traversing the tree
1342 this.size = left.count() + right.count();
1343 }
1344
1345 @Override
1346 public int getChildCount() {
1347 return 2;
1348 }
1349
1350 @Override
1351 public N getChild(int i) {
1352 if (i == 0) return left;
1353 if (i == 1) return right;
1354 throw new IndexOutOfBoundsException();
1355 }
1356
1357 @Override
1358 public long count() {
1359 return size;
1360 }
1361
1362 @Override
1363 public String toString() {
1364 if (count() < 32)
1365 return String.format("%s[%s]", this.getClass().getName(),
1366 Arrays.asList(left, right).stream()
1367 .map(Object::toString)
1368 .collect(toStringJoiner(","))
1369 .toString());
1370 else
1371 return String.format("%s[size=%d]", this.getClass().getName(), count());
1372 }
1373 }
1374
1375 private static class IntArrayNode implements Node.OfInt {
1376 final int[] array;
1377 int curSize;
1378
1379 IntArrayNode(long size) {
1380 if (size >= MAX_ARRAY_SIZE)
1381 throw new IllegalArgumentException("Stream size exceeds max array size");
1382 this.array = new int[(int) size];
1383 this.curSize = 0;
1384 }
1385
1386 IntArrayNode(int[] array) {
1387 this.array = array;
1388 this.curSize = array.length;
1389 }
1390
1391 // Node
1392
1393 @Override
1394 public Spliterator.OfInt spliterator() {
1395 return Arrays.spliterator(array, 0, curSize);
1396 }
1397
1398 @Override
1399 public int[] asIntArray() {
1400 if (array.length == curSize) {
1401 return array;
1402 } else {
1403 return Arrays.copyOf(array, curSize);
1404 }
1405 }
1406
1407 @Override
1408 public void copyInto(int[] dest, int destOffset) {
1409 System.arraycopy(array, 0, dest, destOffset, curSize);
1410 }
1411
1412 @Override
1413 public long count() {
1414 return curSize;
1415 }
1416
1417 @Override
1418 public void forEach(IntConsumer consumer) {
1419 for (int i = 0; i < curSize; i++) {
1420 consumer.accept(array[i]);
1421 }
1422 }
1423
1424 @Override
1425 public String toString() {
1426 return String.format("IntArrayNode[%d][%s]",
1427 array.length - curSize, Arrays.toString(array));
1428 }
1429 }
1430
1431 private static class LongArrayNode implements Node.OfLong {
1432 final long[] array;
1433 int curSize;
1434
1435 LongArrayNode(long size) {
1436 if (size >= MAX_ARRAY_SIZE)
1437 throw new IllegalArgumentException("Stream size exceeds max array size");
1438 this.array = new long[(int) size];
1439 this.curSize = 0;
1440 }
1441
1442 LongArrayNode(long[] array) {
1443 this.array = array;
1444 this.curSize = array.length;
1445 }
1446
1447 @Override
1448 public Spliterator.OfLong spliterator() {
1449 return Arrays.spliterator(array, 0, curSize);
1450 }
1451
1452 @Override
1453 public long[] asLongArray() {
1454 if (array.length == curSize) {
1455 return array;
1456 } else {
1457 return Arrays.copyOf(array, curSize);
1458 }
1459 }
1460
1461 @Override
1462 public void copyInto(long[] dest, int destOffset) {
1463 System.arraycopy(array, 0, dest, destOffset, curSize);
1464 }
1465
1466 @Override
1467 public long count() {
1468 return curSize;
1469 }
1470
1471 @Override
1472 public void forEach(LongConsumer consumer) {
1473 for (int i = 0; i < curSize; i++) {
1474 consumer.accept(array[i]);
1475 }
1476 }
1477
1478 @Override
1479 public String toString() {
1480 return String.format("LongArrayNode[%d][%s]",
1481 array.length - curSize, Arrays.toString(array));
1482 }
1483 }
1484
1485 private static class DoubleArrayNode implements Node.OfDouble {
1486 final double[] array;
1487 int curSize;
1488
1489 DoubleArrayNode(long size) {
1490 if (size >= MAX_ARRAY_SIZE)
1491 throw new IllegalArgumentException("Stream size exceeds max array size");
1492 this.array = new double[(int) size];
1493 this.curSize = 0;
1494 }
1495
1496 DoubleArrayNode(double[] array) {
1497 this.array = array;
1498 this.curSize = array.length;
1499 }
1500
1501 @Override
1502 public Spliterator.OfDouble spliterator() {
1503 return Arrays.spliterator(array, 0, curSize);
1504 }
1505
1506 @Override
1507 public double[] asDoubleArray() {
1508 if (array.length == curSize) {
1509 return array;
1510 } else {
1511 return Arrays.copyOf(array, curSize);
1512 }
1513 }
1514
1515 @Override
1516 public void copyInto(double[] dest, int destOffset) {
1517 System.arraycopy(array, 0, dest, destOffset, curSize);
1518 }
1519
1520 @Override
1521 public long count() {
1522 return curSize;
1523 }
1524
1525 @Override
1526 public void forEach(DoubleConsumer consumer) {
1527 for (int i = 0; i < curSize; i++) {
1528 consumer.accept(array[i]);
1529 }
1530 }
1531
1532 @Override
1533 public String toString() {
1534 return String.format("DoubleArrayNode[%d][%s]",
1535 array.length - curSize, Arrays.toString(array));
1536 }
1537 }
1538
1539 static final class IntConcNode
1540 extends AbstractPrimitiveConcNode<Integer, Node.OfInt>
1541 implements Node.OfInt {
1542
1543 IntConcNode(Node.OfInt left, Node.OfInt right) {
1544 super(left, right);
1545 }
1546
1547 @Override
1548 public void forEach(IntConsumer consumer) {
1549 left.forEach(consumer);
1550 right.forEach(consumer);
1551 }
1552
1553 @Override
1554 public Spliterator.OfInt spliterator() {
1555 return new InternalNodeSpliterator.OfInt(this);
1556 }
1557
1558 @Override
1559 public void copyInto(int[] array, int offset) {
1560 left.copyInto(array, offset);
1561 right.copyInto(array, offset + (int) left.count());
1562 }
1563
1564 @Override
1565 public int[] asIntArray() {
1566 int[] array = new int[(int) count()];
1567 copyInto(array, 0);
1568 return array;
1569 }
1570 }
1571
1572 static final class LongConcNode
1573 extends AbstractPrimitiveConcNode<Long, Node.OfLong>
1574 implements Node.OfLong {
1575
1576 LongConcNode(Node.OfLong left, Node.OfLong right) {
1577 super(left, right);
1578 }
1579
1580 @Override
1581 public void forEach(LongConsumer consumer) {
1582 left.forEach(consumer);
1583 right.forEach(consumer);
1584 }
1585
1586 @Override
1587 public Spliterator.OfLong spliterator() {
1588 return new InternalNodeSpliterator.OfLong(this);
1589 }
1590
1591 @Override
1592 public void copyInto(long[] array, int offset) {
1593 left.copyInto(array, offset);
1594 right.copyInto(array, offset + (int) left.count());
1595 }
1596
1597 @Override
1598 public long[] asLongArray() {
1599 long[] array = new long[(int) count()];
1600 copyInto(array, 0);
1601 return array;
1602 }
1603 }
1604
1605 static final class DoubleConcNode
1606 extends AbstractPrimitiveConcNode<Double, Node.OfDouble>
1607 implements Node.OfDouble {
1608
1609 DoubleConcNode(Node.OfDouble left, Node.OfDouble right) {
1610 super(left, right);
1611 }
1612
1613 @Override
1614 public void forEach(DoubleConsumer consumer) {
1615 left.forEach(consumer);
1616 right.forEach(consumer);
1617 }
1618
1619 @Override
1620 public Spliterator.OfDouble spliterator() {
1621 return new InternalNodeSpliterator.OfDouble(this);
1622 }
1623
1624 @Override
1625 public void copyInto(double[] array, int offset) {
1626 left.copyInto(array, offset);
1627 right.copyInto(array, offset + (int) left.count());
1628 }
1629
1630 @Override
1631 public double[] asDoubleArray() {
1632 double[] array = new double[(int) count()];
1633 copyInto(array, 0);
1634 return array;
1635 }
1636 }
1637
1638 private static final class IntFixedNodeBuilder
1639 extends IntArrayNode
1640 implements Node.Builder.OfInt {
1641
1642 IntFixedNodeBuilder(long size) {
1643 super(size);
1644 assert size < MAX_ARRAY_SIZE;
1645 }
1646
1647 @Override
1648 public Node.OfInt build() {
1649 if (curSize < array.length) {
1650 throw new IllegalStateException(String.format("Current size %d is less than fixed size %d",
1651 curSize, array.length));
1652 }
1653
1654 return this;
1655 }
1656
1657 @Override
1658 public void begin(long size) {
1659 if (size != array.length) {
1660 throw new IllegalStateException(String.format("Begin size %d is not equal to fixed size %d",
1661 size, array.length));
1662 }
1663
1664 curSize = 0;
1665 }
1666
1667 @Override
1668 public void accept(int i) {
1669 if (curSize < array.length) {
1670 array[curSize++] = i;
1671 } else {
1672 throw new IllegalStateException(String.format("Accept exceeded fixed size of %d",
1673 array.length));
1674 }
1675 }
1676
1677 @Override
1678 public void end() {
1679 if (curSize < array.length) {
1680 throw new IllegalStateException(String.format("End size %d is less than fixed size %d",
1681 curSize, array.length));
1682 }
1683 }
1684
1685 @Override
1686 public String toString() {
1687 return String.format("IntFixedNodeBuilder[%d][%s]",
1688 array.length - curSize, Arrays.toString(array));
1689 }
1690 }
1691
1692 private static final class LongFixedNodeBuilder
1693 extends LongArrayNode
1694 implements Node.Builder.OfLong {
1695
1696 LongFixedNodeBuilder(long size) {
1697 super(size);
1698 assert size < MAX_ARRAY_SIZE;
1699 }
1700
1701 @Override
1702 public Node.OfLong build() {
1703 if (curSize < array.length) {
1704 throw new IllegalStateException(String.format("Current size %d is less than fixed size %d",
1705 curSize, array.length));
1706 }
1707
1708 return this;
1709 }
1710
1711 @Override
1712 public void begin(long size) {
1713 if (size != array.length) {
1714 throw new IllegalStateException(String.format("Begin size %d is not equal to fixed size %d",
1715 size, array.length));
1716 }
1717
1718 curSize = 0;
1719 }
1720
1721 @Override
1722 public void accept(long i) {
1723 if (curSize < array.length) {
1724 array[curSize++] = i;
1725 } else {
1726 throw new IllegalStateException(String.format("Accept exceeded fixed size of %d",
1727 array.length));
1728 }
1729 }
1730
1731 @Override
1732 public void end() {
1733 if (curSize < array.length) {
1734 throw new IllegalStateException(String.format("End size %d is less than fixed size %d",
1735 curSize, array.length));
1736 }
1737 }
1738
1739 @Override
1740 public String toString() {
1741 return String.format("LongFixedNodeBuilder[%d][%s]",
1742 array.length - curSize, Arrays.toString(array));
1743 }
1744 }
1745
1746 private static final class DoubleFixedNodeBuilder
1747 extends DoubleArrayNode
1748 implements Node.Builder.OfDouble {
1749
1750 DoubleFixedNodeBuilder(long size) {
1751 super(size);
1752 assert size < MAX_ARRAY_SIZE;
1753 }
1754
1755 @Override
1756 public Node.OfDouble build() {
1757 if (curSize < array.length) {
1758 throw new IllegalStateException(String.format("Current size %d is less than fixed size %d",
1759 curSize, array.length));
1760 }
1761
1762 return this;
1763 }
1764
1765 @Override
1766 public void begin(long size) {
1767 if (size != array.length) {
1768 throw new IllegalStateException(String.format("Begin size %d is not equal to fixed size %d",
1769 size, array.length));
1770 }
1771
1772 curSize = 0;
1773 }
1774
1775 @Override
1776 public void accept(double i) {
1777 if (curSize < array.length) {
1778 array[curSize++] = i;
1779 } else {
1780 throw new IllegalStateException(String.format("Accept exceeded fixed size of %d",
1781 array.length));
1782 }
1783 }
1784
1785 @Override
1786 public void end() {
1787 if (curSize < array.length) {
1788 throw new IllegalStateException(String.format("End size %d is less than fixed size %d",
1789 curSize, array.length));
1790 }
1791 }
1792
1793 @Override
1794 public String toString() {
1795 return String.format("DoubleFixedNodeBuilder[%d][%s]",
1796 array.length - curSize, Arrays.toString(array));
1797 }
1798 }
1799
1800 private static final class IntSpinedNodeBuilder
1801 extends SpinedBuffer.OfInt
1802 implements Node.OfInt, Node.Builder.OfInt {
1803 private boolean building = false;
1804
1805 IntSpinedNodeBuilder() {} // Avoid creation of special accessor
1806
1807 @Override
1808 public Spliterator.OfInt spliterator() {
1809 assert !building : "during building";
1810 return super.spliterator();
1811 }
1812
1813 @Override
1814 public void forEach(IntConsumer consumer) {
1815 assert !building : "during building";
1816 super.forEach(consumer);
1817 }
1818
1819 //
1820 @Override
1821 public void begin(long size) {
1822 assert !building : "was already building";
1823 building = true;
1824 clear();
1825 ensureCapacity(size);
1826 }
1827
1828 @Override
1829 public void accept(int i) {
1830 assert building : "not building";
1831 super.accept(i);
1832 }
1833
1834 @Override
1835 public void end() {
1836 assert building : "was not building";
1837 building = false;
1838 // @@@ check begin(size) and size
1839 }
1840
1841 @Override
1842 public void copyInto(int[] array, int offset) throws IndexOutOfBoundsException {
1843 assert !building : "during building";
1844 super.copyInto(array, offset);
1845 }
1846
1847 @Override
1848 public int[] asIntArray() {
1849 assert !building : "during building";
1850 return super.asIntArray();
1851 }
1852
1853 @Override
1854 public Node.OfInt build() {
1855 assert !building : "during building";
1856 return this;
1857 }
1858 }
1859
1860 private static final class LongSpinedNodeBuilder
1861 extends SpinedBuffer.OfLong
1862 implements Node.OfLong, Node.Builder.OfLong {
1863 private boolean building = false;
1864
1865 LongSpinedNodeBuilder() {} // Avoid creation of special accessor
1866
1867 @Override
1868 public Spliterator.OfLong spliterator() {
1869 assert !building : "during building";
1870 return super.spliterator();
1871 }
1872
1873 @Override
1874 public void forEach(LongConsumer consumer) {
1875 assert !building : "during building";
1876 super.forEach(consumer);
1877 }
1878
1879 //
1880 @Override
1881 public void begin(long size) {
1882 assert !building : "was already building";
1883 building = true;
1884 clear();
1885 ensureCapacity(size);
1886 }
1887
1888 @Override
1889 public void accept(long i) {
1890 assert building : "not building";
1891 super.accept(i);
1892 }
1893
1894 @Override
1895 public void end() {
1896 assert building : "was not building";
1897 building = false;
1898 // @@@ check begin(size) and size
1899 }
1900
1901 @Override
1902 public void copyInto(long[] array, int offset) {
1903 assert !building : "during building";
1904 super.copyInto(array, offset);
1905 }
1906
1907 @Override
1908 public long[] asLongArray() {
1909 assert !building : "during building";
1910 return super.asLongArray();
1911 }
1912
1913 @Override
1914 public Node.OfLong build() {
1915 assert !building : "during building";
1916 return this;
1917 }
1918 }
1919
1920 private static final class DoubleSpinedNodeBuilder
1921 extends SpinedBuffer.OfDouble
1922 implements Node.OfDouble, Node.Builder.OfDouble {
1923 private boolean building = false;
1924
1925 DoubleSpinedNodeBuilder() {} // Avoid creation of special accessor
1926
1927 @Override
1928 public Spliterator.OfDouble spliterator() {
1929 assert !building : "during building";
1930 return super.spliterator();
1931 }
1932
1933 @Override
1934 public void forEach(DoubleConsumer consumer) {
1935 assert !building : "during building";
1936 super.forEach(consumer);
1937 }
1938
1939 //
1940 @Override
1941 public void begin(long size) {
1942 assert !building : "was already building";
1943 building = true;
1944 clear();
1945 ensureCapacity(size);
1946 }
1947
1948 @Override
1949 public void accept(double i) {
1950 assert building : "not building";
1951 super.accept(i);
1952 }
1953
1954 @Override
1955 public void end() {
1956 assert building : "was not building";
1957 building = false;
1958 // @@@ check begin(size) and size
1959 }
1960
1961 @Override
1962 public void copyInto(double[] array, int offset) {
1963 assert !building : "during building";
1964 super.copyInto(array, offset);
1965 }
1966
1967 @Override
1968 public double[] asDoubleArray() {
1969 assert !building : "during building";
1970 return super.asDoubleArray();
1971 }
1972
1973 @Override
1974 public Node.OfDouble build() {
1975 assert !building : "during building";
1976 return this;
1977 }
1978 }
1979
1980 private static abstract class SizedCollectorTask<P_IN, P_OUT, T_SINK extends Sink<P_OUT>,
1981 K extends SizedCollectorTask<P_IN, P_OUT, T_SINK, K>>
1982 extends CountedCompleter<Void>
1983 implements Sink<P_OUT> {
1984 protected final Spliterator<P_IN> spliterator;
1985 protected final PipelineHelper<P_OUT> helper;
1986 protected final long targetSize;
1987 protected long offset;
1988 protected long length;
1989 // For Sink implementation
1990 protected int index, fence;
1991
1992 SizedCollectorTask(Spliterator<P_IN> spliterator,
1993 PipelineHelper<P_OUT> helper,
1994 int arrayLength) {
1995 assert spliterator.hasCharacteristics(Spliterator.SUBSIZED);
1996 this.spliterator = spliterator;
1997 this.helper = helper;
1998 this.targetSize = AbstractTask.suggestTargetSize(spliterator.estimateSize());
1999 this.offset = 0;
2000 this.length = arrayLength;
2001 }
2002
2003 SizedCollectorTask(K parent, Spliterator<P_IN> spliterator,
2004 long offset, long length, int arrayLength) {
2005 super(parent);
2006 assert spliterator.hasCharacteristics(Spliterator.SUBSIZED);
2007 this.spliterator = spliterator;
2008 this.helper = parent.helper;
2009 this.targetSize = parent.targetSize;
2010 this.offset = offset;
2011 this.length = length;
2012
2013 if (offset < 0 || length < 0 || (offset + length - 1 >= arrayLength)) {
2014 throw new IllegalArgumentException(
2015 String.format("offset and length interval [%d, %d + %d) is not within array size interval [0, %d)",
2016 offset, offset, length, arrayLength));
2017 }
2018 }
2019
2020 @Override
2021 public void compute() {
2022 SizedCollectorTask<P_IN, P_OUT, T_SINK, K> task = this;
2023 while (true) {
2024 Spliterator<P_IN> leftSplit;
2025 if (!AbstractTask.suggestSplit(task.spliterator, task.targetSize)
2026 || ((leftSplit = task.spliterator.trySplit()) == null)) {
2027 if (task.offset + task.length >= MAX_ARRAY_SIZE)
2028 throw new IllegalArgumentException("Stream size exceeds max array size");
2029 T_SINK sink = (T_SINK) task;
2030 task.helper.wrapAndCopyInto(sink, task.spliterator);
2031 task.propagateCompletion();
2032 return;
2033 }
2034 else {
2035 task.setPendingCount(1);
2036 long leftSplitSize = leftSplit.estimateSize();
2037 task.makeChild(leftSplit, task.offset, leftSplitSize).fork();
2038 task = task.makeChild(task.spliterator, task.offset + leftSplitSize,
2039 task.length - leftSplitSize);
2040 }
2041 }
2042 }
2043
2044 abstract K makeChild(Spliterator<P_IN> spliterator, long offset, long size);
2045
2046 @Override
2047 public void begin(long size) {
2048 if(size > length)
2049 throw new IllegalStateException("size passed to Sink.begin exceeds array length");
2050 index = (int) offset;
2051 fence = (int) offset + (int) length;
2052 }
2053
2054 static final class OfRef<P_IN, P_OUT>
2055 extends SizedCollectorTask<P_IN, P_OUT, Sink<P_OUT>, OfRef<P_IN, P_OUT>>
2056 implements Sink<P_OUT> {
2057 private final P_OUT[] array;
2058
2059 OfRef(Spliterator<P_IN> spliterator, PipelineHelper<P_OUT> helper, P_OUT[] array) {
2060 super(spliterator, helper, array.length);
2061 this.array = array;
2062 }
2063
2064 OfRef(OfRef<P_IN, P_OUT> parent, Spliterator<P_IN> spliterator,
2065 long offset, long length) {
2066 super(parent, spliterator, offset, length, parent.array.length);
2067 this.array = parent.array;
2068 }
2069
2070 @Override
2071 OfRef<P_IN, P_OUT> makeChild(Spliterator<P_IN> spliterator,
2072 long offset, long size) {
2073 return new OfRef<>(this, spliterator, offset, size);
2074 }
2075
2076 @Override
2077 public void accept(P_OUT value) {
2078 if (index >= fence) {
2079 throw new IndexOutOfBoundsException(Integer.toString(index));
2080 }
2081 array[index++] = value;
2082 }
2083 }
2084
2085 static final class OfInt<P_IN>
2086 extends SizedCollectorTask<P_IN, Integer, Sink.OfInt, OfInt<P_IN>>
2087 implements Sink.OfInt {
2088 private final int[] array;
2089
2090 OfInt(Spliterator<P_IN> spliterator, PipelineHelper<Integer> helper, int[] array) {
2091 super(spliterator, helper, array.length);
2092 this.array = array;
2093 }
2094
2095 OfInt(SizedCollectorTask.OfInt<P_IN> parent, Spliterator<P_IN> spliterator,
2096 long offset, long length) {
2097 super(parent, spliterator, offset, length, parent.array.length);
2098 this.array = parent.array;
2099 }
2100
2101 @Override
2102 SizedCollectorTask.OfInt<P_IN> makeChild(Spliterator<P_IN> spliterator,
2103 long offset, long size) {
2104 return new SizedCollectorTask.OfInt<>(this, spliterator, offset, size);
2105 }
2106
2107 @Override
2108 public void accept(int value) {
2109 if (index >= fence) {
2110 throw new IndexOutOfBoundsException(Integer.toString(index));
2111 }
2112 array[index++] = value;
2113 }
2114 }
2115
2116 static final class OfLong<P_IN>
2117 extends SizedCollectorTask<P_IN, Long, Sink.OfLong, OfLong<P_IN>>
2118 implements Sink.OfLong {
2119 private final long[] array;
2120
2121 OfLong(Spliterator<P_IN> spliterator, PipelineHelper<Long> helper, long[] array) {
2122 super(spliterator, helper, array.length);
2123 this.array = array;
2124 }
2125
2126 OfLong(SizedCollectorTask.OfLong<P_IN> parent, Spliterator<P_IN> spliterator,
2127 long offset, long length) {
2128 super(parent, spliterator, offset, length, parent.array.length);
2129 this.array = parent.array;
2130 }
2131
2132 @Override
2133 SizedCollectorTask.OfLong<P_IN> makeChild(Spliterator<P_IN> spliterator,
2134 long offset, long size) {
2135 return new SizedCollectorTask.OfLong<>(this, spliterator, offset, size);
2136 }
2137
2138 @Override
2139 public void accept(long value) {
2140 if (index >= fence) {
2141 throw new IndexOutOfBoundsException(Integer.toString(index));
2142 }
2143 array[index++] = value;
2144 }
2145 }
2146
2147 static final class OfDouble<P_IN>
2148 extends SizedCollectorTask<P_IN, Double, Sink.OfDouble, OfDouble<P_IN>>
2149 implements Sink.OfDouble {
2150 private final double[] array;
2151
2152 OfDouble(Spliterator<P_IN> spliterator, PipelineHelper<Double> helper, double[] array) {
2153 super(spliterator, helper, array.length);
2154 this.array = array;
2155 }
2156
2157 OfDouble(SizedCollectorTask.OfDouble<P_IN> parent, Spliterator<P_IN> spliterator,
2158 long offset, long length) {
2159 super(parent, spliterator, offset, length, parent.array.length);
2160 this.array = parent.array;
2161 }
2162
2163 @Override
2164 SizedCollectorTask.OfDouble<P_IN> makeChild(Spliterator<P_IN> spliterator,
2165 long offset, long size) {
2166 return new SizedCollectorTask.OfDouble<>(this, spliterator, offset, size);
2167 }
2168
2169 @Override
2170 public void accept(double value) {
2171 if (index >= fence) {
2172 throw new IndexOutOfBoundsException(Integer.toString(index));
2173 }
2174 array[index++] = value;
2175 }
2176 }
2177 }
2178
2179 private static abstract class ToArrayTask<T, T_NODE extends Node<T>,
2180 K extends ToArrayTask<T, T_NODE, K>>
2181 extends CountedCompleter<Void> {
2182 protected final T_NODE node;
2183 protected final int offset;
2184
2185 ToArrayTask(T_NODE node, int offset) {
2186 this.node = node;
2187 this.offset = offset;
2188 }
2189
2190 ToArrayTask(K parent, T_NODE node, int offset) {
2191 super(parent);
2192 this.node = node;
2193 this.offset = offset;
2194 }
2195
2196 abstract void copyNodeToArray();
2197
2198 abstract K makeChild(int childIndex, int offset);
2199
2200 @Override
2201 public void compute() {
2202 ToArrayTask<T, T_NODE, K> task = this;
2203 while (true) {
2204 if (task.node.getChildCount() == 0) {
2205 task.copyNodeToArray();
2206 task.propagateCompletion();
2207 return;
2208 }
2209 else {
2210 task.setPendingCount(task.node.getChildCount() - 1);
2211
2212 int size = 0;
2213 int i = 0;
2214 for (;i < task.node.getChildCount() - 1; i++) {
2215 K leftTask = task.makeChild(i, task.offset + size);
2216 size += leftTask.node.count();
2217 leftTask.fork();
2218 }
2219 task = task.makeChild(i, task.offset + size);
2220 }
2221 }
2222 }
2223
2224 private static final class OfRef<T>
2225 extends ToArrayTask<T, Node<T>, OfRef<T>> {
2226 private final T[] array;
2227
2228 private OfRef(Node<T> node, T[] array, int offset) {
2229 super(node, offset);
2230 this.array = array;
2231 }
2232
2233 private OfRef(OfRef<T> parent, Node<T> node, int offset) {
2234 super(parent, node, offset);
2235 this.array = parent.array;
2236 }
2237
2238 @Override
2239 OfRef<T> makeChild(int childIndex, int offset) {
2240 return new OfRef<>(this, node.getChild(childIndex), offset);
2241 }
2242
2243 @Override
2244 void copyNodeToArray() {
2245 node.copyInto(array, offset);
2246 }
2247 }
2248
2249 private static final class OfInt
2250 extends ToArrayTask<Integer, Node.OfInt, OfInt> {
2251 private final int[] array;
2252
2253 private OfInt(Node.OfInt node, int[] array, int offset) {
2254 super(node, offset);
2255 this.array = array;
2256 }
2257
2258 private OfInt(OfInt parent, Node.OfInt node, int offset) {
2259 super(parent, node, offset);
2260 this.array = parent.array;
2261 }
2262
2263 @Override
2264 OfInt makeChild(int childIndex, int offset) {
2265 return new OfInt(this, node.getChild(childIndex), offset);
2266 }
2267
2268 @Override
2269 void copyNodeToArray() {
2270 node.copyInto(array, offset);
2271 }
2272 }
2273
2274 private static final class OfLong
2275 extends ToArrayTask<Long, Node.OfLong, OfLong> {
2276 private final long[] array;
2277
2278 private OfLong(Node.OfLong node, long[] array, int offset) {
2279 super(node, offset);
2280 this.array = array;
2281 }
2282
2283 private OfLong(OfLong parent, Node.OfLong node, int offset) {
2284 super(parent, node, offset);
2285 this.array = parent.array;
2286 }
2287
2288 @Override
2289 OfLong makeChild(int childIndex, int offset) {
2290 return new OfLong(this, node.getChild(childIndex), offset);
2291 }
2292
2293 @Override
2294 void copyNodeToArray() {
2295 node.copyInto(array, offset);
2296 }
2297 }
2298
2299 private static final class OfDouble
2300 extends ToArrayTask<Double, Node.OfDouble, OfDouble> {
2301 private final double[] array;
2302
2303 private OfDouble(Node.OfDouble node, double[] array, int offset) {
2304 super(node, offset);
2305 this.array = array;
2306 }
2307
2308 private OfDouble(OfDouble parent, Node.OfDouble node, int offset) {
2309 super(parent, node, offset);
2310 this.array = parent.array;
2311 }
2312
2313 @Override
2314 OfDouble makeChild(int childIndex, int offset) {
2315 return new OfDouble(this, node.getChild(childIndex), offset);
2316 }
2317
2318 @Override
2319 void copyNodeToArray() {
2320 node.copyInto(array, offset);
2321 }
2322 }
2323 }
2324
2325 private static final class CollectorTask<P_IN, P_OUT>
2326 extends AbstractTask<P_IN, P_OUT, Node<P_OUT>, CollectorTask<P_IN, P_OUT>> {
2327 private final PipelineHelper<P_OUT> helper;
2328 private final IntFunction<P_OUT[]> generator;
2329
2330 CollectorTask(PipelineHelper<P_OUT> helper,
2331 IntFunction<P_OUT[]> generator,
2332 Spliterator<P_IN> spliterator) {
2333 super(helper, spliterator);
2334 this.helper = helper;
2335 this.generator = generator;
2336 }
2337
2338 CollectorTask(CollectorTask<P_IN, P_OUT> parent, Spliterator<P_IN> spliterator) {
2339 super(parent, spliterator);
2340 helper = parent.helper;
2341 generator = parent.generator;
2342 }
2343
2344 @Override
2345 protected CollectorTask<P_IN, P_OUT> makeChild(Spliterator<P_IN> spliterator) {
2346 return new CollectorTask<>(this, spliterator);
2347 }
2348
2349 @Override
2350 protected Node<P_OUT> doLeaf() {
2351 Node.Builder<P_OUT> builder
2352 = builder(helper.exactOutputSizeIfKnown(spliterator),
2353 generator);
2354 return helper.wrapAndCopyInto(builder, spliterator).build();
2355 }
2356
2357 @Override
2358 public void onCompletion(CountedCompleter caller) {
2359 if (!isLeaf()) {
2360 setLocalResult(new ConcNode<>(leftChild.getLocalResult(), rightChild.getLocalResult()));
2361 }
2362 super.onCompletion(caller);
2363 }
2364 }
2365
2366 private static final class IntCollectorTask<P_IN>
2367 extends AbstractTask<P_IN, Integer, Node.OfInt, IntCollectorTask<P_IN>> {
2368 private final PipelineHelper<Integer> helper;
2369
2370 IntCollectorTask(PipelineHelper<Integer> helper, Spliterator<P_IN> spliterator) {
2371 super(helper, spliterator);
2372 this.helper = helper;
2373 }
2374
2375 IntCollectorTask(IntCollectorTask<P_IN> parent, Spliterator<P_IN> spliterator) {
2376 super(parent, spliterator);
2377 helper = parent.helper;
2378 }
2379
2380 @Override
2381 protected IntCollectorTask<P_IN> makeChild(Spliterator<P_IN> spliterator) {
2382 return new IntCollectorTask<>(this, spliterator);
2383 }
2384
2385 @Override
2386 protected Node.OfInt doLeaf() {
2387 Node.Builder.OfInt builder = intBuilder(helper.exactOutputSizeIfKnown(spliterator));
2388 return helper.wrapAndCopyInto(builder, spliterator).build();
2389 }
2390
2391 @Override
2392 public void onCompletion(CountedCompleter caller) {
2393 if (!isLeaf()) {
2394 setLocalResult(new IntConcNode(leftChild.getLocalResult(), rightChild.getLocalResult()));
2395 }
2396 super.onCompletion(caller);
2397 }
2398 }
2399
2400 private static final class LongCollectorTask<P_IN>
2401 extends AbstractTask<P_IN, Long, Node.OfLong, LongCollectorTask<P_IN>> {
2402 private final PipelineHelper<Long> helper;
2403
2404 LongCollectorTask(PipelineHelper<Long> helper, Spliterator<P_IN> spliterator) {
2405 super(helper, spliterator);
2406 this.helper = helper;
2407 }
2408
2409 LongCollectorTask(LongCollectorTask<P_IN> parent, Spliterator<P_IN> spliterator) {
2410 super(parent, spliterator);
2411 helper = parent.helper;
2412 }
2413
2414 @Override
2415 protected LongCollectorTask<P_IN> makeChild(Spliterator<P_IN> spliterator) {
2416 return new LongCollectorTask<>(this, spliterator);
2417 }
2418
2419 @Override
2420 protected Node.OfLong doLeaf() {
2421 Node.Builder.OfLong builder = longBuilder(helper.exactOutputSizeIfKnown(spliterator));
2422 return helper.wrapAndCopyInto(builder, spliterator).build();
2423 }
2424
2425 @Override
2426 public void onCompletion(CountedCompleter caller) {
2427 if (!isLeaf()) {
2428 setLocalResult(new LongConcNode(leftChild.getLocalResult(), rightChild.getLocalResult()));
2429 }
2430 super.onCompletion(caller);
2431 }
2432 }
2433
2434 private static final class DoubleCollectorTask<P_IN>
2435 extends AbstractTask<P_IN, Double, Node.OfDouble, DoubleCollectorTask<P_IN>> {
2436 private final PipelineHelper<Double> helper;
2437
2438 DoubleCollectorTask(PipelineHelper<Double> helper, Spliterator<P_IN> spliterator) {
2439 super(helper, spliterator);
2440 this.helper = helper;
2441 }
2442
2443 DoubleCollectorTask(DoubleCollectorTask<P_IN> parent, Spliterator<P_IN> spliterator) {
2444 super(parent, spliterator);
2445 helper = parent.helper;
2446 }
2447
2448 @Override
2449 protected DoubleCollectorTask<P_IN> makeChild(Spliterator<P_IN> spliterator) {
2450 return new DoubleCollectorTask<>(this, spliterator);
2451 }
2452
2453 @Override
2454 protected Node.OfDouble doLeaf() {
2455 Node.Builder.OfDouble builder
2456 = doubleBuilder(helper.exactOutputSizeIfKnown(spliterator));
2457 return helper.wrapAndCopyInto(builder, spliterator).build();
2458 }
2459
2460 @Override
2461 public void onCompletion(CountedCompleter caller) {
2462 if (!isLeaf()) {
2463 setLocalResult(new DoubleConcNode(leftChild.getLocalResult(), rightChild.getLocalResult()));
2464 }
2465 super.onCompletion(caller);
2466 }
2467 }
2468 }