1 /*

     2  * Copyright (c) 2013, 2019, 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;

    26 

    27 import java.util.Spliterator;

    28 import java.util.function.Consumer;

    29 import java.util.function.IntConsumer;

    30 import java.util.function.LongConsumer;

    31 import java.util.function.DoubleConsumer;

    32 import java.util.stream.StreamSupport;

    33 import java.util.stream.Stream;

    34 

    35 /**

    36  * This class provides much of the implementation of the

    37  * {@code ArbitrarilyJumpableRng} interface, to minimize the effort

    38  * required to implement that interface.

    39  *

    40  * To implement a pseudorandom number generator, the programmer needs

    41  * only to extend this class and provide implementations for the

    42  * methods {@code nextInt()}, {@code nextLong()}, {@code copy()},

    43  * {@code jump(distance)}, {@code jumpPowerOfTwo(distance)},

    44  * {@code defaultJumpDistance()}, and {@code defaultLeapDistance()}.

    45  *

    46  * (If the pseudorandom number generator also has the ability to split,

    47  * then the programmer may wish to consider instead extending

    48  * {@code AbstractSplittableArbitrarilyJumpableRng}.)

    49  *

    50  * The programmer should generally provide at least three constructors:

    51  * one that takes no arguments, one that accepts a {@code long}

    52  * seed value, and one that accepts an array of seed {@code byte} values.

    53  * This class provides a public {@code initialSeed()} method that may

    54  * be useful in initializing some static state from which to derive

    55  * defaults seeds for use by the no-argument constructor.

    56  *

    57  * For the stream methods (such as {@code ints()} and {@code splits()}),

    58  * this class provides {@code Spliterator}-based implementations that

    59  * allow parallel execution when appropriate.  In this respect

    60  * {@code ArbitrarilyJumpableRng} differs from {@code JumpableRng},

    61  * which provides very simple implementations that produce

    62  * sequential streams only.

    63  *

    64  * <p>An implementation of the {@code AbstractArbitrarilyJumpableRng} class

    65  * must provide concrete definitions for the methods {@code nextInt()},

    66  * {@code nextLong}, {@code period()}, {@code copy()}, {@code jump(double)},

    67  * {@code defaultJumpDistance()}, and {@code defaultLeapDistance()}.

    68  * Default implementations are provided for all other methods.

    69  *

    70  * The documentation for each non-abstract method in this class

    71  * describes its implementation in detail. Each of these methods may

    72  * be overridden if the pseudorandom number generator being

    73  * implemented admits a more efficient implementation.

    74  *

    75  * @author  Guy Steele

    76  * @since   1.9

    77  */

    78 public abstract class AbstractArbitrarilyJumpableRng

    79     extends AbstractSpliteratorRng implements ArbitrarilyJumpableRng {

    80 

    81     /*

    82      * Implementation Overview.

    83      *

    84      * This class provides most of the "user API" methods needed to satisfy

    85      * the interface java.util.ArbitrarilyJumpableRng.  Most of these methods

    86      * are in turn inherited from AbstractRng and the non-public class

    87      * AbstractSpliteratorRng; this file implements four versions of the

    88      * jumps method and defines the spliterators necessary to support them.

    89      *

    90      * File organization: First the non-public methods needed by the class

    91      * AbstractSpliteratorRng, then the main public methods, followed by some

    92      * custom spliterator classes needed for stream methods.

    93      */

    94 

    95     // IllegalArgumentException messages

    96     static final String BadLogDistance  = "logDistance must be non-negative";

    97 

    98     // Methods required by class AbstractSpliteratorRng

    99     Spliterator.OfInt makeIntsSpliterator(long index, long fence, int origin, int bound) {

   100 	return new RandomIntsSpliterator(this, index, fence, origin, bound);

   101     }

   102     Spliterator.OfLong makeLongsSpliterator(long index, long fence, long origin, long bound) {

   103 	return new RandomLongsSpliterator(this, index, fence, origin, bound);

   104     }

   105     Spliterator.OfDouble makeDoublesSpliterator(long index, long fence, double origin, double bound) {

   106 	return new RandomDoublesSpliterator(this, index, fence, origin, bound);

   107     }

   108 

   109     // Similar methods used by this class

   110     Spliterator<Rng> makeJumpsSpliterator(long index, long fence, double distance) {

   111 	return new RandomJumpsSpliterator(this, index, fence, distance);

   112     }

   113     Spliterator<JumpableRng> makeLeapsSpliterator(long index, long fence, double distance) {

   114 	return new RandomLeapsSpliterator(this, index, fence, distance);

   115     }

   116     Spliterator<ArbitrarilyJumpableRng> makeArbitraryJumpsSpliterator(long index, long fence, double distance) {

   117 	return new RandomArbitraryJumpsSpliterator(this, index, fence, distance);

   118     }

   119 

   120     /* ---------------- public methods ---------------- */

   121 

   122     /**

   123      * Returns a new generator whose internal state is an exact copy

   124      * of this generator (therefore their future behavior should be

   125      * identical if subjected to the same series of operations).

   126      *

   127      * @return a new object that is a copy of this generator

   128      */

   129     public abstract AbstractArbitrarilyJumpableRng copy();

   130 

   131     // Stream methods for jumping

   132 

   133     /**

   134      * Returns an effectively unlimited stream of new pseudorandom

   135      * number generators, each of which implements the {@code Rng}

   136      * interface, produced by jumping copies of this generator

   137      * by different integer multiples of the default jump distance.

   138      *

   139      * @implNote This method is implemented to be equivalent to

   140      * {@code jumps(Long.MAX_VALUE)}.

   141      *

   142      * @return a stream of objects that implement the {@code Rng} interface

   143      */

   144     public Stream<Rng> jumps() {

   145         return StreamSupport.stream

   146             (makeJumpsSpliterator(0L, Long.MAX_VALUE, defaultJumpDistance()),

   147              false);

   148     }

   149 

   150     /**

   151      * Returns a stream producing the given {@code streamSize} number of

   152      * new pseudorandom number generators, each of which implements the

   153      * {@code Rng} interface, produced by jumping copies of this generator

   154      * by different integer multiples of the default jump distance.

   155      *

   156      * @param streamSize the number of generators to generate

   157      * @return a stream of objects that implement the {@code Rng} interface

   158      * @throws IllegalArgumentException if {@code streamSize} is

   159      *         less than zero

   160      */

   161     public Stream<Rng> jumps(long streamSize) {

   162         return StreamSupport.stream

   163             (makeJumpsSpliterator(0L, streamSize, defaultJumpDistance()),

   164              false);

   165     }

   166 

   167     /**

   168      * Returns an effectively unlimited stream of new pseudorandom

   169      * number generators, each of which implements the {@code Rng}

   170      * interface, produced by jumping copies of this generator

   171      * by different integer multiples of the specified jump distance.

   172      *

   173      * @implNote This method is implemented to be equivalent to

   174      * {@code jumps(Long.MAX_VALUE)}.

   175      *

   176      * @param distance a distance to jump forward within the state cycle

   177      * @return a stream of objects that implement the {@code Rng} interface

   178      */

   179     public Stream<ArbitrarilyJumpableRng> jumps(double distance) {

   180         return StreamSupport.stream

   181             (makeArbitraryJumpsSpliterator(0L, Long.MAX_VALUE, distance),

   182              false);

   183     }

   184 

   185     /**

   186      * Returns a stream producing the given {@code streamSize} number of

   187      * new pseudorandom number generators, each of which implements the

   188      * {@code Rng} interface, produced by jumping copies of this generator

   189      * by different integer multiples of the specified jump distance.

   190      *

   191      * @param streamSize the number of generators to generate

   192      * @param distance a distance to jump forward within the state cycle

   193      * @return a stream of objects that implement the {@code Rng} interface

   194      * @throws IllegalArgumentException if {@code streamSize} is

   195      *         less than zero

   196      */

   197     public Stream<ArbitrarilyJumpableRng> jumps(long streamSize, double distance) {

   198 	RngSupport.checkStreamSize(streamSize);

   199         return StreamSupport.stream

   200             (makeArbitraryJumpsSpliterator(0L, streamSize, distance),

   201              false);

   202     }

   203 

   204     /**

   205      * Alter the state of this pseudorandom number generator so as to

   206      * jump forward a very large, fixed distance (typically 2<sup>128</sup>

   207      * or more) within its state cycle.  The distance used is that

   208      * returned by method {@code defaultLeapDistance()}.

   209      */

   210     public void leap() { jump(defaultLeapDistance()); }

   211 

   212     // Stream methods for leaping

   213 

   214     /**

   215      * Returns an effectively unlimited stream of new pseudorandom

   216      * number generators, each of which implements the {@code Rng}

   217      * interface, produced by jumping copies of this generator

   218      * by different integer multiples of the default leap distance.

   219      *

   220      * @implNote This method is implemented to be equivalent to

   221      * {@code leaps(Long.MAX_VALUE)}.

   222      *

   223      * @return a stream of objects that implement the {@code Rng} interface

   224      */

   225     public Stream<JumpableRng> leaps() {

   226         return StreamSupport.stream

   227             (makeLeapsSpliterator(0L, Long.MAX_VALUE, defaultLeapDistance()),

   228              false);

   229     }

   230 

   231     /**

   232      * Returns a stream producing the given {@code streamSize} number of

   233      * new pseudorandom number generators, each of which implements the

   234      * {@code Rng} interface, produced by jumping copies of this generator

   235      * by different integer multiples of the default leap distance.

   236      *

   237      * @param streamSize the number of generators to generate

   238      * @return a stream of objects that implement the {@code Rng} interface

   239      * @throws IllegalArgumentException if {@code streamSize} is

   240      *         less than zero

   241      */

   242     public Stream<JumpableRng> leaps(long streamSize) {

   243         return StreamSupport.stream

   244             (makeLeapsSpliterator(0L, streamSize, defaultLeapDistance()),

   245              false);

   246     }

   247 

   248     

   249     /**

   250      * Spliterator for int streams.  We multiplex the four int

   251      * versions into one class by treating a bound less than origin as

   252      * unbounded, and also by treating "infinite" as equivalent to

   253      * Long.MAX_VALUE. For splits, we choose to override the method

   254      * {@code trySplit()} to try to optimize execution speed: instead of

   255      * dividing a range in half, it breaks off the largest possible chunk

   256      * whose size is a power of two such that the remaining chunk is not

   257      * empty.  In this way, the necessary jump distances will tend to be

   258      * powers of two.  The long and double versions of this class are

   259      * identical except for types.

   260      */

   261     static class RandomIntsSpliterator extends RngSupport.RandomSpliterator implements Spliterator.OfInt {

   262 	final ArbitrarilyJumpableRng generatingRng;

   263         final int origin;

   264         final int bound;

   265 

   266         RandomIntsSpliterator(ArbitrarilyJumpableRng generatingRng, long index, long fence, int origin, int bound) {

   267 	    super(index, fence);

   268 	    this.origin = origin; this.bound = bound;

   269 	    this.generatingRng = generatingRng;

   270         }

   271 	

   272         public Spliterator.OfInt trySplit() {

   273             long i = index, delta = Long.highestOneBit((fence - i) - 1), m = i + delta;

   274 	    if (m <= i) return null;

   275 	    index = m;

   276 	    ArbitrarilyJumpableRng r = generatingRng;

   277 	    return new RandomIntsSpliterator(r.copyAndJump((double)delta), i, m, origin, bound);

   278         }

   279 	

   280         public boolean tryAdvance(IntConsumer consumer) {

   281             if (consumer == null) throw new NullPointerException();

   282             long i = index, f = fence;

   283             if (i < f) {

   284                 consumer.accept(RngSupport.boundedNextInt(generatingRng, origin, bound));

   285                 index = i + 1;

   286                 return true;

   287             }

   288             else return false;

   289         }

   290 

   291         public void forEachRemaining(IntConsumer consumer) {

   292             if (consumer == null) throw new NullPointerException();

   293             long i = index, f = fence;

   294             if (i < f) {

   295                 index = f;

   296                 ArbitrarilyJumpableRng r = generatingRng;

   297                 int o = origin, b = bound;

   298                 do {

   299                     consumer.accept(RngSupport.boundedNextInt(r, o, b));

   300                 } while (++i < f);

   301             }

   302         }

   303     }

   304 

   305     /**

   306      * Spliterator for long streams.  

   307      */

   308     static class RandomLongsSpliterator extends RngSupport.RandomSpliterator implements Spliterator.OfLong {

   309 	final ArbitrarilyJumpableRng generatingRng;

   310         final long origin;

   311         final long bound;

   312 

   313         RandomLongsSpliterator(ArbitrarilyJumpableRng generatingRng, long index, long fence, long origin, long bound) {

   314 	    super(index, fence);

   315 	    this.generatingRng = generatingRng;

   316 	    this.origin = origin; this.bound = bound;

   317         }

   318 	

   319         public Spliterator.OfLong trySplit() {

   320             long i = index, delta = Long.highestOneBit((fence - i) - 1), m = i + delta;

   321 	    if (m <= i) return null;

   322 	    index = m;

   323 	    ArbitrarilyJumpableRng r = generatingRng;

   324 	    return new RandomLongsSpliterator(r.copyAndJump((double)delta), i, m, origin, bound);

   325         }

   326 	

   327         public boolean tryAdvance(LongConsumer consumer) {

   328             if (consumer == null) throw new NullPointerException();

   329             long i = index, f = fence;

   330             if (i < f) {

   331                 consumer.accept(RngSupport.boundedNextLong(generatingRng, origin, bound));

   332                 index = i + 1;

   333                 return true;

   334             }

   335             else return false;

   336         }

   337 

   338         public void forEachRemaining(LongConsumer consumer) {

   339             if (consumer == null) throw new NullPointerException();

   340             long i = index, f = fence;

   341             if (i < f) {

   342                 index = f;

   343                 ArbitrarilyJumpableRng r = generatingRng;

   344                 long o = origin, b = bound;

   345                 do {

   346                     consumer.accept(RngSupport.boundedNextLong(r, o, b));

   347                 } while (++i < f);

   348             }

   349         }

   350     }

   351 

   352     /**

   353      * Spliterator for double streams.  

   354      */

   355     static class RandomDoublesSpliterator extends RngSupport.RandomSpliterator implements Spliterator.OfDouble {

   356 	final ArbitrarilyJumpableRng generatingRng;

   357         final double origin;

   358         final double bound;

   359 

   360         RandomDoublesSpliterator(ArbitrarilyJumpableRng generatingRng, long index, long fence, double origin, double bound) {

   361 	    super(index, fence);

   362 	    this.generatingRng = generatingRng;

   363 	    this.origin = origin; this.bound = bound;

   364         }

   365 	

   366         public Spliterator.OfDouble trySplit() {

   367 

   368             long i = index, delta = Long.highestOneBit((fence - i) - 1), m = i + delta;

   369 	    if (m <= i) return null;

   370 	    index = m;

   371 	    ArbitrarilyJumpableRng r = generatingRng;

   372 	    return new RandomDoublesSpliterator(r.copyAndJump((double)delta), i, m, origin, bound);

   373         }

   374 	

   375         public boolean tryAdvance(DoubleConsumer consumer) {

   376             if (consumer == null) throw new NullPointerException();

   377             long i = index, f = fence;

   378             if (i < f) {

   379                 consumer.accept(RngSupport.boundedNextDouble(generatingRng, origin, bound));

   380                 index = i + 1;

   381                 return true;

   382             }

   383             else return false;

   384         }

   385 

   386         public void forEachRemaining(DoubleConsumer consumer) {

   387             if (consumer == null) throw new NullPointerException();

   388             long i = index, f = fence;

   389             if (i < f) {

   390                 index = f;

   391                 ArbitrarilyJumpableRng r = generatingRng;

   392                 double o = origin, b = bound;

   393                 do {

   394                     consumer.accept(RngSupport.boundedNextDouble(r, o, b));

   395                 } while (++i < f);

   396             }

   397         }

   398     }

   399     

   400     // Spliterators for producing new generators by jumping or leaping.  The

   401     // complete implementation of each of these spliterators is right here.

   402     // In the same manner as for the preceding spliterators, the method trySplit() is

   403     // coded to optimize execution speed: instead of dividing a range

   404     // in half, it breaks off the largest possible chunk whose

   405     // size is a power of two such that the remaining chunk is not

   406     // empty.  In this way, the necessary jump distances will tend to be

   407     // powers of two.

   408 

   409     /**

   410      * Spliterator for stream of generators of type Rng produced by jumps.

   411      */

   412     static class RandomJumpsSpliterator extends RngSupport.RandomSpliterator implements Spliterator<Rng> {

   413 	ArbitrarilyJumpableRng generatingRng;

   414 	final double distance;

   415 

   416         RandomJumpsSpliterator(ArbitrarilyJumpableRng generatingRng, long index, long fence, double distance) {

   417             super(index, fence);

   418             this.generatingRng = generatingRng; this.distance = distance;

   419         }

   420 

   421         public Spliterator<Rng> trySplit() {

   422 	    long i = index, delta = Long.highestOneBit((fence - i) - 1), m = i + delta;

   423 	    if (m <= i) return null;

   424 	    index = m;

   425 	    ArbitrarilyJumpableRng r = generatingRng;

   426 	    // Because delta is a power of two, (distance * (double)delta) can always be computed exactly.

   427 	    return new RandomJumpsSpliterator(r.copyAndJump(distance * (double)delta), i, m, distance);

   428         }

   429 

   430         public boolean tryAdvance(Consumer<? super Rng> consumer) {

   431             if (consumer == null) throw new NullPointerException();

   432             long i = index, f = fence;

   433             if (i < f) {

   434 		consumer.accept(generatingRng.copyAndJump(distance));

   435                 index = i + 1;

   436                 return true;

   437             }

   438             return false;

   439         }

   440 

   441         public void forEachRemaining(Consumer<? super Rng> consumer) {

   442             if (consumer == null) throw new NullPointerException();

   443             long i = index, f = fence;

   444             if (i < f) {

   445                 index = f;

   446 		ArbitrarilyJumpableRng r = generatingRng;

   447                 do {

   448                     consumer.accept(r.copyAndJump(distance));

   449                 } while (++i < f);

   450             }

   451         }

   452     }

   453     

   454     /**

   455      * Spliterator for stream of generators of type Rng produced by leaps.

   456      */

   457     static class RandomLeapsSpliterator extends RngSupport.RandomSpliterator implements Spliterator<JumpableRng> {

   458 	ArbitrarilyJumpableRng generatingRng;

   459 	final double distance;

   460 

   461         RandomLeapsSpliterator(ArbitrarilyJumpableRng generatingRng, long index, long fence, double distance) {

   462             super(index, fence);

   463             this.generatingRng = generatingRng; this.distance = distance;

   464         }

   465 

   466         public Spliterator<JumpableRng> trySplit() {

   467 	    long i = index, delta = Long.highestOneBit((fence - i) - 1), m = i + delta;

   468 	    if (m <= i) return null;

   469 	    index = m;

   470 	    // Because delta is a power of two, (distance * (double)delta) can always be computed exactly.

   471 	    return new RandomLeapsSpliterator(generatingRng.copyAndJump(distance * (double)delta), i, m, distance);

   472         }

   473 

   474         public boolean tryAdvance(Consumer<? super JumpableRng> consumer) {

   475             if (consumer == null) throw new NullPointerException();

   476             long i = index, f = fence;

   477             if (i < f) {

   478 		consumer.accept(generatingRng.copyAndJump(distance));

   479                 index = i + 1;

   480                 return true;

   481             }

   482             return false;

   483         }

   484 

   485         public void forEachRemaining(Consumer<? super JumpableRng> consumer) {

   486             if (consumer == null) throw new NullPointerException();

   487             long i = index, f = fence;

   488             if (i < f) {

   489                 index = f;

   490                 ArbitrarilyJumpableRng r = generatingRng;

   491                 do {

   492                     consumer.accept(r.copyAndJump(distance));

   493                 } while (++i < f);

   494             }

   495         }

   496     }

   497 

   498     /**

   499      * Spliterator for stream of generators of type Rng produced by arbitrary jumps.

   500      */

   501     static class RandomArbitraryJumpsSpliterator extends RngSupport.RandomSpliterator implements Spliterator<ArbitrarilyJumpableRng> {

   502 	ArbitrarilyJumpableRng generatingRng;

   503 	final double distance;

   504 

   505         RandomArbitraryJumpsSpliterator(ArbitrarilyJumpableRng generatingRng, long index, long fence, double distance) {

   506             super(index, fence);

   507             this.generatingRng = generatingRng; this.distance = distance;

   508         }

   509 

   510         public Spliterator<ArbitrarilyJumpableRng> trySplit() {

   511 	    long i = index, delta = Long.highestOneBit((fence - i) - 1), m = i + delta;

   512 	    if (m <= i) return null;

   513 	    index = m;

   514 	    // Because delta is a power of two, (distance * (double)delta) can always be computed exactly.

   515 	    return new RandomArbitraryJumpsSpliterator(generatingRng.copyAndJump(distance * (double)delta), i, m, distance);

   516         }

   517 

   518         public boolean tryAdvance(Consumer<? super ArbitrarilyJumpableRng> consumer) {

   519             if (consumer == null) throw new NullPointerException();

   520             long i = index, f = fence;

   521             if (i < f) {

   522 		consumer.accept(generatingRng.copyAndJump(distance));

   523                 index = i + 1;

   524                 return true;

   525             }

   526             return false;

   527         }

   528 

   529         public void forEachRemaining(Consumer<? super ArbitrarilyJumpableRng> consumer) {

   530             if (consumer == null) throw new NullPointerException();

   531             long i = index, f = fence;

   532             if (i < f) {

   533                 index = f;

   534 		ArbitrarilyJumpableRng r = generatingRng;

   535                 do {

   536                     consumer.accept(r.copyAndJump(distance));

   537                 } while (++i < f);

   538             }

   539         }

   540     }

   541 

   542 }