--- a/src/java.base/share/classes/java/util/random/RandomSupport.java Thu Aug 29 11:33:26 2019 -0300
+++ b/src/java.base/share/classes/java/util/random/RandomSupport.java Thu Nov 14 08:54:56 2019 -0400
@@ -51,7 +51,7 @@
* Implementation Overview.
*
* This class provides utility methods and constants frequently
- * useful in the implentation of pseudorandom number generators
+ * useful in the implementation of pseudorandom number generators
* that satisfy the interface {@link RandomGenerator}.
*
* File organization: First some message strings, then the main
@@ -84,7 +84,7 @@
*
* @param distance the proposed jump distance
*
- * @throws IllegalArgumentException if {@code size} not positive, finite, and an exact integer
+ * @throws IllegalArgumentException if {@code size} fails to be positive, finite, and an exact integer
*/
public static void checkJumpDistance(double distance) {
if (!(distance > 0.0 && distance < Float.POSITIVE_INFINITY
@@ -98,7 +98,7 @@
*
* @param bound the upper bound (exclusive)
*
- * @throws IllegalArgumentException if {@code bound} is not positive and finite
+ * @throws IllegalArgumentException if {@code bound} fails to be positive and finite
*/
public static void checkBound(float bound) {
if (!(bound > 0.0 && bound < Float.POSITIVE_INFINITY)) {
@@ -111,7 +111,7 @@
*
* @param bound the upper bound (exclusive)
*
- * @throws IllegalArgumentException if {@code bound} is not positive and finite
+ * @throws IllegalArgumentException if {@code bound} fails to be positive and finite
*/
public static void checkBound(double bound) {
if (!(bound > 0.0 && bound < Double.POSITIVE_INFINITY)) {
@@ -151,8 +151,8 @@
* @param origin the least value (inclusive) in the range
* @param bound the upper bound (exclusive) of the range
*
- * @throws IllegalArgumentException unless {@code origin} is finite, {@code bound} is finite,
- * and {@code bound - origin} is finite
+ * @throws IllegalArgumentException if {@code origin} is not finite, {@code bound} is not finite,
+ * or {@code bound - origin} is not finite
*/
public static void checkRange(float origin, float bound) {
if (!(origin < bound && (bound - origin) < Float.POSITIVE_INFINITY)) {
@@ -166,8 +166,8 @@
* @param origin the least value (inclusive) in the range
* @param bound the upper bound (exclusive) of the range
*
- * @throws IllegalArgumentException unless {@code origin} is finite, {@code bound} is finite,
- * and {@code bound - origin} is finite
+ * @throws IllegalArgumentException if {@code origin} is not finite, {@code bound} is not finite,
+ * or {@code bound - origin} is not finite
*/
public static void checkRange(double origin, double bound) {
if (!(origin < bound && (bound - origin) < Double.POSITIVE_INFINITY)) {
@@ -1141,35 +1141,44 @@
*/
/**
- * Needs comment (was made public to be overridden out of package.)
+ * Create an instance of {@link Spliterator.OfInt} that for each traversal position
+ * between the specified index (inclusive) and the specified fence (exclusive) generates
+ * a pseudorandomly chosen {@code int} value between the specified origin (inclusive) and
+ * the specified bound (exclusive).
*
- * @param index low
- * @param fence high
- * @param origin low
- * @param bound high
- * @return result
+ * @param index the (inclusive) lower bound on traversal positions
+ * @param fence the (exclusive) upper bound on traversal positions
+ * @param origin the (inclusive) lower bound on the pseudorandom values to be generated
+ * @param bound the (exclusive) upper bound on the pseudorandom values to be generated
+ * @return an instance of {@link Spliterator.OfInt}
*/
public abstract Spliterator.OfInt makeIntsSpliterator(long index, long fence, int origin, int bound);
/**
- * Needs comment (was made public to be overridden out of package.)
+ * Create an instance of {@link Spliterator.OfLong} that for each traversal position
+ * between the specified index (inclusive) and the specified fence (exclusive) generates
+ * a pseudorandomly chosen {@code long} value between the specified origin (inclusive) and
+ * the specified bound (exclusive).
*
- * @param index low
- * @param fence high
- * @param origin low
- * @param bound high
- * @return result
+ * @param index the (inclusive) lower bound on traversal positions
+ * @param fence the (exclusive) upper bound on traversal positions
+ * @param origin the (inclusive) lower bound on the pseudorandom values to be generated
+ * @param bound the (exclusive) upper bound on the pseudorandom values to be generated
+ * @return an instance of {@link Spliterator.OfLong}
*/
public abstract Spliterator.OfLong makeLongsSpliterator(long index, long fence, long origin, long bound);
/**
- * Needs comment (was made public to be overridden out of package.)
+ * Create an instance of {@link Spliterator.OfDouble} that for each traversal position
+ * between the specified index (inclusive) and the specified fence (exclusive) generates
+ * a pseudorandomly chosen {@code double} value between the specified origin (inclusive) and
+ * the specified bound (exclusive).
*
- * @param index low
- * @param fence high
- * @param origin low
- * @param bound high
- * @return result
+ * @param index the (inclusive) lower bound on traversal positions
+ * @param fence the (exclusive) upper bound on traversal positions
+ * @param origin the (inclusive) lower bound on the pseudorandom values to be generated
+ * @param bound the (exclusive) upper bound on the pseudorandom values to be generated
+ * @return an instance of {@link Spliterator.OfDouble}
*/
public abstract Spliterator.OfDouble makeDoublesSpliterator(long index, long fence, double origin, double bound);
@@ -1922,11 +1931,10 @@
* provide implementations for the methods {@code nextInt()}, {@code nextLong()}, {@code period()},
* and {@code split(SplittableGenerator)}.
* <p>
- * (If the pseudorandom number generator also has the ability to jump, then the programmer may wish
- * to consider instead extending the class {@link ArbitrarilyJumpableGenerator}. But if the pseudorandom
- * number generator furthermore has the ability to jump an arbitrary specified distance, then the
- * programmer may wish to consider instead extending the class {@link
- * AbstractArbitrarilyJumpableGenerator}.)
+ * (If the pseudorandom number generator also has the ability to jump an arbitrary
+ * specified distance, then the programmer may wish to consider instead extending the
+ * class {@link AbstractArbitrarilyJumpableGenerator}. See also the class
+ * {@link AbstractSplittableWithBrineGenerator}.)
* <p>
* The programmer should generally provide at least three constructors: one that takes no arguments,
* one that accepts a {@code long} seed value, and one that accepts an array of seed {@code byte}
@@ -1934,8 +1942,8 @@
* initializing some static state from which to derive defaults seeds for use by the no-argument
* constructor.
* <p>
- * For the stream methods (such as {@code ints()} and {@code splits()}), this class provides {@link
- * Spliterator} based implementations that allow parallel execution when appropriate.
+ * For the stream methods (such as {@code ints()} and {@code splits()}), this class provides
+ * {@link Spliterator}-based implementations that allow parallel execution when appropriate.
* <p>
* The documentation for each non-abstract method in this class describes its implementation in
* detail. Each of these methods may be overridden if the pseudorandom number generator being
@@ -1949,15 +1957,12 @@
* Implementation Overview.
*
* This class provides most of the "user API" methods needed to
- * satisfy the interface JumpableGenerator. Most of these methods
+ * satisfy the interface SplittableGenerator. Most of these methods
* are in turn inherited from AbstractGenerator and the non-public class
- * AbstractSpliteratorGenerator; this file implements two versions of the
+ * AbstractSpliteratorGenerator; this class provides two versions of the
* splits method and defines the spliterators necessary to support
* them.
*
- * The abstract split() method from interface SplittableGenerator is redeclared
- * here so as to narrow the return type to AbstractSplittableGenerator.
- *
* File organization: First the non-public methods needed by the class
* AbstractSpliteratorGenerator, then the main public methods, followed by some
* custom spliterator classes.
@@ -1982,9 +1987,9 @@
/* ---------------- public methods ---------------- */
/**
- * Implements the @code{split()} method as {@code this.split(this) }.
+ * Implements the @code{split()} method as {@code this.split(this)}.
*
- * @return the new {@link AbstractSplittableGenerator} instance
+ * @return the new {@link SplittableGenerator} instance
*/
public SplittableGenerator split() {
return this.split(this);
@@ -2200,11 +2205,13 @@
* versions into one class by treating "infinite" as equivalent to Long.MAX_VALUE.
* For splits, it uses the standard divide-by-two approach.
*/
- static class RandomSplitsSpliterator extends RandomSupport.RandomSpliterator implements Spliterator<SplittableGenerator> {
+ static class RandomSplitsSpliterator extends RandomSpliterator implements Spliterator<SplittableGenerator> {
final SplittableGenerator generatingGenerator;
final SplittableGenerator constructingGenerator;
- RandomSplitsSpliterator(SplittableGenerator generatingGenerator, long index, long fence, SplittableGenerator constructingGenerator) {
+ RandomSplitsSpliterator(SplittableGenerator generatingGenerator,
+ long index, long fence,
+ SplittableGenerator constructingGenerator) {
super(index, fence);
this.generatingGenerator = generatingGenerator;
this.constructingGenerator = constructingGenerator;
@@ -2244,5 +2251,232 @@
}
+ /**
+ * This class provides much of the implementation of the {@link SplittableGenerator} interface, to
+ * minimize the effort required to implement this interface. It is similar to the class
+ * {@link AbstractSplittableGenerator} but makes use of the brine technique for ensuring that
+ * distinct generators created by a single call to a {@code splits} method have distinct state cycles.
+ * <p>
+ * To implement a pseudorandom number generator, the programmer needs only to extend this class and
+ * provide implementations for the methods {@code nextInt()}, {@code nextLong()}, {@code period()},
+ * and {@code split(SplittableGenerator, long)}.
+ * <p>
+ * The programmer should generally provide at least three constructors: one that takes no arguments,
+ * one that accepts a {@code long} seed value, and one that accepts an array of seed {@code byte}
+ * values. This class provides a public {@code initialSeed()} method that may be useful in
+ * initializing some static state from which to derive defaults seeds for use by the no-argument
+ * constructor.
+ * <p>
+ * For the stream methods (such as {@code ints()} and {@code splits()}), this class provides
+ * {@link Spliterator}-based implementations that allow parallel execution when appropriate.
+ * <p>
+ * The documentation for each non-abstract method in this class describes its implementation in
+ * detail. Each of these methods may be overridden if the pseudorandom number generator being
+ * implemented admits a more efficient implementation.
+ *
+ * @since 14
+ */
+ public abstract static class AbstractSplittableWithBrineGenerator
+ extends AbstractSplittableGenerator {
+
+ /*
+ * Implementation Overview.
+ *
+ * This class provides most of the "user API" methods needed to
+ * satisfy the interface SplittableGenerator. Most of these methods
+ * are in turn inherited from AbstractSplittableGenerator and the non-public class
+ * AbstractSpliteratorGenerator; this class provides four versions of the
+ * splits method and defines the spliterators necessary to support
+ * them.
+ *
+ * File organization: First the non-public methods needed by the class
+ * AbstractSplittableWithBrineGenerator, then the main public methods,
+ * followed by some custom spliterator classes needed for stream methods.
+ */
+
+ // The salt consists groups of bits each SALT_SHIFT in size, starting from
+ // the left-hand (high-order) end of the word. We can regard them as
+ // digits base (1 << SALT_SHIFT). If SALT_SHIFT does not divide 64
+ // evenly, then any leftover bits at the low end of the word are zero.
+ // The lowest digit of the salt is set to the largest possible digit
+ // (all 1-bits, or ((1 << SALT_SHIFT) - 1)); all other digits are set
+ // to a randomly chosen value less than that largest possible digit.
+ // The salt may be shifted left by SALT_SHIFT any number of times.
+ // If any salt remains in the word, its right-hand end can be identified
+ // by searching from left to right for an occurrence of a digit that is
+ // all 1-bits (not that we ever do that; this is simply a proof that one
+ // can identify the boundary between the salt and the index if any salt
+ // remains in the word). The idea is that before computing the bitwise OR
+ // of an index and the salt, one can first check to see whether the
+ // bitwise AND is nonzero; if so, one can shift the salt left by
+ // SALT_SHIFT and try again. In this way, when the bitwise OR is
+ // computed, if the salt is nonzero then its rightmost 1-bit is to the
+ // left of the leftmost 1-bit of the index.
+
+ // We need 2 <= SALT_SHIFT <= 63 (3 through 8 are good values; 4 is probably best)
+ static final int SALT_SHIFT = 4;
+
+ // Methods required by class AbstractSpliteratorGenerator (override)
+ Spliterator<SplittableGenerator> makeSplitsSpliterator(long index, long fence, SplittableGenerator source) {
+ // This little algorithm to generate a new salt value is carefully
+ // designed to work even if SALT_SHIFT does not evenly divide 64
+ // (the number of bits in a long value).
+ long bits = nextLong();
+ long multiplier = (1 << SALT_SHIFT) - 1;
+ long salt = multiplier << (64 - SALT_SHIFT);
+ while ((salt & multiplier) != 0) {
+ long digit = Math.multiplyHigh(bits, multiplier);
+ salt = (salt >>> SALT_SHIFT) | (digit << (64 - SALT_SHIFT));
+ bits *= multiplier;
+ }
+ // This is the point at which newly generated salt gets injected into
+ // the root of a newly created brine-generating splits-spliterator.
+ return new RandomSplitsSpliteratorWithSalt(source, index, fence, this, salt);
+ }
+
+ /* ---------------- public methods ---------------- */
+
+ // Stream methods for splitting
+
+ /**
+ * Constructs and returns a new instance of {@code AbstractSplittableWithBrineGenerator}
+ * that shares no mutable state with this instance. However, with very high
+ * probability, the set of values collectively generated by the two objects
+ * should have the same statistical properties as if the same quantity of
+ * values were generated by a single thread using a single may be
+ * {@code AbstractSplittableWithBrineGenerator} object. Either or both of the two objects
+ * further split using the {@code split()} method, and the same expected
+ * statistical properties apply to the entire set of generators constructed
+ * by such recursive splitting.
+ *
+ * @param brine a long value, of which the low 63 bits provide a unique id
+ * among calls to this method for constructing a single series of Generator objects.
+ *
+ * @return the new {@code AbstractSplittableWithBrineGenerator} instance
+ */
+ public SplittableGenerator split(long brine) {
+ return this.split(this, brine);
+ }
+
+ /**
+ * Constructs and returns a new instance of {@code L64X128MixRandom}
+ * that shares no mutable state with this instance.
+ * However, with very high probability, the set of values collectively
+ * generated by the two objects has the same statistical properties as if
+ * same the quantity of values were generated by a single thread using
+ * a single {@code L64X128MixRandom} object. Either or both of the two
+ * objects may be further split using the {@code split} method,
+ * and the same expected statistical properties apply to the
+ * entire set of generators constructed by such recursive splitting.
+ *
+ * @param source a {@code SplittableGenerator} instance to be used instead
+ * of this one as a source of pseudorandom bits used to
+ * initialize the state of the new ones.
+ * @return a new instance of {@code L64X128MixRandom}
+ */
+ public SplittableGenerator split(SplittableGenerator source) {
+ // It's a one-off: supply randomly chosen brine
+ return this.split(source, source.nextLong());
+ }
+
+ /**
+ * Constructs and returns a new instance of {@code AbstractSplittableWithBrineGenerator}
+ * that shares no mutable state with this instance. However, with very high
+ * probability, the set of values collectively generated by the two objects
+ * should have the same statistical properties as if the same quantity of
+ * values were generated by a single thread using a single may be
+ * {@code AbstractSplittableWithBrineGenerator} object. Either or both of the two objects
+ * further split using the {@code split()} method, and the same expected
+ * statistical properties apply to the entire set of generators constructed
+ * by such recursive splitting.
+ *
+ * @param source a {@code SplittableGenerator} instance to be used instead
+ * of this one as a source of pseudorandom bits used to
+ * initialize the state of the new ones.
+ * @param brine a long value, of which the low 63 bits provide a unique id
+ * among calls to this method for constructing a single series of
+ * {@code RandomGenerator} objects.
+ *
+ * @return the new {@code AbstractSplittableWithBrineGenerator} instance
+ */
+ public abstract SplittableGenerator split(SplittableGenerator source, long brine);
+
+
+ /* ---------------- spliterator ---------------- */
+ /**
+ * Alternate spliterator for stream of generators of type SplittableGenerator. We multiplex
+ * the two versions into one class by treating "infinite" as equivalent to Long.MAX_VALUE.
+ * For splits, it uses the standard divide-by-two approach.
+ *
+ * This differs from {@code SplittableGenerator.RandomSplitsSpliterator} in that it provides
+ * a brine argument (a mixture of salt and an index) when calling the {@code split} method.
+ */
+ static class RandomSplitsSpliteratorWithSalt
+ extends RandomSpliterator implements Spliterator<SplittableGenerator> {
+
+ final SplittableGenerator generatingGenerator;
+ final AbstractSplittableWithBrineGenerator constructingGenerator;
+ long salt;
+
+ // Important invariant: 0 <= index <= fence
+
+ // Important invariant: if salt and index are both nonzero,
+ // the rightmost 1-bit of salt is to the left of the leftmost 1-bit of index.
+ // If necessary, the salt can be leftshifted by SALT_SHIFT as many times as
+ // necessary to maintain the invariant.
+
+ RandomSplitsSpliteratorWithSalt(SplittableGenerator generatingGenerator, long index, long fence,
+ AbstractSplittableWithBrineGenerator constructingGenerator, long salt) {
+ super(index, fence);
+ this.generatingGenerator = generatingGenerator;
+ this.constructingGenerator = constructingGenerator;
+ while ((salt != 0) && (Long.compareUnsigned(salt & -salt, index) <= 0)) {
+ salt = salt << SALT_SHIFT;
+ }
+ this.salt = salt;
+ }
+
+ public Spliterator<SplittableGenerator> trySplit() {
+ long i = index, m = (i + fence) >>> 1;
+ if (m <= i) return null;
+ RandomSplitsSpliteratorWithSalt result =
+ new RandomSplitsSpliteratorWithSalt(generatingGenerator.split(), i, m, constructingGenerator, salt);
+ index = m;
+ while ((salt != 0) && (Long.compareUnsigned(salt & -salt, index) <= 0)) {
+ salt = salt << SALT_SHIFT;
+ }
+ return result;
+ }
+
+ public boolean tryAdvance(Consumer<? super SplittableGenerator> consumer) {
+ if (consumer == null) throw new NullPointerException();
+ long i = index, f = fence;
+ if (i < f) {
+ consumer.accept(constructingGenerator.split(generatingGenerator, salt | i));
+ ++i;
+ index = i;
+ if ((i & salt) != 0) salt <<= SALT_SHIFT;
+ return true;
+ }
+ return false;
+ }
+
+ public void forEachRemaining(Consumer<? super SplittableGenerator> consumer) {
+ if (consumer == null) throw new NullPointerException();
+ long i = index, f = fence;
+ if (i < f) {
+ index = f;
+ AbstractSplittableWithBrineGenerator c = constructingGenerator;
+ SplittableGenerator r = generatingGenerator;
+ do {
+ consumer.accept(c.split(r, salt | i));
+ ++i;
+ if ((i & salt) != 0) salt <<= SALT_SHIFT;
+ } while (i < f);
+ }
+ }
+ }
+
+ }
+
}
-