2254     /**

  2255      * This class provides much of the implementation of the {@link SplittableGenerator} interface, to

  2256      * minimize the effort required to implement this interface.  It is similar to the class

  2257      * {@link AbstractSplittableGenerator} but makes use of the brine technique for ensuring that

  2258      * distinct generators created by a single call to a {@code splits} method have distinct state cycles.

  2259      * <p>

  2260      * To implement a pseudorandom number generator, the programmer needs only to extend this class and

  2261      * provide implementations for the methods {@code nextInt()}, {@code nextLong()}, {@code period()},

  2262      * and {@code split(SplittableGenerator, long)}.

  2263      * <p>

  2264      * The programmer should generally provide at least three constructors: one that takes no arguments,

  2265      * one that accepts a {@code long} seed value, and one that accepts an array of seed {@code byte}

  2266      * values. This class provides a public {@code initialSeed()} method that may be useful in

  2267      * initializing some static state from which to derive defaults seeds for use by the no-argument

  2268      * constructor.

  2269      * <p>

  2270      * For the stream methods (such as {@code ints()} and {@code splits()}), this class provides

  2271      * {@link Spliterator}-based implementations that allow parallel execution when appropriate.

  2272      * <p>

  2273      * The documentation for each non-abstract method in this class describes its implementation in

  2274      * detail. Each of these methods may be overridden if the pseudorandom number generator being

  2275      * implemented admits a more efficient implementation.

  2276      *

  2277      * @since 14

  2278      */

  2279     public abstract static class AbstractSplittableWithBrineGenerator

  2280 	extends AbstractSplittableGenerator {

  2281 

  2282 	/*

  2283 	 * Implementation Overview.

  2284 	 *

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

  2286          * satisfy the interface SplittableGenerator.  Most of these methods

  2287          * are in turn inherited from AbstractSplittableGenerator and the non-public class

  2288          * AbstractSpliteratorGenerator; this class provides four versions of the

  2289          * splits method and defines the spliterators necessary to support

  2290          * them.

  2291 	 *

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

  2293 	 * AbstractSplittableWithBrineGenerator, then the main public methods,

  2294 	 * followed by some custom spliterator classes needed for stream methods.

  2295 	 */

  2296 

  2297 	// The salt consists groups of bits each SALT_SHIFT in size, starting from

  2298 	// the left-hand (high-order) end of the word.  We can regard them as

  2299 	// digits base (1 << SALT_SHIFT).  If SALT_SHIFT does not divide 64

  2300 	// evenly, then any leftover bits at the low end of the word are zero.

  2301 	// The lowest digit of the salt is set to the largest possible digit

  2302 	// (all 1-bits, or ((1 << SALT_SHIFT) - 1)); all other digits are set

  2303 	// to a randomly chosen value less than that largest possible digit.

  2304 	// The salt may be shifted left by SALT_SHIFT any number of times.

  2305 	// If any salt remains in the word, its right-hand end can be identified

  2306 	// by searching from left to right for an occurrence of a digit that is

  2307 	// all 1-bits (not that we ever do that; this is simply a proof that one

  2308 	// can identify the boundary between the salt and the index if any salt

  2309 	// remains in the word).  The idea is that before computing the bitwise OR

  2310 	// of an index and the salt, one can first check to see whether the

  2311 	// bitwise AND is nonzero; if so, one can shift the salt left by

  2312 	// SALT_SHIFT and try again.  In this way, when the bitwise OR is

  2313 	// computed, if the salt is nonzero then its rightmost 1-bit is to the

  2314 	// left of the leftmost 1-bit of the index.

  2315 

  2316 	// We need 2 <= SALT_SHIFT <= 63 (3 through 8 are good values; 4 is probably best)

  2317 	static final int SALT_SHIFT = 4;

  2318 

  2319 	// Methods required by class AbstractSpliteratorGenerator (override)

  2320 	Spliterator<SplittableGenerator> makeSplitsSpliterator(long index, long fence, SplittableGenerator source) {

  2321 	    // This little algorithm to generate a new salt value is carefully

  2322 	    // designed to work even if SALT_SHIFT does not evenly divide 64

  2323 	    // (the number of bits in a long value).

  2324 	    long bits = nextLong();

  2325 	    long multiplier = (1 << SALT_SHIFT) - 1;

  2326 	    long salt = multiplier << (64 - SALT_SHIFT);

  2327 	    while ((salt & multiplier) != 0) {

  2328 		long digit = Math.multiplyHigh(bits, multiplier);

  2329 		salt = (salt >>> SALT_SHIFT) | (digit << (64 - SALT_SHIFT));

  2330 		bits *= multiplier;

  2331 	    }

  2332 	    // This is the point at which newly generated salt gets injected into

  2333 	    // the root of a newly created brine-generating splits-spliterator.

  2334 	    return new RandomSplitsSpliteratorWithSalt(source, index, fence, this, salt);

  2335 	}

  2336 

  2337 	/* ---------------- public methods ---------------- */

  2338 

  2339 	// Stream methods for splitting

  2340 

  2341 	/**

  2342 	 * Constructs and returns a new instance of {@code AbstractSplittableWithBrineGenerator}

  2343 	 * that shares no mutable state with this instance. However, with very high

  2344 	 * probability, the set of values collectively generated by the two objects

  2345 	 * should have the same statistical properties as if the same quantity of

  2346 	 * values were generated by a single thread using a single may be

  2347 	 * {@code AbstractSplittableWithBrineGenerator} object. Either or both of the two objects

  2348 	 * further split using the {@code split()} method, and the same expected

  2349 	 * statistical properties apply to the entire set of generators constructed

  2350 	 * by such recursive splitting.

  2351 	 *

  2352 	 * @param brine a long value, of which the low 63 bits provide a unique id

  2353 	 * among calls to this method for constructing a single series of Generator objects.

  2354 	 *

  2355 	 * @return the new {@code AbstractSplittableWithBrineGenerator} instance

  2356 	 */

  2357 	public SplittableGenerator split(long brine) {

  2358 	    return this.split(this, brine);

  2359 	}

  2360 

  2361 	/**

  2362 	 * Constructs and returns a new instance of {@code L64X128MixRandom}

  2363 	 * that shares no mutable state with this instance.

  2364 	 * However, with very high probability, the set of values collectively

  2365 	 * generated by the two objects has the same statistical properties as if

  2366 	 * same the quantity of values were generated by a single thread using

  2367 	 * a single {@code L64X128MixRandom} object.  Either or both of the two

  2368 	 * objects may be further split using the {@code split} method,

  2369 	 * and the same expected statistical properties apply to the

  2370 	 * entire set of generators constructed by such recursive splitting.

  2371 	 *

  2372 	 * @param source a {@code SplittableGenerator} instance to be used instead

  2373 	 *               of this one as a source of pseudorandom bits used to

  2374 	 *               initialize the state of the new ones.

  2375 	 * @return a new instance of {@code L64X128MixRandom}

  2376 	 */

  2377 	public SplittableGenerator split(SplittableGenerator source) {

  2378 	    // It's a one-off: supply randomly chosen brine

  2379 	    return this.split(source, source.nextLong());

  2380 	}

  2381 

  2382 	/**

  2383 	 * Constructs and returns a new instance of {@code AbstractSplittableWithBrineGenerator}

  2384 	 * that shares no mutable state with this instance. However, with very high

  2385 	 * probability, the set of values collectively generated by the two objects

  2386 	 * should have the same statistical properties as if the same quantity of

  2387 	 * values were generated by a single thread using a single may be

  2388 	 * {@code AbstractSplittableWithBrineGenerator} object. Either or both of the two objects

  2389 	 * further split using the {@code split()} method, and the same expected

  2390 	 * statistical properties apply to the entire set of generators constructed

  2391 	 * by such recursive splitting.

  2392 	 *

  2393 	 * @param source a {@code SplittableGenerator} instance to be used instead

  2394 	 *               of this one as a source of pseudorandom bits used to

  2395 	 *               initialize the state of the new ones.

  2396 	 * @param brine a long value, of which the low 63 bits provide a unique id

  2397 	 *              among calls to this method for constructing a single series of

  2398 	 *              {@code RandomGenerator} objects.

  2399 	 *

  2400 	 * @return the new {@code AbstractSplittableWithBrineGenerator} instance

  2401 	 */

  2402 	public abstract SplittableGenerator split(SplittableGenerator source, long brine);

  2403 

  2404 

  2405 	/* ---------------- spliterator ---------------- */

  2406 	/**

  2407 	 * Alternate spliterator for stream of generators of type SplittableGenerator.  We multiplex

  2408 	 * the two versions into one class by treating "infinite" as equivalent to Long.MAX_VALUE.

  2409 	 * For splits, it uses the standard divide-by-two approach.

  2410 	 *

  2411 	 * This differs from {@code SplittableGenerator.RandomSplitsSpliterator} in that it provides

  2412 	 * a brine argument (a mixture of salt and an index) when calling the {@code split} method.

  2413 	 */

  2414 	static class RandomSplitsSpliteratorWithSalt

  2415 	    extends RandomSpliterator implements Spliterator<SplittableGenerator> {

  2416 

  2417 	    final SplittableGenerator generatingGenerator;

  2418 	    final AbstractSplittableWithBrineGenerator constructingGenerator;

  2419 	    long salt;

  2420 

  2421 	    // Important invariant: 0 <= index <= fence

  2422 

  2423 	    // Important invariant: if salt and index are both nonzero,

  2424 	    // the rightmost 1-bit of salt is to the left of the leftmost 1-bit of index.

  2425 	    // If necessary, the salt can be leftshifted by SALT_SHIFT as many times as

  2426 	    // necessary to maintain the invariant.

  2427 

  2428 	    RandomSplitsSpliteratorWithSalt(SplittableGenerator generatingGenerator, long index, long fence,

  2429 					    AbstractSplittableWithBrineGenerator constructingGenerator, long salt) {

  2430 		super(index, fence);

  2431 		this.generatingGenerator = generatingGenerator;

  2432 		this.constructingGenerator = constructingGenerator;

  2433 		while ((salt != 0) && (Long.compareUnsigned(salt & -salt, index) <= 0)) {

  2434 		    salt = salt << SALT_SHIFT;

  2435 		}

  2436 		this.salt = salt;

  2437 	    }

  2438 

  2439             public Spliterator<SplittableGenerator> trySplit() {

  2440                 long i = index, m = (i + fence) >>> 1;

  2441                 if (m <= i) return null;

  2442 		RandomSplitsSpliteratorWithSalt result =

  2443 		    new RandomSplitsSpliteratorWithSalt(generatingGenerator.split(), i, m, constructingGenerator, salt);

  2444                 index = m;

  2445 		while ((salt != 0) && (Long.compareUnsigned(salt & -salt, index) <= 0)) {

  2446 		    salt = salt << SALT_SHIFT;

  2447 		}

  2448 		return result;

  2449             }

  2450 

  2451 	    public boolean tryAdvance(Consumer<? super SplittableGenerator> consumer) {

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

  2453 		long i = index, f = fence;

  2454 		if (i < f) {

  2455 		    consumer.accept(constructingGenerator.split(generatingGenerator, salt | i));

  2456 		    ++i;

  2457 		    index = i;

  2458 		    if ((i & salt) != 0) salt <<= SALT_SHIFT;

  2459 		    return true;

  2460 		}

  2461 		return false;

  2462 	    }

  2463 

  2464 	    public void forEachRemaining(Consumer<? super SplittableGenerator> consumer) {

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

  2466 		long i = index, f = fence;

  2467 		if (i < f) {

  2468 		    index = f;

  2469 		    AbstractSplittableWithBrineGenerator c = constructingGenerator;

  2470 		    SplittableGenerator r = generatingGenerator;

  2471 		    do {

  2472 			consumer.accept(c.split(r, salt | i));

  2473 			++i;

  2474 			if ((i & salt) != 0) salt <<= SALT_SHIFT;

  2475 		    } while (i < f);

  2476 		}

  2477 	    }

  2478 	}

  2479 

  2480     }

  2481