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