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