/*

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

 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.

 *

 *

 *

 *

 *

 *

 *

 *

 *

 *

 *

 *

 *

 *

 *

 *

 *

 *

 *

 *

 */

// package java.util;

import java.util.Spliterator;

import java.util.function.Consumer;

import java.util.function.IntConsumer;

import java.util.function.LongConsumer;

import java.util.function.DoubleConsumer;

import java.util.stream.StreamSupport;

import java.util.stream.IntStream;

import java.util.stream.LongStream;

import java.util.stream.DoubleStream;

// import java.util.DoubleZigguratTables;

/**

 * Low-level utility methods helpful for implementing pseudorandom number generators.

 *

 * This class is mostly for library writers creating specific implementations of the interface {@link java.util.Rng}.

 *

 * @author  Guy Steele

 * @author  Doug Lea

 * @since   1.9

 */

public class RngSupport {

    /*

     * Implementation Overview.

     *

     * This class provides utility methods and constants frequently

     * useful in the implentation of pseudorandom number generators

     * that satisfy the interface {@code java.util.Rng}.

     *

     * File organization: First some message strings, then the main

     * public methods, followed by a non-public base spliterator class.

     */

    // IllegalArgumentException messages

    static final String BadSize = "size must be non-negative";

    static final String BadDistance = "jump distance must be finite, positive, and an exact integer";

    static final String BadBound = "bound must be positive";

    static final String BadFloatingBound = "bound must be finite and positive";

    static final String BadRange = "bound must be greater than origin";

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

    /**

     * Check a {@code long} proposed stream size for validity.

     *

     * @param streamSize the proposed stream size

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

     */

    public static void checkStreamSize(long streamSize) {

	if (streamSize < 0L)

            throw new IllegalArgumentException(BadSize);

    }

    /**

     * Check a {@code double} proposed jump distance for validity.

     *

     * @param distance the proposed jump distance

     * @throws IllegalArgumentException if {@code size} not positive,

     * finite, and an exact integer

     */

    public static void checkJumpDistance(double distance) {

	if (!(distance > 0.0 && distance < Float.POSITIVE_INFINITY && distance == Math.floor(distance)))

            throw new IllegalArgumentException(BadDistance);

    }

    /**

     * Checks a {@code float} upper bound value for validity.

     *

     * @param bound the upper bound (exclusive)

     * @throws IllegalArgumentException if {@code bound} is not

     *         positive and finite

     */

    public static void checkBound(float bound) {

	if (!(bound > 0.0 && bound < Float.POSITIVE_INFINITY))

            throw new IllegalArgumentException(BadFloatingBound);

    }

    /**

     * Checks a {@code double} upper bound value for validity.

     *

     * @param bound the upper bound (exclusive)

     * @throws IllegalArgumentException if {@code bound} is not

     *         positive and finite

     */

    public static void checkBound(double bound) {

	if (!(bound > 0.0 && bound < Double.POSITIVE_INFINITY))

            throw new IllegalArgumentException(BadFloatingBound);

    }

    /**

     * Checks an {@code int} upper bound value for validity.

     *

     * @param bound the upper bound (exclusive)

     * @throws IllegalArgumentException if {@code bound} is not positive

     */

    public static void checkBound(int bound) {

        if (bound <= 0)

            throw new IllegalArgumentException(BadBound);

    }

    /**

     * Checks a {@code long} upper bound value for validity.

     *

     * @param bound the upper bound (exclusive)

     * @throws IllegalArgumentException if {@code bound} is not positive

     */

    public static void checkBound(long bound) {

        if (bound <= 0)

            throw new IllegalArgumentException(BadBound);

    }

    /**

     * Checks a {@code float} range for validity.

     *

     * @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

     */

    public static void checkRange(float origin, float bound) {

        if (!(origin < bound && (bound - origin) < Float.POSITIVE_INFINITY))

            throw new IllegalArgumentException(BadRange);

    }

    /**

     * Checks a {@code double} range for validity.

     *

     * @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

     */

    public static void checkRange(double origin, double bound) {

        if (!(origin < bound && (bound - origin) < Double.POSITIVE_INFINITY))

            throw new IllegalArgumentException(BadRange);

    }

    /**

     * Checks an {@code int} range for validity.

     *

     * @param origin the least value that can be returned

     * @param bound the upper bound (exclusive) for the returned value

     * @throws IllegalArgumentException if {@code origin} is greater than

     *         or equal to {@code bound}

     */

    public static void checkRange(int origin, int bound) {

        if (origin >= bound)

            throw new IllegalArgumentException(BadRange);

    }

    /**

     * Checks a {@code long} range for validity.

     *

     * @param origin the least value that can be returned

     * @param bound the upper bound (exclusive) for the returned value

     * @throws IllegalArgumentException if {@code origin} is greater than

     *         or equal to {@code bound}

     */

