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