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