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