1 /* 2 * Copyright (c) 2012, 2015, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 package java.util.stream; 26 27 import java.util.ArrayDeque; 28 import java.util.Arrays; 29 import java.util.Collection; 30 import java.util.Deque; 31 import java.util.List; 32 import java.util.Objects; 33 import java.util.Spliterator; 34 import java.util.Spliterators; 35 import java.util.concurrent.CountedCompleter; 36 import java.util.function.BinaryOperator; 37 import java.util.function.Consumer; 38 import java.util.function.DoubleConsumer; 39 import java.util.function.IntConsumer; 40 import java.util.function.IntFunction; 41 import java.util.function.LongConsumer; 42 import java.util.function.LongFunction; 43 44 /** 45 * Factory methods for constructing implementations of {@link Node} and 46 * {@link Node.Builder} and their primitive specializations. Fork/Join tasks 47 * for collecting output from a {@link PipelineHelper} to a {@link Node} and 48 * flattening {@link Node}s. 49 * 50 * @since 1.8 51 */ 52 final class Nodes { 53 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 private static final class OfInt 594 extends EmptyNode<Integer, int[], IntConsumer> 595 implements Node.OfInt { 596 OfInt()597 OfInt() { } // Avoid creation of special accessor 598 599 @Override spliterator()600 public Spliterator.OfInt spliterator() { 601 return Spliterators.emptyIntSpliterator(); 602 } 603 604 @Override asPrimitiveArray()605 public int[] asPrimitiveArray() { 606 return EMPTY_INT_ARRAY; 607 } 608 } 609 610 private static final class OfLong 611 extends EmptyNode<Long, long[], LongConsumer> 612 implements Node.OfLong { 613 OfLong()614 OfLong() { } // Avoid creation of special accessor 615 616 @Override spliterator()617 public Spliterator.OfLong spliterator() { 618 return Spliterators.emptyLongSpliterator(); 619 } 620 621 @Override asPrimitiveArray()622 public long[] asPrimitiveArray() { 623 return EMPTY_LONG_ARRAY; 624 } 625 } 626 627 private static final class OfDouble 628 extends EmptyNode<Double, double[], DoubleConsumer> 629 implements Node.OfDouble { 630 OfDouble()631 OfDouble() { } // Avoid creation of special accessor 632 633 @Override spliterator()634 public Spliterator.OfDouble spliterator() { 635 return Spliterators.emptyDoubleSpliterator(); 636 } 637 638 @Override asPrimitiveArray()639 public double[] asPrimitiveArray() { 640 return EMPTY_DOUBLE_ARRAY; 641 } 642 } 643 } 644 645 /** Node class for a reference array */ 646 private static class ArrayNode<T> implements Node<T> { 647 final T[] array; 648 int curSize; 649 650 @SuppressWarnings("unchecked") ArrayNode(long size, IntFunction<T[]> generator)651 ArrayNode(long size, IntFunction<T[]> generator) { 652 if (size >= MAX_ARRAY_SIZE) 653 throw new IllegalArgumentException(BAD_SIZE); 654 this.array = generator.apply((int) size); 655 this.curSize = 0; 656 } 657 ArrayNode(T[] array)658 ArrayNode(T[] array) { 659 this.array = array; 660 this.curSize = array.length; 661 } 662 663 // Node 664 665 @Override spliterator()666 public Spliterator<T> spliterator() { 667 return Arrays.spliterator(array, 0, curSize); 668 } 669 670 @Override copyInto(T[] dest, int destOffset)671 public void copyInto(T[] dest, int destOffset) { 672 System.arraycopy(array, 0, dest, destOffset, curSize); 673 } 674 675 @Override asArray(IntFunction<T[]> generator)676 public T[] asArray(IntFunction<T[]> generator) { 677 if (array.length == curSize) { 678 return array; 679 } else { 680 throw new IllegalStateException(); 681 } 682 } 683 684 @Override count()685 public long count() { 686 return curSize; 687 } 688 689 @Override forEach(Consumer<? super T> consumer)690 public void forEach(Consumer<? super T> consumer) { 691 for (int i = 0; i < curSize; i++) { 692 consumer.accept(array[i]); 693 } 694 } 695 696 // 697 698 @Override toString()699 public String toString() { 700 return String.format("ArrayNode[%d][%s]", 701 array.length - curSize, Arrays.toString(array)); 702 } 703 } 704 705 /** Node class for a Collection */ 706 private static final class CollectionNode<T> implements Node<T> { 707 private final Collection<T> c; 708 CollectionNode(Collection<T> c)709 CollectionNode(Collection<T> c) { 710 this.c = c; 711 } 712 713 // Node 714 715 @Override spliterator()716 public Spliterator<T> spliterator() { 717 return c.stream().spliterator(); 718 } 719 720 @Override copyInto(T[] array, int offset)721 public void copyInto(T[] array, int offset) { 722 for (T t : c) 723 array[offset++] = t; 724 } 725 726 @Override 727 @SuppressWarnings("unchecked") asArray(IntFunction<T[]> generator)728 public T[] asArray(IntFunction<T[]> generator) { 729 return c.toArray(generator.apply(c.size())); 730 } 731 732 @Override count()733 public long count() { 734 return c.size(); 735 } 736 737 @Override forEach(Consumer<? super T> consumer)738 public void forEach(Consumer<? super T> consumer) { 739 c.forEach(consumer); 740 } 741 742 // 743 744 @Override toString()745 public String toString() { 746 return String.format("CollectionNode[%d][%s]", c.size(), c); 747 } 748 } 749 750 /** 751 * Node class for an internal node with two or more children 752 */ 753 private abstract static class AbstractConcNode<T, T_NODE extends Node<T>> implements Node<T> { 754 protected final T_NODE left; 755 protected final T_NODE right; 756 private final long size; 757 AbstractConcNode(T_NODE left, T_NODE right)758 AbstractConcNode(T_NODE left, T_NODE right) { 759 this.left = left; 760 this.right = right; 761 // The Node count will be required when the Node spliterator is 762 // obtained and it is cheaper to aggressively calculate bottom up 763 // as the tree is built rather than later on from the top down 764 // traversing the tree 765 this.size = left.count() + right.count(); 766 } 767 768 @Override getChildCount()769 public int getChildCount() { 770 return 2; 771 } 772 773 @Override getChild(int i)774 public T_NODE getChild(int i) { 775 if (i == 0) return left; 776 if (i == 1) return right; 777 throw new IndexOutOfBoundsException(); 778 } 779 780 @Override count()781 public long count() { 782 return size; 783 } 784 } 785 786 static final class ConcNode<T> 787 extends AbstractConcNode<T, Node<T>> 788 implements Node<T> { 789 ConcNode(Node<T> left, Node<T> right)790 ConcNode(Node<T> left, Node<T> right) { 791 super(left, right); 792 } 793 794 @Override spliterator()795 public Spliterator<T> spliterator() { 796 return new Nodes.InternalNodeSpliterator.OfRef<>(this); 797 } 798 799 @Override copyInto(T[] array, int offset)800 public void copyInto(T[] array, int offset) { 801 Objects.requireNonNull(array); 802 left.copyInto(array, offset); 803 // Cast to int is safe since it is the callers responsibility to 804 // ensure that there is sufficient room in the array 805 right.copyInto(array, offset + (int) left.count()); 806 } 807 808 @Override asArray(IntFunction<T[]> generator)809 public T[] asArray(IntFunction<T[]> generator) { 810 long size = count(); 811 if (size >= MAX_ARRAY_SIZE) 812 throw new IllegalArgumentException(BAD_SIZE); 813 T[] array = generator.apply((int) size); 814 copyInto(array, 0); 815 return array; 816 } 817 818 @Override forEach(Consumer<? super T> consumer)819 public void forEach(Consumer<? super T> consumer) { 820 left.forEach(consumer); 821 right.forEach(consumer); 822 } 823 824 @Override truncate(long from, long to, IntFunction<T[]> generator)825 public Node<T> truncate(long from, long to, IntFunction<T[]> generator) { 826 if (from == 0 && to == count()) 827 return this; 828 long leftCount = left.count(); 829 if (from >= leftCount) 830 return right.truncate(from - leftCount, to - leftCount, generator); 831 else if (to <= leftCount) 832 return left.truncate(from, to, generator); 833 else { 834 return Nodes.conc(getShape(), left.truncate(from, leftCount, generator), 835 right.truncate(0, to - leftCount, generator)); 836 } 837 } 838 839 @Override toString()840 public String toString() { 841 if (count() < 32) { 842 return String.format("ConcNode[%s.%s]", left, right); 843 } else { 844 return String.format("ConcNode[size=%d]", count()); 845 } 846 } 847 848 private abstract static class OfPrimitive<E, T_CONS, T_ARR, 849 T_SPLITR extends Spliterator.OfPrimitive<E, T_CONS, T_SPLITR>, 850 T_NODE extends Node.OfPrimitive<E, T_CONS, T_ARR, T_SPLITR, T_NODE>> 851 extends AbstractConcNode<E, T_NODE> 852 implements Node.OfPrimitive<E, T_CONS, T_ARR, T_SPLITR, T_NODE> { 853 OfPrimitive(T_NODE left, T_NODE right)854 OfPrimitive(T_NODE left, T_NODE right) { 855 super(left, right); 856 } 857 858 @Override forEach(T_CONS consumer)859 public void forEach(T_CONS consumer) { 860 left.forEach(consumer); 861 right.forEach(consumer); 862 } 863 864 @Override copyInto(T_ARR array, int offset)865 public void copyInto(T_ARR array, int offset) { 866 left.copyInto(array, offset); 867 // Cast to int is safe since it is the callers responsibility to 868 // ensure that there is sufficient room in the array 869 right.copyInto(array, offset + (int) left.count()); 870 } 871 872 @Override asPrimitiveArray()873 public T_ARR asPrimitiveArray() { 874 long size = count(); 875 if (size >= MAX_ARRAY_SIZE) 876 throw new IllegalArgumentException(BAD_SIZE); 877 T_ARR array = newArray((int) size); 878 copyInto(array, 0); 879 return array; 880 } 881 882 @Override toString()883 public String toString() { 884 if (count() < 32) 885 return String.format("%s[%s.%s]", this.getClass().getName(), left, right); 886 else 887 return String.format("%s[size=%d]", this.getClass().getName(), count()); 888 } 889 } 890 891 static final class OfInt 892 extends ConcNode.OfPrimitive<Integer, IntConsumer, int[], Spliterator.OfInt, Node.OfInt> 893 implements Node.OfInt { 894 OfInt(Node.OfInt left, Node.OfInt right)895 OfInt(Node.OfInt left, Node.OfInt right) { 896 super(left, right); 897 } 898 899 @Override spliterator()900 public Spliterator.OfInt spliterator() { 901 return new InternalNodeSpliterator.OfInt(this); 902 } 903 } 904 905 static final class OfLong 906 extends ConcNode.OfPrimitive<Long, LongConsumer, long[], Spliterator.OfLong, Node.OfLong> 907 implements Node.OfLong { 908 OfLong(Node.OfLong left, Node.OfLong right)909 OfLong(Node.OfLong left, Node.OfLong right) { 910 super(left, right); 911 } 912 913 @Override spliterator()914 public Spliterator.OfLong spliterator() { 915 return new InternalNodeSpliterator.OfLong(this); 916 } 917 } 918 919 static final class OfDouble 920 extends ConcNode.OfPrimitive<Double, DoubleConsumer, double[], Spliterator.OfDouble, Node.OfDouble> 921 implements Node.OfDouble { 922 OfDouble(Node.OfDouble left, Node.OfDouble right)923 OfDouble(Node.OfDouble left, Node.OfDouble right) { 924 super(left, right); 925 } 926 927 @Override spliterator()928 public Spliterator.OfDouble spliterator() { 929 return new InternalNodeSpliterator.OfDouble(this); 930 } 931 } 932 } 933 934 /** Abstract class for spliterator for all internal node classes */ 935 private abstract static class InternalNodeSpliterator<T, 936 S extends Spliterator<T>, 937 N extends Node<T>> 938 implements Spliterator<T> { 939 // Node we are pointing to 940 // null if full traversal has occurred 941 N curNode; 942 943 // next child of curNode to consume 944 int curChildIndex; 945 946 // The spliterator of the curNode if that node is last and has no children. 947 // This spliterator will be delegated to for splitting and traversing. 948 // null if curNode has children 949 S lastNodeSpliterator; 950 951 // spliterator used while traversing with tryAdvance 952 // null if no partial traversal has occurred 953 S tryAdvanceSpliterator; 954 955 // node stack used when traversing to search and find leaf nodes 956 // null if no partial traversal has occurred 957 Deque<N> tryAdvanceStack; 958 InternalNodeSpliterator(N curNode)959 InternalNodeSpliterator(N curNode) { 960 this.curNode = curNode; 961 } 962 963 /** 964 * Initiate a stack containing, in left-to-right order, the child nodes 965 * covered by this spliterator 966 */ 967 @SuppressWarnings("unchecked") initStack()968 protected final Deque<N> initStack() { 969 // Bias size to the case where leaf nodes are close to this node 970 // 8 is the minimum initial capacity for the ArrayDeque implementation 971 Deque<N> stack = new ArrayDeque<>(8); 972 for (int i = curNode.getChildCount() - 1; i >= curChildIndex; i--) 973 stack.addFirst((N) curNode.getChild(i)); 974 return stack; 975 } 976 977 /** 978 * Depth first search, in left-to-right order, of the node tree, using 979 * an explicit stack, to find the next non-empty leaf node. 980 */ 981 @SuppressWarnings("unchecked") findNextLeafNode(Deque<N> stack)982 protected final N findNextLeafNode(Deque<N> stack) { 983 N n = null; 984 while ((n = stack.pollFirst()) != null) { 985 if (n.getChildCount() == 0) { 986 if (n.count() > 0) 987 return n; 988 } else { 989 for (int i = n.getChildCount() - 1; i >= 0; i--) 990 stack.addFirst((N) n.getChild(i)); 991 } 992 } 993 994 return null; 995 } 996 997 @SuppressWarnings("unchecked") initTryAdvance()998 protected final boolean initTryAdvance() { 999 if (curNode == null) 1000 return false; 1001 1002 if (tryAdvanceSpliterator == null) { 1003 if (lastNodeSpliterator == null) { 1004 // Initiate the node stack 1005 tryAdvanceStack = initStack(); 1006 N leaf = findNextLeafNode(tryAdvanceStack); 1007 if (leaf != null) 1008 tryAdvanceSpliterator = (S) leaf.spliterator(); 1009 else { 1010 // A non-empty leaf node was not found 1011 // No elements to traverse 1012 curNode = null; 1013 return false; 1014 } 1015 } 1016 else 1017 tryAdvanceSpliterator = lastNodeSpliterator; 1018 } 1019 return true; 1020 } 1021 1022 @Override 1023 @SuppressWarnings("unchecked") trySplit()1024 public final S trySplit() { 1025 if (curNode == null || tryAdvanceSpliterator != null) 1026 return null; // Cannot split if fully or partially traversed 1027 else if (lastNodeSpliterator != null) 1028 return (S) lastNodeSpliterator.trySplit(); 1029 else if (curChildIndex < curNode.getChildCount() - 1) 1030 return (S) curNode.getChild(curChildIndex++).spliterator(); 1031 else { 1032 curNode = (N) curNode.getChild(curChildIndex); 1033 if (curNode.getChildCount() == 0) { 1034 lastNodeSpliterator = (S) curNode.spliterator(); 1035 return (S) lastNodeSpliterator.trySplit(); 1036 } 1037 else { 1038 curChildIndex = 0; 1039 return (S) curNode.getChild(curChildIndex++).spliterator(); 1040 } 1041 } 1042 } 1043 1044 @Override estimateSize()1045 public final long estimateSize() { 1046 if (curNode == null) 1047 return 0; 1048 1049 // Will not reflect the effects of partial traversal. 1050 // This is compliant with the specification 1051 if (lastNodeSpliterator != null) 1052 return lastNodeSpliterator.estimateSize(); 1053 else { 1054 long size = 0; 1055 for (int i = curChildIndex; i < curNode.getChildCount(); i++) 1056 size += curNode.getChild(i).count(); 1057 return size; 1058 } 1059 } 1060 1061 @Override characteristics()1062 public final int characteristics() { 1063 return Spliterator.SIZED; 1064 } 1065 1066 private static final class OfRef<T> 1067 extends InternalNodeSpliterator<T, Spliterator<T>, Node<T>> { 1068 OfRef(Node<T> curNode)1069 OfRef(Node<T> curNode) { 1070 super(curNode); 1071 } 1072 1073 @Override tryAdvance(Consumer<? super T> consumer)1074 public boolean tryAdvance(Consumer<? super T> consumer) { 1075 if (!initTryAdvance()) 1076 return false; 1077 1078 boolean hasNext = tryAdvanceSpliterator.tryAdvance(consumer); 1079 if (!hasNext) { 1080 if (lastNodeSpliterator == null) { 1081 // Advance to the spliterator of the next non-empty leaf node 1082 Node<T> leaf = findNextLeafNode(tryAdvanceStack); 1083 if (leaf != null) { 1084 tryAdvanceSpliterator = leaf.spliterator(); 1085 // Since the node is not-empty the spliterator can be advanced 1086 return tryAdvanceSpliterator.tryAdvance(consumer); 1087 } 1088 } 1089 // No more elements to traverse 1090 curNode = null; 1091 } 1092 return hasNext; 1093 } 1094 1095 @Override forEachRemaining(Consumer<? super T> consumer)1096 public void forEachRemaining(Consumer<? super T> consumer) { 1097 if (curNode == null) 1098 return; 1099 1100 if (tryAdvanceSpliterator == null) { 1101 if (lastNodeSpliterator == null) { 1102 Deque<Node<T>> stack = initStack(); 1103 Node<T> leaf; 1104 while ((leaf = findNextLeafNode(stack)) != null) { 1105 leaf.forEach(consumer); 1106 } 1107 curNode = null; 1108 } 1109 else 1110 lastNodeSpliterator.forEachRemaining(consumer); 1111 } 1112 else 1113 while(tryAdvance(consumer)) { } 1114 } 1115 } 1116 1117 private abstract static class OfPrimitive<T, T_CONS, T_ARR, 1118 T_SPLITR extends Spliterator.OfPrimitive<T, T_CONS, T_SPLITR>, 1119 N extends Node.OfPrimitive<T, T_CONS, T_ARR, T_SPLITR, N>> 1120 extends InternalNodeSpliterator<T, T_SPLITR, N> 1121 implements Spliterator.OfPrimitive<T, T_CONS, T_SPLITR> { 1122 OfPrimitive(N cur)1123 OfPrimitive(N cur) { 1124 super(cur); 1125 } 1126 1127 @Override tryAdvance(T_CONS consumer)1128 public boolean tryAdvance(T_CONS consumer) { 1129 if (!initTryAdvance()) 1130 return false; 1131 1132 boolean hasNext = tryAdvanceSpliterator.tryAdvance(consumer); 1133 if (!hasNext) { 1134 if (lastNodeSpliterator == null) { 1135 // Advance to the spliterator of the next non-empty leaf node 1136 N leaf = findNextLeafNode(tryAdvanceStack); 1137 if (leaf != null) { 1138 tryAdvanceSpliterator = leaf.spliterator(); 1139 // Since the node is not-empty the spliterator can be advanced 1140 return tryAdvanceSpliterator.tryAdvance(consumer); 1141 } 1142 } 1143 // No more elements to traverse 1144 curNode = null; 1145 } 1146 return hasNext; 1147 } 1148 1149 @Override forEachRemaining(T_CONS consumer)1150 public void forEachRemaining(T_CONS consumer) { 1151 if (curNode == null) 1152 return; 1153 1154 if (tryAdvanceSpliterator == null) { 1155 if (lastNodeSpliterator == null) { 1156 Deque<N> stack = initStack(); 1157 N leaf; 1158 while ((leaf = findNextLeafNode(stack)) != null) { 1159 leaf.forEach(consumer); 1160 } 1161 curNode = null; 1162 } 1163 else 1164 lastNodeSpliterator.forEachRemaining(consumer); 1165 } 1166 else 1167 while(tryAdvance(consumer)) { } 1168 } 1169 } 1170 1171 private static final class OfInt 1172 extends OfPrimitive<Integer, IntConsumer, int[], Spliterator.OfInt, Node.OfInt> 1173 implements Spliterator.OfInt { 1174 OfInt(Node.OfInt cur)1175 OfInt(Node.OfInt cur) { 1176 super(cur); 1177 } 1178 } 1179 1180 private static final class OfLong 1181 extends OfPrimitive<Long, LongConsumer, long[], Spliterator.OfLong, Node.OfLong> 1182 implements Spliterator.OfLong { 1183 OfLong(Node.OfLong cur)1184 OfLong(Node.OfLong cur) { 1185 super(cur); 1186 } 1187 } 1188 1189 private static final class OfDouble 1190 extends OfPrimitive<Double, DoubleConsumer, double[], Spliterator.OfDouble, Node.OfDouble> 1191 implements Spliterator.OfDouble { 1192 OfDouble(Node.OfDouble cur)1193 OfDouble(Node.OfDouble cur) { 1194 super(cur); 1195 } 1196 } 1197 } 1198 1199 /** 1200 * Fixed-sized builder class for reference nodes 1201 */ 1202 private static final class FixedNodeBuilder<T> 1203 extends ArrayNode<T> 1204 implements Node.Builder<T> { 1205 FixedNodeBuilder(long size, IntFunction<T[]> generator)1206 FixedNodeBuilder(long size, IntFunction<T[]> generator) { 1207 super(size, generator); 1208 assert size < MAX_ARRAY_SIZE; 1209 } 1210 1211 @Override 1212 public Node<T> build() { 1213 if (curSize < array.length) 1214 throw new IllegalStateException(String.format("Current size %d is less than fixed size %d", 1215 curSize, array.length)); 1216 return this; 1217 } 1218 1219 @Override 1220 public void begin(long size) { 1221 if (size != array.length) 1222 throw new IllegalStateException(String.format("Begin size %d is not equal to fixed size %d", 1223 size, array.length)); 1224 curSize = 0; 1225 } 1226 1227 @Override 1228 public void accept(T t) { 1229 if (curSize < array.length) { 1230 array[curSize++] = t; 1231 } else { 1232 throw new IllegalStateException(String.format("Accept exceeded fixed size of %d", 1233 array.length)); 1234 } 1235 } 1236 1237 @Override 1238 public void end() { 1239 if (curSize < array.length) 1240 throw new IllegalStateException(String.format("End size %d is less than fixed size %d", 1241 curSize, array.length)); 1242 } 1243 1244 @Override 1245 public String toString() { 1246 return String.format("FixedNodeBuilder[%d][%s]", 1247 array.length - curSize, Arrays.toString(array)); 1248 } 1249 } 1250 1251 /** 1252 * Variable-sized builder class for reference nodes 1253 */ 1254 private static final class SpinedNodeBuilder<T> 1255 extends SpinedBuffer<T> 1256 implements Node<T>, Node.Builder<T> { 1257 private boolean building = false; 1258 1259 SpinedNodeBuilder() {} // Avoid creation of special accessor 1260 1261 @Override 1262 public Spliterator<T> spliterator() { 1263 assert !building : "during building"; 1264 return super.spliterator(); 1265 } 1266 1267 @Override 1268 public void forEach(Consumer<? super T> consumer) { 1269 assert !building : "during building"; 1270 super.forEach(consumer); 1271 } 1272 1273 // 1274 @Override 1275 public void begin(long size) { 1276 assert !building : "was already building"; 1277 building = true; 1278 clear(); 1279 ensureCapacity(size); 1280 } 1281 1282 @Override 1283 public void accept(T t) { 1284 assert building : "not building"; 1285 super.accept(t); 1286 } 1287 1288 @Override 1289 public void end() { 1290 assert building : "was not building"; 1291 building = false; 1292 // @@@ check begin(size) and size 1293 } 1294 1295 @Override 1296 public void copyInto(T[] array, int offset) { 1297 assert !building : "during building"; 1298 super.copyInto(array, offset); 1299 } 1300 1301 @Override 1302 public T[] asArray(IntFunction<T[]> arrayFactory) { 1303 assert !building : "during building"; 1304 return super.asArray(arrayFactory); 1305 } 1306 1307 @Override 1308 public Node<T> build() { 1309 assert !building : "during building"; 1310 return this; 1311 } 1312 } 1313 1314 // 1315 1316 private static final int[] EMPTY_INT_ARRAY = new int[0]; 1317 private static final long[] EMPTY_LONG_ARRAY = new long[0]; 1318 private static final double[] EMPTY_DOUBLE_ARRAY = new double[0]; 1319 1320 private static class IntArrayNode implements Node.OfInt { 1321 final int[] array; 1322 int curSize; 1323 1324 IntArrayNode(long size) { 1325 if (size >= MAX_ARRAY_SIZE) 1326 throw new IllegalArgumentException(BAD_SIZE); 1327 this.array = new int[(int) size]; 1328 this.curSize = 0; 1329 } 1330 1331 IntArrayNode(int[] array) { 1332 this.array = array; 1333 this.curSize = array.length; 1334 } 1335 1336 // Node 1337 1338 @Override 1339 public Spliterator.OfInt spliterator() { 1340 return Arrays.spliterator(array, 0, curSize); 1341 } 1342 1343 @Override 1344 public int[] asPrimitiveArray() { 1345 if (array.length == curSize) { 1346 return array; 1347 } else { 1348 return Arrays.copyOf(array, curSize); 1349 } 1350 } 1351 1352 @Override 1353 public void copyInto(int[] dest, int destOffset) { 1354 System.arraycopy(array, 0, dest, destOffset, curSize); 1355 } 1356 1357 @Override 1358 public long count() { 1359 return curSize; 1360 } 1361 1362 @Override 1363 public void forEach(IntConsumer consumer) { 1364 for (int i = 0; i < curSize; i++) { 1365 consumer.accept(array[i]); 1366 } 1367 } 1368 1369 @Override 1370 public String toString() { 1371 return String.format("IntArrayNode[%d][%s]", 1372 array.length - curSize, Arrays.toString(array)); 1373 } 1374 } 1375 1376 private static class LongArrayNode implements Node.OfLong { 1377 final long[] array; 1378 int curSize; 1379 1380 LongArrayNode(long size) { 1381 if (size >= MAX_ARRAY_SIZE) 1382 throw new IllegalArgumentException(BAD_SIZE); 1383 this.array = new long[(int) size]; 1384 this.curSize = 0; 1385 } 1386 1387 LongArrayNode(long[] array) { 1388 this.array = array; 1389 this.curSize = array.length; 1390 } 1391 1392 @Override 1393 public Spliterator.OfLong spliterator() { 1394 return Arrays.spliterator(array, 0, curSize); 1395 } 1396 1397 @Override 1398 public long[] asPrimitiveArray() { 1399 if (array.length == curSize) { 1400 return array; 1401 } else { 1402 return Arrays.copyOf(array, curSize); 1403 } 1404 } 1405 1406 @Override 1407 public void copyInto(long[] dest, int destOffset) { 1408 System.arraycopy(array, 0, dest, destOffset, curSize); 1409 } 1410 1411 @Override 1412 public long count() { 1413 return curSize; 1414 } 1415 1416 @Override 1417 public void forEach(LongConsumer consumer) { 1418 for (int i = 0; i < curSize; i++) { 1419 consumer.accept(array[i]); 1420 } 1421 } 1422 1423 @Override 1424 public String toString() { 1425 return String.format("LongArrayNode[%d][%s]", 1426 array.length - curSize, Arrays.toString(array)); 1427 } 1428 } 1429 1430 private static class DoubleArrayNode implements Node.OfDouble { 1431 final double[] array; 1432 int curSize; 1433 1434 DoubleArrayNode(long size) { 1435 if (size >= MAX_ARRAY_SIZE) 1436 throw new IllegalArgumentException(BAD_SIZE); 1437 this.array = new double[(int) size]; 1438 this.curSize = 0; 1439 } 1440 1441 DoubleArrayNode(double[] array) { 1442 this.array = array; 1443 this.curSize = array.length; 1444 } 1445 1446 @Override 1447 public Spliterator.OfDouble spliterator() { 1448 return Arrays.spliterator(array, 0, curSize); 1449 } 1450 1451 @Override 1452 public double[] asPrimitiveArray() { 1453 if (array.length == curSize) { 1454 return array; 1455 } else { 1456 return Arrays.copyOf(array, curSize); 1457 } 1458 } 1459 1460 @Override 1461 public void copyInto(double[] dest, int destOffset) { 1462 System.arraycopy(array, 0, dest, destOffset, curSize); 1463 } 1464 1465 @Override 1466 public long count() { 1467 return curSize; 1468 } 1469 1470 @Override 1471 public void forEach(DoubleConsumer consumer) { 1472 for (int i = 0; i < curSize; i++) { 1473 consumer.accept(array[i]); 1474 } 1475 } 1476 1477 @Override 1478 public String toString() { 1479 return String.format("DoubleArrayNode[%d][%s]", 1480 array.length - curSize, Arrays.toString(array)); 1481 } 1482 } 1483 1484 private static final class IntFixedNodeBuilder 1485 extends IntArrayNode 1486 implements Node.Builder.OfInt { 1487 1488 IntFixedNodeBuilder(long size) { 1489 super(size); 1490 assert size < MAX_ARRAY_SIZE; 1491 } 1492 1493 @Override 1494 public Node.OfInt build() { 1495 if (curSize < array.length) { 1496 throw new IllegalStateException(String.format("Current size %d is less than fixed size %d", 1497 curSize, array.length)); 1498 } 1499 1500 return this; 1501 } 1502 1503 @Override 1504 public void begin(long size) { 1505 if (size != array.length) { 1506 throw new IllegalStateException(String.format("Begin size %d is not equal to fixed size %d", 1507 size, array.length)); 1508 } 1509 1510 curSize = 0; 1511 } 1512 1513 @Override 1514 public void accept(int i) { 1515 if (curSize < array.length) { 1516 array[curSize++] = i; 1517 } else { 1518 throw new IllegalStateException(String.format("Accept exceeded fixed size of %d", 1519 array.length)); 1520 } 1521 } 1522 1523 @Override 1524 public void end() { 1525 if (curSize < array.length) { 1526 throw new IllegalStateException(String.format("End size %d is less than fixed size %d", 1527 curSize, array.length)); 1528 } 1529 } 1530 1531 @Override 1532 public String toString() { 1533 return String.format("IntFixedNodeBuilder[%d][%s]", 1534 array.length - curSize, Arrays.toString(array)); 1535 } 1536 } 1537 1538 private static final class LongFixedNodeBuilder 1539 extends LongArrayNode 1540 implements Node.Builder.OfLong { 1541 1542 LongFixedNodeBuilder(long size) { 1543 super(size); 1544 assert size < MAX_ARRAY_SIZE; 1545 } 1546 1547 @Override 1548 public Node.OfLong build() { 1549 if (curSize < array.length) { 1550 throw new IllegalStateException(String.format("Current size %d is less than fixed size %d", 1551 curSize, array.length)); 1552 } 1553 1554 return this; 1555 } 1556 1557 @Override 1558 public void begin(long size) { 1559 if (size != array.length) { 1560 throw new IllegalStateException(String.format("Begin size %d is not equal to fixed size %d", 1561 size, array.length)); 1562 } 1563 1564 curSize = 0; 1565 } 1566 1567 @Override 1568 public void accept(long i) { 1569 if (curSize < array.length) { 1570 array[curSize++] = i; 1571 } else { 1572 throw new IllegalStateException(String.format("Accept exceeded fixed size of %d", 1573 array.length)); 1574 } 1575 } 1576 1577 @Override 1578 public void end() { 1579 if (curSize < array.length) { 1580 throw new IllegalStateException(String.format("End size %d is less than fixed size %d", 1581 curSize, array.length)); 1582 } 1583 } 1584 1585 @Override 1586 public String toString() { 1587 return String.format("LongFixedNodeBuilder[%d][%s]", 1588 array.length - curSize, Arrays.toString(array)); 1589 } 1590 } 1591 1592 private static final class DoubleFixedNodeBuilder 1593 extends DoubleArrayNode 1594 implements Node.Builder.OfDouble { 1595 1596 DoubleFixedNodeBuilder(long size) { 1597 super(size); 1598 assert size < MAX_ARRAY_SIZE; 1599 } 1600 1601 @Override 1602 public Node.OfDouble build() { 1603 if (curSize < array.length) { 1604 throw new IllegalStateException(String.format("Current size %d is less than fixed size %d", 1605 curSize, array.length)); 1606 } 1607 1608 return this; 1609 } 1610 1611 @Override 1612 public void begin(long size) { 1613 if (size != array.length) { 1614 throw new IllegalStateException(String.format("Begin size %d is not equal to fixed size %d", 1615 size, array.length)); 1616 } 1617 1618 curSize = 0; 1619 } 1620 1621 @Override 1622 public void accept(double i) { 1623 if (curSize < array.length) { 1624 array[curSize++] = i; 1625 } else { 1626 throw new IllegalStateException(String.format("Accept exceeded fixed size of %d", 1627 array.length)); 1628 } 1629 } 1630 1631 @Override 1632 public void end() { 1633 if (curSize < array.length) { 1634 throw new IllegalStateException(String.format("End size %d is less than fixed size %d", 1635 curSize, array.length)); 1636 } 1637 } 1638 1639 @Override 1640 public String toString() { 1641 return String.format("DoubleFixedNodeBuilder[%d][%s]", 1642 array.length - curSize, Arrays.toString(array)); 1643 } 1644 } 1645 1646 private static final class IntSpinedNodeBuilder 1647 extends SpinedBuffer.OfInt 1648 implements Node.OfInt, Node.Builder.OfInt { 1649 private boolean building = false; 1650 1651 IntSpinedNodeBuilder() {} // Avoid creation of special accessor 1652 1653 @Override 1654 public Spliterator.OfInt spliterator() { 1655 assert !building : "during building"; 1656 return super.spliterator(); 1657 } 1658 1659 @Override 1660 public void forEach(IntConsumer consumer) { 1661 assert !building : "during building"; 1662 super.forEach(consumer); 1663 } 1664 1665 // 1666 @Override 1667 public void begin(long size) { 1668 assert !building : "was already building"; 1669 building = true; 1670 clear(); 1671 ensureCapacity(size); 1672 } 1673 1674 @Override 1675 public void accept(int i) { 1676 assert building : "not building"; 1677 super.accept(i); 1678 } 1679 1680 @Override 1681 public void end() { 1682 assert building : "was not building"; 1683 building = false; 1684 // @@@ check begin(size) and size 1685 } 1686 1687 @Override 1688 public void copyInto(int[] array, int offset) throws IndexOutOfBoundsException { 1689 assert !building : "during building"; 1690 super.copyInto(array, offset); 1691 } 1692 1693 @Override 1694 public int[] asPrimitiveArray() { 1695 assert !building : "during building"; 1696 return super.asPrimitiveArray(); 1697 } 1698 1699 @Override 1700 public Node.OfInt build() { 1701 assert !building : "during building"; 1702 return this; 1703 } 1704 } 1705 1706 private static final class LongSpinedNodeBuilder 1707 extends SpinedBuffer.OfLong 1708 implements Node.OfLong, Node.Builder.OfLong { 1709 private boolean building = false; 1710 1711 LongSpinedNodeBuilder() {} // Avoid creation of special accessor 1712 1713 @Override 1714 public Spliterator.OfLong spliterator() { 1715 assert !building : "during building"; 1716 return super.spliterator(); 1717 } 1718 1719 @Override 1720 public void forEach(LongConsumer consumer) { 1721 assert !building : "during building"; 1722 super.forEach(consumer); 1723 } 1724 1725 // 1726 @Override 1727 public void begin(long size) { 1728 assert !building : "was already building"; 1729 building = true; 1730 clear(); 1731 ensureCapacity(size); 1732 } 1733 1734 @Override 1735 public void accept(long i) { 1736 assert building : "not building"; 1737 super.accept(i); 1738 } 1739 1740 @Override 1741 public void end() { 1742 assert building : "was not building"; 1743 building = false; 1744 // @@@ check begin(size) and size 1745 } 1746 1747 @Override 1748 public void copyInto(long[] array, int offset) { 1749 assert !building : "during building"; 1750 super.copyInto(array, offset); 1751 } 1752 1753 @Override 1754 public long[] asPrimitiveArray() { 1755 assert !building : "during building"; 1756 return super.asPrimitiveArray(); 1757 } 1758 1759 @Override 1760 public Node.OfLong build() { 1761 assert !building : "during building"; 1762 return this; 1763 } 1764 } 1765 1766 private static final class DoubleSpinedNodeBuilder 1767 extends SpinedBuffer.OfDouble 1768 implements Node.OfDouble, Node.Builder.OfDouble { 1769 private boolean building = false; 1770 1771 DoubleSpinedNodeBuilder() {} // Avoid creation of special accessor 1772 1773 @Override 1774 public Spliterator.OfDouble spliterator() { 1775 assert !building : "during building"; 1776 return super.spliterator(); 1777 } 1778 1779 @Override 1780 public void forEach(DoubleConsumer consumer) { 1781 assert !building : "during building"; 1782 super.forEach(consumer); 1783 } 1784 1785 // 1786 @Override 1787 public void begin(long size) { 1788 assert !building : "was already building"; 1789 building = true; 1790 clear(); 1791 ensureCapacity(size); 1792 } 1793 1794 @Override 1795 public void accept(double i) { 1796 assert building : "not building"; 1797 super.accept(i); 1798 } 1799 1800 @Override 1801 public void end() { 1802 assert building : "was not building"; 1803 building = false; 1804 // @@@ check begin(size) and size 1805 } 1806 1807 @Override 1808 public void copyInto(double[] array, int offset) { 1809 assert !building : "during building"; 1810 super.copyInto(array, offset); 1811 } 1812 1813 @Override 1814 public double[] asPrimitiveArray() { 1815 assert !building : "during building"; 1816 return super.asPrimitiveArray(); 1817 } 1818 1819 @Override 1820 public Node.OfDouble build() { 1821 assert !building : "during building"; 1822 return this; 1823 } 1824 } 1825 1826 /* 1827 * This and subclasses are not intended to be serializable 1828 */ 1829 @SuppressWarnings("serial") 1830 private abstract static class SizedCollectorTask<P_IN, P_OUT, T_SINK extends Sink<P_OUT>, 1831 K extends SizedCollectorTask<P_IN, P_OUT, T_SINK, K>> 1832 extends CountedCompleter<Void> 1833 implements Sink<P_OUT> { 1834 protected final Spliterator<P_IN> spliterator; 1835 protected final PipelineHelper<P_OUT> helper; 1836 protected final long targetSize; 1837 protected long offset; 1838 protected long length; 1839 // For Sink implementation 1840 protected int index, fence; 1841 1842 SizedCollectorTask(Spliterator<P_IN> spliterator, 1843 PipelineHelper<P_OUT> helper, 1844 int arrayLength) { 1845 assert spliterator.hasCharacteristics(Spliterator.SUBSIZED); 1846 this.spliterator = spliterator; 1847 this.helper = helper; 1848 this.targetSize = AbstractTask.suggestTargetSize(spliterator.estimateSize()); 1849 this.offset = 0; 1850 this.length = arrayLength; 1851 } 1852 1853 SizedCollectorTask(K parent, Spliterator<P_IN> spliterator, 1854 long offset, long length, int arrayLength) { 1855 super(parent); 1856 assert spliterator.hasCharacteristics(Spliterator.SUBSIZED); 1857 this.spliterator = spliterator; 1858 this.helper = parent.helper; 1859 this.targetSize = parent.targetSize; 1860 this.offset = offset; 1861 this.length = length; 1862 1863 if (offset < 0 || length < 0 || (offset + length - 1 >= arrayLength)) { 1864 throw new IllegalArgumentException( 1865 String.format("offset and length interval [%d, %d + %d) is not within array size interval [0, %d)", 1866 offset, offset, length, arrayLength)); 1867 } 1868 } 1869 1870 @Override 1871 public void compute() { 1872 SizedCollectorTask<P_IN, P_OUT, T_SINK, K> task = this; 1873 Spliterator<P_IN> rightSplit = spliterator, leftSplit; 1874 while (rightSplit.estimateSize() > task.targetSize && 1875 (leftSplit = rightSplit.trySplit()) != null) { 1876 task.setPendingCount(1); 1877 long leftSplitSize = leftSplit.estimateSize(); 1878 task.makeChild(leftSplit, task.offset, leftSplitSize).fork(); 1879 task = task.makeChild(rightSplit, task.offset + leftSplitSize, 1880 task.length - leftSplitSize); 1881 } 1882 1883 assert task.offset + task.length < MAX_ARRAY_SIZE; 1884 @SuppressWarnings("unchecked") 1885 T_SINK sink = (T_SINK) task; 1886 task.helper.wrapAndCopyInto(sink, rightSplit); 1887 task.propagateCompletion(); 1888 } 1889 1890 abstract K makeChild(Spliterator<P_IN> spliterator, long offset, long size); 1891 1892 @Override 1893 public void begin(long size) { 1894 if (size > length) 1895 throw new IllegalStateException("size passed to Sink.begin exceeds array length"); 1896 // Casts to int are safe since absolute size is verified to be within 1897 // bounds when the root concrete SizedCollectorTask is constructed 1898 // with the shared array 1899 index = (int) offset; 1900 fence = index + (int) length; 1901 } 1902 1903 @SuppressWarnings("serial") 1904 static final class OfRef<P_IN, P_OUT> 1905 extends SizedCollectorTask<P_IN, P_OUT, Sink<P_OUT>, OfRef<P_IN, P_OUT>> 1906 implements Sink<P_OUT> { 1907 private final P_OUT[] array; 1908 1909 OfRef(Spliterator<P_IN> spliterator, PipelineHelper<P_OUT> helper, P_OUT[] array) { 1910 super(spliterator, helper, array.length); 1911 this.array = array; 1912 } 1913 1914 OfRef(OfRef<P_IN, P_OUT> parent, Spliterator<P_IN> spliterator, 1915 long offset, long length) { 1916 super(parent, spliterator, offset, length, parent.array.length); 1917 this.array = parent.array; 1918 } 1919 1920 @Override 1921 OfRef<P_IN, P_OUT> makeChild(Spliterator<P_IN> spliterator, 1922 long offset, long size) { 1923 return new OfRef<>(this, spliterator, offset, size); 1924 } 1925 1926 @Override 1927 public void accept(P_OUT value) { 1928 if (index >= fence) { 1929 throw new IndexOutOfBoundsException(Integer.toString(index)); 1930 } 1931 array[index++] = value; 1932 } 1933 } 1934 1935 @SuppressWarnings("serial") 1936 static final class OfInt<P_IN> 1937 extends SizedCollectorTask<P_IN, Integer, Sink.OfInt, OfInt<P_IN>> 1938 implements Sink.OfInt { 1939 private final int[] array; 1940 1941 OfInt(Spliterator<P_IN> spliterator, PipelineHelper<Integer> helper, int[] array) { 1942 super(spliterator, helper, array.length); 1943 this.array = array; 1944 } 1945 1946 OfInt(SizedCollectorTask.OfInt<P_IN> parent, Spliterator<P_IN> spliterator, 1947 long offset, long length) { 1948 super(parent, spliterator, offset, length, parent.array.length); 1949 this.array = parent.array; 1950 } 1951 1952 @Override 1953 SizedCollectorTask.OfInt<P_IN> makeChild(Spliterator<P_IN> spliterator, 1954 long offset, long size) { 1955 return new SizedCollectorTask.OfInt<>(this, spliterator, offset, size); 1956 } 1957 1958 @Override 1959 public void accept(int value) { 1960 if (index >= fence) { 1961 throw new IndexOutOfBoundsException(Integer.toString(index)); 1962 } 1963 array[index++] = value; 1964 } 1965 } 1966 1967 @SuppressWarnings("serial") 1968 static final class OfLong<P_IN> 1969 extends SizedCollectorTask<P_IN, Long, Sink.OfLong, OfLong<P_IN>> 1970 implements Sink.OfLong { 1971 private final long[] array; 1972 1973 OfLong(Spliterator<P_IN> spliterator, PipelineHelper<Long> helper, long[] array) { 1974 super(spliterator, helper, array.length); 1975 this.array = array; 1976 } 1977 1978 OfLong(SizedCollectorTask.OfLong<P_IN> parent, Spliterator<P_IN> spliterator, 1979 long offset, long length) { 1980 super(parent, spliterator, offset, length, parent.array.length); 1981 this.array = parent.array; 1982 } 1983 1984 @Override 1985 SizedCollectorTask.OfLong<P_IN> makeChild(Spliterator<P_IN> spliterator, 1986 long offset, long size) { 1987 return new SizedCollectorTask.OfLong<>(this, spliterator, offset, size); 1988 } 1989 1990 @Override 1991 public void accept(long value) { 1992 if (index >= fence) { 1993 throw new IndexOutOfBoundsException(Integer.toString(index)); 1994 } 1995 array[index++] = value; 1996 } 1997 } 1998 1999 @SuppressWarnings("serial") 2000 static final class OfDouble<P_IN> 2001 extends SizedCollectorTask<P_IN, Double, Sink.OfDouble, OfDouble<P_IN>> 2002 implements Sink.OfDouble { 2003 private final double[] array; 2004 2005 OfDouble(Spliterator<P_IN> spliterator, PipelineHelper<Double> helper, double[] array) { 2006 super(spliterator, helper, array.length); 2007 this.array = array; 2008 } 2009 2010 OfDouble(SizedCollectorTask.OfDouble<P_IN> parent, Spliterator<P_IN> spliterator, 2011 long offset, long length) { 2012 super(parent, spliterator, offset, length, parent.array.length); 2013 this.array = parent.array; 2014 } 2015 2016 @Override 2017 SizedCollectorTask.OfDouble<P_IN> makeChild(Spliterator<P_IN> spliterator, 2018 long offset, long size) { 2019 return new SizedCollectorTask.OfDouble<>(this, spliterator, offset, size); 2020 } 2021 2022 @Override 2023 public void accept(double value) { 2024 if (index >= fence) { 2025 throw new IndexOutOfBoundsException(Integer.toString(index)); 2026 } 2027 array[index++] = value; 2028 } 2029 } 2030 } 2031 2032 @SuppressWarnings("serial") 2033 private abstract static class ToArrayTask<T, T_NODE extends Node<T>, 2034 K extends ToArrayTask<T, T_NODE, K>> 2035 extends CountedCompleter<Void> { 2036 protected final T_NODE node; 2037 protected final int offset; 2038 2039 ToArrayTask(T_NODE node, int offset) { 2040 this.node = node; 2041 this.offset = offset; 2042 } 2043 2044 ToArrayTask(K parent, T_NODE node, int offset) { 2045 super(parent); 2046 this.node = node; 2047 this.offset = offset; 2048 } 2049 2050 abstract void copyNodeToArray(); 2051 2052 abstract K makeChild(int childIndex, int offset); 2053 2054 @Override 2055 public void compute() { 2056 ToArrayTask<T, T_NODE, K> task = this; 2057 while (true) { 2058 if (task.node.getChildCount() == 0) { 2059 task.copyNodeToArray(); 2060 task.propagateCompletion(); 2061 return; 2062 } 2063 else { 2064 task.setPendingCount(task.node.getChildCount() - 1); 2065 2066 int size = 0; 2067 int i = 0; 2068 for (;i < task.node.getChildCount() - 1; i++) { 2069 K leftTask = task.makeChild(i, task.offset + size); 2070 size += leftTask.node.count(); 2071 leftTask.fork(); 2072 } 2073 task = task.makeChild(i, task.offset + size); 2074 } 2075 } 2076 } 2077 2078 @SuppressWarnings("serial") 2079 private static final class OfRef<T> 2080 extends ToArrayTask<T, Node<T>, OfRef<T>> { 2081 private final T[] array; 2082 2083 private OfRef(Node<T> node, T[] array, int offset) { 2084 super(node, offset); 2085 this.array = array; 2086 } 2087 2088 private OfRef(OfRef<T> parent, Node<T> node, int offset) { 2089 super(parent, node, offset); 2090 this.array = parent.array; 2091 } 2092 2093 @Override 2094 OfRef<T> makeChild(int childIndex, int offset) { 2095 return new OfRef<>(this, node.getChild(childIndex), offset); 2096 } 2097 2098 @Override 2099 void copyNodeToArray() { 2100 node.copyInto(array, offset); 2101 } 2102 } 2103 2104 @SuppressWarnings("serial") 2105 private static class OfPrimitive<T, T_CONS, T_ARR, 2106 T_SPLITR extends Spliterator.OfPrimitive<T, T_CONS, T_SPLITR>, 2107 T_NODE extends Node.OfPrimitive<T, T_CONS, T_ARR, T_SPLITR, T_NODE>> 2108 extends ToArrayTask<T, T_NODE, OfPrimitive<T, T_CONS, T_ARR, T_SPLITR, T_NODE>> { 2109 private final T_ARR array; 2110 2111 private OfPrimitive(T_NODE node, T_ARR array, int offset) { 2112 super(node, offset); 2113 this.array = array; 2114 } 2115 2116 private OfPrimitive(OfPrimitive<T, T_CONS, T_ARR, T_SPLITR, T_NODE> parent, T_NODE node, int offset) { 2117 super(parent, node, offset); 2118 this.array = parent.array; 2119 } 2120 2121 @Override 2122 OfPrimitive<T, T_CONS, T_ARR, T_SPLITR, T_NODE> makeChild(int childIndex, int offset) { 2123 return new OfPrimitive<>(this, node.getChild(childIndex), offset); 2124 } 2125 2126 @Override 2127 void copyNodeToArray() { 2128 node.copyInto(array, offset); 2129 } 2130 } 2131 2132 @SuppressWarnings("serial") 2133 private static final class OfInt 2134 extends OfPrimitive<Integer, IntConsumer, int[], Spliterator.OfInt, Node.OfInt> { 2135 private OfInt(Node.OfInt node, int[] array, int offset) { 2136 super(node, array, offset); 2137 } 2138 } 2139 2140 @SuppressWarnings("serial") 2141 private static final class OfLong 2142 extends OfPrimitive<Long, LongConsumer, long[], Spliterator.OfLong, Node.OfLong> { 2143 private OfLong(Node.OfLong node, long[] array, int offset) { 2144 super(node, array, offset); 2145 } 2146 } 2147 2148 @SuppressWarnings("serial") 2149 private static final class OfDouble 2150 extends OfPrimitive<Double, DoubleConsumer, double[], Spliterator.OfDouble, Node.OfDouble> { 2151 private OfDouble(Node.OfDouble node, double[] array, int offset) { 2152 super(node, array, offset); 2153 } 2154 } 2155 } 2156 2157 @SuppressWarnings("serial") 2158 private static class CollectorTask<P_IN, P_OUT, T_NODE extends Node<P_OUT>, T_BUILDER extends Node.Builder<P_OUT>> 2159 extends AbstractTask<P_IN, P_OUT, T_NODE, CollectorTask<P_IN, P_OUT, T_NODE, T_BUILDER>> { 2160 protected final PipelineHelper<P_OUT> helper; 2161 protected final LongFunction<T_BUILDER> builderFactory; 2162 protected final BinaryOperator<T_NODE> concFactory; 2163 2164 CollectorTask(PipelineHelper<P_OUT> helper, 2165 Spliterator<P_IN> spliterator, 2166 LongFunction<T_BUILDER> builderFactory, 2167 BinaryOperator<T_NODE> concFactory) { 2168 super(helper, spliterator); 2169 this.helper = helper; 2170 this.builderFactory = builderFactory; 2171 this.concFactory = concFactory; 2172 } 2173 2174 CollectorTask(CollectorTask<P_IN, P_OUT, T_NODE, T_BUILDER> parent, 2175 Spliterator<P_IN> spliterator) { 2176 super(parent, spliterator); 2177 helper = parent.helper; 2178 builderFactory = parent.builderFactory; 2179 concFactory = parent.concFactory; 2180 } 2181 2182 @Override 2183 protected CollectorTask<P_IN, P_OUT, T_NODE, T_BUILDER> makeChild(Spliterator<P_IN> spliterator) { 2184 return new CollectorTask<>(this, spliterator); 2185 } 2186 2187 @Override 2188 @SuppressWarnings("unchecked") 2189 protected T_NODE doLeaf() { 2190 T_BUILDER builder = builderFactory.apply(helper.exactOutputSizeIfKnown(spliterator)); 2191 return (T_NODE) helper.wrapAndCopyInto(builder, spliterator).build(); 2192 } 2193 2194 @Override 2195 public void onCompletion(CountedCompleter<?> caller) { 2196 if (!isLeaf()) 2197 setLocalResult(concFactory.apply(leftChild.getLocalResult(), rightChild.getLocalResult())); 2198 super.onCompletion(caller); 2199 } 2200 2201 @SuppressWarnings("serial") 2202 private static final class OfRef<P_IN, P_OUT> 2203 extends CollectorTask<P_IN, P_OUT, Node<P_OUT>, Node.Builder<P_OUT>> { 2204 OfRef(PipelineHelper<P_OUT> helper, 2205 IntFunction<P_OUT[]> generator, 2206 Spliterator<P_IN> spliterator) { 2207 super(helper, spliterator, s -> builder(s, generator), ConcNode::new); 2208 } 2209 } 2210 2211 @SuppressWarnings("serial") 2212 private static final class OfInt<P_IN> 2213 extends CollectorTask<P_IN, Integer, Node.OfInt, Node.Builder.OfInt> { 2214 OfInt(PipelineHelper<Integer> helper, Spliterator<P_IN> spliterator) { 2215 super(helper, spliterator, Nodes::intBuilder, ConcNode.OfInt::new); 2216 } 2217 } 2218 2219 @SuppressWarnings("serial") 2220 private static final class OfLong<P_IN> 2221 extends CollectorTask<P_IN, Long, Node.OfLong, Node.Builder.OfLong> { 2222 OfLong(PipelineHelper<Long> helper, Spliterator<P_IN> spliterator) { 2223 super(helper, spliterator, Nodes::longBuilder, ConcNode.OfLong::new); 2224 } 2225 } 2226 2227 @SuppressWarnings("serial") 2228 private static final class OfDouble<P_IN> 2229 extends CollectorTask<P_IN, Double, Node.OfDouble, Node.Builder.OfDouble> { 2230 OfDouble(PipelineHelper<Double> helper, Spliterator<P_IN> spliterator) { 2231 super(helper, spliterator, Nodes::doubleBuilder, ConcNode.OfDouble::new); 2232 } 2233 } 2234 } 2235 } 2236