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