Source code

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