    public static void checkRange(long origin, long bound) {

        if (origin >= bound)

            throw new IllegalArgumentException(BadRange);

    }

    public static long[] convertSeedBytesToLongs(byte[] seed, int n, int z) {

	final long[] result = new long[n];

	final int m = Math.min(seed.length, n << 3);

	// Distribute seed bytes into the words to be formed.

	for (int j = 0; j < m; j++) {

	    result[j>>3] = (result[j>>3] << 8) | seed[j];

	}

	// If there aren't enough seed bytes for all the words we need,

	// use a SplitMix-style PRNG to fill in the rest.

	long v = result[0];

	for (int j = (m + 7) >> 3; j < n; j++) {

	    result[j] = mixMurmur64(v += SILVER_RATIO_64);

	}

	// Finally, we need to make sure the last z words are not all zero.

	search: {

	    for (int j = n - z; j < n; j++) {

		if (result[j] != 0) break search;

	    }

	    // If they are, fill in using a SplitMix-style PRNG.

	    // Using "& ~1L" in the next line defends against the case z==1

	    // by guaranteeing that the first generated value will be nonzero.

	    long w = result[0] & ~1L;

	    for (int j = n - z; j < n; j++) {

		result[j] = mixMurmur64(w += SILVER_RATIO_64);

	    }

	}

	return result;

    }

    public static int[] convertSeedBytesToInts(byte[] seed, int n, int z) {

	final int[] result = new int[n];

	final int m = Math.min(seed.length, n << 2);

	// Distribute seed bytes into the words to be formed.

	for (int j = 0; j < m; j++) {

	    result[j>>2] = (result[j>>2] << 8) | seed[j];

	}

	// If there aren't enough seed bytes for all the words we need,

	// use a SplitMix-style PRNG to fill in the rest.

	int v = result[0];

	for (int j = (m + 3) >> 2; j < n; j++) {

	    result[j] = mixMurmur32(v += SILVER_RATIO_32);

	}

	// Finally, we need to make sure the last z words are not all zero.

	search: {

	    for (int j = n - z; j < n; j++) {

		if (result[j] != 0) break search;

	    }

	    // If they are, fill in using a SplitMix-style PRNG.

	    // Using "& ~1" in the next line defends against the case z==1

	    // by guaranteeing that the first generated value will be nonzero.

	    int w = result[0] & ~1;

	    for (int j = n - z; j < n; j++) {

		result[j] = mixMurmur32(w += SILVER_RATIO_32);

	    }

	}

	return result;

    }

    /*

     * Bounded versions of nextX methods used by streams, as well as

     * the public nextX(origin, bound) methods.  These exist mainly to

     * avoid the need for multiple versions of stream spliterators

     * across the different exported forms of streams.

     */

    /**

     * This is the form of {@code nextLong} used by a {@code LongStream}

     * {@code Spliterator} and by the public method

     * {@code nextLong(origin, bound)}.  If {@code origin} is greater

     * than {@code bound}, then this method simply calls the unbounded

     * version of {@code nextLong()}, choosing pseudorandomly from

     * among all 2<sup>64</sup> possible {@code long} values}, and

     * otherwise uses one or more calls to {@code nextLong()} to

     * choose a value pseudorandomly from the possible values

     * between {@code origin} (inclusive) and {@code bound} (exclusive).

     *

     * @implNote This method first calls {@code nextLong()} to obtain

     * a {@code long} value that is assumed to be pseudorandomly

     * chosen uniformly and independently from the 2<sup>64</sup>

     * possible {@code long} values (that is, each of the 2<sup>64</sup>

     * possible long values is equally likely to be chosen).

     * Under some circumstances (when the specified range is not

     * a power of 2), {@code nextLong()} may be called additional times

     * to ensure that that the values in the specified range are

     * equally likely to be chosen (provided the assumption holds).

     *

     * <p> The implementation considers four cases:

     * <ol>

     *

     * <li> If the {@code} bound} is less than or equal to the {@code origin}

     *      (indicated an unbounded form), the 64-bit {@code long} value

     *      obtained from {@code nextLong()} is returned directly.

     *

     * <li> Otherwise, if the length <it>n</it> of the specified range is an

     *      exact power of two 2<sup><it>m</it></sup> for some integer

     *      <it>m</it>, then return the sum of {@code origin} and the

     *      <it>m</it> lowest-order bits of the value from {@code nextLong()}.

     *

     * <li> Otherwise, if the length <it>n</it> of the specified range

     *      is less than 2<sup>63</sup>, then the basic idea is to use the

     *      remainder modulo <it>n</it> of the value from {@code nextLong()},

     *      but with this approach some values will be over-represented.

     *      Therefore a loop is used to avoid potential bias by rejecting

     *      candidates that are too large.  Assuming that the results from

     *      {@code nextLong()} are truly chosen uniformly and independently,

     *      the expected number of iterations will be somewhere between

     *      1 and 2, depending on the precise value of <it>n</it>.

     *

     * <li> Otherwise, the length <it>n</it> of the specified range

     *      cannot be represented as a positive {@code long} value.

     *      A loop repeatedly calls {@code nextlong()} until obtaining

     *      a suitable candidate,  Again, the expected number of iterations

     *      is less than 2.

     *

     * </ol>

     *

     * @param origin the least value that can be produced,

     *        unless greater than or equal to {@code bound}

     * @param bound the upper bound (exclusive), unless {@code origin}

     *        is greater than or equal to {@code bound}

     * @return a pseudorandomly chosen {@code long} value,

     *         which will be between {@code origin} (inclusive) and

     *         {@code bound} exclusive unless {@code origin}

     *         is greater than or equal to {@code bound}

     */

