001/*
002 * Copyright (C) 2015 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License"); you
005 * may not use this file except in compliance with the License.  You may
006 * obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
013 * implied.  See the License for the specific language governing
014 * permissions and limitations under the License.
015 */
016
017package com.google.common.collect;
018
019import static com.google.common.base.Preconditions.checkNotNull;
020import static com.google.common.collect.NullnessCasts.uncheckedCastNullableTToT;
021import static java.lang.Math.min;
022import static java.util.Objects.requireNonNull;
023
024import com.google.common.annotations.Beta;
025import com.google.common.annotations.GwtCompatible;
026import com.google.common.math.LongMath;
027import com.google.errorprone.annotations.InlineMe;
028import com.google.errorprone.annotations.InlineMeValidationDisabled;
029import java.util.ArrayDeque;
030import java.util.Collection;
031import java.util.Deque;
032import java.util.Iterator;
033import java.util.OptionalDouble;
034import java.util.OptionalInt;
035import java.util.OptionalLong;
036import java.util.PrimitiveIterator;
037import java.util.Spliterator;
038import java.util.Spliterators;
039import java.util.Spliterators.AbstractSpliterator;
040import java.util.function.BiConsumer;
041import java.util.function.BiFunction;
042import java.util.function.Consumer;
043import java.util.function.DoubleConsumer;
044import java.util.function.IntConsumer;
045import java.util.function.LongConsumer;
046import java.util.stream.BaseStream;
047import java.util.stream.DoubleStream;
048import java.util.stream.IntStream;
049import java.util.stream.LongStream;
050import java.util.stream.Stream;
051import java.util.stream.StreamSupport;
052import javax.annotation.CheckForNull;
053import org.checkerframework.checker.nullness.qual.Nullable;
054
055/**
056 * Static utility methods related to {@code Stream} instances.
057 *
058 * @since 21.0 (but only since 33.4.0 in the Android flavor)
059 */
060@GwtCompatible
061@ElementTypesAreNonnullByDefault
062public final class Streams {
063  /**
064   * Returns a sequential {@link Stream} of the contents of {@code iterable}, delegating to {@link
065   * Collection#stream} if possible.
066   */
067  public static <T extends @Nullable Object> Stream<T> stream(Iterable<T> iterable) {
068    return (iterable instanceof Collection)
069        ? ((Collection<T>) iterable).stream()
070        : StreamSupport.stream(iterable.spliterator(), false);
071  }
072
073  /**
074   * Returns {@link Collection#stream}.
075   *
076   * @deprecated There is no reason to use this; just invoke {@code collection.stream()} directly.
077   */
078  @Deprecated
079  @InlineMe(replacement = "collection.stream()")
080  public static <T extends @Nullable Object> Stream<T> stream(Collection<T> collection) {
081    return collection.stream();
082  }
083
084  /**
085   * Returns a sequential {@link Stream} of the remaining contents of {@code iterator}. Do not use
086   * {@code iterator} directly after passing it to this method.
087   */
088  public static <T extends @Nullable Object> Stream<T> stream(Iterator<T> iterator) {
089    return StreamSupport.stream(Spliterators.spliteratorUnknownSize(iterator, 0), false);
090  }
091
092  /**
093   * If a value is present in {@code optional}, returns a stream containing only that element,
094   * otherwise returns an empty stream.
095   */
096  public static <T> Stream<T> stream(com.google.common.base.Optional<T> optional) {
097    return optional.isPresent() ? Stream.of(optional.get()) : Stream.empty();
098  }
099
100  /**
101   * If a value is present in {@code optional}, returns a stream containing only that element,
102   * otherwise returns an empty stream.
103   *
104   * <p><b>Java 9 users:</b> use {@code optional.stream()} instead.
105   */
106  @Beta
107  @InlineMe(replacement = "optional.stream()")
108  @InlineMeValidationDisabled("Java 9+ API only")
109  public static <T> Stream<T> stream(java.util.Optional<T> optional) {
110    return optional.isPresent() ? Stream.of(optional.get()) : Stream.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  @Beta
120  @InlineMe(replacement = "optional.stream()")
121  @InlineMeValidationDisabled("Java 9+ API only")
122  public static IntStream stream(OptionalInt optional) {
123    return optional.isPresent() ? IntStream.of(optional.getAsInt()) : IntStream.empty();
124  }
125
126  /**
127   * If a value is present in {@code optional}, returns a stream containing only that element,
128   * otherwise returns an empty stream.
129   *
130   * <p><b>Java 9 users:</b> use {@code optional.stream()} instead.
131   */
132  @Beta
133  @InlineMe(replacement = "optional.stream()")
134  @InlineMeValidationDisabled("Java 9+ API only")
135  public static LongStream stream(OptionalLong optional) {
136    return optional.isPresent() ? LongStream.of(optional.getAsLong()) : LongStream.empty();
137  }
138
139  /**
140   * If a value is present in {@code optional}, returns a stream containing only that element,
141   * otherwise returns an empty stream.
142   *
143   * <p><b>Java 9 users:</b> use {@code optional.stream()} instead.
144   */
145  @Beta
146  @InlineMe(replacement = "optional.stream()")
147  @InlineMeValidationDisabled("Java 9+ API only")
148  public static DoubleStream stream(OptionalDouble optional) {
149    return optional.isPresent() ? DoubleStream.of(optional.getAsDouble()) : DoubleStream.empty();
150  }
151
152  @SuppressWarnings("CatchingUnchecked") // sneaky checked exception
153  private static void closeAll(BaseStream<?, ?>[] toClose) {
154    // If one of the streams throws an exception, continue closing the others, then throw the
155    // exception later. If more than one stream throws an exception, the later ones are added to the
156    // first as suppressed exceptions. We don't catch Error on the grounds that it should be allowed
157    // to propagate immediately.
158    Exception exception = null;
159    for (BaseStream<?, ?> stream : toClose) {
160      try {
161        stream.close();
162      } catch (Exception e) { // sneaky checked exception
163        if (exception == null) {
164          exception = e;
165        } else {
166          exception.addSuppressed(e);
167        }
168      }
169    }
170    if (exception != null) {
171      // Normally this is a RuntimeException that doesn't need sneakyThrow.
172      // But theoretically we could see sneaky checked exception
173      sneakyThrow(exception);
174    }
175  }
176
177  /** Throws an undeclared checked exception. */
178  private static void sneakyThrow(Throwable t) {
179    class SneakyThrower<T extends Throwable> {
180      @SuppressWarnings("unchecked") // not really safe, but that's the point
181      void throwIt(Throwable t) throws T {
182        throw (T) t;
183      }
184    }
185    new SneakyThrower<Error>().throwIt(t);
186  }
187
188  /**
189   * Returns a {@link Stream} containing the elements of the first stream, followed by the elements
190   * of the second stream, and so on.
191   *
192   * <p>This is equivalent to {@code Stream.of(streams).flatMap(stream -> stream)}, but the returned
193   * stream may perform better.
194   *
195   * @see Stream#concat(Stream, Stream)
196   */
197  @SuppressWarnings("unchecked") // could probably be avoided with a forwarding Spliterator
198  @SafeVarargs
199  public static <T extends @Nullable Object> Stream<T> concat(Stream<? extends T>... streams) {
200    // TODO(lowasser): consider an implementation that can support SUBSIZED
201    boolean isParallel = false;
202    int characteristics = Spliterator.ORDERED | Spliterator.SIZED | Spliterator.NONNULL;
203    long estimatedSize = 0L;
204    ImmutableList.Builder<Spliterator<? extends T>> splitrsBuilder =
205        new ImmutableList.Builder<>(streams.length);
206    for (Stream<? extends T> stream : streams) {
207      isParallel |= stream.isParallel();
208      Spliterator<? extends T> splitr = stream.spliterator();
209      splitrsBuilder.add(splitr);
210      characteristics &= splitr.characteristics();
211      estimatedSize = LongMath.saturatedAdd(estimatedSize, splitr.estimateSize());
212    }
213    return StreamSupport.stream(
214            CollectSpliterators.flatMap(
215                splitrsBuilder.build().spliterator(),
216                splitr -> (Spliterator<T>) splitr,
217                characteristics,
218                estimatedSize),
219            isParallel)
220        .onClose(() -> closeAll(streams));
221  }
222
223  /**
224   * Returns an {@link IntStream} containing the elements of the first stream, followed by the
225   * elements of the second stream, and so on.
226   *
227   * <p>This is equivalent to {@code Stream.of(streams).flatMapToInt(stream -> stream)}, but the
228   * returned stream may perform better.
229   *
230   * @see IntStream#concat(IntStream, IntStream)
231   */
232  public static IntStream concat(IntStream... streams) {
233    boolean isParallel = false;
234    int characteristics = Spliterator.ORDERED | Spliterator.SIZED | Spliterator.NONNULL;
235    long estimatedSize = 0L;
236    ImmutableList.Builder<Spliterator.OfInt> splitrsBuilder =
237        new ImmutableList.Builder<>(streams.length);
238    for (IntStream stream : streams) {
239      isParallel |= stream.isParallel();
240      Spliterator.OfInt splitr = stream.spliterator();
241      splitrsBuilder.add(splitr);
242      characteristics &= splitr.characteristics();
243      estimatedSize = LongMath.saturatedAdd(estimatedSize, splitr.estimateSize());
244    }
245    return StreamSupport.intStream(
246            CollectSpliterators.flatMapToInt(
247                splitrsBuilder.build().spliterator(),
248                splitr -> splitr,
249                characteristics,
250                estimatedSize),
251            isParallel)
252        .onClose(() -> closeAll(streams));
253  }
254
255  /**
256   * Returns a {@link LongStream} containing the elements of the first stream, followed by the
257   * elements of the second stream, and so on.
258   *
259   * <p>This is equivalent to {@code Stream.of(streams).flatMapToLong(stream -> stream)}, but the
260   * returned stream may perform better.
261   *
262   * @see LongStream#concat(LongStream, LongStream)
263   */
264  public static LongStream concat(LongStream... streams) {
265    boolean isParallel = false;
266    int characteristics = Spliterator.ORDERED | Spliterator.SIZED | Spliterator.NONNULL;
267    long estimatedSize = 0L;
268    ImmutableList.Builder<Spliterator.OfLong> splitrsBuilder =
269        new ImmutableList.Builder<>(streams.length);
270    for (LongStream stream : streams) {
271      isParallel |= stream.isParallel();
272      Spliterator.OfLong splitr = stream.spliterator();
273      splitrsBuilder.add(splitr);
274      characteristics &= splitr.characteristics();
275      estimatedSize = LongMath.saturatedAdd(estimatedSize, splitr.estimateSize());
276    }
277    return StreamSupport.longStream(
278            CollectSpliterators.flatMapToLong(
279                splitrsBuilder.build().spliterator(),
280                splitr -> splitr,
281                characteristics,
282                estimatedSize),
283            isParallel)
284        .onClose(() -> closeAll(streams));
285  }
286
287  /**
288   * Returns a {@link DoubleStream} containing the elements of the first stream, followed by the
289   * elements of the second stream, and so on.
290   *
291   * <p>This is equivalent to {@code Stream.of(streams).flatMapToDouble(stream -> stream)}, but the
292   * returned stream may perform better.
293   *
294   * @see DoubleStream#concat(DoubleStream, DoubleStream)
295   */
296  public static DoubleStream concat(DoubleStream... streams) {
297    boolean isParallel = false;
298    int characteristics = Spliterator.ORDERED | Spliterator.SIZED | Spliterator.NONNULL;
299    long estimatedSize = 0L;
300    ImmutableList.Builder<Spliterator.OfDouble> splitrsBuilder =
301        new ImmutableList.Builder<>(streams.length);
302    for (DoubleStream stream : streams) {
303      isParallel |= stream.isParallel();
304      Spliterator.OfDouble splitr = stream.spliterator();
305      splitrsBuilder.add(splitr);
306      characteristics &= splitr.characteristics();
307      estimatedSize = LongMath.saturatedAdd(estimatedSize, splitr.estimateSize());
308    }
309    return StreamSupport.doubleStream(
310            CollectSpliterators.flatMapToDouble(
311                splitrsBuilder.build().spliterator(),
312                splitr -> splitr,
313                characteristics,
314                estimatedSize),
315            isParallel)
316        .onClose(() -> closeAll(streams));
317  }
318
319  /**
320   * Returns a stream in which each element is the result of passing the corresponding element of
321   * each of {@code streamA} and {@code streamB} to {@code function}.
322   *
323   * <p>For example:
324   *
325   * <pre>{@code
326   * Streams.zip(
327   *   Stream.of("foo1", "foo2", "foo3"),
328   *   Stream.of("bar1", "bar2"),
329   *   (arg1, arg2) -> arg1 + ":" + arg2)
330   * }</pre>
331   *
332   * <p>will return {@code Stream.of("foo1:bar1", "foo2:bar2")}.
333   *
334   * <p>The resulting stream will only be as long as the shorter of the two input streams; if one
335   * stream is longer, its extra elements will be ignored.
336   *
337   * <p>Note that if you are calling {@link Stream#forEach} on the resulting stream, you might want
338   * to consider using {@link #forEachPair} instead of this method.
339   *
340   * <p><b>Performance note:</b> The resulting stream is not <a
341   * href="http://gee.cs.oswego.edu/dl/html/StreamParallelGuidance.html">efficiently splittable</a>.
342   * This may harm parallel performance.
343   */
344  @Beta
345  public static <A extends @Nullable Object, B extends @Nullable Object, R extends @Nullable Object>
346      Stream<R> zip(
347          Stream<A> streamA, Stream<B> streamB, BiFunction<? super A, ? super B, R> function) {
348    checkNotNull(streamA);
349    checkNotNull(streamB);
350    checkNotNull(function);
351    boolean isParallel = streamA.isParallel() || streamB.isParallel(); // same as Stream.concat
352    Spliterator<A> splitrA = streamA.spliterator();
353    Spliterator<B> splitrB = streamB.spliterator();
354    int characteristics =
355        splitrA.characteristics()
356            & splitrB.characteristics()
357            & (Spliterator.SIZED | Spliterator.ORDERED);
358    Iterator<A> itrA = Spliterators.iterator(splitrA);
359    Iterator<B> itrB = Spliterators.iterator(splitrB);
360    return StreamSupport.stream(
361            new AbstractSpliterator<R>(
362                min(splitrA.estimateSize(), splitrB.estimateSize()), characteristics) {
363              @Override
364              public boolean tryAdvance(Consumer<? super R> action) {
365                if (itrA.hasNext() && itrB.hasNext()) {
366                  action.accept(function.apply(itrA.next(), itrB.next()));
367                  return true;
368                }
369                return false;
370              }
371            },
372            isParallel)
373        .onClose(streamA::close)
374        .onClose(streamB::close);
375  }
376
377  /**
378   * Invokes {@code consumer} once for each pair of <i>corresponding</i> elements in {@code streamA}
379   * and {@code streamB}. If one stream is longer than the other, the extra elements are silently
380   * ignored. Elements passed to the consumer are guaranteed to come from the same position in their
381   * respective source streams. For example:
382   *
383   * <pre>{@code
384   * Streams.forEachPair(
385   *   Stream.of("foo1", "foo2", "foo3"),
386   *   Stream.of("bar1", "bar2"),
387   *   (arg1, arg2) -> System.out.println(arg1 + ":" + arg2)
388   * }</pre>
389   *
390   * <p>will print:
391   *
392   * <pre>{@code
393   * foo1:bar1
394   * foo2:bar2
395   * }</pre>
396   *
397   * <p><b>Warning:</b> If either supplied stream is a parallel stream, the same correspondence
398   * between elements will be made, but the order in which those pairs of elements are passed to the
399   * consumer is <i>not</i> defined.
400   *
401   * <p>Note that many usages of this method can be replaced with simpler calls to {@link #zip}.
402   * This method behaves equivalently to {@linkplain #zip zipping} the stream elements into
403   * temporary pair objects and then using {@link Stream#forEach} on that stream.
404   *
405   * @since 22.0 (but only since 33.4.0 in the Android flavor)
406   */
407  @Beta
408  public static <A extends @Nullable Object, B extends @Nullable Object> void forEachPair(
409      Stream<A> streamA, Stream<B> streamB, BiConsumer<? super A, ? super B> consumer) {
410    checkNotNull(consumer);
411
412    if (streamA.isParallel() || streamB.isParallel()) {
413      zip(streamA, streamB, TemporaryPair::new).forEach(pair -> consumer.accept(pair.a, pair.b));
414    } else {
415      Iterator<A> iterA = streamA.iterator();
416      Iterator<B> iterB = streamB.iterator();
417      while (iterA.hasNext() && iterB.hasNext()) {
418        consumer.accept(iterA.next(), iterB.next());
419      }
420    }
421  }
422
423  // Use this carefully - it doesn't implement value semantics
424  private static class TemporaryPair<A extends @Nullable Object, B extends @Nullable Object> {
425    @ParametricNullness final A a;
426    @ParametricNullness final B b;
427
428    TemporaryPair(@ParametricNullness A a, @ParametricNullness B b) {
429      this.a = a;
430      this.b = b;
431    }
432  }
433
434  /**
435   * Returns a stream consisting of the results of applying the given function to the elements of
436   * {@code stream} and their indices in the stream. For example,
437   *
438   * <pre>{@code
439   * mapWithIndex(
440   *     Stream.of("a", "b", "c"),
441   *     (e, index) -> index + ":" + e)
442   * }</pre>
443   *
444   * <p>would return {@code Stream.of("0:a", "1:b", "2:c")}.
445   *
446   * <p>The resulting stream is <a
447   * href="http://gee.cs.oswego.edu/dl/html/StreamParallelGuidance.html">efficiently splittable</a>
448   * if and only if {@code stream} was efficiently splittable and its underlying spliterator
449   * reported {@link Spliterator#SUBSIZED}. This is generally the case if the underlying stream
450   * comes from a data structure supporting efficient indexed random access, typically an array or
451   * list.
452   *
453   * <p>The order of the resulting stream is defined if and only if the order of the original stream
454   * was defined.
455   */
456  public static <T extends @Nullable Object, R extends @Nullable Object> Stream<R> mapWithIndex(
457      Stream<T> stream, FunctionWithIndex<? super T, ? extends R> function) {
458    checkNotNull(stream);
459    checkNotNull(function);
460    boolean isParallel = stream.isParallel();
461    Spliterator<T> fromSpliterator = stream.spliterator();
462
463    if (!fromSpliterator.hasCharacteristics(Spliterator.SUBSIZED)) {
464      Iterator<T> fromIterator = Spliterators.iterator(fromSpliterator);
465      return StreamSupport.stream(
466              new AbstractSpliterator<R>(
467                  fromSpliterator.estimateSize(),
468                  fromSpliterator.characteristics() & (Spliterator.ORDERED | Spliterator.SIZED)) {
469                long index = 0;
470
471                @Override
472                public boolean tryAdvance(Consumer<? super R> action) {
473                  if (fromIterator.hasNext()) {
474                    action.accept(function.apply(fromIterator.next(), index++));
475                    return true;
476                  }
477                  return false;
478                }
479              },
480              isParallel)
481          .onClose(stream::close);
482    }
483    class Splitr extends MapWithIndexSpliterator<Spliterator<T>, R, Splitr> implements Consumer<T> {
484      @CheckForNull T holder;
485
486      Splitr(Spliterator<T> splitr, long index) {
487        super(splitr, index);
488      }
489
490      @Override
491      public void accept(@ParametricNullness T t) {
492        this.holder = t;
493      }
494
495      @Override
496      public boolean tryAdvance(Consumer<? super R> action) {
497        if (fromSpliterator.tryAdvance(this)) {
498          try {
499            // The cast is safe because tryAdvance puts a T into `holder`.
500            action.accept(function.apply(uncheckedCastNullableTToT(holder), index++));
501            return true;
502          } finally {
503            holder = null;
504          }
505        }
506        return false;
507      }
508
509      @Override
510      Splitr createSplit(Spliterator<T> from, long i) {
511        return new Splitr(from, i);
512      }
513    }
514    return StreamSupport.stream(new Splitr(fromSpliterator, 0), isParallel).onClose(stream::close);
515  }
516
517  /**
518   * Returns a stream consisting of the results of applying the given function to the elements of
519   * {@code stream} and their indexes in the stream. For example,
520   *
521   * <pre>{@code
522   * mapWithIndex(
523   *     IntStream.of(10, 11, 12),
524   *     (e, index) -> index + ":" + e)
525   * }</pre>
526   *
527   * <p>...would return {@code Stream.of("0:10", "1:11", "2:12")}.
528   *
529   * <p>The resulting stream is <a
530   * href="http://gee.cs.oswego.edu/dl/html/StreamParallelGuidance.html">efficiently splittable</a>
531   * if and only if {@code stream} was efficiently splittable and its underlying spliterator
532   * reported {@link Spliterator#SUBSIZED}. This is generally the case if the underlying stream
533   * comes from a data structure supporting efficient indexed random access, typically an array or
534   * list.
535   *
536   * <p>The order of the resulting stream is defined if and only if the order of the original stream
537   * was defined.
538   */
539  public static <R extends @Nullable Object> Stream<R> mapWithIndex(
540      IntStream stream, IntFunctionWithIndex<R> function) {
541    checkNotNull(stream);
542    checkNotNull(function);
543    boolean isParallel = stream.isParallel();
544    Spliterator.OfInt fromSpliterator = stream.spliterator();
545
546    if (!fromSpliterator.hasCharacteristics(Spliterator.SUBSIZED)) {
547      PrimitiveIterator.OfInt fromIterator = Spliterators.iterator(fromSpliterator);
548      return StreamSupport.stream(
549              new AbstractSpliterator<R>(
550                  fromSpliterator.estimateSize(),
551                  fromSpliterator.characteristics() & (Spliterator.ORDERED | Spliterator.SIZED)) {
552                long index = 0;
553
554                @Override
555                public boolean tryAdvance(Consumer<? super R> action) {
556                  if (fromIterator.hasNext()) {
557                    action.accept(function.apply(fromIterator.nextInt(), index++));
558                    return true;
559                  }
560                  return false;
561                }
562              },
563              isParallel)
564          .onClose(stream::close);
565    }
566    class Splitr extends MapWithIndexSpliterator<Spliterator.OfInt, R, Splitr>
567        implements IntConsumer, Spliterator<R> {
568      int holder;
569
570      Splitr(Spliterator.OfInt splitr, long index) {
571        super(splitr, index);
572      }
573
574      @Override
575      public void accept(int t) {
576        this.holder = t;
577      }
578
579      @Override
580      public boolean tryAdvance(Consumer<? super R> action) {
581        if (fromSpliterator.tryAdvance(this)) {
582          action.accept(function.apply(holder, index++));
583          return true;
584        }
585        return false;
586      }
587
588      @Override
589      Splitr createSplit(Spliterator.OfInt from, long i) {
590        return new Splitr(from, i);
591      }
592    }
593    return StreamSupport.stream(new Splitr(fromSpliterator, 0), isParallel).onClose(stream::close);
594  }
595
596  /**
597   * Returns a stream consisting of the results of applying the given function to the elements of
598   * {@code stream} and their indexes in the stream. For example,
599   *
600   * <pre>{@code
601   * mapWithIndex(
602   *     LongStream.of(10, 11, 12),
603   *     (e, index) -> index + ":" + e)
604   * }</pre>
605   *
606   * <p>...would return {@code Stream.of("0:10", "1:11", "2:12")}.
607   *
608   * <p>The resulting stream is <a
609   * href="http://gee.cs.oswego.edu/dl/html/StreamParallelGuidance.html">efficiently splittable</a>
610   * if and only if {@code stream} was efficiently splittable and its underlying spliterator
611   * reported {@link Spliterator#SUBSIZED}. This is generally the case if the underlying stream
612   * comes from a data structure supporting efficient indexed random access, typically an array or
613   * list.
614   *
615   * <p>The order of the resulting stream is defined if and only if the order of the original stream
616   * was defined.
617   */
618  public static <R extends @Nullable Object> Stream<R> mapWithIndex(
619      LongStream stream, LongFunctionWithIndex<R> function) {
620    checkNotNull(stream);
621    checkNotNull(function);
622    boolean isParallel = stream.isParallel();
623    Spliterator.OfLong fromSpliterator = stream.spliterator();
624
625    if (!fromSpliterator.hasCharacteristics(Spliterator.SUBSIZED)) {
626      PrimitiveIterator.OfLong fromIterator = Spliterators.iterator(fromSpliterator);
627      return StreamSupport.stream(
628              new AbstractSpliterator<R>(
629                  fromSpliterator.estimateSize(),
630                  fromSpliterator.characteristics() & (Spliterator.ORDERED | Spliterator.SIZED)) {
631                long index = 0;
632
633                @Override
634                public boolean tryAdvance(Consumer<? super R> action) {
635                  if (fromIterator.hasNext()) {
636                    action.accept(function.apply(fromIterator.nextLong(), index++));
637                    return true;
638                  }
639                  return false;
640                }
641              },
642              isParallel)
643          .onClose(stream::close);
644    }
645    class Splitr extends MapWithIndexSpliterator<Spliterator.OfLong, R, Splitr>
646        implements LongConsumer, Spliterator<R> {
647      long holder;
648
649      Splitr(Spliterator.OfLong splitr, long index) {
650        super(splitr, index);
651      }
652
653      @Override
654      public void accept(long t) {
655        this.holder = t;
656      }
657
658      @Override
659      public boolean tryAdvance(Consumer<? super R> action) {
660        if (fromSpliterator.tryAdvance(this)) {
661          action.accept(function.apply(holder, index++));
662          return true;
663        }
664        return false;
665      }
666
667      @Override
668      Splitr createSplit(Spliterator.OfLong from, long i) {
669        return new Splitr(from, i);
670      }
671    }
672    return StreamSupport.stream(new Splitr(fromSpliterator, 0), isParallel).onClose(stream::close);
673  }
674
675  /**
676   * Returns a stream consisting of the results of applying the given function to the elements of
677   * {@code stream} and their indexes in the stream. For example,
678   *
679   * <pre>{@code
680   * mapWithIndex(
681   *     DoubleStream.of(0.0, 1.0, 2.0)
682   *     (e, index) -> index + ":" + e)
683   * }</pre>
684   *
685   * <p>...would return {@code Stream.of("0:0.0", "1:1.0", "2:2.0")}.
686   *
687   * <p>The resulting stream is <a
688   * href="http://gee.cs.oswego.edu/dl/html/StreamParallelGuidance.html">efficiently splittable</a>
689   * if and only if {@code stream} was efficiently splittable and its underlying spliterator
690   * reported {@link Spliterator#SUBSIZED}. This is generally the case if the underlying stream
691   * comes from a data structure supporting efficient indexed random access, typically an array or
692   * list.
693   *
694   * <p>The order of the resulting stream is defined if and only if the order of the original stream
695   * was defined.
696   */
697  public static <R extends @Nullable Object> Stream<R> mapWithIndex(
698      DoubleStream stream, DoubleFunctionWithIndex<R> function) {
699    checkNotNull(stream);
700    checkNotNull(function);
701    boolean isParallel = stream.isParallel();
702    Spliterator.OfDouble fromSpliterator = stream.spliterator();
703
704    if (!fromSpliterator.hasCharacteristics(Spliterator.SUBSIZED)) {
705      PrimitiveIterator.OfDouble fromIterator = Spliterators.iterator(fromSpliterator);
706      return StreamSupport.stream(
707              new AbstractSpliterator<R>(
708                  fromSpliterator.estimateSize(),
709                  fromSpliterator.characteristics() & (Spliterator.ORDERED | Spliterator.SIZED)) {
710                long index = 0;
711
712                @Override
713                public boolean tryAdvance(Consumer<? super R> action) {
714                  if (fromIterator.hasNext()) {
715                    action.accept(function.apply(fromIterator.nextDouble(), index++));
716                    return true;
717                  }
718                  return false;
719                }
720              },
721              isParallel)
722          .onClose(stream::close);
723    }
724    class Splitr extends MapWithIndexSpliterator<Spliterator.OfDouble, R, Splitr>
725        implements DoubleConsumer, Spliterator<R> {
726      double holder;
727
728      Splitr(Spliterator.OfDouble splitr, long index) {
729        super(splitr, index);
730      }
731
732      @Override
733      public void accept(double t) {
734        this.holder = t;
735      }
736
737      @Override
738      public boolean tryAdvance(Consumer<? super R> action) {
739        if (fromSpliterator.tryAdvance(this)) {
740          action.accept(function.apply(holder, index++));
741          return true;
742        }
743        return false;
744      }
745
746      @Override
747      Splitr createSplit(Spliterator.OfDouble from, long i) {
748        return new Splitr(from, i);
749      }
750    }
751    return StreamSupport.stream(new Splitr(fromSpliterator, 0), isParallel).onClose(stream::close);
752  }
753
754  /**
755   * An analogue of {@link java.util.function.Function} also accepting an index.
756   *
757   * <p>This interface is only intended for use by callers of {@link #mapWithIndex(Stream,
758   * FunctionWithIndex)}.
759   *
760   * @since 21.0 (but only since 33.4.0 in the Android flavor)
761   */
762  public interface FunctionWithIndex<T extends @Nullable Object, R extends @Nullable Object> {
763    /** Applies this function to the given argument and its index within a stream. */
764    @ParametricNullness
765    R apply(@ParametricNullness T from, long index);
766  }
767
768  private abstract static class MapWithIndexSpliterator<
769          F extends Spliterator<?>,
770          R extends @Nullable Object,
771          S extends MapWithIndexSpliterator<F, R, S>>
772      implements Spliterator<R> {
773    final F fromSpliterator;
774    long index;
775
776    MapWithIndexSpliterator(F fromSpliterator, long index) {
777      this.fromSpliterator = fromSpliterator;
778      this.index = index;
779    }
780
781    abstract S createSplit(F from, long i);
782
783    @Override
784    @CheckForNull
785    public S trySplit() {
786      Spliterator<?> splitOrNull = fromSpliterator.trySplit();
787      if (splitOrNull == null) {
788        return null;
789      }
790      @SuppressWarnings("unchecked")
791      F split = (F) splitOrNull;
792      S result = createSplit(split, index);
793      this.index += split.getExactSizeIfKnown();
794      return result;
795    }
796
797    @Override
798    public long estimateSize() {
799      return fromSpliterator.estimateSize();
800    }
801
802    @Override
803    public int characteristics() {
804      return fromSpliterator.characteristics()
805          & (Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED);
806    }
807  }
808
809  /**
810   * An analogue of {@link java.util.function.IntFunction} also accepting an index.
811   *
812   * <p>This interface is only intended for use by callers of {@link #mapWithIndex(IntStream,
813   * IntFunctionWithIndex)}.
814   *
815   * @since 21.0 (but only since 33.4.0 in the Android flavor)
816   */
817  public interface IntFunctionWithIndex<R extends @Nullable Object> {
818    /** Applies this function to the given argument and its index within a stream. */
819    @ParametricNullness
820    R apply(int from, long index);
821  }
822
823  /**
824   * An analogue of {@link java.util.function.LongFunction} also accepting an index.
825   *
826   * <p>This interface is only intended for use by callers of {@link #mapWithIndex(LongStream,
827   * LongFunctionWithIndex)}.
828   *
829   * @since 21.0 (but only since 33.4.0 in the Android flavor)
830   */
831  public interface LongFunctionWithIndex<R extends @Nullable Object> {
832    /** Applies this function to the given argument and its index within a stream. */
833    @ParametricNullness
834    R apply(long from, long index);
835  }
836
837  /**
838   * An analogue of {@link java.util.function.DoubleFunction} also accepting an index.
839   *
840   * <p>This interface is only intended for use by callers of {@link #mapWithIndex(DoubleStream,
841   * DoubleFunctionWithIndex)}.
842   *
843   * @since 21.0 (but only since 33.4.0 in the Android flavor)
844   */
845  public interface DoubleFunctionWithIndex<R extends @Nullable Object> {
846    /** Applies this function to the given argument and its index within a stream. */
847    @ParametricNullness
848    R apply(double from, long index);
849  }
850
851  /**
852   * Returns the last element of the specified stream, or {@link java.util.Optional#empty} if the
853   * stream is empty.
854   *
855   * <p>Equivalent to {@code stream.reduce((a, b) -> b)}, but may perform significantly better. This
856   * method's runtime will be between O(log n) and O(n), performing better on <a
857   * href="http://gee.cs.oswego.edu/dl/html/StreamParallelGuidance.html">efficiently splittable</a>
858   * streams.
859   *
860   * <p>If the stream has nondeterministic order, this has equivalent semantics to {@link
861   * Stream#findAny} (which you might as well use).
862   *
863   * @see Stream#findFirst()
864   * @throws NullPointerException if the last element of the stream is null
865   */
866  /*
867   * By declaring <T> instead of <T extends @Nullable Object>, we declare this method as requiring a
868   * stream whose elements are non-null. However, the method goes out of its way to still handle
869   * nulls in the stream. This means that the method can safely be used with a stream that contains
870   * nulls as long as the *last* element is *not* null.
871   *
872   * (To "go out of its way," the method tracks a `set` bit so that it can distinguish "the final
873   * split has a last element of null, so throw NPE" from "the final split was empty, so look for an
874   * element in the prior one.")
875   */
876  public static <T> java.util.Optional<T> findLast(Stream<T> stream) {
877    class OptionalState {
878      boolean set = false;
879      @CheckForNull T value = null;
880
881      void set(T value) {
882        this.set = true;
883        this.value = value;
884      }
885
886      T get() {
887        /*
888         * requireNonNull is safe because we call get() only if we've previously called set().
889         *
890         * (For further discussion of nullness, see the comment above the method.)
891         */
892        return requireNonNull(value);
893      }
894    }
895    OptionalState state = new OptionalState();
896
897    Deque<Spliterator<T>> splits = new ArrayDeque<>();
898    splits.addLast(stream.spliterator());
899
900    while (!splits.isEmpty()) {
901      Spliterator<T> spliterator = splits.removeLast();
902
903      if (spliterator.getExactSizeIfKnown() == 0) {
904        continue; // drop this split
905      }
906
907      // Many spliterators will have trySplits that are SUBSIZED even if they are not themselves
908      // SUBSIZED.
909      if (spliterator.hasCharacteristics(Spliterator.SUBSIZED)) {
910        // we can drill down to exactly the smallest nonempty spliterator
911        while (true) {
912          Spliterator<T> prefix = spliterator.trySplit();
913          if (prefix == null || prefix.getExactSizeIfKnown() == 0) {
914            break;
915          } else if (spliterator.getExactSizeIfKnown() == 0) {
916            spliterator = prefix;
917            break;
918          }
919        }
920
921        // spliterator is known to be nonempty now
922        spliterator.forEachRemaining(state::set);
923        return java.util.Optional.of(state.get());
924      }
925
926      Spliterator<T> prefix = spliterator.trySplit();
927      if (prefix == null || prefix.getExactSizeIfKnown() == 0) {
928        // we can't split this any further
929        spliterator.forEachRemaining(state::set);
930        if (state.set) {
931          return java.util.Optional.of(state.get());
932        }
933        // fall back to the last split
934        continue;
935      }
936      splits.addLast(prefix);
937      splits.addLast(spliterator);
938    }
939    return java.util.Optional.empty();
940  }
941
942  /**
943   * Returns the last element of the specified stream, or {@link OptionalInt#empty} if the stream is
944   * empty.
945   *
946   * <p>Equivalent to {@code stream.reduce((a, b) -> b)}, but may perform significantly better. This
947   * method's runtime will be between O(log n) and O(n), performing better on <a
948   * href="http://gee.cs.oswego.edu/dl/html/StreamParallelGuidance.html">efficiently splittable</a>
949   * streams.
950   *
951   * @see IntStream#findFirst()
952   * @throws NullPointerException if the last element of the stream is null
953   */
954  public static OptionalInt findLast(IntStream stream) {
955    // findLast(Stream) does some allocation, so we might as well box some more
956    java.util.Optional<Integer> boxedLast = findLast(stream.boxed());
957    return boxedLast.map(OptionalInt::of).orElse(OptionalInt.empty());
958  }
959
960  /**
961   * Returns the last element of the specified stream, or {@link OptionalLong#empty} if the stream
962   * is empty.
963   *
964   * <p>Equivalent to {@code stream.reduce((a, b) -> b)}, but may perform significantly better. This
965   * method's runtime will be between O(log n) and O(n), performing better on <a
966   * href="http://gee.cs.oswego.edu/dl/html/StreamParallelGuidance.html">efficiently splittable</a>
967   * streams.
968   *
969   * @see LongStream#findFirst()
970   * @throws NullPointerException if the last element of the stream is null
971   */
972  public static OptionalLong findLast(LongStream stream) {
973    // findLast(Stream) does some allocation, so we might as well box some more
974    java.util.Optional<Long> boxedLast = findLast(stream.boxed());
975    return boxedLast.map(OptionalLong::of).orElse(OptionalLong.empty());
976  }
977
978  /**
979   * Returns the last element of the specified stream, or {@link OptionalDouble#empty} if the stream
980   * is empty.
981   *
982   * <p>Equivalent to {@code stream.reduce((a, b) -> b)}, but may perform significantly better. This
983   * method's runtime will be between O(log n) and O(n), performing better on <a
984   * href="http://gee.cs.oswego.edu/dl/html/StreamParallelGuidance.html">efficiently splittable</a>
985   * streams.
986   *
987   * @see DoubleStream#findFirst()
988   * @throws NullPointerException if the last element of the stream is null
989   */
990  public static OptionalDouble findLast(DoubleStream stream) {
991    // findLast(Stream) does some allocation, so we might as well box some more
992    java.util.Optional<Double> boxedLast = findLast(stream.boxed());
993    return boxedLast.map(OptionalDouble::of).orElse(OptionalDouble.empty());
994  }
995
996  private Streams() {}
997}