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