    public static long boundedNextLong(Rng rng, long origin, long bound) {

        long r = rng.nextLong();

        if (origin < bound) {

	    // It's not case (1).

            final long n = bound - origin;

	    final long m = n - 1;

            if ((n & m) == 0L) {

		// It is case (2): length of range is a power of 2.

                r = (r & m) + origin;

	    } else if (n > 0L) {

		// It is case (3): need to reject over-represented candidates.

		/* This loop takes an unlovable form (but it works):

		   because the first candidate is already available,

		   we need a break-in-the-middle construction,

		   which is concisely but cryptically performed

		   within the while-condition of a body-less for loop. */

                for (long u = r >>> 1;            // ensure nonnegative

                     u + m - (r = u % n) < 0L;    // rejection check

                     u = rng.nextLong() >>> 1) // retry

                    ;

                r += origin;

            }

            else {              

		// It is case (4): length of range not representable as long.

                while (r < origin || r >= bound)

                    r = rng.nextLong();

            }

        }

        return r;

    }

    /**

     * This is the form of {@code nextLong} used by the public method

     * {@code nextLong(bound)}.  This is essentially a version of

     * {@code boundedNextLong(origin, bound)} that has been

     * specialized for the case where the {@code origin} is zero

     * and the {@code bound} is greater than zero.  The value

     * returned is chosen pseudorandomly from nonnegative integer

     * values less than {@code bound}.

     *

     * @implNote This method first calls {@code nextLong()} to obtain

     * a {@code long} value that is assumed to be pseudorandomly

     * chosen uniformly and independently from the 2<sup>64</sup>

     * possible {@code long} values (that is, each of the 2<sup>64</sup>

     * possible long values is equally likely to be chosen).

     * Under some circumstances (when the specified range is not

     * a power of 2), {@code nextLong()} may be called additional times

     * to ensure that that the values in the specified range are

     * equally likely to be chosen (provided the assumption holds).

     *

     * <p> The implementation considers two cases:

     * <ol>

     *

     * <li> If {@code bound} is an exact power of two 2<sup><it>m</it></sup>

     *      for some integer <it>m</it>, then return the sum of {@code origin}

     *      and the <it>m</it> lowest-order bits of the value from

     *      {@code nextLong()}.

     *

     * <li> Otherwise, the basic idea is to use the remainder modulo

     *      <it>bound</it> of the value from {@code nextLong()},

     *      but with this approach some values will be over-represented.

     *      Therefore a loop is used to avoid potential bias by rejecting

     *      candidates that vare too large.  Assuming that the results from

     *      {@code nextLong()} are truly chosen uniformly and independently,

     *      the expected number of iterations will be somewhere between

     *      1 and 2, depending on the precise value of <it>bound</it>.

     *

     * </ol>

     *

     * @param bound the upper bound (exclusive); must be greater than zero

     * @return a pseudorandomly chosen {@code long} value

     */

    public static long boundedNextLong(Rng rng, long bound) {

        // Specialize boundedNextLong for origin == 0, bound > 0

        final long m = bound - 1;

        long r = rng.nextLong();

        if ((bound & m) == 0L) {

	    // The bound is a power of 2.

            r &= m;

	} else {

	    // Must reject over-represented candidates

	    /* This loop takes an unlovable form (but it works):

	       because the first candidate is already available,

	       we need a break-in-the-middle construction,

	       which is concisely but cryptically performed

	       within the while-condition of a body-less for loop. */

            for (long u = r >>> 1;

                 u + m - (r = u % bound) < 0L;

                 u = rng.nextLong() >>> 1)

                ;

        }

        return r;

    }

