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