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