1 /*

     2  * Copyright (c) 2012, 2013, Oracle and/or its affiliates. All rights reserved.

     3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

     4  *

     5  * This code is free software; you can redistribute it and/or modify it

     6  * under the terms of the GNU General Public License version 2 only, as

     7  * published by the Free Software Foundation.  Oracle designates this

     8  * particular file as subject to the "Classpath" exception as provided

     9  * by Oracle in the LICENSE file that accompanied this code.

    10  *

    11  * This code is distributed in the hope that it will be useful, but WITHOUT

    12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

    13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

    14  * version 2 for more details (a copy is included in the LICENSE file that

    15  * accompanied this code).

    16  *

    17  * You should have received a copy of the GNU General Public License version

    18  * 2 along with this work; if not, write to the Free Software Foundation,

    19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

    20  *

    21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

    22  * or visit www.oracle.com if you need additional information or have any

    23  * questions.

    24  */

    25 package java.util.stream;

    26 

    27 import java.util.ArrayDeque;

    28 import java.util.Arrays;

    29 import java.util.Collection;

    30 import java.util.Deque;

    31 import java.util.List;

    32 import java.util.Objects;

    33 import java.util.Spliterator;

    34 import java.util.Spliterators;

    35 import java.util.concurrent.CountedCompleter;

    36 import java.util.function.Consumer;

    37 import java.util.function.DoubleConsumer;

    38 import java.util.function.IntConsumer;

    39 import java.util.function.IntFunction;

    40 import java.util.function.LongConsumer;

    41 

    42 /**

    43  * Factory methods for constructing implementations of {@link Node} and

    44  * {@link Node.Builder} and their primitive specializations.  Fork/Join tasks

    45  * for collecting output from a {@link PipelineHelper} to a {@link Node} and

    46  * flattening {@link Node}s.

    47  *

    48  * @since 1.8

    49  */

    50 final class Nodes {

    51 

    52     private Nodes() {

    53         throw new Error("no instances");

    54     }

    55 

    56     /**

    57      * The maximum size of an array that can be allocated.

    58      */

    59     static final long MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    60 

    61     private static final Node EMPTY_NODE = new EmptyNode.OfRef();

    62     private static final Node.OfInt EMPTY_INT_NODE = new EmptyNode.OfInt();

    63     private static final Node.OfLong EMPTY_LONG_NODE = new EmptyNode.OfLong();

    64     private static final Node.OfDouble EMPTY_DOUBLE_NODE = new EmptyNode.OfDouble();

    65 

    66     // General shape-based node creation methods

    67 

    68     /**

    69      * Produces an empty node whose count is zero, has no children and no content.

    70      *

    71      * @param <T> the type of elements of the created node

    72      * @param shape the shape of the node to be created

    73      * @return an empty node.

    74      */

    75     @SuppressWarnings("unchecked")

    76     static <T> Node<T> emptyNode(StreamShape shape) {

    77         switch (shape) {

    78             case REFERENCE:    return (Node<T>) EMPTY_NODE;

    79             case INT_VALUE:    return (Node<T>) EMPTY_INT_NODE;

    80             case LONG_VALUE:   return (Node<T>) EMPTY_LONG_NODE;

    81             case DOUBLE_VALUE: return (Node<T>) EMPTY_DOUBLE_NODE;

    82             default:

    83                 throw new IllegalStateException("Unknown shape " + shape);

    84         }

    85     }

    86 

    87     /**

    88      * Produces a concatenated {@link Node} that has two or more children.

    89      * <p>The count of the concatenated node is equal to the sum of the count

    90      * of each child. Traversal of the concatenated node traverses the content

    91      * of each child in encounter order of the list of children. Splitting a

    92      * spliterator obtained from the concatenated node preserves the encounter

    93      * order of the list of children.

    94      *

    95      * <p>The result may be a concatenated node, the input sole node if the size

    96      * of the list is 1, or an empty node.

    97      *

    98      * @param <T> the type of elements of the concatenated node

    99      * @param shape the shape of the concatenated node to be created

   100      * @param nodes the input nodes

   101      * @return a {@code Node} covering the elements of the input nodes

   102      * @throws IllegalStateException if all {@link Node} elements of the list

   103      * are an not instance of type supported by this factory.

   104      */

   105     @SuppressWarnings("unchecked")

   106     static <T> Node<T> conc(StreamShape shape, List<? extends Node<T>> nodes) {

   107         int size = nodes.size();

   108         if (size == 0)

   109             return emptyNode(shape);

   110         else if (size == 1)

   111             return nodes.get(0);

   112         else {

   113             // Create a right-balanced tree when there are more that 2 nodes

   114             switch (shape) {

   115                 case REFERENCE: {

   116                     List<Node<T>> refNodes = (List<Node<T>>) nodes;

   117                     ConcNode<T> c = new ConcNode<>(refNodes.get(size - 2), refNodes.get(size - 1));

   118                     for (int i = size - 3; i >= 0; i--) {

   119                         c = new ConcNode<>(refNodes.get(i), c);

   120                     }

   121                     return c;

   122                 }

   123                 case INT_VALUE: {

   124                     List<? extends Node.OfInt> intNodes = (List<? extends Node.OfInt>) nodes;

   125                     IntConcNode c = new IntConcNode(intNodes.get(size - 2), intNodes.get(size - 1));

   126                     for (int i = size - 3; i >= 0; i--) {

   127                         c = new IntConcNode(intNodes.get(i), c);

   128                     }

   129                     return (Node<T>) c;

   130                 }

   131                 case LONG_VALUE: {

   132                     List<? extends Node.OfLong> longNodes = (List<? extends Node.OfLong>) nodes;

   133                     LongConcNode c = new LongConcNode(longNodes.get(size - 2), longNodes.get(size - 1));

   134                     for (int i = size - 3; i >= 0; i--) {

   135                         c = new LongConcNode(longNodes.get(i), c);

   136                     }

   137                     return (Node<T>) c;

   138                 }

   139                 case DOUBLE_VALUE: {

   140                     List<? extends Node.OfDouble> doubleNodes = (List<? extends Node.OfDouble>) nodes;

   141                     DoubleConcNode c = new DoubleConcNode(doubleNodes.get(size - 2), doubleNodes.get(size - 1));

   142                     for (int i = size - 3; i >= 0; i--) {

   143                         c = new DoubleConcNode(doubleNodes.get(i), c);

   144                     }

   145                     return (Node<T>) c;

   146                 }

   147                 default:

   148                     throw new IllegalStateException("Unknown shape " + shape);

   149             }

   150         }

   151 

   152     }

   153 

   154     /**

   155      * Truncate a {@link Node}, returning a node describing a subsequence of

   156      * the contents of the input node.

   157      *

   158      * @param <T> the type of elements of the input node and truncated node

   159      * @param input the input node

   160      * @param from the starting offset to include in the truncated node (inclusive)

   161      * @param to the ending offset ot include in the truncated node (exclusive)

   162      * @param generator the array factory (only used for reference nodes)

   163      * @return the truncated node

   164      */

   165     @SuppressWarnings("unchecked")

   166     static <T> Node<T> truncateNode(Node<T> input, long from, long to, IntFunction<T[]> generator) {

   167         StreamShape shape = input.getShape();

   168         long size = truncatedSize(input.count(), from, to);

   169         if (size == 0)

   170             return emptyNode(shape);

   171         else if (from == 0 && to >= input.count())

   172             return input;

   173 

   174         switch (shape) {

   175             case REFERENCE: {

   176                 Spliterator<T> spliterator = input.spliterator();

   177                 Node.Builder<T> nodeBuilder = Nodes.builder(size, generator);

   178                 nodeBuilder.begin(size);

   179                 for (int i = 0; i < from && spliterator.tryAdvance(e -> { }); i++) { }

   180                 for (int i = 0; (i < size) && spliterator.tryAdvance(nodeBuilder); i++) { }

   181                 nodeBuilder.end();

   182                 return nodeBuilder.build();

   183             }

   184             case INT_VALUE: {

   185                 Spliterator.OfInt spliterator = ((Node.OfInt) input).spliterator();

   186                 Node.Builder.OfInt nodeBuilder = Nodes.intBuilder(size);

   187                 nodeBuilder.begin(size);

   188                 for (int i = 0; i < from && spliterator.tryAdvance((IntConsumer) e -> { }); i++) { }

   189                 for (int i = 0; (i < size) && spliterator.tryAdvance((IntConsumer) nodeBuilder); i++) { }

   190                 nodeBuilder.end();

   191                 return (Node<T>) nodeBuilder.build();

   192             }

   193             case LONG_VALUE: {

   194                 Spliterator.OfLong spliterator = ((Node.OfLong) input).spliterator();

   195                 Node.Builder.OfLong nodeBuilder = Nodes.longBuilder(size);

   196                 nodeBuilder.begin(size);

   197                 for (int i = 0; i < from && spliterator.tryAdvance((LongConsumer) e -> { }); i++) { }

   198                 for (int i = 0; (i < size) && spliterator.tryAdvance((LongConsumer) nodeBuilder); i++) { }

   199                 nodeBuilder.end();

   200                 return (Node<T>) nodeBuilder.build();

   201             }

   202             case DOUBLE_VALUE: {

   203                 Spliterator.OfDouble spliterator = ((Node.OfDouble) input).spliterator();

   204                 Node.Builder.OfDouble nodeBuilder = Nodes.doubleBuilder(size);

   205                 nodeBuilder.begin(size);

   206                 for (int i = 0; i < from && spliterator.tryAdvance((DoubleConsumer) e -> { }); i++) { }

   207                 for (int i = 0; (i < size) && spliterator.tryAdvance((DoubleConsumer) nodeBuilder); i++) { }

   208                 nodeBuilder.end();

   209                 return (Node<T>) nodeBuilder.build();

   210             }

   211             default:

   212                 throw new IllegalStateException("Unknown shape " + shape);

   213         }

   214     }

   215 

   216     private static long truncatedSize(long size, long from, long to) {

   217         if (from >= 0)

   218             size = Math.max(0, size - from);

   219         long limit = to - from;

   220         if (limit >= 0)

   221             size = Math.min(size, limit);

   222         return size;

   223     }

   224 

   225     // Reference-based node methods

   226 

   227     /**

   228      * Produces a {@link Node} describing an array.

   229      *

   230      * <p>The node will hold a reference to the array and will not make a copy.

   231      *

   232      * @param <T> the type of elements held by the node

   233      * @param array the array

   234      * @return a node holding an array

   235      */

   236     static <T> Node<T> node(T[] array) {

   237         return new ArrayNode<>(array);

   238     }

   239 

   240     /**

   241      * Produces a {@link Node} describing a {@link Collection}.

   242      * <p>

   243      * The node will hold a reference to the collection and will not make a copy.

   244      *

   245      * @param <T> the type of elements held by the node

   246      * @param c the collection

   247      * @return a node holding a collection

   248      */

   249     static <T> Node<T> node(Collection<T> c) {

   250         return new CollectionNode<>(c);

   251     }

   252 

   253     /**

   254      * Produces a {@link Node.Builder}.

   255      *

   256      * @param exactSizeIfKnown -1 if a variable size builder is requested,

   257      * otherwise the exact capacity desired.  A fixed capacity builder will

   258      * fail if the wrong number of elements are added to the builder.

   259      * @param generator the array factory

   260      * @param <T> the type of elements of the node builder

   261      * @return a {@code Node.Builder}

   262      */

   263     static <T> Node.Builder<T> builder(long exactSizeIfKnown, IntFunction<T[]> generator) {

   264         return (exactSizeIfKnown >= 0 && exactSizeIfKnown < MAX_ARRAY_SIZE)

   265                ? new FixedNodeBuilder<>(exactSizeIfKnown, generator)

   266                : builder();

   267     }

   268 

   269     /**

   270      * Produces a variable size @{link Node.Builder}.

   271      *

   272      * @param <T> the type of elements of the node builder

   273      * @return a {@code Node.Builder}

   274      */

   275     static <T> Node.Builder<T> builder() {

   276         return new SpinedNodeBuilder<>();

   277     }

   278 

   279     // Int nodes

   280 

   281     /**

   282      * Produces a {@link Node.OfInt} describing an int[] array.

   283      *

   284      * <p>The node will hold a reference to the array and will not make a copy.

   285      *

   286      * @param array the array

   287      * @return a node holding an array

   288      */

   289     static Node.OfInt node(int[] array) {

   290         return new IntArrayNode(array);

   291     }

   292 

   293     /**

   294      * Produces a {@link Node.Builder.OfInt}.

   295      *

   296      * @param exactSizeIfKnown -1 if a variable size builder is requested,

   297      * otherwise the exact capacity desired.  A fixed capacity builder will

   298      * fail if the wrong number of elements are added to the builder.

   299      * @return a {@code Node.Builder.OfInt}

   300      */

   301     static Node.Builder.OfInt intBuilder(long exactSizeIfKnown) {

   302         return (exactSizeIfKnown >= 0 && exactSizeIfKnown < MAX_ARRAY_SIZE)

   303                ? new IntFixedNodeBuilder(exactSizeIfKnown)

   304                : intBuilder();

   305     }

   306 

   307     /**

   308      * Produces a variable size @{link Node.Builder.OfInt}.

   309      *

   310      * @return a {@code Node.Builder.OfInt}

   311      */

   312     static Node.Builder.OfInt intBuilder() {

   313         return new IntSpinedNodeBuilder();

   314     }

   315 

   316     // Long nodes

   317 

   318     /**

   319      * Produces a {@link Node.OfLong} describing a long[] array.

   320      * <p>

   321      * The node will hold a reference to the array and will not make a copy.

   322      *

   323      * @param array the array

   324      * @return a node holding an array

   325      */

   326     static Node.OfLong node(final long[] array) {

   327         return new LongArrayNode(array);

   328     }

   329 

   330     /**

   331      * Produces a {@link Node.Builder.OfLong}.

   332      *

   333      * @param exactSizeIfKnown -1 if a variable size builder is requested,

   334      * otherwise the exact capacity desired.  A fixed capacity builder will

   335      * fail if the wrong number of elements are added to the builder.

   336      * @return a {@code Node.Builder.OfLong}

   337      */

   338     static Node.Builder.OfLong longBuilder(long exactSizeIfKnown) {

   339         return (exactSizeIfKnown >= 0 && exactSizeIfKnown < MAX_ARRAY_SIZE)

   340                ? new LongFixedNodeBuilder(exactSizeIfKnown)

   341                : longBuilder();

   342     }

   343 

   344     /**

   345      * Produces a variable size @{link Node.Builder.OfLong}.

   346      *

   347      * @return a {@code Node.Builder.OfLong}

   348      */

   349     static Node.Builder.OfLong longBuilder() {

   350         return new LongSpinedNodeBuilder();

   351     }

   352 

   353     // Double nodes

   354 

   355     /**

   356      * Produces a {@link Node.OfDouble} describing a double[] array.

   357      *

   358      * <p>The node will hold a reference to the array and will not make a copy.

   359      *

   360      * @param array the array

   361      * @return a node holding an array

   362      */

   363     static Node.OfDouble node(final double[] array) {

   364         return new DoubleArrayNode(array);

   365     }

   366 

   367     /**

   368      * Produces a {@link Node.Builder.OfDouble}.

   369      *

   370      * @param exactSizeIfKnown -1 if a variable size builder is requested,

   371      * otherwise the exact capacity desired.  A fixed capacity builder will

   372      * fail if the wrong number of elements are added to the builder.

   373      * @return a {@code Node.Builder.OfDouble}

   374      */

   375     static Node.Builder.OfDouble doubleBuilder(long exactSizeIfKnown) {

   376         return (exactSizeIfKnown >= 0 && exactSizeIfKnown < MAX_ARRAY_SIZE)

   377                ? new DoubleFixedNodeBuilder(exactSizeIfKnown)

   378                : doubleBuilder();

   379     }

   380 

   381     /**

   382      * Produces a variable size @{link Node.Builder.OfDouble}.

   383      *

   384      * @return a {@code Node.Builder.OfDouble}

   385      */

   386     static Node.Builder.OfDouble doubleBuilder() {

   387         return new DoubleSpinedNodeBuilder();

   388     }

   389 

   390     // Parallel evaluation of pipelines to nodes

   391 

   392     /**

   393      * Collect, in parallel, elements output from a pipeline and describe those

   394      * elements with a {@link Node}.

   395      *

   396      * @implSpec

   397      * If the exact size of the output from the pipeline is known and the source

   398      * {@link Spliterator} has the {@link Spliterator#SUBSIZED} characteristic,

   399      * then a flat {@link Node} will be returned whose content is an array,

   400      * since the size is known the array can be constructed in advance and

   401      * output elements can be placed into the array concurrently by leaf

   402      * tasks at the correct offsets.  If the exact size is not known, output

   403      * elements are collected into a conc-node whose shape mirrors that

   404      * of the computation. This conc-node can then be flattened in

   405      * parallel to produce a flat {@code Node} if desired.

   406      *

   407      * @param helper the pipeline helper describing the pipeline

   408      * @param flattenTree whether a conc node should be flattened into a node

   409      *                    describing an array before returning

   410      * @param generator the array generator

   411      * @return a {@link Node} describing the output elements

   412      */

   413     public static <P_IN, P_OUT> Node<P_OUT> collect(PipelineHelper<P_OUT> helper,

   414                                                     Spliterator<P_IN> spliterator,

   415                                                     boolean flattenTree,

   416                                                     IntFunction<P_OUT[]> generator) {

   417         long size = helper.exactOutputSizeIfKnown(spliterator);

   418         if (size >= 0 && spliterator.hasCharacteristics(Spliterator.SUBSIZED)) {

   419             if (size >= MAX_ARRAY_SIZE)

   420                 throw new IllegalArgumentException("Stream size exceeds max array size");

   421             P_OUT[] array = generator.apply((int) size);

   422             new SizedCollectorTask.OfRef<>(spliterator, helper, array).invoke();

   423             return node(array);

   424         } else {

   425             Node<P_OUT> node = new CollectorTask<>(helper, generator, spliterator).invoke();

   426             return flattenTree ? flatten(node, generator) : node;

   427         }

   428     }

   429 

   430     /**

   431      * Collect, in parallel, elements output from an int-valued pipeline and

   432      * describe those elements with a {@link Node.OfInt}.

   433      *

   434      * @implSpec

   435      * If the exact size of the output from the pipeline is known and the source

   436      * {@link Spliterator} has the {@link Spliterator#SUBSIZED} characteristic,

   437      * then a flat {@link Node} will be returned whose content is an array,

   438      * since the size is known the array can be constructed in advance and

   439      * output elements can be placed into the array concurrently by leaf

   440      * tasks at the correct offsets.  If the exact size is not known, output

   441      * elements are collected into a conc-node whose shape mirrors that

   442      * of the computation. This conc-node can then be flattened in

   443      * parallel to produce a flat {@code Node.OfInt} if desired.

   444      *

   445      * @param <P_IN> the type of elements from the source Spliterator

   446      * @param helper the pipeline helper describing the pipeline

   447      * @param flattenTree whether a conc node should be flattened into a node

   448      *                    describing an array before returning

   449      * @return a {@link Node.OfInt} describing the output elements

   450      */

   451     public static <P_IN> Node.OfInt collectInt(PipelineHelper<Integer> helper,

   452                                                Spliterator<P_IN> spliterator,

   453                                                boolean flattenTree) {

   454         long size = helper.exactOutputSizeIfKnown(spliterator);

   455         if (size >= 0 && spliterator.hasCharacteristics(Spliterator.SUBSIZED)) {

   456             if (size >= MAX_ARRAY_SIZE)

   457                 throw new IllegalArgumentException("Stream size exceeds max array size");

   458             int[] array = new int[(int) size];

   459             new SizedCollectorTask.OfInt<>(spliterator, helper, array).invoke();

   460             return node(array);

   461         }

   462         else {

   463             Node.OfInt node = new IntCollectorTask<>(helper, spliterator).invoke();

   464             return flattenTree ? flattenInt(node) : node;

   465         }

   466     }

   467 

   468     /**

   469      * Collect, in parallel, elements output from a long-valued pipeline and

   470      * describe those elements with a {@link Node.OfLong}.

   471      *

   472      * @implSpec

   473      * If the exact size of the output from the pipeline is known and the source

   474      * {@link Spliterator} has the {@link Spliterator#SUBSIZED} characteristic,

   475      * then a flat {@link Node} will be returned whose content is an array,

   476      * since the size is known the array can be constructed in advance and

   477      * output elements can be placed into the array concurrently by leaf

   478      * tasks at the correct offsets.  If the exact size is not known, output

   479      * elements are collected into a conc-node whose shape mirrors that

   480      * of the computation. This conc-node can then be flattened in

   481      * parallel to produce a flat {@code Node.OfLong} if desired.

   482      *

   483      * @param <P_IN> the type of elements from the source Spliterator

   484      * @param helper the pipeline helper describing the pipeline

   485      * @param flattenTree whether a conc node should be flattened into a node

   486      *                    describing an array before returning

   487      * @return a {@link Node.OfLong} describing the output elements

   488      */

   489     public static <P_IN> Node.OfLong collectLong(PipelineHelper<Long> helper,

   490                                                  Spliterator<P_IN> spliterator,

   491                                                  boolean flattenTree) {

   492         long size = helper.exactOutputSizeIfKnown(spliterator);

   493         if (size >= 0 && spliterator.hasCharacteristics(Spliterator.SUBSIZED)) {

   494             if (size >= MAX_ARRAY_SIZE)

   495                 throw new IllegalArgumentException("Stream size exceeds max array size");

   496             long[] array = new long[(int) size];

   497             new SizedCollectorTask.OfLong<>(spliterator, helper, array).invoke();

   498             return node(array);

   499         }

   500         else {

   501             Node.OfLong node = new LongCollectorTask<>(helper, spliterator).invoke();

   502             return flattenTree ? flattenLong(node) : node;

   503         }

   504     }

   505 

   506     /**

   507      * Collect, in parallel, elements output from n double-valued pipeline and

   508      * describe those elements with a {@link Node.OfDouble}.

   509      *

   510      * @implSpec

   511      * If the exact size of the output from the pipeline is known and the source

   512      * {@link Spliterator} has the {@link Spliterator#SUBSIZED} characteristic,

   513      * then a flat {@link Node} will be returned whose content is an array,

   514      * since the size is known the array can be constructed in advance and

   515      * output elements can be placed into the array concurrently by leaf

   516      * tasks at the correct offsets.  If the exact size is not known, output

   517      * elements are collected into a conc-node whose shape mirrors that

   518      * of the computation. This conc-node can then be flattened in

   519      * parallel to produce a flat {@code Node.OfDouble} if desired.

   520      *

   521      * @param <P_IN> the type of elements from the source Spliterator

   522      * @param helper the pipeline helper describing the pipeline

   523      * @param flattenTree whether a conc node should be flattened into a node

   524      *                    describing an array before returning

   525      * @return a {@link Node.OfDouble} describing the output elements

   526      */

   527     public static <P_IN> Node.OfDouble collectDouble(PipelineHelper<Double> helper,

   528                                                      Spliterator<P_IN> spliterator,

   529                                                      boolean flattenTree) {

   530         long size = helper.exactOutputSizeIfKnown(spliterator);

   531         if (size >= 0 && spliterator.hasCharacteristics(Spliterator.SUBSIZED)) {

   532             if (size >= MAX_ARRAY_SIZE)

   533                 throw new IllegalArgumentException("Stream size exceeds max array size");

   534             double[] array = new double[(int) size];

   535             new SizedCollectorTask.OfDouble<>(spliterator, helper, array).invoke();

   536             return node(array);

   537         }

   538         else {

   539             Node.OfDouble node = new DoubleCollectorTask<>(helper, spliterator).invoke();

   540             return flattenTree ? flattenDouble(node) : node;

   541         }

   542     }

   543 

   544     // Parallel flattening of nodes

   545 

   546     /**

   547      * Flatten, in parallel, a {@link Node}.  A flattened node is one that has

   548      * no children.  If the node is already flat, it is simply returned.

   549      *

   550      * @implSpec

   551      * If a new node is to be created, the generator is used to create an array

   552      * whose length is {@link Node#count()}.  Then the node tree is traversed

   553      * and leaf node elements are placed in the array concurrently by leaf tasks

   554      * at the correct offsets.

   555      *

   556      * @param <T> type of elements contained by the node

   557      * @param node the node to flatten

   558      * @param generator the array factory used to create array instances

   559      * @return a flat {@code Node}

   560      */

   561     public static <T> Node<T> flatten(Node<T> node, IntFunction<T[]> generator) {

   562         if (node.getChildCount() > 0) {

   563             T[] array = generator.apply((int) node.count());

   564             new ToArrayTask.OfRef<>(node, array, 0).invoke();

   565             return node(array);

   566         } else {

   567             return node;

   568         }

   569     }

   570 

   571     /**

   572      * Flatten, in parallel, a {@link Node.OfInt}.  A flattened node is one that

   573      * has no children.  If the node is already flat, it is simply returned.

   574      *

   575      * @implSpec

   576      * If a new node is to be created, a new int[] array is created whose length

   577      * is {@link Node#count()}.  Then the node tree is traversed and leaf node

   578      * elements are placed in the array concurrently by leaf tasks at the

   579      * correct offsets.

   580      *

   581      * @param node the node to flatten

   582      * @return a flat {@code Node.OfInt}

   583      */

   584     public static Node.OfInt flattenInt(Node.OfInt node) {

   585         if (node.getChildCount() > 0) {

   586             int[] array = new int[(int) node.count()];

   587             new ToArrayTask.OfInt(node, array, 0).invoke();

   588             return node(array);

   589         } else {

   590             return node;

   591         }

   592     }

   593 

   594     /**

   595      * Flatten, in parallel, a {@link Node.OfLong}.  A flattened node is one that

   596      * has no children.  If the node is already flat, it is simply returned.

   597      *

   598      * @implSpec

   599      * If a new node is to be created, a new long[] array is created whose length

   600      * is {@link Node#count()}.  Then the node tree is traversed and leaf node

   601      * elements are placed in the array concurrently by leaf tasks at the

   602      * correct offsets.

   603      *

   604      * @param node the node to flatten

   605      * @return a flat {@code Node.OfLong}

   606      */

   607     public static Node.OfLong flattenLong(Node.OfLong node) {

   608         if (node.getChildCount() > 0) {

   609             long[] array = new long[(int) node.count()];

   610             new ToArrayTask.OfLong(node, array, 0).invoke();

   611             return node(array);

   612         } else {

   613             return node;

   614         }

   615     }

   616 

   617     /**

   618      * Flatten, in parallel, a {@link Node.OfDouble}.  A flattened node is one that

   619      * has no children.  If the node is already flat, it is simply returned.

   620      *

   621      * @implSpec

   622      * If a new node is to be created, a new double[] array is created whose length

   623      * is {@link Node#count()}.  Then the node tree is traversed and leaf node

   624      * elements are placed in the array concurrently by leaf tasks at the

   625      * correct offsets.

   626      *

   627      * @param node the node to flatten

   628      * @return a flat {@code Node.OfDouble}

   629      */

   630     public static Node.OfDouble flattenDouble(Node.OfDouble node) {

   631         if (node.getChildCount() > 0) {

   632             double[] array = new double[(int) node.count()];

   633             new ToArrayTask.OfDouble(node, array, 0).invoke();

   634             return node(array);

   635         } else {

   636             return node;

   637         }

   638     }

   639 

   640     // Implementations

   641 

   642     private static abstract class EmptyNode<T, T_ARR, T_CONS> implements Node<T> {

   643         EmptyNode() { }

   644 

   645         @Override

   646         public T[] asArray(IntFunction<T[]> generator) {

   647             return generator.apply(0);

   648         }

   649 

   650         public void copyInto(T_ARR array, int offset) { }

   651 

   652         @Override

   653         public long count() {

   654             return 0;

   655         }

   656 

   657         public void forEach(T_CONS consumer) { }

   658 

   659         private static class OfRef<T> extends EmptyNode<T, T[], Consumer<? super T>> {

   660             private OfRef() {

   661                 super();

   662             }

   663 

   664             @Override

   665             public Spliterator<T> spliterator() {

   666                 return Spliterators.emptySpliterator();

   667             }

   668         }

   669 

   670         private static final class OfInt

   671                 extends EmptyNode<Integer, int[], IntConsumer>

   672                 implements Node.OfInt {

   673 

   674             OfInt() { } // Avoid creation of special accessor

   675 

   676             @Override

   677             public Spliterator.OfInt spliterator() {

   678                 return Spliterators.emptyIntSpliterator();

   679             }

   680 

   681             @Override

   682             public int[] asIntArray() {

   683                 return EMPTY_INT_ARRAY;

   684             }

   685         }

   686 

   687         private static final class OfLong

   688                 extends EmptyNode<Long, long[], LongConsumer>

   689                 implements Node.OfLong {

   690 

   691             OfLong() { } // Avoid creation of special accessor

   692 

   693             @Override

   694             public Spliterator.OfLong spliterator() {

   695                 return Spliterators.emptyLongSpliterator();

   696             }

   697 

   698             @Override

   699             public long[] asLongArray() {

   700                 return EMPTY_LONG_ARRAY;

   701             }

   702         }

   703 

   704         private static final class OfDouble

   705                 extends EmptyNode<Double, double[], DoubleConsumer>

   706                 implements Node.OfDouble {

   707 

   708             OfDouble() { } // Avoid creation of special accessor

   709 

   710             @Override

   711             public Spliterator.OfDouble spliterator() {

   712                 return Spliterators.emptyDoubleSpliterator();

   713             }

   714 

   715             @Override

   716             public double[] asDoubleArray() {

   717                 return EMPTY_DOUBLE_ARRAY;

   718             }

   719         }

   720     }

   721 

   722     /** Node class for a reference array */

   723     private static class ArrayNode<T> implements Node<T> {

   724         final T[] array;

   725         int curSize;

   726 

   727         @SuppressWarnings("unchecked")

   728         ArrayNode(long size, IntFunction<T[]> generator) {

   729             if (size >= MAX_ARRAY_SIZE)

   730                 throw new IllegalArgumentException("Stream size exceeds max array size");

   731             this.array = generator.apply((int) size);

   732             this.curSize = 0;

   733         }

   734 

   735         ArrayNode(T[] array) {

   736             this.array = array;

   737             this.curSize = array.length;

   738         }

   739 

   740         // Node

   741 

   742         @Override

   743         public Spliterator<T> spliterator() {

   744             return Arrays.spliterator(array, 0, curSize);

   745         }

   746 

   747         @Override

   748         public void copyInto(T[] dest, int destOffset) {

   749             System.arraycopy(array, 0, dest, destOffset, curSize);

   750         }

   751 

   752         @Override

   753         public T[] asArray(IntFunction<T[]> generator) {

   754             if (array.length == curSize) {

   755                 return array;

   756             } else {

   757                 throw new IllegalStateException();

   758             }

   759         }

   760 

   761         @Override

   762         public long count() {

   763             return curSize;

   764         }

   765 

   766         // Traversable

   767 

   768         @Override

   769         public void forEach(Consumer<? super T> consumer) {

   770             for (int i = 0; i < curSize; i++) {

   771                 consumer.accept(array[i]);

   772             }

   773         }

   774 

   775         //

   776 

   777         @Override

   778         public String toString() {

   779             return String.format("ArrayNode[%d][%s]",

   780                                  array.length - curSize, Arrays.toString(array));

   781         }

   782     }

   783 

   784     /** Node class for a Collection */

   785     private static final class CollectionNode<T> implements Node<T> {

   786         private final Collection<T> c;

   787 

   788         CollectionNode(Collection<T> c) {

   789             this.c = c;

   790         }

   791 

   792         // Node

   793 

   794         @Override

   795         public Spliterator<T> spliterator() {

   796             return c.stream().spliterator();

   797         }

   798 

   799         @Override

   800         public void copyInto(T[] array, int offset) {

   801             for (T t : c)

   802                 array[offset++] = t;

   803         }

   804 

   805         @Override

   806         @SuppressWarnings("unchecked")

   807         public T[] asArray(IntFunction<T[]> generator) {

   808             return c.toArray(generator.apply(c.size()));

   809         }

   810 

   811         @Override

   812         public long count() {

   813             return c.size();

   814         }

   815 

   816         @Override

   817         public void forEach(Consumer<? super T> consumer) {

   818             c.forEach(consumer);

   819         }

   820 

   821         //

   822 

   823         @Override

   824         public String toString() {

   825             return String.format("CollectionNode[%d][%s]", c.size(), c);

   826         }

   827     }

   828 

   829     /**

   830      * Node class for an internal node with two or more children

   831      */

   832     static final class ConcNode<T> implements Node<T> {

   833         private final Node<T> left;

   834         private final Node<T> right;

   835 

   836         private final long size;

   837 

   838         ConcNode(Node<T> left, Node<T> right) {

   839             this.left = left;

   840             this.right = right;

   841             // The Node count will be required when the Node spliterator is

   842             // obtained and it is cheaper to aggressively calculate bottom up

   843             // as the tree is built rather than later on from the top down

   844             // traversing the tree

   845             this.size = left.count() + right.count();

   846         }

   847 

   848         // Node

   849 

   850         @Override

   851         public Spliterator<T> spliterator() {

   852             return new Nodes.InternalNodeSpliterator.OfRef<>(this);

   853         }

   854 

   855         @Override

   856         public int getChildCount() {

   857             return 2;

   858         }

   859 

   860         @Override

   861         public Node<T> getChild(int i) {

   862             if (i == 0) return left;

   863             if (i == 1) return right;

   864             throw new IndexOutOfBoundsException();

   865         }

   866 

   867         @Override

   868         public void copyInto(T[] array, int offset) {

   869             Objects.requireNonNull(array);

   870             left.copyInto(array, offset);

   871             right.copyInto(array, offset + (int) left.count());

   872         }

   873 

   874         @Override

   875         public T[] asArray(IntFunction<T[]> generator) {

   876             T[] array = generator.apply((int) count());

   877             copyInto(array, 0);

   878             return array;

   879         }

   880 

   881         @Override

   882         public long count() {

   883             return size;

   884         }

   885 

   886         @Override

   887         public void forEach(Consumer<? super T> consumer) {

   888             left.forEach(consumer);

   889             right.forEach(consumer);

   890         }

   891 

   892         @Override

   893         public String toString() {

   894             if (count() < 32) {

   895                 return String.format("ConcNode[%s.%s]", left, right);

   896             } else {

   897                 return String.format("ConcNode[size=%d]", count());

   898             }

   899         }

   900     }

   901 

   902     /** Abstract class for spliterator for all internal node classes */

   903     private static abstract class InternalNodeSpliterator<T,

   904                                                           S extends Spliterator<T>,

   905                                                           N extends Node<T>, C>

   906             implements Spliterator<T> {

   907         // Node we are pointing to

   908         // null if full traversal has occurred

   909         N curNode;

   910 

   911         // next child of curNode to consume

   912         int curChildIndex;

   913 

   914         // The spliterator of the curNode if that node is last and has no children.

   915         // This spliterator will be delegated to for splitting and traversing.

   916         // null if curNode has children

   917         S lastNodeSpliterator;

   918 

   919         // spliterator used while traversing with tryAdvance

   920         // null if no partial traversal has occurred

   921         S tryAdvanceSpliterator;

   922 

   923         // node stack used when traversing to search and find leaf nodes

   924         // null if no partial traversal has occurred

   925         Deque<N> tryAdvanceStack;

   926 

   927         InternalNodeSpliterator(N curNode) {

   928             this.curNode = curNode;

   929         }

   930 

   931         /**

   932          * Initiate a stack containing, in left-to-right order, the child nodes

   933          * covered by this spliterator

   934          */

   935         protected final Deque<N> initStack() {

   936             // Bias size to the case where leaf nodes are close to this node

   937             // 8 is the minimum initial capacity for the ArrayDeque implementation

   938             Deque<N> stack = new ArrayDeque<>(8);

   939             for (int i = curNode.getChildCount() - 1; i >= curChildIndex; i--)

   940                 stack.addFirst((N) curNode.getChild(i));

   941             return stack;

   942         }

   943 

   944         /**

   945          * Depth first search, in left-to-right order, of the node tree, using

   946          * an explicit stack, to find the next non-empty leaf node.

   947          */

   948         protected final N findNextLeafNode(Deque<N> stack) {

   949             N n = null;

   950             while ((n = stack.pollFirst()) != null) {

   951                 if (n.getChildCount() == 0) {

   952                     if (n.count() > 0)

   953                         return n;

   954                 } else {

   955                     for (int i = n.getChildCount() - 1; i >= 0; i--)

   956                         stack.addFirst((N) n.getChild(i));

   957                 }

   958             }

   959 

   960             return null;

   961         }

   962 

   963         protected final boolean internalTryAdvance(C consumer) {

   964             if (curNode == null)

   965                 return false;

   966 

   967             if (tryAdvanceSpliterator == null) {

   968                 if (lastNodeSpliterator == null) {

   969                     // Initiate the node stack

   970                     tryAdvanceStack = initStack();

   971                     N leaf = findNextLeafNode(tryAdvanceStack);

   972                     if (leaf != null)

   973                         tryAdvanceSpliterator = (S) leaf.spliterator();

   974                     else {

   975                         // A non-empty leaf node was not found

   976                         // No elements to traverse

   977                         curNode = null;

   978                         return false;

   979                     }

   980                 }

   981                 else

   982                     tryAdvanceSpliterator = lastNodeSpliterator;

   983             }

   984 

   985             boolean hasNext = tryAdvance(tryAdvanceSpliterator, consumer);

   986             if (!hasNext) {

   987                 if (lastNodeSpliterator == null) {

   988                     // Advance to the spliterator of the next non-empty leaf node

   989                     Node<T> leaf = findNextLeafNode(tryAdvanceStack);

   990                     if (leaf != null) {

   991                         tryAdvanceSpliterator = (S) leaf.spliterator();

   992                         // Since the node is not-empty the spliterator can be advanced

   993                         return tryAdvance(tryAdvanceSpliterator, consumer);

   994                     }

   995                 }

   996                 // No more elements to traverse

   997                 curNode = null;

   998             }

   999             return hasNext;

  1000         }

  1001 

  1002         protected abstract boolean tryAdvance(S spliterator, C consumer);

  1003 

  1004         @Override

  1005         @SuppressWarnings("unchecked")

  1006         public S trySplit() {

  1007             if (curNode == null || tryAdvanceSpliterator != null)

  1008                 return null; // Cannot split if fully or partially traversed

  1009             else if (lastNodeSpliterator != null)

  1010                 return (S) lastNodeSpliterator.trySplit();

  1011             else if (curChildIndex < curNode.getChildCount() - 1)

  1012                 return (S) curNode.getChild(curChildIndex++).spliterator();

  1013             else {

  1014                 curNode = (N) curNode.getChild(curChildIndex);

  1015                 if (curNode.getChildCount() == 0) {

  1016                     lastNodeSpliterator = (S) curNode.spliterator();

  1017                     return (S) lastNodeSpliterator.trySplit();

  1018                 }

  1019                 else {

  1020                     curChildIndex = 0;

  1021                     return (S) curNode.getChild(curChildIndex++).spliterator();

  1022                 }

  1023             }

  1024         }

  1025 

  1026         @Override

  1027         public long estimateSize() {

  1028             if (curNode == null)

  1029                 return 0;

  1030 

  1031             // Will not reflect the effects of partial traversal.

  1032             // This is compliant with the specification

  1033             if (lastNodeSpliterator != null)

  1034                 return lastNodeSpliterator.estimateSize();

  1035             else {

  1036                 long size = 0;

  1037                 for (int i = curChildIndex; i < curNode.getChildCount(); i++)

  1038                     size += curNode.getChild(i).count();

  1039                 return size;

  1040             }

  1041         }

  1042 

  1043         @Override

  1044         public int characteristics() {

  1045             return Spliterator.SIZED;

  1046         }

  1047 

  1048         private static final class OfRef<T>

  1049                 extends InternalNodeSpliterator<T, Spliterator<T>, Node<T>, Consumer<? super T>> {

  1050 

  1051             OfRef(Node<T> curNode) {

  1052                 super(curNode);

  1053             }

  1054 

  1055             @Override

  1056             public boolean tryAdvance(Consumer<? super T> consumer) {

  1057                 return internalTryAdvance(consumer);

  1058             }

  1059 

  1060             @Override

  1061             protected boolean tryAdvance(Spliterator<T> spliterator,

  1062                                          Consumer<? super T> consumer) {

  1063                 return spliterator.tryAdvance(consumer);

  1064             }

  1065 

  1066             @Override

  1067             public void forEachRemaining(Consumer<? super T> consumer) {

  1068                 if (curNode == null)

  1069                     return;

  1070 

  1071                 if (tryAdvanceSpliterator == null) {

  1072                     if (lastNodeSpliterator == null) {

  1073                         Deque<Node<T>> stack = initStack();

  1074                         Node<T> leaf;

  1075                         while ((leaf = findNextLeafNode(stack)) != null) {

  1076                             leaf.forEach(consumer);

  1077                         }

  1078                         curNode = null;

  1079                     }

  1080                     else

  1081                         lastNodeSpliterator.forEachRemaining(consumer);

  1082                 }

  1083                 else

  1084                     while(tryAdvance(consumer)) { }

  1085             }

  1086         }

  1087 

  1088         private static final class OfInt

  1089                 extends InternalNodeSpliterator<Integer, Spliterator.OfInt, Node.OfInt, IntConsumer>

  1090                 implements Spliterator.OfInt {

  1091 

  1092             OfInt(Node.OfInt cur) {

  1093                 super(cur);

  1094             }

  1095 

  1096             @Override

  1097             public boolean tryAdvance(IntConsumer consumer) {

  1098                 return internalTryAdvance(consumer);

  1099             }

  1100 

  1101             @Override

  1102             protected boolean tryAdvance(Spliterator.OfInt spliterator,

  1103                                          IntConsumer consumer) {

  1104                 return spliterator.tryAdvance(consumer);

  1105             }

  1106 

  1107             @Override

  1108             public void forEachRemaining(IntConsumer consumer) {

  1109                 if (curNode == null)

  1110                     return;

  1111 

  1112                 if (tryAdvanceSpliterator == null) {

  1113                     if (lastNodeSpliterator == null) {

  1114                         Deque<Node.OfInt> stack = initStack();

  1115                         Node.OfInt leaf;

  1116                         while ((leaf = findNextLeafNode(stack)) != null) {

  1117                             leaf.forEach(consumer);

  1118                         }

  1119                         curNode = null;

  1120                     }

  1121                     else

  1122                         lastNodeSpliterator.forEachRemaining(consumer);

  1123                 }

  1124                 else

  1125                     while(tryAdvance(consumer)) { }

  1126             }

  1127         }

  1128 

  1129         private static final class OfLong

  1130                 extends InternalNodeSpliterator<Long, Spliterator.OfLong, Node.OfLong, LongConsumer>

  1131                 implements Spliterator.OfLong {

  1132 

  1133             OfLong(Node.OfLong cur) {

  1134                 super(cur);

  1135             }