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