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