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