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