    /**

     * This is the form of {@code nextInt} used by an {@code IntStream}

     * {@code Spliterator} and by the public method

     * {@code nextInt(origin, bound)}.  If {@code origin} is greater

     * than {@code bound}, then this method simply calls the unbounded

     * version of {@code nextInt()}, choosing pseudorandomly from

     * among all 2<sup>64</sup> possible {@code int} values}, and

     * otherwise uses one or more calls to {@code nextInt()} to

     * choose a value pseudorandomly from the possible values

     * between {@code origin} (inclusive) and {@code bound} (exclusive).

     *

     * @implNote The implementation of this method is identical to

     *     the implementation of {@code nextLong(origin, bound)}

     *     except that {@code int} values and the {@code nextInt()}

     *     method are used rather than {@code long} values and the

     *     {@code nextLong()} method.

     *

     * @param origin the least value that can be produced,

     *        unless greater than or equal to {@code bound}

     * @param bound the upper bound (exclusive), unless {@code origin}

     *        is greater than or equal to {@code bound}

     * @return a pseudorandomly chosen {@code int} value,

     *         which will be between {@code origin} (inclusive) and

     *         {@code bound} exclusive unless {@code origin}

     *         is greater than or equal to {@code bound}

     */

    public static int boundedNextInt(Rng rng, int origin, int bound) {

        int r = rng.nextInt();

        if (origin < bound) {

	    // It's not case (1).

            final int n = bound - origin;

	    final int m = n - 1;

            if ((n & m) == 0) {

		// It is case (2): length of range is a power of 2.

                r = (r & m) + origin;

	    } else if (n > 0) {

		// It is case (3): need to reject over-represented candidates.

                for (int u = r >>> 1;

                     u + m - (r = u % n) < 0;

                     u = rng.nextInt() >>> 1)

                    ;

                r += origin;

            }

            else {

		// It is case (4): length of range not representable as long.

                while (r < origin || r >= bound)

		    r = rng.nextInt();

            }

        }

        return r;

    }

    /**

     * This is the form of {@code nextInt} used by the public method

     * {@code nextInt(bound)}.  This is essentially a version of

     * {@code boundedNextInt(origin, bound)} that has been

     * specialized for the case where the {@code origin} is zero

     * and the {@code bound} is greater than zero.  The value

     * returned is chosen pseudorandomly from nonnegative integer

     * values less than {@code bound}.

     *

     * @implNote The implementation of this method is identical to

     *     the implementation of {@code nextLong(bound)}

     *     except that {@code int} values and the {@code nextInt()}

     *     method are used rather than {@code long} values and the

     *     {@code nextLong()} method.

     *

     * @param bound the upper bound (exclusive); must be greater than zero

     * @return a pseudorandomly chosen {@code long} value

     */

    public static int boundedNextInt(Rng rng, int bound) {

        // Specialize boundedNextInt for origin == 0, bound > 0

        final int m = bound - 1;

        int r = rng.nextInt();

        if ((bound & m) == 0) {

	    // The bound is a power of 2.

            r &= m;

	} else {

	    // Must reject over-represented candidates

            for (int u = r >>> 1;

                 u + m - (r = u % bound) < 0;

                 u = rng.nextInt() >>> 1)

                ;

        }

        return r;

    }

    /**

     * This is the form of {@code nextDouble} used by a {@code DoubleStream}

     * {@code Spliterator} and by the public method

     * {@code nextDouble(origin, bound)}.  If {@code origin} is greater

     * than {@code bound}, then this method simply calls the unbounded

     * version of {@code nextDouble()}, and otherwise scales and translates

     * the result of a call to {@code nextDouble()} so that it lies

     * between {@code origin} (inclusive) and {@code bound} (exclusive).

     *

     * @implNote The implementation considers two cases:

     * <ol>

     *

     * <li> If the {@code bound} is less than or equal to the {@code origin}

     *      (indicated an unbounded form), the 64-bit {@code double} value

     *      obtained from {@code nextDouble()} is returned directly.

     *

     * <li> Otherwise, the result of a call to {@code nextDouble} is

     *      multiplied by {@code (bound - origin)}, then {@code origin}

     *      is added, and then if this this result is not less than

     *      {@code bound} (which can sometimes occur because of rounding),

     *      it is replaced with the largest {@code double} value that

     *      is less than {@code bound}.

     *

     * </ol>

     *

     * @param origin the least value that can be produced,

     *        unless greater than or equal to {@code bound}; must be finite

     * @param bound the upper bound (exclusive), unless {@code origin}

     *        is greater than or equal to {@code bound}; must be finite

     * @return a pseudorandomly chosen {@code double} value,

     *         which will be between {@code origin} (inclusive) and