View Javadoc
1   /*
2    * Copyright (C) 2015 The Guava Authors
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License"); you
5    * may not use this file except in compliance with the License.  You may
6    * obtain a copy of the License at
7    *
8    * http://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS,
12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
13   * implied.  See the License for the specific language governing
14   * permissions and limitations under the License.
15   */
16  
17  package com.google.common.collect;
18  
19  import static com.google.common.base.Preconditions.checkNotNull;
20  import static com.google.common.base.Preconditions.checkState;
21  
22  import com.google.common.annotations.Beta;
23  import com.google.common.annotations.GwtCompatible;
24  import com.google.common.math.LongMath;
25  import java.util.ArrayDeque;
26  import java.util.Collection;
27  import java.util.Deque;
28  import java.util.Iterator;
29  import java.util.OptionalDouble;
30  import java.util.OptionalInt;
31  import java.util.OptionalLong;
32  import java.util.PrimitiveIterator;
33  import java.util.Spliterator;
34  import java.util.Spliterators;
35  import java.util.Spliterators.AbstractSpliterator;
36  import java.util.function.BiConsumer;
37  import java.util.function.BiFunction;
38  import java.util.function.Consumer;
39  import java.util.function.DoubleConsumer;
40  import java.util.function.IntConsumer;
41  import java.util.function.LongConsumer;
42  import java.util.stream.DoubleStream;
43  import java.util.stream.IntStream;
44  import java.util.stream.LongStream;
45  import java.util.stream.Stream;
46  import java.util.stream.StreamSupport;
47  import javax.annotation.Nullable;
48  
49  /**
50   * Static utility methods related to {@code Stream} instances.
51   *
52   * @since 21.0
53   */
54  @Beta
55  @GwtCompatible
56  public final class Streams {
57    /**
58     * Returns a sequential {@link Stream} of the contents of {@code iterable}, delegating to {@link
59     * Collection#stream} if possible.
60     */
61    public static <T> Stream<T> stream(Iterable<T> iterable) {
62      return (iterable instanceof Collection)
63          ? ((Collection<T>) iterable).stream()
64          : StreamSupport.stream(iterable.spliterator(), false);
65    }
66  
67    /**
68     * Returns {@link Collection#stream}.
69     *
70     * @deprecated There is no reason to use this; just invoke {@code collection.stream()} directly.
71     */
72    @Deprecated
73    public static <T> Stream<T> stream(Collection<T> collection) {
74      return collection.stream();
75    }
76  
77    /**
78     * Returns a sequential {@link Stream} of the remaining contents of {@code iterator}. Do not use
79     * {@code iterator} directly after passing it to this method.
80     */
81    public static <T> Stream<T> stream(Iterator<T> iterator) {
82      return StreamSupport.stream(Spliterators.spliteratorUnknownSize(iterator, 0), false);
83    }
84  
85    /**
86     * If a value is present in {@code optional}, returns a stream containing only that element,
87     * otherwise returns an empty stream.
88     */
89    public static <T> Stream<T> stream(com.google.common.base.Optional<T> optional) {
90      return optional.isPresent() ? Stream.of(optional.get()) : Stream.of();
91    }
92  
93    /**
94     * If a value is present in {@code optional}, returns a stream containing only that element,
95     * otherwise returns an empty stream.
96     *
97     * <p><b>Java 9 users:</b> use {@code optional.stream()} instead.
98     */
99    public static <T> Stream<T> stream(java.util.Optional<T> optional) {
100     return optional.isPresent() ? Stream.of(optional.get()) : Stream.of();
101   }
102 
103   /**
104    * If a value is present in {@code optional}, returns a stream containing only that element,
105    * otherwise returns an empty stream.
106    *
107    * <p><b>Java 9 users:</b> use {@code optional.stream()} instead.
108    */
109   public static IntStream stream(OptionalInt optional) {
110     return optional.isPresent() ? IntStream.of(optional.getAsInt()) : IntStream.empty();
111   }
112 
113   /**
114    * If a value is present in {@code optional}, returns a stream containing only that element,
115    * otherwise returns an empty stream.
116    *
117    * <p><b>Java 9 users:</b> use {@code optional.stream()} instead.
118    */
119   public static LongStream stream(OptionalLong optional) {
120     return optional.isPresent() ? LongStream.of(optional.getAsLong()) : LongStream.empty();
121   }
122 
123   /**
124    * If a value is present in {@code optional}, returns a stream containing only that element,
125    * otherwise returns an empty stream.
126    *
127    * <p><b>Java 9 users:</b> use {@code optional.stream()} instead.
128    */
129   public static DoubleStream stream(OptionalDouble optional) {
130     return optional.isPresent() ? DoubleStream.of(optional.getAsDouble()) : DoubleStream.empty();
131   }
132 
133   /**
134    * Returns a {@link Stream} containing the elements of the first stream, followed by the elements
135    * of the second stream, and so on.
136    *
137    * <p>This is equivalent to {@code Stream.of(streams).flatMap(stream -> stream)}, but the returned
138    * stream may perform better.
139    *
140    * @see Stream#concat(Stream, Stream)
141    */
142   @SafeVarargs
143   public static <T> Stream<T> concat(Stream<? extends T>... streams) {
144     // TODO(lowasser): consider an implementation that can support SUBSIZED
145     boolean isParallel = false;
146     int characteristics = Spliterator.ORDERED | Spliterator.SIZED | Spliterator.NONNULL;
147     long estimatedSize = 0L;
148     ImmutableList.Builder<Spliterator<? extends T>> splitrsBuilder =
149         new ImmutableList.Builder<>(streams.length);
150     for (Stream<? extends T> stream : streams) {
151       isParallel |= stream.isParallel();
152       Spliterator<? extends T> splitr = stream.spliterator();
153       splitrsBuilder.add(splitr);
154       characteristics &= splitr.characteristics();
155       estimatedSize = LongMath.saturatedAdd(estimatedSize, splitr.estimateSize());
156     }
157     return StreamSupport.stream(
158             CollectSpliterators.flatMap(
159                 splitrsBuilder.build().spliterator(),
160                 splitr -> (Spliterator<T>) splitr,
161                 characteristics,
162                 estimatedSize),
163             isParallel)
164         .onClose(
165             () -> {
166               for (Stream<? extends T> stream : streams) {
167                 stream.close();
168               }
169             });
170   }
171 
172   /**
173    * Returns an {@link IntStream} containing the elements of the first stream, followed by the
174    * elements of the second stream, and so on.
175    *
176    * <p>This is equivalent to {@code Stream.of(streams).flatMapToInt(stream -> stream)}, but the
177    * returned stream may perform better.
178    *
179    * @see IntStream#concat(IntStream, IntStream)
180    */
181   public static IntStream concat(IntStream... streams) {
182     // TODO(lowasser): optimize this later
183     return Stream.of(streams).flatMapToInt(stream -> stream);
184   }
185 
186   /**
187    * Returns a {@link LongStream} containing the elements of the first stream, followed by the
188    * elements of the second stream, and so on.
189    *
190    * <p>This is equivalent to {@code Stream.of(streams).flatMapToLong(stream -> stream)}, but the
191    * returned stream may perform better.
192    *
193    * @see LongStream#concat(LongStream, LongStream)
194    */
195   public static LongStream concat(LongStream... streams) {
196     // TODO(lowasser): optimize this later
197     return Stream.of(streams).flatMapToLong(stream -> stream);
198   }
199 
200   /**
201    * Returns a {@link DoubleStream} containing the elements of the first stream, followed by the
202    * elements of the second stream, and so on.
203    *
204    * <p>This is equivalent to {@code Stream.of(streams).flatMapToDouble(stream -> stream)}, but the
205    * returned stream may perform better.
206    *
207    * @see DoubleStream#concat(DoubleStream, DoubleStream)
208    */
209   public static DoubleStream concat(DoubleStream... streams) {
210     // TODO(lowasser): optimize this later
211     return Stream.of(streams).flatMapToDouble(stream -> stream);
212   }
213 
214   /**
215    * Returns a stream in which each element is the result of passing the corresponding elementY of
216    * each of {@code streamA} and {@code streamB} to {@code function}.
217    *
218    * <p>For example:
219    *
220    * <pre>{@code
221    * Streams.zip(
222    *   Stream.of("foo1", "foo2", "foo3"),
223    *   Stream.of("bar1", "bar2"),
224    *   (arg1, arg2) -> arg1 + ":" + arg2)
225    * }</pre>
226    *
227    * <p>will return {@code Stream.of("foo1:bar1", "foo2:bar2")}.
228    *
229    * <p>The resulting stream will only be as long as the shorter of the two input streams; if one
230    * stream is longer, its extra elements will be ignored.
231    *
232    * <p>Note that if you are calling {@link Stream#forEach} on the resulting stream, you might want
233    * to consider using {@link #forEachPair} instead of this method.
234    *
235    * <p><b>Performance note:</b> The resulting stream is not <a
236    * href="http://gee.cs.oswego.edu/dl/html/StreamParallelGuidance.html">efficiently splittable</a>.
237    * This may harm parallel performance.
238    */
239   public static <A, B, R> Stream<R> zip(
240       Stream<A> streamA, Stream<B> streamB, BiFunction<? super A, ? super B, R> function) {
241     checkNotNull(streamA);
242     checkNotNull(streamB);
243     checkNotNull(function);
244     boolean isParallel = streamA.isParallel() || streamB.isParallel(); // same as Stream.concat
245     Spliterator<A> splitrA = streamA.spliterator();
246     Spliterator<B> splitrB = streamB.spliterator();
247     int characteristics =
248         splitrA.characteristics()
249             & splitrB.characteristics()
250             & (Spliterator.SIZED | Spliterator.ORDERED);
251     Iterator<A> itrA = Spliterators.iterator(splitrA);
252     Iterator<B> itrB = Spliterators.iterator(splitrB);
253     return StreamSupport.stream(
254             new AbstractSpliterator<R>(
255                 Math.min(splitrA.estimateSize(), splitrB.estimateSize()), characteristics) {
256               @Override
257               public boolean tryAdvance(Consumer<? super R> action) {
258                 if (itrA.hasNext() && itrB.hasNext()) {
259                   action.accept(function.apply(itrA.next(), itrB.next()));
260                   return true;
261                 }
262                 return false;
263               }
264             },
265             isParallel)
266         .onClose(streamA::close)
267         .onClose(streamB::close);
268   }
269 
270   /**
271    * Invokes {@code consumer} once for each pair of <i>corresponding</i> elements in {@code streamA}
272    * and {@code streamB}. If one stream is longer than the other, the extra elements are silently
273    * ignored. Elements passed to the consumer are guaranteed to come from the same position in their
274    * respective source streams. For example:
275    *
276    * <pre>{@code
277    * Streams.forEachPair(
278    *   Stream.of("foo1", "foo2", "foo3"),
279    *   Stream.of("bar1", "bar2"),
280    *   (arg1, arg2) -> System.out.println(arg1 + ":" + arg2)
281    * }</pre>
282    *
283    * <p>will print:
284    *
285    * <pre>{@code
286    * foo1:bar1
287    * foo2:bar2
288    * }</pre>
289    *
290    * <p><b>Warning:</b> If either supplied stream is a parallel stream, the same correspondence
291    * between elements will be made, but the order in which those pairs of elements are passed to the
292    * consumer is <i>not</i> defined.
293    *
294    * <p>Note that many usages of this method can be replaced with simpler calls to {@link #zip}.
295    * This method behaves equivalently to {@linkplain #zip zipping} the stream elements into
296    * temporary pair objects and then using {@link Stream#forEach} on that stream.
297    *
298    * @since 22.0
299    */
300   public static <A, B> void forEachPair(
301       Stream<A> streamA, Stream<B> streamB, BiConsumer<? super A, ? super B> consumer) {
302     checkNotNull(consumer);
303 
304     if (streamA.isParallel() || streamB.isParallel()) {
305       zip(streamA, streamB, TemporaryPair::new).forEach(pair -> consumer.accept(pair.a, pair.b));
306     } else {
307       Iterator<A> iterA = streamA.iterator();
308       Iterator<B> iterB = streamB.iterator();
309       while (iterA.hasNext() && iterB.hasNext()) {
310         consumer.accept(iterA.next(), iterB.next());
311       }
312     }
313   }
314 
315   // Use this carefully - it doesn't implement value semantics
316   private static class TemporaryPair<A, B> {
317     final A a;
318     final B b;
319 
320     TemporaryPair(A a, B b) {
321       this.a = a;
322       this.b = b;
323     }
324   }
325 
326   /**
327    * Returns a stream consisting of the results of applying the given function to the elements of
328    * {@code stream} and their indices in the stream. For example,
329    *
330    * <pre>{@code
331    * mapWithIndex(
332    *     Stream.of("a", "b", "c"),
333    *     (str, index) -> str + ":" + index)
334    * }</pre>
335    *
336    * <p>would return {@code Stream.of("a:0", "b:1", "c:2")}.
337    *
338    * <p>The resulting stream is <a
339    * href="http://gee.cs.oswego.edu/dl/html/StreamParallelGuidance.html">efficiently splittable</a>
340    * if and only if {@code stream} was efficiently splittable and its underlying spliterator
341    * reported {@link Spliterator#SUBSIZED}. This is generally the case if the underlying stream
342    * comes from a data structure supporting efficient indexed random access, typically an array or
343    * list.
344    *
345    * <p>The order of the resulting stream is defined if and only if the order of the original stream
346    * was defined.
347    */
348   public static <T, R> Stream<R> mapWithIndex(
349       Stream<T> stream, FunctionWithIndex<? super T, ? extends R> function) {
350     checkNotNull(stream);
351     checkNotNull(function);
352     boolean isParallel = stream.isParallel();
353     Spliterator<T> fromSpliterator = stream.spliterator();
354 
355     if (!fromSpliterator.hasCharacteristics(Spliterator.SUBSIZED)) {
356       Iterator<T> fromIterator = Spliterators.iterator(fromSpliterator);
357       return StreamSupport.stream(
358           new AbstractSpliterator<R>(
359               fromSpliterator.estimateSize(),
360               fromSpliterator.characteristics() & (Spliterator.ORDERED | Spliterator.SIZED)) {
361             long index = 0;
362 
363             @Override
364             public boolean tryAdvance(Consumer<? super R> action) {
365               if (fromIterator.hasNext()) {
366                 action.accept(function.apply(fromIterator.next(), index++));
367                 return true;
368               }
369               return false;
370             }
371           },
372           isParallel).onClose(stream::close);
373     }
374     class Splitr extends MapWithIndexSpliterator<Spliterator<T>, R, Splitr> implements Consumer<T> {
375       T holder;
376 
377       Splitr(Spliterator<T> splitr, long index) {
378         super(splitr, index);
379       }
380 
381       @Override
382       public void accept(@Nullable T t) {
383         this.holder = t;
384       }
385 
386       @Override
387       public boolean tryAdvance(Consumer<? super R> action) {
388         if (fromSpliterator.tryAdvance(this)) {
389           try {
390             action.accept(function.apply(holder, index++));
391             return true;
392           } finally {
393             holder = null;
394           }
395         }
396         return false;
397       }
398 
399       @Override
400       Splitr createSplit(Spliterator<T> from, long i) {
401         return new Splitr(from, i);
402       }
403     }
404     return StreamSupport.stream(new Splitr(fromSpliterator, 0), isParallel).onClose(stream::close);
405   }
406 
407   /**
408    * An analogue of {@link java.util.function.Function} also accepting an index.
409    *
410    * <p>This interface is only intended for use by callers of {@link #mapWithIndex(Stream,
411    * FunctionWithIndex)}.
412    *
413    * @since 21.0
414    */
415   @Beta
416   public interface FunctionWithIndex<T, R> {
417     /** Applies this function to the given argument and its index within a stream. */
418     R apply(T from, long index);
419   }
420 
421   private abstract static class MapWithIndexSpliterator<
422           F extends Spliterator<?>, R, S extends MapWithIndexSpliterator<F, R, S>>
423       implements Spliterator<R> {
424     final F fromSpliterator;
425     long index;
426 
427     MapWithIndexSpliterator(F fromSpliterator, long index) {
428       this.fromSpliterator = fromSpliterator;
429       this.index = index;
430     }
431 
432     abstract S createSplit(F from, long i);
433 
434     @Override
435     public S trySplit() {
436       @SuppressWarnings("unchecked")
437       F split = (F) fromSpliterator.trySplit();
438       if (split == null) {
439         return null;
440       }
441       S result = createSplit(split, index);
442       this.index += split.getExactSizeIfKnown();
443       return result;
444     }
445 
446     @Override
447     public long estimateSize() {
448       return fromSpliterator.estimateSize();
449     }
450 
451     @Override
452     public int characteristics() {
453       return fromSpliterator.characteristics()
454           & (Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED);
455     }
456   }
457 
458   /**
459    * Returns a stream consisting of the results of applying the given function to the elements of
460    * {@code stream} and their indexes in the stream. For example,
461    *
462    * <pre>{@code
463    * mapWithIndex(
464    *     IntStream.of(0, 1, 2),
465    *     (i, index) -> i + ":" + index)
466    * }</pre>
467    *
468    * <p>...would return {@code Stream.of("0:0", "1:1", "2:2")}.
469    *
470    * <p>The resulting stream is <a
471    * href="http://gee.cs.oswego.edu/dl/html/StreamParallelGuidance.html">efficiently splittable</a>
472    * if and only if {@code stream} was efficiently splittable and its underlying spliterator
473    * reported {@link Spliterator#SUBSIZED}. This is generally the case if the underlying stream
474    * comes from a data structure supporting efficient indexed random access, typically an array or
475    * list.
476    *
477    * <p>The order of the resulting stream is defined if and only if the order of the original stream
478    * was defined.
479    */
480   public static <R> Stream<R> mapWithIndex(IntStream stream, IntFunctionWithIndex<R> function) {
481     checkNotNull(stream);
482     checkNotNull(function);
483     boolean isParallel = stream.isParallel();
484     Spliterator.OfInt fromSpliterator = stream.spliterator();
485 
486     if (!fromSpliterator.hasCharacteristics(Spliterator.SUBSIZED)) {
487       PrimitiveIterator.OfInt fromIterator = Spliterators.iterator(fromSpliterator);
488       return StreamSupport.stream(
489               new AbstractSpliterator<R>(
490                   fromSpliterator.estimateSize(),
491                   fromSpliterator.characteristics() & (Spliterator.ORDERED | Spliterator.SIZED)) {
492                 long index = 0;
493 
494                 @Override
495                 public boolean tryAdvance(Consumer<? super R> action) {
496                   if (fromIterator.hasNext()) {
497                     action.accept(function.apply(fromIterator.nextInt(), index++));
498                     return true;
499                   }
500                   return false;
501                 }
502               },
503               isParallel)
504           .onClose(stream::close);
505     }
506     class Splitr extends MapWithIndexSpliterator<Spliterator.OfInt, R, Splitr>
507         implements IntConsumer, Spliterator<R> {
508       int holder;
509 
510       Splitr(Spliterator.OfInt splitr, long index) {
511         super(splitr, index);
512       }
513 
514       @Override
515       public void accept(int t) {
516         this.holder = t;
517       }
518 
519       @Override
520       public boolean tryAdvance(Consumer<? super R> action) {
521         if (fromSpliterator.tryAdvance(this)) {
522           action.accept(function.apply(holder, index++));
523           return true;
524         }
525         return false;
526       }
527 
528       @Override
529       Splitr createSplit(Spliterator.OfInt from, long i) {
530         return new Splitr(from, i);
531       }
532     }
533     return StreamSupport.stream(new Splitr(fromSpliterator, 0), isParallel).onClose(stream::close);
534   }
535 
536   /**
537    * An analogue of {@link java.util.function.IntFunction} also accepting an index.
538    *
539    * <p>This interface is only intended for use by callers of {@link #mapWithIndex(IntStream,
540    * IntFunctionWithIndex)}.
541    *
542    * @since 21.0
543    */
544   @Beta
545   public interface IntFunctionWithIndex<R> {
546     /** Applies this function to the given argument and its index within a stream. */
547     R apply(int from, long index);
548   }
549 
550   /**
551    * Returns a stream consisting of the results of applying the given function to the elements of
552    * {@code stream} and their indexes in the stream. For example,
553    *
554    * <pre>{@code
555    * mapWithIndex(
556    *     LongStream.of(0, 1, 2),
557    *     (i, index) -> i + ":" + index)
558    * }</pre>
559    *
560    * <p>...would return {@code Stream.of("0:0", "1:1", "2:2")}.
561    *
562    * <p>The resulting stream is <a
563    * href="http://gee.cs.oswego.edu/dl/html/StreamParallelGuidance.html">efficiently splittable</a>
564    * if and only if {@code stream} was efficiently splittable and its underlying spliterator
565    * reported {@link Spliterator#SUBSIZED}. This is generally the case if the underlying stream
566    * comes from a data structure supporting efficient indexed random access, typically an array or
567    * list.
568    *
569    * <p>The order of the resulting stream is defined if and only if the order of the original stream
570    * was defined.
571    */
572   public static <R> Stream<R> mapWithIndex(LongStream stream, LongFunctionWithIndex<R> function) {
573     checkNotNull(stream);
574     checkNotNull(function);
575     boolean isParallel = stream.isParallel();
576     Spliterator.OfLong fromSpliterator = stream.spliterator();
577 
578     if (!fromSpliterator.hasCharacteristics(Spliterator.SUBSIZED)) {
579       PrimitiveIterator.OfLong fromIterator = Spliterators.iterator(fromSpliterator);
580       return StreamSupport.stream(
581               new AbstractSpliterator<R>(
582                   fromSpliterator.estimateSize(),
583                   fromSpliterator.characteristics() & (Spliterator.ORDERED | Spliterator.SIZED)) {
584                 long index = 0;
585 
586                 @Override
587                 public boolean tryAdvance(Consumer<? super R> action) {
588                   if (fromIterator.hasNext()) {
589                     action.accept(function.apply(fromIterator.nextLong(), index++));
590                     return true;
591                   }
592                   return false;
593                 }
594               },
595               isParallel)
596           .onClose(stream::close);
597     }
598     class Splitr extends MapWithIndexSpliterator<Spliterator.OfLong, R, Splitr>
599         implements LongConsumer, Spliterator<R> {
600       long holder;
601 
602       Splitr(Spliterator.OfLong splitr, long index) {
603         super(splitr, index);
604       }
605 
606       @Override
607       public void accept(long t) {
608         this.holder = t;
609       }
610 
611       @Override
612       public boolean tryAdvance(Consumer<? super R> action) {
613         if (fromSpliterator.tryAdvance(this)) {
614           action.accept(function.apply(holder, index++));
615           return true;
616         }
617         return false;
618       }
619 
620       @Override
621       Splitr createSplit(Spliterator.OfLong from, long i) {
622         return new Splitr(from, i);
623       }
624     }
625     return StreamSupport.stream(new Splitr(fromSpliterator, 0), isParallel).onClose(stream::close);
626   }
627 
628   /**
629    * An analogue of {@link java.util.function.LongFunction} also accepting an index.
630    *
631    * <p>This interface is only intended for use by callers of {@link #mapWithIndex(LongStream,
632    * LongFunctionWithIndex)}.
633    *
634    * @since 21.0
635    */
636   @Beta
637   public interface LongFunctionWithIndex<R> {
638     /** Applies this function to the given argument and its index within a stream. */
639     R apply(long from, long index);
640   }
641 
642   /**
643    * Returns a stream consisting of the results of applying the given function to the elements of
644    * {@code stream} and their indexes in the stream. For example,
645    *
646    * <pre>{@code
647    * mapWithIndex(
648    *     DoubleStream.of(0, 1, 2),
649    *     (x, index) -> x + ":" + index)
650    * }</pre>
651    *
652    * <p>...would return {@code Stream.of("0.0:0", "1.0:1", "2.0:2")}.
653    *
654    * <p>The resulting stream is <a
655    * href="http://gee.cs.oswego.edu/dl/html/StreamParallelGuidance.html">efficiently splittable</a>
656    * if and only if {@code stream} was efficiently splittable and its underlying spliterator
657    * reported {@link Spliterator#SUBSIZED}. This is generally the case if the underlying stream
658    * comes from a data structure supporting efficient indexed random access, typically an array or
659    * list.
660    *
661    * <p>The order of the resulting stream is defined if and only if the order of the original stream
662    * was defined.
663    */
664   public static <R> Stream<R> mapWithIndex(
665       DoubleStream stream, DoubleFunctionWithIndex<R> function) {
666     checkNotNull(stream);
667     checkNotNull(function);
668     boolean isParallel = stream.isParallel();
669     Spliterator.OfDouble fromSpliterator = stream.spliterator();
670 
671     if (!fromSpliterator.hasCharacteristics(Spliterator.SUBSIZED)) {
672       PrimitiveIterator.OfDouble fromIterator = Spliterators.iterator(fromSpliterator);
673       return StreamSupport.stream(
674               new AbstractSpliterator<R>(
675                   fromSpliterator.estimateSize(),
676                   fromSpliterator.characteristics() & (Spliterator.ORDERED | Spliterator.SIZED)) {
677                 long index = 0;
678 
679                 @Override
680                 public boolean tryAdvance(Consumer<? super R> action) {
681                   if (fromIterator.hasNext()) {
682                     action.accept(function.apply(fromIterator.nextDouble(), index++));
683                     return true;
684                   }
685                   return false;
686                 }
687               },
688               isParallel)
689           .onClose(stream::close);
690     }
691     class Splitr extends MapWithIndexSpliterator<Spliterator.OfDouble, R, Splitr>
692         implements DoubleConsumer, Spliterator<R> {
693       double holder;
694 
695       Splitr(Spliterator.OfDouble splitr, long index) {
696         super(splitr, index);
697       }
698 
699       @Override
700       public void accept(double t) {
701         this.holder = t;
702       }
703 
704       @Override
705       public boolean tryAdvance(Consumer<? super R> action) {
706         if (fromSpliterator.tryAdvance(this)) {
707           action.accept(function.apply(holder, index++));
708           return true;
709         }
710         return false;
711       }
712 
713       @Override
714       Splitr createSplit(Spliterator.OfDouble from, long i) {
715         return new Splitr(from, i);
716       }
717     }
718     return StreamSupport.stream(new Splitr(fromSpliterator, 0), isParallel).onClose(stream::close);
719   }
720 
721   /**
722    * An analogue of {@link java.util.function.DoubleFunction} also accepting an index.
723    *
724    * <p>This interface is only intended for use by callers of {@link #mapWithIndex(DoubleStream,
725    * DoubleFunctionWithIndex)}.
726    *
727    * @since 21.0
728    */
729   @Beta
730   public interface DoubleFunctionWithIndex<R> {
731     /** Applies this function to the given argument and its index within a stream. */
732     R apply(double from, long index);
733   }
734 
735   /**
736    * Returns the last element of the specified stream, or {@link java.util.Optional#empty} if the
737    * stream is empty.
738    *
739    * <p>Equivalent to {@code stream.reduce((a, b) -> b)}, but may perform significantly better. This
740    * method's runtime will be between O(log n) and O(n), performing better on <a
741    * href="http://gee.cs.oswego.edu/dl/html/StreamParallelGuidance.html">efficiently splittable</a>
742    * streams.
743    *
744    * <p>If the stream has nondeterministic order, this has equivalent semantics to {@link
745    * Stream#findAny} (which you might as well use).
746    *
747    * @see Stream#findFirst()
748    * @throws NullPointerException if the last element of the stream is null
749    */
750   public static <T> java.util.Optional<T> findLast(Stream<T> stream) {
751     class OptionalState {
752       boolean set = false;
753       T value = null;
754 
755       void set(@Nullable T value) {
756         this.set = true;
757         this.value = value;
758       }
759 
760       T get() {
761         checkState(set);
762         return value;
763       }
764     }
765     OptionalState state = new OptionalState();
766 
767     Deque<Spliterator<T>> splits = new ArrayDeque<>();
768     splits.addLast(stream.spliterator());
769 
770     while (!splits.isEmpty()) {
771       Spliterator<T> spliterator = splits.removeLast();
772 
773       if (spliterator.getExactSizeIfKnown() == 0) {
774         continue; // drop this split
775       }
776 
777       // Many spliterators will have trySplits that are SUBSIZED even if they are not themselves
778       // SUBSIZED.
779       if (spliterator.hasCharacteristics(Spliterator.SUBSIZED)) {
780         // we can drill down to exactly the smallest nonempty spliterator
781         while (true) {
782           Spliterator<T> prefix = spliterator.trySplit();
783           if (prefix == null || prefix.getExactSizeIfKnown() == 0) {
784             break;
785           } else if (spliterator.getExactSizeIfKnown() == 0) {
786             spliterator = prefix;
787             break;
788           }
789         }
790 
791         // spliterator is known to be nonempty now
792         spliterator.forEachRemaining(state::set);
793         return java.util.Optional.of(state.get());
794       }
795 
796       Spliterator<T> prefix = spliterator.trySplit();
797       if (prefix == null || prefix.getExactSizeIfKnown() == 0) {
798         // we can't split this any further
799         spliterator.forEachRemaining(state::set);
800         if (state.set) {
801           return java.util.Optional.of(state.get());
802         }
803         // fall back to the last split
804         continue;
805       }
806       splits.addLast(prefix);
807       splits.addLast(spliterator);
808     }
809     return java.util.Optional.empty();
810   }
811 
812   /**
813    * Returns the last element of the specified stream, or {@link OptionalInt#empty} if the stream is
814    * empty.
815    *
816    * <p>Equivalent to {@code stream.reduce((a, b) -> b)}, but may perform significantly better. This
817    * method's runtime will be between O(log n) and O(n), performing better on <a
818    * href="http://gee.cs.oswego.edu/dl/html/StreamParallelGuidance.html">efficiently splittable</a>
819    * streams.
820    *
821    * @see IntStream#findFirst()
822    * @throws NullPointerException if the last element of the stream is null
823    */
824   public static OptionalInt findLast(IntStream stream) {
825     // findLast(Stream) does some allocation, so we might as well box some more
826     java.util.Optional<Integer> boxedLast = findLast(stream.boxed());
827     return boxedLast.isPresent() ? OptionalInt.of(boxedLast.get()) : OptionalInt.empty();
828   }
829 
830   /**
831    * Returns the last element of the specified stream, or {@link OptionalLong#empty} if the stream
832    * is empty.
833    *
834    * <p>Equivalent to {@code stream.reduce((a, b) -> b)}, but may perform significantly better. This
835    * method's runtime will be between O(log n) and O(n), performing better on <a
836    * href="http://gee.cs.oswego.edu/dl/html/StreamParallelGuidance.html">efficiently splittable</a>
837    * streams.
838    *
839    * @see LongStream#findFirst()
840    * @throws NullPointerException if the last element of the stream is null
841    */
842   public static OptionalLong findLast(LongStream stream) {
843     // findLast(Stream) does some allocation, so we might as well box some more
844     java.util.Optional<Long> boxedLast = findLast(stream.boxed());
845     return boxedLast.isPresent() ? OptionalLong.of(boxedLast.get()) : OptionalLong.empty();
846   }
847 
848   /**
849    * Returns the last element of the specified stream, or {@link OptionalDouble#empty} if the stream
850    * is empty.
851    *
852    * <p>Equivalent to {@code stream.reduce((a, b) -> b)}, but may perform significantly better. This
853    * method's runtime will be between O(log n) and O(n), performing better on <a
854    * href="http://gee.cs.oswego.edu/dl/html/StreamParallelGuidance.html">efficiently splittable</a>
855    * streams.
856    *
857    * @see DoubleStream#findFirst()
858    * @throws NullPointerException if the last element of the stream is null
859    */
860   public static OptionalDouble findLast(DoubleStream stream) {
861     // findLast(Stream) does some allocation, so we might as well box some more
862     java.util.Optional<Double> boxedLast = findLast(stream.boxed());
863     return boxedLast.isPresent() ? OptionalDouble.of(boxedLast.get()) : OptionalDouble.empty();
864   }
865 
866   private Streams() {}
867 }