/*

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

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

 *

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

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

 * published by the Free Software Foundation.  Oracle designates this

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

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

 *

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

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

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

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

 * accompanied this code).

 *

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

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

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

 *

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

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

 * questions.

 */

package java.util.random;

import java.util.function.Consumer;

import java.util.function.DoubleConsumer;

import java.util.function.IntConsumer;

import java.util.function.LongConsumer;

import java.util.random.RandomGenerator.SplittableGenerator;

import java.util.Spliterator;

import java.util.stream.DoubleStream;

import java.util.stream.IntStream;

import java.util.stream.LongStream;

import java.util.stream.Stream;

import java.util.stream.StreamSupport;

/**

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

 *

 * This class is mostly for library writers creating specific implementations of the

 * interface {@link RandomGenerator}.

 *

 * @since 14

 */

public class RandomSupport {

    /*

     * Implementation Overview.

     *

     * This class provides utility methods and constants frequently

     * useful in the implentation of pseudorandom number generators

     * that satisfy the interface {@link RandomGenerator}.

     *

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

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

     */

    // IllegalArgumentException messages

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

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

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

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

    static final String BAD_RANGE = "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(BAD_SIZE);

    }

    /**

     * 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(BAD_DISTANCE);

        }

    }

    /**

     * 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(BAD_FLOATING_BOUND);

        }

    }

    /**

     * 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(BAD_FLOATING_BOUND);

        }

    }

    /**

     * 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(BAD_BOUND);

        }

    }

    /**

     * 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(BAD_BOUND);

        }

    }

    /**

     * 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(BAD_RANGE);

        }

    }

    /**

     * 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(BAD_RANGE);

        }

    }

    /**

     * 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(BAD_RANGE);

        }

    }

    /**

     * 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(BAD_RANGE);

        }

    }

    /**

     * Given an array of seed bytes of any length, construct an array

     * of {@code long} seed values of length {@code n}, such that the

     * last {@code z} values are not all zero.

     *

     * @param seed an array of {@code byte} values

     * @param n the length of the result array (should be nonnegative)

     * @param z the number of trailing result elements that are required

     *        to be not all zero (should be nonnegative but not larger

     *        than {@code n})

     *

     * @return an array of length {@code n} containing {@code long} seed values

     */

    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;

    }

    /**

     * Given an array of seed bytes of any length, construct an array

     * of {@code int} seed values of length {@code n}, such that the

     * last {@code z} values are not all zero.

     *

     * @param seed an array of {@code byte} values

     * @param n the length of the result array (should be nonnegative)

     * @param z the number of trailing result elements that are required

     *        to be not all zero (should be nonnegative but not larger

     *        than {@code n})

     *

     * @return an array of length {@code n} containing {@code int} seed values

     */

    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 {@link LongStream}

     * {@link 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 <i>n</i> of the specified range is an

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

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

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

     *

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

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

     *      remainder modulo <i>n</i> 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 <i>n</i>.

     *

     * <li> Otherwise, the length <i>n</i> 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 rng a random number generator to be used as a

     *        source of pseudorandom {@code long} values

     * @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(RandomGenerator 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><i>m</i></sup>

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

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

     *      {@code nextLong()}.

     *

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

     *      <i>bound</i> 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 <i>bound</i>.

     *

     * </ol>

     *

     * @param rng a random number generator to be used as a

     *        source of pseudorandom {@code long} values

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

     *

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

     */

    public static long boundedNextLong(RandomGenerator 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 {@link IntStream}

     * {@link 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).

     *

     * @param rng a random number generator to be used as a

     *        source of pseudorandom {@code int} values

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

     *

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

     */

    public static int boundedNextInt(RandomGenerator 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}.

     *

     * @param rng a random number generator to be used as a

     *        source of pseudorandom {@code long} values

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

     *

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

     *

     * @implNote The implementation of this method is identical to