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