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