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 }