1 /* 2 * Copyright (c) 2012, 2013, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 package java.util.stream; 26 27 import java.util.Comparator; 28 import java.util.Objects; 29 import java.util.Spliterator; 30 import java.util.function.Consumer; 31 import java.util.function.DoubleConsumer; 32 import java.util.function.IntConsumer; 33 import java.util.function.LongConsumer; 34 35 /** 36 * Utility methods for operating on and creating streams. 37 * 38 * <p>Unless otherwise stated, streams are created as sequential streams. A 39 * sequential stream can be transformed into a parallel stream by calling the 40 * {@code parallel()} method on the created stream. 41 * 42 * @since 1.8 43 */ 44 final class Streams { 45 46 private Streams() { 47 throw new Error("no instances"); 48 } 49 50 /** 51 * An object instance representing no value, that cannot be an actual 52 * data element of a stream. Used when processing streams that can contain 53 * {@code null} elements to distinguish between a {@code null} value and no 54 * value. 55 */ 56 static final Object NONE = new Object(); 57 58 /** 59 * An {@code int} range spliterator. 60 */ 61 static final class RangeIntSpliterator implements Spliterator.OfInt { 62 // Can never be greater that upTo, this avoids overflow if upper bound 63 // is Integer.MAX_VALUE 64 // All elements are traversed if from == upTo & last == 0 65 private int from; 66 private final int upTo; 67 // 1 if the range is closed and the last element has not been traversed 68 // Otherwise, 0 if the range is open, or is a closed range and all 69 // elements have been traversed 70 private int last; 71 72 RangeIntSpliterator(int from, int upTo, boolean closed) { 73 this(from, upTo, closed ? 1 : 0); 74 } 75 76 private RangeIntSpliterator(int from, int upTo, int last) { 77 this.from = from; 78 this.upTo = upTo; 79 this.last = last; 80 } 81 82 @Override 83 public boolean tryAdvance(IntConsumer consumer) { 84 Objects.requireNonNull(consumer); 85 86 final int i = from; 87 if (i < upTo) { 88 from++; 89 consumer.accept(i); 90 return true; 91 } 92 else if (last > 0) { 93 last = 0; 94 consumer.accept(i); 95 return true; 96 } 97 return false; 98 } 99 100 @Override 101 public void forEachRemaining(IntConsumer consumer) { 102 Objects.requireNonNull(consumer); 103 104 int i = from; 105 final int hUpTo = upTo; 106 int hLast = last; 107 from = upTo; 108 last = 0; 109 while (i < hUpTo) { 110 consumer.accept(i++); 111 } 112 if (hLast > 0) { 113 // Last element of closed range 114 consumer.accept(i); 115 } 116 } 117 118 @Override 119 public long estimateSize() { 120 // Ensure ranges of size > Integer.MAX_VALUE report the correct size 121 return ((long) upTo) - from + last; 122 } 123 124 @Override 125 public int characteristics() { 126 return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED | 127 Spliterator.IMMUTABLE | Spliterator.NONNULL | 128 Spliterator.DISTINCT | Spliterator.SORTED; 129 } 130 131 @Override 132 public Comparator<? super Integer> getComparator() { 133 return null; 134 } 135 136 @Override 137 public Spliterator.OfInt trySplit() { 138 long size = estimateSize(); 139 return size <= 1 140 ? null 141 // Left split always has a half-open range 142 : new RangeIntSpliterator(from, from = from + splitPoint(size), 0); 143 } 144 145 /** 146 * The spliterator size below which the spliterator will be split 147 * at the mid-point to produce balanced splits. Above this size the 148 * spliterator will be split at a ratio of 149 * 1:(RIGHT_BALANCED_SPLIT_RATIO - 1) 150 * to produce right-balanced splits. 151 * 152 * <p>Such splitting ensures that for very large ranges that the left 153 * side of the range will more likely be processed at a lower-depth 154 * than a balanced tree at the expense of a higher-depth for the right 155 * side of the range. 156 * 157 * <p>This is optimized for cases such as IntStream.ints() that is 158 * implemented as range of 0 to Integer.MAX_VALUE but is likely to be 159 * augmented with a limit operation that limits the number of elements 160 * to a count lower than this threshold. 161 */ 162 private static final int BALANCED_SPLIT_THRESHOLD = 1 << 24; 163 164 /** 165 * The split ratio of the left and right split when the spliterator 166 * size is above BALANCED_SPLIT_THRESHOLD. 167 */ 168 private static final int RIGHT_BALANCED_SPLIT_RATIO = 1 << 3; 169 170 private int splitPoint(long size) { 171 int d = (size < BALANCED_SPLIT_THRESHOLD) ? 2 : RIGHT_BALANCED_SPLIT_RATIO; 172 // 2 <= size <= 2^32 173 return (int) (size / d); 174 } 175 } 176 177 /** 178 * A {@code long} range spliterator. 179 * 180 * This implementation cannot be used for ranges whose size is greater 181 * than Long.MAX_VALUE 182 */ 183 static final class RangeLongSpliterator implements Spliterator.OfLong { 184 // Can never be greater that upTo, this avoids overflow if upper bound 185 // is Long.MAX_VALUE 186 // All elements are traversed if from == upTo & last == 0 187 private long from; 188 private final long upTo; 189 // 1 if the range is closed and the last element has not been traversed 190 // Otherwise, 0 if the range is open, or is a closed range and all 191 // elements have been traversed 192 private int last; 193 194 RangeLongSpliterator(long from, long upTo, boolean closed) { 195 this(from, upTo, closed ? 1 : 0); 196 } 197 198 private RangeLongSpliterator(long from, long upTo, int last) { 199 assert upTo - from + last > 0; 200 this.from = from; 201 this.upTo = upTo; 202 this.last = last; 203 } 204 205 @Override 206 public boolean tryAdvance(LongConsumer consumer) { 207 Objects.requireNonNull(consumer); 208 209 final long i = from; 210 if (i < upTo) { 211 from++; 212 consumer.accept(i); 213 return true; 214 } 215 else if (last > 0) { 216 last = 0; 217 consumer.accept(i); 218 return true; 219 } 220 return false; 221 } 222 223 @Override 224 public void forEachRemaining(LongConsumer consumer) { 225 Objects.requireNonNull(consumer); 226 227 long i = from; 228 final long hUpTo = upTo; 229 int hLast = last; 230 from = upTo; 231 last = 0; 232 while (i < hUpTo) { 233 consumer.accept(i++); 234 } 235 if (hLast > 0) { 236 // Last element of closed range 237 consumer.accept(i); 238 } 239 } 240 241 @Override 242 public long estimateSize() { 243 return upTo - from + last; 244 } 245 246 @Override 247 public int characteristics() { 248 return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED | 249 Spliterator.IMMUTABLE | Spliterator.NONNULL | 250 Spliterator.DISTINCT | Spliterator.SORTED; 251 } 252 253 @Override 254 public Comparator<? super Long> getComparator() { 255 return null; 256 } 257 258 @Override 259 public Spliterator.OfLong trySplit() { 260 long size = estimateSize(); 261 return size <= 1 262 ? null 263 // Left split always has a half-open range 264 : new RangeLongSpliterator(from, from = from + splitPoint(size), 0); 265 } 266 267 /** 268 * The spliterator size below which the spliterator will be split 269 * at the mid-point to produce balanced splits. Above this size the 270 * spliterator will be split at a ratio of 271 * 1:(RIGHT_BALANCED_SPLIT_RATIO - 1) 272 * to produce right-balanced splits. 273 * 274 * <p>Such splitting ensures that for very large ranges that the left 275 * side of the range will more likely be processed at a lower-depth 276 * than a balanced tree at the expense of a higher-depth for the right 277 * side of the range. 278 * 279 * <p>This is optimized for cases such as LongStream.longs() that is 280 * implemented as range of 0 to Long.MAX_VALUE but is likely to be 281 * augmented with a limit operation that limits the number of elements 282 * to a count lower than this threshold. 283 */ 284 private static final long BALANCED_SPLIT_THRESHOLD = 1 << 24; 285 286 /** 287 * The split ratio of the left and right split when the spliterator 288 * size is above BALANCED_SPLIT_THRESHOLD. 289 */ 290 private static final long RIGHT_BALANCED_SPLIT_RATIO = 1 << 3; 291 292 private long splitPoint(long size) { 293 long d = (size < BALANCED_SPLIT_THRESHOLD) ? 2 : RIGHT_BALANCED_SPLIT_RATIO; 294 // 2 <= size <= Long.MAX_VALUE 295 return size / d; 296 } 297 } 298 299 private static abstract class AbstractStreamBuilderImpl<T, S extends Spliterator<T>> implements Spliterator<T> { 300 // >= 0 when building, < 0 when built 301 // -1 == no elements 302 // -2 == one element, held by first 303 // -3 == two or more elements, held by buffer 304 int count; 305 306 // Spliterator implementation for 0 or 1 element 307 // count == -1 for no elements 308 // count == -2 for one element held by first 309 310 @Override 311 public S trySplit() { 312 return null; 313 } 314 315 @Override 316 public long estimateSize() { 317 return -count - 1; 318 } 319 320 @Override 321 public int characteristics() { 322 return Spliterator.SIZED | Spliterator.SUBSIZED | 323 Spliterator.ORDERED | Spliterator.IMMUTABLE; 324 } 325 } 326 327 static final class StreamBuilderImpl<T> 328 extends AbstractStreamBuilderImpl<T, Spliterator<T>> 329 implements Stream.Builder<T> { 330 // The first element in the stream 331 // valid if count == 1 332 T first; 333 334 // The first and subsequent elements in the stream 335 // non-null if count == 2 336 SpinedBuffer<T> buffer; 337 338 /** 339 * Constructor for building a stream of 0 or more elements. 340 */ 341 StreamBuilderImpl() { } 342 343 /** 344 * Constructor for a singleton stream. 345 * 346 * @param t the single element 347 */ 348 StreamBuilderImpl(T t) { 349 first = t; 350 count = -2; 351 } 352 353 // StreamBuilder implementation 354 355 @Override 356 public void accept(T t) { 357 if (count == 0) { 358 first = t; 359 count++; 360 } 361 else if (count > 0) { 362 if (buffer == null) { 363 buffer = new SpinedBuffer<>(); 364 buffer.accept(first); 365 count++; 366 } 367 368 buffer.accept(t); 369 } 370 else { 371 throw new IllegalStateException(); 372 } 373 } 374 375 public Stream.Builder<T> add(T t) { 376 accept(t); 377 return this; 378 } 379 380 @Override 381 public Stream<T> build() { 382 int c = count; 383 if (c >= 0) { 384 // Switch count to negative value signalling the builder is built 385 count = -count - 1; 386 // Use this spliterator if 0 or 1 elements, otherwise use 387 // the spliterator of the spined buffer 388 return (c < 2) ? StreamSupport.stream(this, false) : StreamSupport.stream(buffer.spliterator(), false); 389 } 390 391 throw new IllegalStateException(); 392 } 393 394 // Spliterator implementation for 0 or 1 element 395 // count == -1 for no elements 396 // count == -2 for one element held by first 397 398 @Override 399 public boolean tryAdvance(Consumer<? super T> action) { 400 Objects.requireNonNull(action); 401 402 if (count == -2) { 403 action.accept(first); 404 count = -1; 405 return true; 406 } 407 else { 408 return false; 409 } 410 } 411 412 @Override 413 public void forEachRemaining(Consumer<? super T> action) { 414 Objects.requireNonNull(action); 415 416 if (count == -2) { 417 action.accept(first); 418 count = -1; 419 } 420 } 421 } 422 423 static final class IntStreamBuilderImpl 424 extends AbstractStreamBuilderImpl<Integer, Spliterator.OfInt> 425 implements IntStream.Builder, Spliterator.OfInt { 426 // The first element in the stream 427 // valid if count == 1 428 int first; 429 430 // The first and subsequent elements in the stream 431 // non-null if count == 2 432 SpinedBuffer.OfInt buffer; 433 434 /** 435 * Constructor for building a stream of 0 or more elements. 436 */ 437 IntStreamBuilderImpl() { } 438 439 /** 440 * Constructor for a singleton stream. 441 * 442 * @param t the single element 443 */ 444 IntStreamBuilderImpl(int t) { 445 first = t; 446 count = -2; 447 } 448 449 // StreamBuilder implementation 450 451 @Override 452 public void accept(int t) { 453 if (count == 0) { 454 first = t; 455 count++; 456 } 457 else if (count > 0) { 458 if (buffer == null) { 459 buffer = new SpinedBuffer.OfInt(); 460 buffer.accept(first); 461 count++; 462 } 463 464 buffer.accept(t); 465 } 466 else { 467 throw new IllegalStateException(); 468 } 469 } 470 471 @Override 472 public IntStream build() { 473 int c = count; 474 if (c >= 0) { 475 // Switch count to negative value signalling the builder is built 476 count = -count - 1; 477 // Use this spliterator if 0 or 1 elements, otherwise use 478 // the spliterator of the spined buffer 479 return (c < 2) ? StreamSupport.intStream(this, false) : StreamSupport.intStream(buffer.spliterator(), false); 480 } 481 482 throw new IllegalStateException(); 483 } 484 485 // Spliterator implementation for 0 or 1 element 486 // count == -1 for no elements 487 // count == -2 for one element held by first 488 489 @Override 490 public boolean tryAdvance(IntConsumer action) { 491 Objects.requireNonNull(action); 492 493 if (count == -2) { 494 action.accept(first); 495 count = -1; 496 return true; 497 } 498 else { 499 return false; 500 } 501 } 502 503 @Override 504 public void forEachRemaining(IntConsumer action) { 505 Objects.requireNonNull(action); 506 507 if (count == -2) { 508 action.accept(first); 509 count = -1; 510 } 511 } 512 } 513 514 static final class LongStreamBuilderImpl 515 extends AbstractStreamBuilderImpl<Long, Spliterator.OfLong> 516 implements LongStream.Builder, Spliterator.OfLong { 517 // The first element in the stream 518 // valid if count == 1 519 long first; 520 521 // The first and subsequent elements in the stream 522 // non-null if count == 2 523 SpinedBuffer.OfLong buffer; 524 525 /** 526 * Constructor for building a stream of 0 or more elements. 527 */ 528 LongStreamBuilderImpl() { } 529 530 /** 531 * Constructor for a singleton stream. 532 * 533 * @param t the single element 534 */ 535 LongStreamBuilderImpl(long t) { 536 first = t; 537 count = -2; 538 } 539 540 // StreamBuilder implementation 541 542 @Override 543 public void accept(long t) { 544 if (count == 0) { 545 first = t; 546 count++; 547 } 548 else if (count > 0) { 549 if (buffer == null) { 550 buffer = new SpinedBuffer.OfLong(); 551 buffer.accept(first); 552 count++; 553 } 554 555 buffer.accept(t); 556 } 557 else { 558 throw new IllegalStateException(); 559 } 560 } 561 562 @Override 563 public LongStream build() { 564 int c = count; 565 if (c >= 0) { 566 // Switch count to negative value signalling the builder is built 567 count = -count - 1; 568 // Use this spliterator if 0 or 1 elements, otherwise use 569 // the spliterator of the spined buffer 570 return (c < 2) ? StreamSupport.longStream(this, false) : StreamSupport.longStream(buffer.spliterator(), false); 571 } 572 573 throw new IllegalStateException(); 574 } 575 576 // Spliterator implementation for 0 or 1 element 577 // count == -1 for no elements 578 // count == -2 for one element held by first 579 580 @Override 581 public boolean tryAdvance(LongConsumer action) { 582 Objects.requireNonNull(action); 583 584 if (count == -2) { 585 action.accept(first); 586 count = -1; 587 return true; 588 } 589 else { 590 return false; 591 } 592 } 593 594 @Override 595 public void forEachRemaining(LongConsumer action) { 596 Objects.requireNonNull(action); 597 598 if (count == -2) { 599 action.accept(first); 600 count = -1; 601 } 602 } 603 } 604 605 static final class DoubleStreamBuilderImpl 606 extends AbstractStreamBuilderImpl<Double, Spliterator.OfDouble> 607 implements DoubleStream.Builder, Spliterator.OfDouble { 608 // The first element in the stream 609 // valid if count == 1 610 double first; 611 612 // The first and subsequent elements in the stream 613 // non-null if count == 2 614 SpinedBuffer.OfDouble buffer; 615 616 /** 617 * Constructor for building a stream of 0 or more elements. 618 */ 619 DoubleStreamBuilderImpl() { } 620 621 /** 622 * Constructor for a singleton stream. 623 * 624 * @param t the single element 625 */ 626 DoubleStreamBuilderImpl(double t) { 627 first = t; 628 count = -2; 629 } 630 631 // StreamBuilder implementation 632 633 @Override 634 public void accept(double t) { 635 if (count == 0) { 636 first = t; 637 count++; 638 } 639 else if (count > 0) { 640 if (buffer == null) { 641 buffer = new SpinedBuffer.OfDouble(); 642 buffer.accept(first); 643 count++; 644 } 645 646 buffer.accept(t); 647 } 648 else { 649 throw new IllegalStateException(); 650 } 651 } 652 653 @Override 654 public DoubleStream build() { 655 int c = count; 656 if (c >= 0) { 657 // Switch count to negative value signalling the builder is built 658 count = -count - 1; 659 // Use this spliterator if 0 or 1 elements, otherwise use 660 // the spliterator of the spined buffer 661 return (c < 2) ? StreamSupport.doubleStream(this, false) : StreamSupport.doubleStream(buffer.spliterator(), false); 662 } 663 664 throw new IllegalStateException(); 665 } 666 667 // Spliterator implementation for 0 or 1 element 668 // count == -1 for no elements 669 // count == -2 for one element held by first 670 671 @Override 672 public boolean tryAdvance(DoubleConsumer action) { 673 Objects.requireNonNull(action); 674 675 if (count == -2) { 676 action.accept(first); 677 count = -1; 678 return true; 679 } 680 else { 681 return false; 682 } 683 } 684 685 @Override 686 public void forEachRemaining(DoubleConsumer action) { 687 Objects.requireNonNull(action); 688 689 if (count == -2) { 690 action.accept(first); 691 count = -1; 692 } 693 } 694 } 695 696 abstract static class ConcatSpliterator<T, T_SPLITR extends Spliterator<T>> 697 implements Spliterator<T> { 698 protected final T_SPLITR aSpliterator; 699 protected final T_SPLITR bSpliterator; 700 // True when no split has occurred, otherwise false 701 boolean beforeSplit; 702 // Never read after splitting 703 final boolean unsized; 704 705 public ConcatSpliterator(T_SPLITR aSpliterator, T_SPLITR bSpliterator) { 706 this.aSpliterator = aSpliterator; 707 this.bSpliterator = bSpliterator; 708 beforeSplit = true; 709 // The spliterator is known to be unsized before splitting if the 710 // sum of the estimates overflows. 711 unsized = aSpliterator.estimateSize() + bSpliterator.estimateSize() < 0; 712 } 713 714 @Override 715 public T_SPLITR trySplit() { 716 T_SPLITR ret = beforeSplit ? aSpliterator : (T_SPLITR) bSpliterator.trySplit(); 717 beforeSplit = false; 718 return ret; 719 } 720 721 @Override 722 public boolean tryAdvance(Consumer<? super T> consumer) { 723 boolean hasNext; 724 if (beforeSplit) { 725 hasNext = aSpliterator.tryAdvance(consumer); 726 if (!hasNext) { 727 beforeSplit = false; 728 hasNext = bSpliterator.tryAdvance(consumer); 729 } 730 } 731 else 732 hasNext = bSpliterator.tryAdvance(consumer); 733 return hasNext; 734 } 735 736 @Override 737 public void forEachRemaining(Consumer<? super T> consumer) { 738 if (beforeSplit) 739 aSpliterator.forEachRemaining(consumer); 740 bSpliterator.forEachRemaining(consumer); 741 } 742 743 @Override 744 public long estimateSize() { 745 if (beforeSplit) { 746 // If one or both estimates are Long.MAX_VALUE then the sum 747 // will either be Long.MAX_VALUE or overflow to a negative value 748 long size = aSpliterator.estimateSize() + bSpliterator.estimateSize(); 749 return (size >= 0) ? size : Long.MAX_VALUE; 750 } 751 else { 752 return bSpliterator.estimateSize(); 753 } 754 } 755 756 @Override 757 public int characteristics() { 758 if (beforeSplit) { 759 // Concatenation loses DISTINCT and SORTED characteristics 760 return aSpliterator.characteristics() & bSpliterator.characteristics() 761 & ~(Spliterator.DISTINCT | Spliterator.SORTED 762 | (unsized ? Spliterator.SIZED | Spliterator.SUBSIZED : 0)); 763 } 764 else { 765 return bSpliterator.characteristics(); 766 } 767 } 768 769 @Override 770 public Comparator<? super T> getComparator() { 771 if (beforeSplit) 772 throw new IllegalStateException(); 773 return bSpliterator.getComparator(); 774 } 775 776 static class OfRef<T> extends ConcatSpliterator<T, Spliterator<T>> { 777 OfRef(Spliterator<T> aSpliterator, Spliterator<T> bSpliterator) { 778 super(aSpliterator, bSpliterator); 779 } 780 } 781 782 private static abstract class OfPrimitive<T, T_CONS, T_SPLITR extends Spliterator.OfPrimitive<T, T_CONS, T_SPLITR>> 783 extends ConcatSpliterator<T, T_SPLITR> 784 implements Spliterator.OfPrimitive<T, T_CONS, T_SPLITR> { 785 private OfPrimitive(T_SPLITR aSpliterator, T_SPLITR bSpliterator) { 786 super(aSpliterator, bSpliterator); 787 } 788 789 @Override 790 public boolean tryAdvance(T_CONS action) { 791 boolean hasNext; 792 if (beforeSplit) { 793 hasNext = aSpliterator.tryAdvance(action); 794 if (!hasNext) { 795 beforeSplit = false; 796 hasNext = bSpliterator.tryAdvance(action); 797 } 798 } 799 else 800 hasNext = bSpliterator.tryAdvance(action); 801 return hasNext; 802 } 803 804 @Override 805 public void forEachRemaining(T_CONS action) { 806 if (beforeSplit) 807 aSpliterator.forEachRemaining(action); 808 bSpliterator.forEachRemaining(action); 809 } 810 } 811 812 static class OfInt 813 extends ConcatSpliterator.OfPrimitive<Integer, IntConsumer, Spliterator.OfInt> 814 implements Spliterator.OfInt { 815 OfInt(Spliterator.OfInt aSpliterator, Spliterator.OfInt bSpliterator) { 816 super(aSpliterator, bSpliterator); 817 } 818 } 819 820 static class OfLong 821 extends ConcatSpliterator.OfPrimitive<Long, LongConsumer, Spliterator.OfLong> 822 implements Spliterator.OfLong { 823 OfLong(Spliterator.OfLong aSpliterator, Spliterator.OfLong bSpliterator) { 824 super(aSpliterator, bSpliterator); 825 } 826 } 827 828 static class OfDouble 829 extends ConcatSpliterator.OfPrimitive<Double, DoubleConsumer, Spliterator.OfDouble> 830 implements Spliterator.OfDouble { 831 OfDouble(Spliterator.OfDouble aSpliterator, Spliterator.OfDouble bSpliterator) { 832 super(aSpliterator, bSpliterator); 833 } 834 } 835 } 836 }