1 /*
   2  * Copyright (c) 2012, 2017, 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.Comparator;
  28 import java.util.Objects;
  29 import java.util.Spliterator;
  30 import java.util.concurrent.ConcurrentHashMap;
  31 import java.util.concurrent.atomic.AtomicLong;
  32 import java.util.function.BooleanSupplier;
  33 import java.util.function.Consumer;
  34 import java.util.function.DoubleConsumer;
  35 import java.util.function.DoubleSupplier;
  36 import java.util.function.IntConsumer;
  37 import java.util.function.IntSupplier;
  38 import java.util.function.LongConsumer;
  39 import java.util.function.LongSupplier;
  40 import java.util.function.Supplier;
  41 
  42 /**
  43  * Spliterator implementations for wrapping and delegating spliterators, used
  44  * in the implementation of the {@link Stream#spliterator()} method.
  45  *
  46  * @since 1.8
  47  */
  48 class StreamSpliterators {
  49 
  50     /**
  51      * Abstract wrapping spliterator that binds to the spliterator of a
  52      * pipeline helper on first operation.
  53      *
  54      * <p>This spliterator is not late-binding and will bind to the source
  55      * spliterator when first operated on.
  56      *
  57      * <p>A wrapping spliterator produced from a sequential stream
  58      * cannot be split if there are stateful operations present.
  59      */
  60     private abstract static class AbstractWrappingSpliterator<P_IN, P_OUT,
  61                                                               T_BUFFER extends AbstractSpinedBuffer>
  62             implements Spliterator<P_OUT> {
  63 
  64         // @@@ Detect if stateful operations are present or not
  65         //     If not then can split otherwise cannot
  66 
  67         /**
  68          * True if this spliterator supports splitting
  69          */
  70         final boolean isParallel;
  71 
  72         final PipelineHelper<P_OUT> ph;
  73 
  74         /**
  75          * Supplier for the source spliterator.  Client provides either a
  76          * spliterator or a supplier.
  77          */
  78         private Supplier<Spliterator<P_IN>> spliteratorSupplier;
  79 
  80         /**
  81          * Source spliterator.  Either provided from client or obtained from
  82          * supplier.
  83          */
  84         Spliterator<P_IN> spliterator;
  85 
  86         /**
  87          * Sink chain for the downstream stages of the pipeline, ultimately
  88          * leading to the buffer. Used during partial traversal.
  89          */
  90         Sink<P_IN> bufferSink;
  91 
  92         /**
  93          * A function that advances one element of the spliterator, pushing
  94          * it to bufferSink.  Returns whether any elements were processed.
  95          * Used during partial traversal.
  96          */
  97         BooleanSupplier pusher;
  98 
  99         /** Next element to consume from the buffer, used during partial traversal */
 100         long nextToConsume;
 101 
 102         /** Buffer into which elements are pushed.  Used during partial traversal. */
 103         T_BUFFER buffer;
 104 
 105         /**
 106          * True if full traversal has occurred (with possible cancellation).
 107          * If doing a partial traversal, there may be still elements in buffer.
 108          */
 109         boolean finished;
 110 
 111         /**
 112          * Construct an AbstractWrappingSpliterator from a
 113          * {@code Supplier<Spliterator>}.
 114          */
 115         AbstractWrappingSpliterator(PipelineHelper<P_OUT> ph,
 116                                     Supplier<Spliterator<P_IN>> spliteratorSupplier,
 117                                     boolean parallel) {
 118             this.ph = ph;
 119             this.spliteratorSupplier = spliteratorSupplier;
 120             this.spliterator = null;
 121             this.isParallel = parallel;
 122         }
 123 
 124         /**
 125          * Construct an AbstractWrappingSpliterator from a
 126          * {@code Spliterator}.
 127          */
 128         AbstractWrappingSpliterator(PipelineHelper<P_OUT> ph,
 129                                     Spliterator<P_IN> spliterator,
 130                                     boolean parallel) {
 131             this.ph = ph;
 132             this.spliteratorSupplier = null;
 133             this.spliterator = spliterator;
 134             this.isParallel = parallel;
 135         }
 136 
 137         /**
 138          * Called before advancing to set up spliterator, if needed.
 139          */
 140         final void init() {
 141             if (spliterator == null) {
 142                 spliterator = spliteratorSupplier.get();
 143                 spliteratorSupplier = null;
 144             }
 145         }
 146 
 147         /**
 148          * Get an element from the source, pushing it into the sink chain,
 149          * setting up the buffer if needed
 150          * @return whether there are elements to consume from the buffer
 151          */
 152         final boolean doAdvance() {
 153             if (buffer == null) {
 154                 if (finished)
 155                     return false;
 156 
 157                 init();
 158                 initPartialTraversalState();
 159                 nextToConsume = 0;
 160                 bufferSink.begin(spliterator.getExactSizeIfKnown());
 161                 return fillBuffer();
 162             }
 163             else {
 164                 ++nextToConsume;
 165                 boolean hasNext = nextToConsume < buffer.count();
 166                 if (!hasNext) {
 167                     nextToConsume = 0;
 168                     buffer.clear();
 169                     hasNext = fillBuffer();
 170                 }
 171                 return hasNext;
 172             }
 173         }
 174 
 175         /**
 176          * Invokes the shape-specific constructor with the provided arguments
 177          * and returns the result.
 178          */
 179         abstract AbstractWrappingSpliterator<P_IN, P_OUT, ?> wrap(Spliterator<P_IN> s);
 180 
 181         /**
 182          * Initializes buffer, sink chain, and pusher for a shape-specific
 183          * implementation.
 184          */
 185         abstract void initPartialTraversalState();
 186 
 187         @Override
 188         public Spliterator<P_OUT> trySplit() {
 189             if (isParallel && buffer == null && !finished) {
 190                 init();
 191 
 192                 Spliterator<P_IN> split = spliterator.trySplit();
 193                 return (split == null) ? null : wrap(split);
 194             }
 195             else
 196                 return null;
 197         }
 198 
 199         /**
 200          * If the buffer is empty, push elements into the sink chain until
 201          * the source is empty or cancellation is requested.
 202          * @return whether there are elements to consume from the buffer
 203          */
 204         private boolean fillBuffer() {
 205             while (buffer.count() == 0) {
 206                 if (bufferSink.cancellationRequested() || !pusher.getAsBoolean()) {
 207                     if (finished)
 208                         return false;
 209                     else {
 210                         bufferSink.end(); // might trigger more elements
 211                         finished = true;
 212                     }
 213                 }
 214             }
 215             return true;
 216         }
 217 
 218         @Override
 219         public final long estimateSize() {
 220             init();
 221             // Use the estimate of the wrapped spliterator
 222             // Note this may not be accurate if there are filter/flatMap
 223             // operations filtering or adding elements to the stream
 224             return spliterator.estimateSize();
 225         }
 226 
 227         @Override
 228         public final long getExactSizeIfKnown() {
 229             init();
 230             return StreamOpFlag.SIZED.isKnown(ph.getStreamAndOpFlags())
 231                    ? spliterator.getExactSizeIfKnown()
 232                    : -1;
 233         }
 234 
 235         @Override
 236         public final int characteristics() {
 237             init();
 238 
 239             // Get the characteristics from the pipeline
 240             int c = StreamOpFlag.toCharacteristics(StreamOpFlag.toStreamFlags(ph.getStreamAndOpFlags()));
 241 
 242             // Mask off the size and uniform characteristics and replace with
 243             // those of the spliterator
 244             // Note that a non-uniform spliterator can change from something
 245             // with an exact size to an estimate for a sub-split, for example
 246             // with HashSet where the size is known at the top level spliterator
 247             // but for sub-splits only an estimate is known
 248             if ((c & Spliterator.SIZED) != 0) {
 249                 c &= ~(Spliterator.SIZED | Spliterator.SUBSIZED);
 250                 c |= (spliterator.characteristics() & (Spliterator.SIZED | Spliterator.SUBSIZED));
 251             }
 252 
 253             return c;
 254         }
 255 
 256         @Override
 257         public Comparator<? super P_OUT> getComparator() {
 258             if (!hasCharacteristics(SORTED))
 259                 throw new IllegalStateException();
 260             return null;
 261         }
 262 
 263         @Override
 264         public final String toString() {
 265             return String.format("%s[%s]", getClass().getName(), spliterator);
 266         }
 267     }
 268 
 269     static final class WrappingSpliterator<P_IN, P_OUT>
 270             extends AbstractWrappingSpliterator<P_IN, P_OUT, SpinedBuffer<P_OUT>> {
 271 
 272         WrappingSpliterator(PipelineHelper<P_OUT> ph,
 273                             Supplier<Spliterator<P_IN>> supplier,
 274                             boolean parallel) {
 275             super(ph, supplier, parallel);
 276         }
 277 
 278         WrappingSpliterator(PipelineHelper<P_OUT> ph,
 279                             Spliterator<P_IN> spliterator,
 280                             boolean parallel) {
 281             super(ph, spliterator, parallel);
 282         }
 283 
 284         @Override
 285         WrappingSpliterator<P_IN, P_OUT> wrap(Spliterator<P_IN> s) {
 286             return new WrappingSpliterator<>(ph, s, isParallel);
 287         }
 288 
 289         @Override
 290         void initPartialTraversalState() {
 291             SpinedBuffer<P_OUT> b = new SpinedBuffer<>();
 292             buffer = b;
 293             bufferSink = ph.wrapSink(b::accept);
 294             pusher = () -> spliterator.tryAdvance(bufferSink);
 295         }
 296 
 297         @Override
 298         public boolean tryAdvance(Consumer<? super P_OUT> consumer) {
 299             Objects.requireNonNull(consumer);
 300             boolean hasNext = doAdvance();
 301             if (hasNext)
 302                 consumer.accept(buffer.get(nextToConsume));
 303             return hasNext;
 304         }
 305 
 306         @Override
 307         public void forEachRemaining(Consumer<? super P_OUT> consumer) {
 308             if (buffer == null && !finished) {
 309                 Objects.requireNonNull(consumer);
 310                 init();
 311 
 312                 ph.wrapAndCopyInto((Sink<P_OUT>) consumer::accept, spliterator);
 313                 finished = true;
 314             }
 315             else {
 316                 do { } while (tryAdvance(consumer));
 317             }
 318         }
 319     }
 320 
 321     static final class IntWrappingSpliterator<P_IN>
 322             extends AbstractWrappingSpliterator<P_IN, Integer, SpinedBuffer.OfInt>
 323             implements Spliterator.OfInt {
 324 
 325         IntWrappingSpliterator(PipelineHelper<Integer> ph,
 326                                Supplier<Spliterator<P_IN>> supplier,
 327                                boolean parallel) {
 328             super(ph, supplier, parallel);
 329         }
 330 
 331         IntWrappingSpliterator(PipelineHelper<Integer> ph,
 332                                Spliterator<P_IN> spliterator,
 333                                boolean parallel) {
 334             super(ph, spliterator, parallel);
 335         }
 336 
 337         @Override
 338         AbstractWrappingSpliterator<P_IN, Integer, ?> wrap(Spliterator<P_IN> s) {
 339             return new IntWrappingSpliterator<>(ph, s, isParallel);
 340         }
 341 
 342         @Override
 343         void initPartialTraversalState() {
 344             SpinedBuffer.OfInt b = new SpinedBuffer.OfInt();
 345             buffer = b;
 346             bufferSink = ph.wrapSink((Sink.OfInt) b::accept);
 347             pusher = () -> spliterator.tryAdvance(bufferSink);
 348         }
 349 
 350         @Override
 351         public Spliterator.OfInt trySplit() {
 352             return (Spliterator.OfInt) super.trySplit();
 353         }
 354 
 355         @Override
 356         public boolean tryAdvance(IntConsumer consumer) {
 357             Objects.requireNonNull(consumer);
 358             boolean hasNext = doAdvance();
 359             if (hasNext)
 360                 consumer.accept(buffer.get(nextToConsume));
 361             return hasNext;
 362         }
 363 
 364         @Override
 365         public void forEachRemaining(IntConsumer consumer) {
 366             if (buffer == null && !finished) {
 367                 Objects.requireNonNull(consumer);
 368                 init();
 369 
 370                 ph.wrapAndCopyInto((Sink.OfInt) consumer::accept, spliterator);
 371                 finished = true;
 372             }
 373             else {
 374                 do { } while (tryAdvance(consumer));
 375             }
 376         }
 377     }
 378 
 379     static final class LongWrappingSpliterator<P_IN>
 380             extends AbstractWrappingSpliterator<P_IN, Long, SpinedBuffer.OfLong>
 381             implements Spliterator.OfLong {
 382 
 383         LongWrappingSpliterator(PipelineHelper<Long> ph,
 384                                 Supplier<Spliterator<P_IN>> supplier,
 385                                 boolean parallel) {
 386             super(ph, supplier, parallel);
 387         }
 388 
 389         LongWrappingSpliterator(PipelineHelper<Long> ph,
 390                                 Spliterator<P_IN> spliterator,
 391                                 boolean parallel) {
 392             super(ph, spliterator, parallel);
 393         }
 394 
 395         @Override
 396         AbstractWrappingSpliterator<P_IN, Long, ?> wrap(Spliterator<P_IN> s) {
 397             return new LongWrappingSpliterator<>(ph, s, isParallel);
 398         }
 399 
 400         @Override
 401         void initPartialTraversalState() {
 402             SpinedBuffer.OfLong b = new SpinedBuffer.OfLong();
 403             buffer = b;
 404             bufferSink = ph.wrapSink((Sink.OfLong) b::accept);
 405             pusher = () -> spliterator.tryAdvance(bufferSink);
 406         }
 407 
 408         @Override
 409         public Spliterator.OfLong trySplit() {
 410             return (Spliterator.OfLong) super.trySplit();
 411         }
 412 
 413         @Override
 414         public boolean tryAdvance(LongConsumer consumer) {
 415             Objects.requireNonNull(consumer);
 416             boolean hasNext = doAdvance();
 417             if (hasNext)
 418                 consumer.accept(buffer.get(nextToConsume));
 419             return hasNext;
 420         }
 421 
 422         @Override
 423         public void forEachRemaining(LongConsumer consumer) {
 424             if (buffer == null && !finished) {
 425                 Objects.requireNonNull(consumer);
 426                 init();
 427 
 428                 ph.wrapAndCopyInto((Sink.OfLong) consumer::accept, spliterator);
 429                 finished = true;
 430             }
 431             else {
 432                 do { } while (tryAdvance(consumer));
 433             }
 434         }
 435     }
 436 
 437     static final class DoubleWrappingSpliterator<P_IN>
 438             extends AbstractWrappingSpliterator<P_IN, Double, SpinedBuffer.OfDouble>
 439             implements Spliterator.OfDouble {
 440 
 441         DoubleWrappingSpliterator(PipelineHelper<Double> ph,
 442                                   Supplier<Spliterator<P_IN>> supplier,
 443                                   boolean parallel) {
 444             super(ph, supplier, parallel);
 445         }
 446 
 447         DoubleWrappingSpliterator(PipelineHelper<Double> ph,
 448                                   Spliterator<P_IN> spliterator,
 449                                   boolean parallel) {
 450             super(ph, spliterator, parallel);
 451         }
 452 
 453         @Override
 454         AbstractWrappingSpliterator<P_IN, Double, ?> wrap(Spliterator<P_IN> s) {
 455             return new DoubleWrappingSpliterator<>(ph, s, isParallel);
 456         }
 457 
 458         @Override
 459         void initPartialTraversalState() {
 460             SpinedBuffer.OfDouble b = new SpinedBuffer.OfDouble();
 461             buffer = b;
 462             bufferSink = ph.wrapSink((Sink.OfDouble) b::accept);
 463             pusher = () -> spliterator.tryAdvance(bufferSink);
 464         }
 465 
 466         @Override
 467         public Spliterator.OfDouble trySplit() {
 468             return (Spliterator.OfDouble) super.trySplit();
 469         }
 470 
 471         @Override
 472         public boolean tryAdvance(DoubleConsumer consumer) {
 473             Objects.requireNonNull(consumer);
 474             boolean hasNext = doAdvance();
 475             if (hasNext)
 476                 consumer.accept(buffer.get(nextToConsume));
 477             return hasNext;
 478         }
 479 
 480         @Override
 481         public void forEachRemaining(DoubleConsumer consumer) {
 482             if (buffer == null && !finished) {
 483                 Objects.requireNonNull(consumer);
 484                 init();
 485 
 486                 ph.wrapAndCopyInto((Sink.OfDouble) consumer::accept, spliterator);
 487                 finished = true;
 488             }
 489             else {
 490                 do { } while (tryAdvance(consumer));
 491             }
 492         }
 493     }
 494 
 495     /**
 496      * Spliterator implementation that delegates to an underlying spliterator,
 497      * acquiring the spliterator from a {@code Supplier<Spliterator>} on the
 498      * first call to any spliterator method.
 499      * @param <T>
 500      */
 501     static class DelegatingSpliterator<T, T_SPLITR extends Spliterator<T>>
 502             implements Spliterator<T> {
 503         private final Supplier<? extends T_SPLITR> supplier;
 504 
 505         private T_SPLITR s;
 506 
 507         DelegatingSpliterator(Supplier<? extends T_SPLITR> supplier) {
 508             this.supplier = supplier;
 509         }
 510 
 511         T_SPLITR get() {
 512             if (s == null) {
 513                 s = supplier.get();
 514             }
 515             return s;
 516         }
 517 
 518         @Override
 519         @SuppressWarnings("unchecked")
 520         public T_SPLITR trySplit() {
 521             return (T_SPLITR) get().trySplit();
 522         }
 523 
 524         @Override
 525         public boolean tryAdvance(Consumer<? super T> consumer) {
 526             return get().tryAdvance(consumer);
 527         }
 528 
 529         @Override
 530         public void forEachRemaining(Consumer<? super T> consumer) {
 531             get().forEachRemaining(consumer);
 532         }
 533 
 534         @Override
 535         public long estimateSize() {
 536             return get().estimateSize();
 537         }
 538 
 539         @Override
 540         public int characteristics() {
 541             return get().characteristics();
 542         }
 543 
 544         @Override
 545         public Comparator<? super T> getComparator() {
 546             return get().getComparator();
 547         }
 548 
 549         @Override
 550         public long getExactSizeIfKnown() {
 551             return get().getExactSizeIfKnown();
 552         }
 553 
 554         @Override
 555         public String toString() {
 556             return getClass().getName() + "[" + get() + "]";
 557         }
 558 
 559         static class OfPrimitive<T, T_CONS, T_SPLITR extends Spliterator.OfPrimitive<T, T_CONS, T_SPLITR>>
 560             extends DelegatingSpliterator<T, T_SPLITR>
 561             implements Spliterator.OfPrimitive<T, T_CONS, T_SPLITR> {
 562             OfPrimitive(Supplier<? extends T_SPLITR> supplier) {
 563                 super(supplier);
 564             }
 565 
 566             @Override
 567             public boolean tryAdvance(T_CONS consumer) {
 568                 return get().tryAdvance(consumer);
 569             }
 570 
 571             @Override
 572             public void forEachRemaining(T_CONS consumer) {
 573                 get().forEachRemaining(consumer);
 574             }
 575         }
 576 
 577         static final class OfInt
 578                 extends OfPrimitive<Integer, IntConsumer, Spliterator.OfInt>
 579                 implements Spliterator.OfInt {
 580 
 581             OfInt(Supplier<Spliterator.OfInt> supplier) {
 582                 super(supplier);
 583             }
 584         }
 585 
 586         static final class OfLong
 587                 extends OfPrimitive<Long, LongConsumer, Spliterator.OfLong>
 588                 implements Spliterator.OfLong {
 589 
 590             OfLong(Supplier<Spliterator.OfLong> supplier) {
 591                 super(supplier);
 592             }
 593         }
 594 
 595         static final class OfDouble
 596                 extends OfPrimitive<Double, DoubleConsumer, Spliterator.OfDouble>
 597                 implements Spliterator.OfDouble {
 598 
 599             OfDouble(Supplier<Spliterator.OfDouble> supplier) {
 600                 super(supplier);
 601             }
 602         }
 603     }
 604 
 605     /**
 606      * A slice Spliterator from a source Spliterator that reports
 607      * {@code SUBSIZED}.
 608      *
 609      */
 610     abstract static class SliceSpliterator<T, T_SPLITR extends Spliterator<T>> {
 611         // The start index of the slice
 612         final long sliceOrigin;
 613         // One past the last index of the slice
 614         final long sliceFence;
 615 
 616         // The spliterator to slice
 617         T_SPLITR s;
 618         // current (absolute) index, modified on advance/split
 619         long index;
 620         // one past last (absolute) index or sliceFence, which ever is smaller
 621         long fence;
 622 
 623         SliceSpliterator(T_SPLITR s, long sliceOrigin, long sliceFence, long origin, long fence) {
 624             assert s.hasCharacteristics(Spliterator.SUBSIZED);
 625             this.s = s;
 626             this.sliceOrigin = sliceOrigin;
 627             this.sliceFence = sliceFence;
 628             this.index = origin;
 629             this.fence = fence;
 630         }
 631 
 632         protected abstract T_SPLITR makeSpliterator(T_SPLITR s, long sliceOrigin, long sliceFence, long origin, long fence);
 633 
 634         public T_SPLITR trySplit() {
 635             if (sliceOrigin >= fence)
 636                 return null;
 637 
 638             if (index >= fence)
 639                 return null;
 640 
 641             // Keep splitting until the left and right splits intersect with the slice
 642             // thereby ensuring the size estimate decreases.
 643             // This also avoids creating empty spliterators which can result in
 644             // existing and additionally created F/J tasks that perform
 645             // redundant work on no elements.
 646             while (true) {
 647                 @SuppressWarnings("unchecked")
 648                 T_SPLITR leftSplit = (T_SPLITR) s.trySplit();
 649                 if (leftSplit == null)
 650                     return null;
 651 
 652                 long leftSplitFenceUnbounded = index + leftSplit.estimateSize();
 653                 long leftSplitFence = Math.min(leftSplitFenceUnbounded, sliceFence);
 654                 if (sliceOrigin >= leftSplitFence) {
 655                     // The left split does not intersect with, and is to the left of, the slice
 656                     // The right split does intersect
 657                     // Discard the left split and split further with the right split
 658                     index = leftSplitFence;
 659                 }
 660                 else if (leftSplitFence >= sliceFence) {
 661                     // The right split does not intersect with, and is to the right of, the slice
 662                     // The left split does intersect
 663                     // Discard the right split and split further with the left split
 664                     s = leftSplit;
 665                     fence = leftSplitFence;
 666                 }
 667                 else if (index >= sliceOrigin && leftSplitFenceUnbounded <= sliceFence) {
 668                     // The left split is contained within the slice, return the underlying left split
 669                     // Right split is contained within or intersects with the slice
 670                     index = leftSplitFence;
 671                     return leftSplit;
 672                 } else {
 673                     // The left split intersects with the slice
 674                     // Right split is contained within or intersects with the slice
 675                     return makeSpliterator(leftSplit, sliceOrigin, sliceFence, index, index = leftSplitFence);
 676                 }
 677             }
 678         }
 679 
 680         public long estimateSize() {
 681             return (sliceOrigin < fence)
 682                    ? fence - Math.max(sliceOrigin, index) : 0;
 683         }
 684 
 685         public int characteristics() {
 686             return s.characteristics();
 687         }
 688 
 689         static final class OfRef<T>
 690                 extends SliceSpliterator<T, Spliterator<T>>
 691                 implements Spliterator<T> {
 692 
 693             OfRef(Spliterator<T> s, long sliceOrigin, long sliceFence) {
 694                 this(s, sliceOrigin, sliceFence, 0, Math.min(s.estimateSize(), sliceFence));
 695             }
 696 
 697             private OfRef(Spliterator<T> s,
 698                           long sliceOrigin, long sliceFence, long origin, long fence) {
 699                 super(s, sliceOrigin, sliceFence, origin, fence);
 700             }
 701 
 702             @Override
 703             protected Spliterator<T> makeSpliterator(Spliterator<T> s,
 704                                                      long sliceOrigin, long sliceFence,
 705                                                      long origin, long fence) {
 706                 return new OfRef<>(s, sliceOrigin, sliceFence, origin, fence);
 707             }
 708 
 709             @Override
 710             public boolean tryAdvance(Consumer<? super T> action) {
 711                 Objects.requireNonNull(action);
 712 
 713                 if (sliceOrigin >= fence)
 714                     return false;
 715 
 716                 while (sliceOrigin > index) {
 717                     s.tryAdvance(e -> {});
 718                     index++;
 719                 }
 720 
 721                 if (index >= fence)
 722                     return false;
 723 
 724                 index++;
 725                 return s.tryAdvance(action);
 726             }
 727 
 728             @Override
 729             public void forEachRemaining(Consumer<? super T> action) {
 730                 Objects.requireNonNull(action);
 731 
 732                 if (sliceOrigin >= fence)
 733                     return;
 734 
 735                 if (index >= fence)
 736                     return;
 737 
 738                 if (index >= sliceOrigin && (index + s.estimateSize()) <= sliceFence) {
 739                     // The spliterator is contained within the slice
 740                     s.forEachRemaining(action);
 741                     index = fence;
 742                 } else {
 743                     // The spliterator intersects with the slice
 744                     while (sliceOrigin > index) {
 745                         s.tryAdvance(e -> {});
 746                         index++;
 747                     }
 748                     // Traverse elements up to the fence
 749                     for (;index < fence; index++) {
 750                         s.tryAdvance(action);
 751                     }
 752                 }
 753             }
 754         }
 755 
 756         abstract static class OfPrimitive<T,
 757                 T_SPLITR extends Spliterator.OfPrimitive<T, T_CONS, T_SPLITR>,
 758                 T_CONS>
 759                 extends SliceSpliterator<T, T_SPLITR>
 760                 implements Spliterator.OfPrimitive<T, T_CONS, T_SPLITR> {
 761 
 762             OfPrimitive(T_SPLITR s, long sliceOrigin, long sliceFence) {
 763                 this(s, sliceOrigin, sliceFence, 0, Math.min(s.estimateSize(), sliceFence));
 764             }
 765 
 766             private OfPrimitive(T_SPLITR s,
 767                                 long sliceOrigin, long sliceFence, long origin, long fence) {
 768                 super(s, sliceOrigin, sliceFence, origin, fence);
 769             }
 770 
 771             @Override
 772             public boolean tryAdvance(T_CONS action) {
 773                 Objects.requireNonNull(action);
 774 
 775                 if (sliceOrigin >= fence)
 776                     return false;
 777 
 778                 while (sliceOrigin > index) {
 779                     s.tryAdvance(emptyConsumer());
 780                     index++;
 781                 }
 782 
 783                 if (index >= fence)
 784                     return false;
 785 
 786                 index++;
 787                 return s.tryAdvance(action);
 788             }
 789 
 790             @Override
 791             public void forEachRemaining(T_CONS action) {
 792                 Objects.requireNonNull(action);
 793 
 794                 if (sliceOrigin >= fence)
 795                     return;
 796 
 797                 if (index >= fence)
 798                     return;
 799 
 800                 if (index >= sliceOrigin && (index + s.estimateSize()) <= sliceFence) {
 801                     // The spliterator is contained within the slice
 802                     s.forEachRemaining(action);
 803                     index = fence;
 804                 } else {
 805                     // The spliterator intersects with the slice
 806                     while (sliceOrigin > index) {
 807                         s.tryAdvance(emptyConsumer());
 808                         index++;
 809                     }
 810                     // Traverse elements up to the fence
 811                     for (;index < fence; index++) {
 812                         s.tryAdvance(action);
 813                     }
 814                 }
 815             }
 816 
 817             protected abstract T_CONS emptyConsumer();
 818         }
 819 
 820         static final class OfInt extends OfPrimitive<Integer, Spliterator.OfInt, IntConsumer>
 821                 implements Spliterator.OfInt {
 822             OfInt(Spliterator.OfInt s, long sliceOrigin, long sliceFence) {
 823                 super(s, sliceOrigin, sliceFence);
 824             }
 825 
 826             OfInt(Spliterator.OfInt s,
 827                   long sliceOrigin, long sliceFence, long origin, long fence) {
 828                 super(s, sliceOrigin, sliceFence, origin, fence);
 829             }
 830 
 831             @Override
 832             protected Spliterator.OfInt makeSpliterator(Spliterator.OfInt s,
 833                                                         long sliceOrigin, long sliceFence,
 834                                                         long origin, long fence) {
 835                 return new SliceSpliterator.OfInt(s, sliceOrigin, sliceFence, origin, fence);
 836             }
 837 
 838             @Override
 839             protected IntConsumer emptyConsumer() {
 840                 return e -> {};
 841             }
 842         }
 843 
 844         static final class OfLong extends OfPrimitive<Long, Spliterator.OfLong, LongConsumer>
 845                 implements Spliterator.OfLong {
 846             OfLong(Spliterator.OfLong s, long sliceOrigin, long sliceFence) {
 847                 super(s, sliceOrigin, sliceFence);
 848             }
 849 
 850             OfLong(Spliterator.OfLong s,
 851                    long sliceOrigin, long sliceFence, long origin, long fence) {
 852                 super(s, sliceOrigin, sliceFence, origin, fence);
 853             }
 854 
 855             @Override
 856             protected Spliterator.OfLong makeSpliterator(Spliterator.OfLong s,
 857                                                          long sliceOrigin, long sliceFence,
 858                                                          long origin, long fence) {
 859                 return new SliceSpliterator.OfLong(s, sliceOrigin, sliceFence, origin, fence);
 860             }
 861 
 862             @Override
 863             protected LongConsumer emptyConsumer() {
 864                 return e -> {};
 865             }
 866         }
 867 
 868         static final class OfDouble extends OfPrimitive<Double, Spliterator.OfDouble, DoubleConsumer>
 869                 implements Spliterator.OfDouble {
 870             OfDouble(Spliterator.OfDouble s, long sliceOrigin, long sliceFence) {
 871                 super(s, sliceOrigin, sliceFence);
 872             }
 873 
 874             OfDouble(Spliterator.OfDouble s,
 875                      long sliceOrigin, long sliceFence, long origin, long fence) {
 876                 super(s, sliceOrigin, sliceFence, origin, fence);
 877             }
 878 
 879             @Override
 880             protected Spliterator.OfDouble makeSpliterator(Spliterator.OfDouble s,
 881                                                            long sliceOrigin, long sliceFence,
 882                                                            long origin, long fence) {
 883                 return new SliceSpliterator.OfDouble(s, sliceOrigin, sliceFence, origin, fence);
 884             }
 885 
 886             @Override
 887             protected DoubleConsumer emptyConsumer() {
 888                 return e -> {};
 889             }
 890         }
 891     }
 892 
 893     /**
 894      * A slice Spliterator that does not preserve order, if any, of a source
 895      * Spliterator.
 896      *
 897      * Note: The source spliterator may report {@code ORDERED} since that
 898      * spliterator be the result of a previous pipeline stage that was
 899      * collected to a {@code Node}. It is the order of the pipeline stage
 900      * that governs whether this slice spliterator is to be used or not.
 901      */
 902     abstract static class UnorderedSliceSpliterator<T, T_SPLITR extends Spliterator<T>> {
 903         static final int CHUNK_SIZE = 1 << 7;
 904 
 905         // The spliterator to slice
 906         protected final T_SPLITR s;
 907         protected final boolean unlimited;
 908         protected final int chunkSize;
 909         private final long skipThreshold;
 910         private final AtomicLong permits;
 911 
 912         UnorderedSliceSpliterator(T_SPLITR s, long skip, long limit) {
 913             this.s = s;
 914             this.unlimited = limit < 0;
 915             this.skipThreshold = limit >= 0 ? limit : 0;
 916             this.chunkSize = limit >= 0 ? (int)Math.min(CHUNK_SIZE,
 917                                                         ((skip + limit) / AbstractTask.getLeafTarget()) + 1) : CHUNK_SIZE;
 918             this.permits = new AtomicLong(limit >= 0 ? skip + limit : skip);
 919         }
 920 
 921         UnorderedSliceSpliterator(T_SPLITR s,
 922                                   UnorderedSliceSpliterator<T, T_SPLITR> parent) {
 923             this.s = s;
 924             this.unlimited = parent.unlimited;
 925             this.permits = parent.permits;
 926             this.skipThreshold = parent.skipThreshold;
 927             this.chunkSize = parent.chunkSize;
 928         }
 929 
 930         /**
 931          * Acquire permission to skip or process elements.  The caller must
 932          * first acquire the elements, then consult this method for guidance
 933          * as to what to do with the data.
 934          *
 935          * <p>We use an {@code AtomicLong} to atomically maintain a counter,
 936          * which is initialized as skip+limit if we are limiting, or skip only
 937          * if we are not limiting.  The user should consult the method
 938          * {@code checkPermits()} before acquiring data elements.
 939          *
 940          * @param numElements the number of elements the caller has in hand
 941          * @return the number of elements that should be processed; any
 942          * remaining elements should be discarded.
 943          */
 944         protected final long acquirePermits(long numElements) {
 945             long remainingPermits;
 946             long grabbing;
 947             // permits never increase, and don't decrease below zero
 948             assert numElements > 0;
 949             do {
 950                 remainingPermits = permits.get();
 951                 if (remainingPermits == 0)
 952                     return unlimited ? numElements : 0;
 953                 grabbing = Math.min(remainingPermits, numElements);
 954             } while (grabbing > 0 &&
 955                      !permits.compareAndSet(remainingPermits, remainingPermits - grabbing));
 956 
 957             if (unlimited)
 958                 return Math.max(numElements - grabbing, 0);
 959             else if (remainingPermits > skipThreshold)
 960                 return Math.max(grabbing - (remainingPermits - skipThreshold), 0);
 961             else
 962                 return grabbing;
 963         }
 964 
 965         enum PermitStatus { NO_MORE, MAYBE_MORE, UNLIMITED }
 966 
 967         /** Call to check if permits might be available before acquiring data */
 968         protected final PermitStatus permitStatus() {
 969             if (permits.get() > 0)
 970                 return PermitStatus.MAYBE_MORE;
 971             else
 972                 return unlimited ?  PermitStatus.UNLIMITED : PermitStatus.NO_MORE;
 973         }
 974 
 975         public final T_SPLITR trySplit() {
 976             // Stop splitting when there are no more limit permits
 977             if (permits.get() == 0)
 978                 return null;
 979             @SuppressWarnings("unchecked")
 980             T_SPLITR split = (T_SPLITR) s.trySplit();
 981             return split == null ? null : makeSpliterator(split);
 982         }
 983 
 984         protected abstract T_SPLITR makeSpliterator(T_SPLITR s);
 985 
 986         public final long estimateSize() {
 987             return s.estimateSize();
 988         }
 989 
 990         public final int characteristics() {
 991             return s.characteristics() &
 992                    ~(Spliterator.SIZED | Spliterator.SUBSIZED | Spliterator.ORDERED);
 993         }
 994 
 995         static final class OfRef<T> extends UnorderedSliceSpliterator<T, Spliterator<T>>
 996                 implements Spliterator<T>, Consumer<T> {
 997             T tmpSlot;
 998 
 999             OfRef(Spliterator<T> s, long skip, long limit) {
1000                 super(s, skip, limit);
1001             }
1002 
1003             OfRef(Spliterator<T> s, OfRef<T> parent) {
1004                 super(s, parent);
1005             }
1006 
1007             @Override
1008             public final void accept(T t) {
1009                 tmpSlot = t;
1010             }
1011 
1012             @Override
1013             public boolean tryAdvance(Consumer<? super T> action) {
1014                 Objects.requireNonNull(action);
1015 
1016                 while (permitStatus() != PermitStatus.NO_MORE) {
1017                     if (!s.tryAdvance(this))
1018                         return false;
1019                     else if (acquirePermits(1) == 1) {
1020                         action.accept(tmpSlot);
1021                         tmpSlot = null;
1022                         return true;
1023                     }
1024                 }
1025                 return false;
1026             }
1027 
1028             @Override
1029             public void forEachRemaining(Consumer<? super T> action) {
1030                 Objects.requireNonNull(action);
1031 
1032                 ArrayBuffer.OfRef<T> sb = null;
1033                 PermitStatus permitStatus;
1034                 while ((permitStatus = permitStatus()) != PermitStatus.NO_MORE) {
1035                     if (permitStatus == PermitStatus.MAYBE_MORE) {
1036                         // Optimistically traverse elements up to a threshold of chunkSize
1037                         if (sb == null)
1038                             sb = new ArrayBuffer.OfRef<>(chunkSize);
1039                         else
1040                             sb.reset();
1041                         long permitsRequested = 0;
1042                         do { } while (s.tryAdvance(sb) && ++permitsRequested < chunkSize);
1043                         if (permitsRequested == 0)
1044                             return;
1045                         sb.forEach(action, acquirePermits(permitsRequested));
1046                     }
1047                     else {
1048                         // Must be UNLIMITED; let 'er rip
1049                         s.forEachRemaining(action);
1050                         return;
1051                     }
1052                 }
1053             }
1054 
1055             @Override
1056             protected Spliterator<T> makeSpliterator(Spliterator<T> s) {
1057                 return new UnorderedSliceSpliterator.OfRef<>(s, this);
1058             }
1059         }
1060 
1061         /**
1062          * Concrete sub-types must also be an instance of type {@code T_CONS}.
1063          *
1064          * @param <T_BUFF> the type of the spined buffer. Must also be a type of
1065          *        {@code T_CONS}.
1066          */
1067         abstract static class OfPrimitive<
1068                 T,
1069                 T_CONS,
1070                 T_BUFF extends ArrayBuffer.OfPrimitive<T_CONS>,
1071                 T_SPLITR extends Spliterator.OfPrimitive<T, T_CONS, T_SPLITR>>
1072                 extends UnorderedSliceSpliterator<T, T_SPLITR>
1073                 implements Spliterator.OfPrimitive<T, T_CONS, T_SPLITR> {
1074             OfPrimitive(T_SPLITR s, long skip, long limit) {
1075                 super(s, skip, limit);
1076             }
1077 
1078             OfPrimitive(T_SPLITR s, UnorderedSliceSpliterator.OfPrimitive<T, T_CONS, T_BUFF, T_SPLITR> parent) {
1079                 super(s, parent);
1080             }
1081 
1082             @Override
1083             public boolean tryAdvance(T_CONS action) {
1084                 Objects.requireNonNull(action);
1085                 @SuppressWarnings("unchecked")
1086                 T_CONS consumer = (T_CONS) this;
1087 
1088                 while (permitStatus() != PermitStatus.NO_MORE) {
1089                     if (!s.tryAdvance(consumer))
1090                         return false;
1091                     else if (acquirePermits(1) == 1) {
1092                         acceptConsumed(action);
1093                         return true;
1094                     }
1095                 }
1096                 return false;
1097             }
1098 
1099             protected abstract void acceptConsumed(T_CONS action);
1100 
1101             @Override
1102             public void forEachRemaining(T_CONS action) {
1103                 Objects.requireNonNull(action);
1104 
1105                 T_BUFF sb = null;
1106                 PermitStatus permitStatus;
1107                 while ((permitStatus = permitStatus()) != PermitStatus.NO_MORE) {
1108                     if (permitStatus == PermitStatus.MAYBE_MORE) {
1109                         // Optimistically traverse elements up to a threshold of chunkSize
1110                         if (sb == null)
1111                             sb = bufferCreate(chunkSize);
1112                         else
1113                             sb.reset();
1114                         @SuppressWarnings("unchecked")
1115                         T_CONS sbc = (T_CONS) sb;
1116                         long permitsRequested = 0;
1117                         do { } while (s.tryAdvance(sbc) && ++permitsRequested < chunkSize);
1118                         if (permitsRequested == 0)
1119                             return;
1120                         sb.forEach(action, acquirePermits(permitsRequested));
1121                     }
1122                     else {
1123                         // Must be UNLIMITED; let 'er rip
1124                         s.forEachRemaining(action);
1125                         return;
1126                     }
1127                 }
1128             }
1129 
1130             protected abstract T_BUFF bufferCreate(int initialCapacity);
1131         }
1132 
1133         static final class OfInt
1134                 extends OfPrimitive<Integer, IntConsumer, ArrayBuffer.OfInt, Spliterator.OfInt>
1135                 implements Spliterator.OfInt, IntConsumer {
1136 
1137             int tmpValue;
1138 
1139             OfInt(Spliterator.OfInt s, long skip, long limit) {
1140                 super(s, skip, limit);
1141             }
1142 
1143             OfInt(Spliterator.OfInt s, UnorderedSliceSpliterator.OfInt parent) {
1144                 super(s, parent);
1145             }
1146 
1147             @Override
1148             public void accept(int value) {
1149                 tmpValue = value;
1150             }
1151 
1152             @Override
1153             protected void acceptConsumed(IntConsumer action) {
1154                 action.accept(tmpValue);
1155             }
1156 
1157             @Override
1158             protected ArrayBuffer.OfInt bufferCreate(int initialCapacity) {
1159                 return new ArrayBuffer.OfInt(initialCapacity);
1160             }
1161 
1162             @Override
1163             protected Spliterator.OfInt makeSpliterator(Spliterator.OfInt s) {
1164                 return new UnorderedSliceSpliterator.OfInt(s, this);
1165             }
1166         }
1167 
1168         static final class OfLong
1169                 extends OfPrimitive<Long, LongConsumer, ArrayBuffer.OfLong, Spliterator.OfLong>
1170                 implements Spliterator.OfLong, LongConsumer {
1171 
1172             long tmpValue;
1173 
1174             OfLong(Spliterator.OfLong s, long skip, long limit) {
1175                 super(s, skip, limit);
1176             }
1177 
1178             OfLong(Spliterator.OfLong s, UnorderedSliceSpliterator.OfLong parent) {
1179                 super(s, parent);
1180             }
1181 
1182             @Override
1183             public void accept(long value) {
1184                 tmpValue = value;
1185             }
1186 
1187             @Override
1188             protected void acceptConsumed(LongConsumer action) {
1189                 action.accept(tmpValue);
1190             }
1191 
1192             @Override
1193             protected ArrayBuffer.OfLong bufferCreate(int initialCapacity) {
1194                 return new ArrayBuffer.OfLong(initialCapacity);
1195             }
1196 
1197             @Override
1198             protected Spliterator.OfLong makeSpliterator(Spliterator.OfLong s) {
1199                 return new UnorderedSliceSpliterator.OfLong(s, this);
1200             }
1201         }
1202 
1203         static final class OfDouble
1204                 extends OfPrimitive<Double, DoubleConsumer, ArrayBuffer.OfDouble, Spliterator.OfDouble>
1205                 implements Spliterator.OfDouble, DoubleConsumer {
1206 
1207             double tmpValue;
1208 
1209             OfDouble(Spliterator.OfDouble s, long skip, long limit) {
1210                 super(s, skip, limit);
1211             }
1212 
1213             OfDouble(Spliterator.OfDouble s, UnorderedSliceSpliterator.OfDouble parent) {
1214                 super(s, parent);
1215             }
1216 
1217             @Override
1218             public void accept(double value) {
1219                 tmpValue = value;
1220             }
1221 
1222             @Override
1223             protected void acceptConsumed(DoubleConsumer action) {
1224                 action.accept(tmpValue);
1225             }
1226 
1227             @Override
1228             protected ArrayBuffer.OfDouble bufferCreate(int initialCapacity) {
1229                 return new ArrayBuffer.OfDouble(initialCapacity);
1230             }
1231 
1232             @Override
1233             protected Spliterator.OfDouble makeSpliterator(Spliterator.OfDouble s) {
1234                 return new UnorderedSliceSpliterator.OfDouble(s, this);
1235             }
1236         }
1237     }
1238 
1239     /**
1240      * A wrapping spliterator that only reports distinct elements of the
1241      * underlying spliterator. Does not preserve size and encounter order.
1242      */
1243     static final class DistinctSpliterator<T> implements Spliterator<T>, Consumer<T> {
1244 
1245         // The value to represent null in the ConcurrentHashMap
1246         private static final Object NULL_VALUE = new Object();
1247 
1248         // The underlying spliterator
1249         private final Spliterator<T> s;
1250 
1251         // ConcurrentHashMap holding distinct elements as keys
1252         private final ConcurrentHashMap<T, Boolean> seen;
1253 
1254         // Temporary element, only used with tryAdvance
1255         private T tmpSlot;
1256 
1257         DistinctSpliterator(Spliterator<T> s) {
1258             this(s, new ConcurrentHashMap<>());
1259         }
1260 
1261         private DistinctSpliterator(Spliterator<T> s, ConcurrentHashMap<T, Boolean> seen) {
1262             this.s = s;
1263             this.seen = seen;
1264         }
1265 
1266         @Override
1267         public void accept(T t) {
1268             this.tmpSlot = t;
1269         }
1270 
1271         @SuppressWarnings("unchecked")
1272         private T mapNull(T t) {
1273             return t != null ? t : (T) NULL_VALUE;
1274         }
1275 
1276         @Override
1277         public boolean tryAdvance(Consumer<? super T> action) {
1278             while (s.tryAdvance(this)) {
1279                 if (seen.putIfAbsent(mapNull(tmpSlot), Boolean.TRUE) == null) {
1280                     action.accept(tmpSlot);
1281                     tmpSlot = null;
1282                     return true;
1283                 }
1284             }
1285             return false;
1286         }
1287 
1288         @Override
1289         public void forEachRemaining(Consumer<? super T> action) {
1290             s.forEachRemaining(t -> {
1291                 if (seen.putIfAbsent(mapNull(t), Boolean.TRUE) == null) {
1292                     action.accept(t);
1293                 }
1294             });
1295         }
1296 
1297         @Override
1298         public Spliterator<T> trySplit() {
1299             Spliterator<T> split = s.trySplit();
1300             return (split != null) ? new DistinctSpliterator<>(split, seen) : null;
1301         }
1302 
1303         @Override
1304         public long estimateSize() {
1305             return s.estimateSize();
1306         }
1307 
1308         @Override
1309         public int characteristics() {
1310             return (s.characteristics() & ~(Spliterator.SIZED | Spliterator.SUBSIZED |
1311                                             Spliterator.SORTED | Spliterator.ORDERED))
1312                    | Spliterator.DISTINCT;
1313         }
1314 
1315         @Override
1316         public Comparator<? super T> getComparator() {
1317             return s.getComparator();
1318         }
1319     }
1320 
1321     /**
1322      * A Spliterator that infinitely supplies elements in no particular order.
1323      *
1324      * <p>Splitting divides the estimated size in two and stops when the
1325      * estimate size is 0.
1326      *
1327      * <p>The {@code forEachRemaining} method if invoked will never terminate.
1328      * The {@code tryAdvance} method always returns true.
1329      *
1330      */
1331     abstract static class InfiniteSupplyingSpliterator<T> implements Spliterator<T> {
1332         long estimate;
1333 
1334         protected InfiniteSupplyingSpliterator(long estimate) {
1335             this.estimate = estimate;
1336         }
1337 
1338         @Override
1339         public long estimateSize() {
1340             return estimate;
1341         }
1342 
1343         @Override
1344         public int characteristics() {
1345             return IMMUTABLE;
1346         }
1347 
1348         static final class OfRef<T> extends InfiniteSupplyingSpliterator<T> {
1349             final Supplier<? extends T> s;
1350 
1351             OfRef(long size, Supplier<? extends T> s) {
1352                 super(size);
1353                 this.s = s;
1354             }
1355 
1356             @Override
1357             public boolean tryAdvance(Consumer<? super T> action) {
1358                 Objects.requireNonNull(action);
1359 
1360                 action.accept(s.get());
1361                 return true;
1362             }
1363 
1364             @Override
1365             public Spliterator<T> trySplit() {
1366                 if (estimate == 0)
1367                     return null;
1368                 return new InfiniteSupplyingSpliterator.OfRef<>(estimate >>>= 1, s);
1369             }
1370         }
1371 
1372         static final class OfInt extends InfiniteSupplyingSpliterator<Integer>
1373                 implements Spliterator.OfInt {
1374             final IntSupplier s;
1375 
1376             OfInt(long size, IntSupplier s) {
1377                 super(size);
1378                 this.s = s;
1379             }
1380 
1381             @Override
1382             public boolean tryAdvance(IntConsumer action) {
1383                 Objects.requireNonNull(action);
1384 
1385                 action.accept(s.getAsInt());
1386                 return true;
1387             }
1388 
1389             @Override
1390             public Spliterator.OfInt trySplit() {
1391                 if (estimate == 0)
1392                     return null;
1393                 return new InfiniteSupplyingSpliterator.OfInt(estimate = estimate >>> 1, s);
1394             }
1395         }
1396 
1397         static final class OfLong extends InfiniteSupplyingSpliterator<Long>
1398                 implements Spliterator.OfLong {
1399             final LongSupplier s;
1400 
1401             OfLong(long size, LongSupplier s) {
1402                 super(size);
1403                 this.s = s;
1404             }
1405 
1406             @Override
1407             public boolean tryAdvance(LongConsumer action) {
1408                 Objects.requireNonNull(action);
1409 
1410                 action.accept(s.getAsLong());
1411                 return true;
1412             }
1413 
1414             @Override
1415             public Spliterator.OfLong trySplit() {
1416                 if (estimate == 0)
1417                     return null;
1418                 return new InfiniteSupplyingSpliterator.OfLong(estimate = estimate >>> 1, s);
1419             }
1420         }
1421 
1422         static final class OfDouble extends InfiniteSupplyingSpliterator<Double>
1423                 implements Spliterator.OfDouble {
1424             final DoubleSupplier s;
1425 
1426             OfDouble(long size, DoubleSupplier s) {
1427                 super(size);
1428                 this.s = s;
1429             }
1430 
1431             @Override
1432             public boolean tryAdvance(DoubleConsumer action) {
1433                 Objects.requireNonNull(action);
1434 
1435                 action.accept(s.getAsDouble());
1436                 return true;
1437             }
1438 
1439             @Override
1440             public Spliterator.OfDouble trySplit() {
1441                 if (estimate == 0)
1442                     return null;
1443                 return new InfiniteSupplyingSpliterator.OfDouble(estimate = estimate >>> 1, s);
1444             }
1445         }
1446     }
1447 
1448     // @@@ Consolidate with Node.Builder
1449     abstract static class ArrayBuffer {
1450         int index;
1451 
1452         void reset() {
1453             index = 0;
1454         }
1455 
1456         static final class OfRef<T> extends ArrayBuffer implements Consumer<T> {
1457             final Object[] array;
1458 
1459             OfRef(int size) {
1460                 this.array = new Object[size];
1461             }
1462 
1463             @Override
1464             public void accept(T t) {
1465                 array[index++] = t;
1466             }
1467 
1468             public void forEach(Consumer<? super T> action, long fence) {
1469                 for (int i = 0; i < fence; i++) {
1470                     @SuppressWarnings("unchecked")
1471                     T t = (T) array[i];
1472                     action.accept(t);
1473                 }
1474             }
1475         }
1476 
1477         abstract static class OfPrimitive<T_CONS> extends ArrayBuffer {
1478             int index;
1479 
1480             @Override
1481             void reset() {
1482                 index = 0;
1483             }
1484 
1485             abstract void forEach(T_CONS action, long fence);
1486         }
1487 
1488         static final class OfInt extends OfPrimitive<IntConsumer>
1489                 implements IntConsumer {
1490             final int[] array;
1491 
1492             OfInt(int size) {
1493                 this.array = new int[size];
1494             }
1495 
1496             @Override
1497             public void accept(int t) {
1498                 array[index++] = t;
1499             }
1500 
1501             @Override
1502             public void forEach(IntConsumer action, long fence) {
1503                 for (int i = 0; i < fence; i++) {
1504                     action.accept(array[i]);
1505                 }
1506             }
1507         }
1508 
1509         static final class OfLong extends OfPrimitive<LongConsumer>
1510                 implements LongConsumer {
1511             final long[] array;
1512 
1513             OfLong(int size) {
1514                 this.array = new long[size];
1515             }
1516 
1517             @Override
1518             public void accept(long t) {
1519                 array[index++] = t;
1520             }
1521 
1522             @Override
1523             public void forEach(LongConsumer action, long fence) {
1524                 for (int i = 0; i < fence; i++) {
1525                     action.accept(array[i]);
1526                 }
1527             }
1528         }
1529 
1530         static final class OfDouble extends OfPrimitive<DoubleConsumer>
1531                 implements DoubleConsumer {
1532             final double[] array;
1533 
1534             OfDouble(int size) {
1535                 this.array = new double[size];
1536             }
1537 
1538             @Override
1539             public void accept(double t) {
1540                 array[index++] = t;
1541             }
1542 
1543             @Override
1544             void forEach(DoubleConsumer action, long fence) {
1545                 for (int i = 0; i < fence; i++) {
1546                     action.accept(array[i]);
1547                 }
1548             }
1549         }
1550     }
1551 }
1552