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