1 /*

     2  * Copyright (c) 2012, 2013, Oracle and/or its affiliates. All rights reserved.

     3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

     4  *

     5  * This code is free software; you can redistribute it and/or modify it

     6  * under the terms of the GNU General Public License version 2 only, as

     7  * published by the Free Software Foundation.  Oracle designates this

     8  * particular file as subject to the "Classpath" exception as provided

     9  * by Oracle in the LICENSE file that accompanied this code.

    10  *

    11  * This code is distributed in the hope that it will be useful, but WITHOUT

    12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

    13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

    14  * version 2 for more details (a copy is included in the LICENSE file that

    15  * accompanied this code).

    16  *

    17  * You should have received a copy of the GNU General Public License version

    18  * 2 along with this work; if not, write to the Free Software Foundation,

    19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

    20  *

    21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

    22  * or visit www.oracle.com if you need additional information or have any

    23  * questions.

    24  */

    25 package java.util.stream;

    26 

    27 import java.util.Comparator;

    28 import java.util.Iterator;

    29 import java.util.Objects;

    30 import java.util.Spliterator;

    31 import java.util.Spliterators;

    32 import java.util.function.BiFunction;

    33 import java.util.function.Consumer;

    34 import java.util.function.DoubleConsumer;

    35 import java.util.function.IntConsumer;

    36 import java.util.function.LongConsumer;

    37 

    38 /**

    39  * Utility methods for operating on and creating streams.

    40  *

    41  * <p>Unless otherwise stated, streams are created as sequential streams.  A

    42  * sequential stream can be transformed into a parallel stream by calling the

    43  * {@code parallel()} method on the created stream.

    44  *

    45  * @since 1.8

    46  */

    47 class Streams {

    48 

    49     private Streams() {

    50         throw new Error("no instances");

    51     }

    52 

    53     /**

    54      * An object instance representing no value, that cannot be an actual

    55      * data element of a stream.  Used when processing streams that can contain

    56      * {@code null} elements to distinguish between a {@code null} value and no

    57      * value.

    58      */

    59     static final Object NONE = new Object();

    60 

    61     /**

    62      * An {@code int} range spliterator.

    63      */

    64     static final class RangeIntSpliterator implements Spliterator.OfInt {

    65         private int from;

    66         private final int upTo;

    67         private final int step;

    68 

    69         RangeIntSpliterator(int from, int upTo, int step) {

    70             this.from = from;

    71             this.upTo = upTo;

    72             this.step = step;

    73         }

    74 

    75         @Override

    76         public boolean tryAdvance(IntConsumer consumer) {

    77             boolean hasNext = from < upTo;

    78             if (hasNext) {

    79                 consumer.accept(from);

    80                 from += step;

    81             }

    82             return hasNext;

    83         }

    84 

    85         @Override

    86         public void forEachRemaining(IntConsumer consumer) {

    87             int hUpTo = upTo;

    88             int hStep = step; // hoist accesses and checks from loop

    89             for (int i = from; i < hUpTo; i += hStep)

    90                 consumer.accept(i);

    91             from = upTo;

    92         }

    93 

    94         @Override

    95         public long estimateSize() {

    96             int d = upTo - from;

    97             return (d / step) + ((d % step == 0) ? 0 : 1);

    98         }

    99 

   100         @Override

   101         public int characteristics() {

   102             return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED |

   103                    Spliterator.IMMUTABLE | Spliterator.NONNULL |

   104                    Spliterator.DISTINCT | Spliterator.SORTED;

   105         }

   106 

   107         @Override

   108         public Comparator<? super Integer> getComparator() {

   109             return null;

   110         }

   111 

   112         @Override

   113         public Spliterator.OfInt trySplit() {

   114             return estimateSize() <= 1

   115                    ? null

   116                    : new RangeIntSpliterator(from, from = from + midPoint(), step);

   117         }

   118 

   119         private int midPoint() {

   120             // Size is known to be >= 2

   121             int bisection = (upTo - from) / 2;

   122             // If bisection > step then round down to nearest multiple of step

   123             // otherwise round up to step

   124             return bisection > step ? bisection - bisection % step : step;

   125         }

   126     }

   127 

   128     /**

   129      * A {@code long} range spliterator.

   130      */

   131     static final class RangeLongSpliterator implements Spliterator.OfLong {

   132         private long from;

   133         private final long upTo;

   134         private final long step;

   135 

   136         RangeLongSpliterator(long from, long upTo, long step) {

   137             this.from = from;

   138             this.upTo = upTo;

   139             this.step = step;

   140         }

   141 

   142         @Override

   143         public boolean tryAdvance(LongConsumer consumer) {

   144             boolean hasNext = from < upTo;

   145             if (hasNext) {

   146                 consumer.accept(from);

   147                 from += step;

   148             }

   149             return hasNext;

   150         }

   151 

   152         @Override

   153         public void forEachRemaining(LongConsumer consumer) {

   154             long hUpTo = upTo;

   155             long hStep = step; // hoist accesses and checks from loop

   156             for (long i = from; i < hUpTo; i += hStep)

   157                 consumer.accept(i);

   158             from = upTo;

   159         }

   160 

   161         @Override

   162         public long estimateSize() {

   163             long d = upTo - from;

   164             return (d / step) + ((d % step == 0) ? 0 : 1);

   165         }

   166 

   167         @Override

   168         public int characteristics() {

   169             return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED |

   170                    Spliterator.IMMUTABLE | Spliterator.NONNULL |

   171                    Spliterator.DISTINCT | Spliterator.SORTED;

   172         }

   173 

   174         @Override

   175         public Comparator<? super Long> getComparator() {

   176             return null;

   177         }

   178 

   179         @Override

   180         public Spliterator.OfLong trySplit() {

   181             return estimateSize() <= 1

   182                    ? null

   183                    : new RangeLongSpliterator(from, from = from + midPoint(), step);

   184         }

   185 

   186         private long midPoint() {

   187             // Size is known to be >= 2

   188             long bisection = (upTo - from) / 2;

   189             // If bisection > step then round down to nearest multiple of step

   190             // otherwise round up to step

   191             return bisection > step ? bisection - bisection % step : step;

   192         }

   193     }

   194 

   195     /**

   196      * A {@code double} range spliterator.

   197      *

   198      * <p>The traversing and splitting logic is equivalent to that of

   199      * {@code RangeLongSpliterator} for increasing values with a {@code step} of

   200      * {@code 1}.

   201      *

   202      *  <p>A {@code double} value is calculated from the function

   203      * {@code start + i * step} where {@code i} is the absolute position of the

   204      * value when traversing an instance of this class that has not been split.

   205      * This ensures the same values are produced at the same absolute positions

   206      * regardless of how an instance of this class is split or traversed.

   207      */

   208     static final class RangeDoubleSpliterator implements Spliterator.OfDouble {

   209         private final double from;

   210         private final double upTo;

   211         private final double step;

   212 

   213         private long lFrom;

   214         private final long lUpTo;

   215 

   216         RangeDoubleSpliterator(double from, double upTo, double step, long lFrom, long lUpTo) {

   217             this.from = from;

   218             this.upTo = upTo;

   219             this.step = step;

   220             this.lFrom = lFrom;

   221             this.lUpTo = lUpTo;

   222         }

   223 

   224         @Override

   225         public boolean tryAdvance(DoubleConsumer consumer) {

   226             boolean hasNext = lFrom < lUpTo;

   227             if (hasNext) {

   228                 consumer.accept(from + lFrom * step);

   229                 lFrom++;

   230             }

   231             return hasNext;

   232         }

   233 

   234         @Override

   235         public void forEachRemaining(DoubleConsumer consumer) {

   236             double hOrigin = from;

   237             double hStep = step;

   238             long hLUpTo = lUpTo;

   239             long i = lFrom;

   240             for (; i < hLUpTo; i++) {

   241                 consumer.accept(hOrigin + i * hStep);

   242             }

   243             lFrom = i;

   244         }

   245 

   246         @Override

   247         public long estimateSize() {

   248             return lUpTo - lFrom;

   249         }

   250 

   251         @Override

   252         public int characteristics() {

   253             return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED |

   254                    Spliterator.IMMUTABLE | Spliterator.NONNULL |

   255                    Spliterator.DISTINCT | Spliterator.SORTED;

   256         }

   257 

   258         @Override

   259         public Comparator<? super Double> getComparator() {

   260             return null;

   261         }

   262 

   263         @Override

   264         public Spliterator.OfDouble trySplit() {

   265             return estimateSize() <= 1

   266                    ? null

   267                    : new RangeDoubleSpliterator(from, upTo, step, lFrom, lFrom = lFrom + midPoint());

   268         }

   269 

   270         private long midPoint() {

   271             // Size is known to be >= 2

   272             return (lUpTo - lFrom) / 2;

   273         }

   274     }

   275 

   276     private static abstract class AbstractStreamBuilderImpl<T, S extends Spliterator<T>> implements Spliterator<T> {

   277         // >= 0 when building, < 0 when built

   278         // -1 == no elements

   279         // -2 == one element, held by first

   280         // -3 == two or more elements, held by buffer

   281         int count;

   282 

   283         // Spliterator implementation for 0 or 1 element

   284         // count == -1 for no elements

   285         // count == -2 for one element held by first

   286 

   287         @Override

   288         public S trySplit() {

   289             return null;

   290         }

   291 

   292         @Override

   293         public long estimateSize() {

   294             return -count - 1;

   295         }

   296 

   297         @Override

   298         public int characteristics() {

   299             return Spliterator.SIZED | Spliterator.SUBSIZED |

   300                    Spliterator.ORDERED | Spliterator.IMMUTABLE;

   301         }

   302     }

   303 

   304     static final class StreamBuilderImpl<T>

   305             extends AbstractStreamBuilderImpl<T, Spliterator<T>>

   306             implements StreamBuilder<T> {

   307         // The first element in the stream

   308         // valid if count == 1

   309         T first;

   310 

   311         // The first and subsequent elements in the stream

   312         // non-null if count == 2

   313         SpinedBuffer<T> buffer;

   314 

   315         /**

   316          * Constructor for building a stream of 0 or more elements.

   317          */

   318         StreamBuilderImpl() { }

   319 

   320         /**

   321          * Constructor for a singleton stream.

   322          *

   323          * @param t the single element

   324          */

   325         StreamBuilderImpl(T t) {

   326             first = t;

   327             count = -2;

   328         }

   329 

   330         // StreamBuilder implementation

   331 

   332         @Override

   333         public void accept(T t) {

   334             if (count == 0) {

   335                 first = t;

   336                 count++;

   337             }

   338             else if (count > 0) {

   339                 if (buffer == null) {

   340                     buffer = new SpinedBuffer<>();

   341                     buffer.accept(first);

   342                     count++;

   343                 }

   344 

   345                 buffer.accept(t);

   346             }

   347             else {

   348                 throw new IllegalStateException();

   349             }

   350         }

   351 

   352         public StreamBuilder<T> add(T t) {

   353             accept(t);

   354             return this;

   355         }

   356 

   357         @Override

   358         public Stream<T> build() {

   359             int c = count;

   360             if (c >= 0) {

   361                 // Switch count to negative value signalling the builder is built

   362                 count = -count - 1;

   363                 // Use this spliterator if 0 or 1 elements, otherwise use

   364                 // the spliterator of the spined buffer

   365                 return (c < 2) ? StreamSupport.stream(this) : StreamSupport.stream(buffer.spliterator());

   366             }

   367 

   368             throw new IllegalStateException();

   369         }

   370 

   371         // Spliterator implementation for 0 or 1 element

   372         // count == -1 for no elements

   373         // count == -2 for one element held by first

   374 

   375         @Override

   376         public boolean tryAdvance(Consumer<? super T> action) {

   377             if (count == -2) {

   378                 action.accept(first);

   379                 count = -1;

   380                 return true;

   381             }

   382             else {

   383                 return false;

   384             }

   385         }

   386 

   387         @Override

   388         public void forEachRemaining(Consumer<? super T> action) {

   389             if (count == -2) {

   390                 action.accept(first);

   391                 count = -1;

   392             }

   393         }

   394     }

   395 

   396     static final class IntStreamBuilderImpl

   397             extends AbstractStreamBuilderImpl<Integer, Spliterator.OfInt>

   398             implements StreamBuilder.OfInt, Spliterator.OfInt {

   399         // The first element in the stream

   400         // valid if count == 1

   401         int first;

   402 

   403         // The first and subsequent elements in the stream

   404         // non-null if count == 2

   405         SpinedBuffer.OfInt buffer;

   406 

   407         /**

   408          * Constructor for building a stream of 0 or more elements.

   409          */

   410         IntStreamBuilderImpl() { }

   411 

   412         /**

   413          * Constructor for a singleton stream.

   414          *

   415          * @param t the single element

   416          */

   417         IntStreamBuilderImpl(int t) {

   418             first = t;

   419             count = -2;

   420         }

   421 

   422         // StreamBuilder implementation

   423 

   424         @Override

   425         public void accept(int t) {

   426             if (count == 0) {

   427                 first = t;

   428                 count++;

   429             }

   430             else if (count > 0) {

   431                 if (buffer == null) {

   432                     buffer = new SpinedBuffer.OfInt();

   433                     buffer.accept(first);

   434                     count++;

   435                 }

   436 

   437                 buffer.accept(t);

   438             }

   439             else {

   440                 throw new IllegalStateException();

   441             }

   442         }

   443 

   444         @Override

   445         public IntStream build() {

   446             int c = count;

   447             if (c >= 0) {

   448                 // Switch count to negative value signalling the builder is built

   449                 count = -count - 1;

   450                 // Use this spliterator if 0 or 1 elements, otherwise use

   451                 // the spliterator of the spined buffer

   452                 return (c < 2) ? StreamSupport.intStream(this) : StreamSupport.intStream(buffer.spliterator());

   453             }

   454 

   455             throw new IllegalStateException();

   456         }

   457 

   458         // Spliterator implementation for 0 or 1 element

   459         // count == -1 for no elements

   460         // count == -2 for one element held by first

   461 

   462         @Override

   463         public boolean tryAdvance(IntConsumer action) {

   464             if (count == -2) {

   465                 action.accept(first);

   466                 count = -1;

   467                 return true;

   468             }

   469             else {

   470                 return false;

   471             }

   472         }

   473 

   474         @Override

   475         public void forEachRemaining(IntConsumer action) {

   476             if (count == -2) {

   477                 action.accept(first);

   478                 count = -1;

   479             }

   480         }

   481     }

   482 

   483     static final class LongStreamBuilderImpl

   484             extends AbstractStreamBuilderImpl<Long, Spliterator.OfLong>

   485             implements StreamBuilder.OfLong, Spliterator.OfLong {

   486         // The first element in the stream

   487         // valid if count == 1

   488         long first;

   489 

   490         // The first and subsequent elements in the stream

   491         // non-null if count == 2

   492         SpinedBuffer.OfLong buffer;

   493 

   494         /**

   495          * Constructor for building a stream of 0 or more elements.

   496          */

   497         LongStreamBuilderImpl() { }

   498 

   499         /**

   500          * Constructor for a singleton stream.

   501          *

   502          * @param t the single element

   503          */

   504         LongStreamBuilderImpl(long t) {

   505             first = t;

   506             count = -2;

   507         }

   508 

   509         // StreamBuilder implementation

   510 

   511         @Override

   512         public void accept(long t) {

   513             if (count == 0) {

   514                 first = t;

   515                 count++;

   516             }

   517             else if (count > 0) {

   518                 if (buffer == null) {

   519                     buffer = new SpinedBuffer.OfLong();

   520                     buffer.accept(first);

   521                     count++;

   522                 }

   523 

   524                 buffer.accept(t);

   525             }

   526             else {

   527                 throw new IllegalStateException();

   528             }

   529         }

   530 

   531         @Override

   532         public LongStream build() {

   533             int c = count;

   534             if (c >= 0) {

   535                 // Switch count to negative value signalling the builder is built

   536                 count = -count - 1;

   537                 // Use this spliterator if 0 or 1 elements, otherwise use

   538                 // the spliterator of the spined buffer

   539                 return (c < 2) ? StreamSupport.longStream(this) : StreamSupport.longStream(buffer.spliterator());

   540             }

   541 

   542             throw new IllegalStateException();

   543         }

   544 

   545         // Spliterator implementation for 0 or 1 element

   546         // count == -1 for no elements

   547         // count == -2 for one element held by first

   548 

   549         @Override

   550         public boolean tryAdvance(LongConsumer action) {

   551             if (count == -2) {

   552                 action.accept(first);

   553                 count = -1;

   554                 return true;

   555             }

   556             else {

   557                 return false;

   558             }

   559         }

   560 

   561         @Override

   562         public void forEachRemaining(LongConsumer action) {

   563             if (count == -2) {

   564                 action.accept(first);

   565                 count = -1;

   566             }

   567         }

   568     }

   569 

   570     static final class DoubleStreamBuilderImpl

   571             extends AbstractStreamBuilderImpl<Double, Spliterator.OfDouble>

   572             implements StreamBuilder.OfDouble, Spliterator.OfDouble {

   573         // The first element in the stream

   574         // valid if count == 1

   575         double first;

   576 

   577         // The first and subsequent elements in the stream

   578         // non-null if count == 2

   579         SpinedBuffer.OfDouble buffer;

   580 

   581         /**

   582          * Constructor for building a stream of 0 or more elements.

   583          */

   584         DoubleStreamBuilderImpl() { }

   585 

   586         /**

   587          * Constructor for a singleton stream.

   588          *

   589          * @param t the single element

   590          */

   591         DoubleStreamBuilderImpl(double t) {

   592             first = t;

   593             count = -2;

   594         }

   595 

   596         // StreamBuilder implementation

   597 

   598         @Override

   599         public void accept(double t) {

   600             if (count == 0) {

   601                 first = t;

   602                 count++;

   603             }

   604             else if (count > 0) {

   605                 if (buffer == null) {

   606                     buffer = new SpinedBuffer.OfDouble();

   607                     buffer.accept(first);

   608                     count++;

   609                 }

   610 

   611                 buffer.accept(t);

   612             }

   613             else {

   614                 throw new IllegalStateException();

   615             }

   616         }

   617 

   618         @Override

   619         public DoubleStream build() {

   620             int c = count;

   621             if (c >= 0) {

   622                 // Switch count to negative value signalling the builder is built

   623                 count = -count - 1;

   624                 // Use this spliterator if 0 or 1 elements, otherwise use

   625                 // the spliterator of the spined buffer

   626                 return (c < 2) ? StreamSupport.doubleStream(this) : StreamSupport.doubleStream(buffer.spliterator());

   627             }

   628 

   629             throw new IllegalStateException();

   630         }

   631 

   632         // Spliterator implementation for 0 or 1 element

   633         // count == -1 for no elements

   634         // count == -2 for one element held by first

   635 

   636         @Override

   637         public boolean tryAdvance(DoubleConsumer action) {

   638             if (count == -2) {

   639                 action.accept(first);

   640                 count = -1;

   641                 return true;

   642             }

   643             else {

   644                 return false;

   645             }

   646         }

   647 

   648         @Override

   649         public void forEachRemaining(DoubleConsumer action) {

   650             if (count == -2) {

   651                 action.accept(first);

   652                 count = -1;

   653             }

   654         }

   655     }

   656 }