/*

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

 */

/*

 * This file is available under and governed by the GNU General Public

 * License version 2 only, as published by the Free Software Foundation.

 * However, the following notice accompanied the original version of this

 * file:

 *

 * Written by Doug Lea with assistance from members of JCP JSR-166

 * Expert Group and released to the public domain, as explained at

 * http://creativecommons.org/publicdomain/zero/1.0/

 */

package java.util.concurrent;

import java.io.ObjectStreamField;

import java.util.Random;

import java.util.Spliterator;

import java.util.concurrent.atomic.AtomicInteger;

import java.util.concurrent.atomic.AtomicLong;

import java.util.function.DoubleConsumer;

import java.util.function.IntConsumer;

import java.util.function.LongConsumer;

import java.util.stream.DoubleStream;

import java.util.stream.IntStream;

import java.util.stream.LongStream;

import java.util.stream.StreamSupport;

/**

 * A random number generator isolated to the current thread.  Like the

 * global {@link java.util.Random} generator used by the {@link

 * java.lang.Math} class, a {@code ThreadLocalRandom} is initialized

 * with an internally generated seed that may not otherwise be

 * modified. When applicable, use of {@code ThreadLocalRandom} rather

 * than shared {@code Random} objects in concurrent programs will

 * typically encounter much less overhead and contention.  Use of

 * {@code ThreadLocalRandom} is particularly appropriate when multiple

 * tasks (for example, each a {@link ForkJoinTask}) use random numbers

 * in parallel in thread pools.

 *

 * <p>Usages of this class should typically be of the form:

 * {@code ThreadLocalRandom.current().nextX(...)} (where

 * {@code X} is {@code Int}, {@code Long}, etc).

 * When all usages are of this form, it is never possible to

 * accidently share a {@code ThreadLocalRandom} across multiple threads.

 *

 * <p>This class also provides additional commonly used bounded random

 * generation methods.

 *

 * <p>Instances of {@code ThreadLocalRandom} are not cryptographically

 * secure.  Consider instead using {@link java.security.SecureRandom}

 *

 * @since 1.7

 * @author Doug Lea

 */

public class ThreadLocalRandom extends Random {

    /*

     * This class implements the java.util.Random API (and subclasses

     * Random) using a single static instance that accesses random

     * number state held in class Thread (primarily, field

     * threadLocalRandomSeed). In doing so, it also provides a home

     * for managing package-private utilities that rely on exactly the

     * same state as needed to maintain the ThreadLocalRandom

     * instances. We leverage the need for an initialization flag

     * field to also use it as a "probe" -- a self-adjusting thread

     * hash used for contention avoidance, as well as a secondary

     * simpler (xorShift) random seed that is conservatively used to

     * avoid otherwise surprising users by hijacking the

     * ThreadLocalRandom sequence.  The dual use is a marriage of

     * convenience, but is a simple and efficient way of reducing

     * application-level overhead and footprint of most concurrent

     * programs.

     *

     * Even though this class subclasses java.util.Random, it uses the

     * same basic algorithm as java.util.SplittableRandom.  (See its

     * internal documentation for explanations, which are not repeated

     * here.)  Because ThreadLocalRandoms are not splittable

     * though, we use only a single 64bit gamma.

     *

     * Because this class is in a different package than class Thread,

     * field access methods use Unsafe to bypass access control rules.

     * To conform to the requirements of the Random superclass

     * constructor, the common static ThreadLocalRandom maintains an

     * "initialized" field for the sake of rejecting user calls to

     * setSeed while still allowing a call from constructor.  Note

     * that serialization is completely unnecessary because there is

     * only a static singleton.  But we generate a serial form

     * containing "rnd" and "initialized" fields to ensure

     * compatibility across versions.

     *

     * Implementations of non-core methods are mostly the same as in

     * SplittableRandom, that were in part derived from a previous

     * version of this class.

     *

     * The nextLocalGaussian ThreadLocal supports the very rarely used

     * nextGaussian method by providing a holder for the second of a

     * pair of them. As is true for the base class version of this

     * method, this time/space tradeoff is probably never worthwhile,

     * but we provide identical statistical properties.

     */

    /** Generates per-thread initialization/probe field */

    private static final AtomicInteger probeGenerator =

        new AtomicInteger();

    /**

     * The next seed for default constructors.

     */

    /**

     * The seed increment

     */

    private static final long GAMMA = 0x9e3779b97f4a7c15L;

    /**

     * The increment for generating probe values

     */

    private static final int PROBE_INCREMENT = 0x9e3779b9;

    /**

     * The increment of seeder per new instance

     */

    private static final long SEEDER_INCREMENT = 0xbb67ae8584caa73bL;

    // Constants from SplittableRandom

    private static final double DOUBLE_UNIT = 1.0 / (1L << 53);

    private static final float  FLOAT_UNIT  = 1.0f / (1 << 24);

    /** Rarely-used holder for the second of a pair of Gaussians */

    private static final ThreadLocal<Double> nextLocalGaussian =

        new ThreadLocal<Double>();

    private static long mix64(long z) {

        z = (z ^ (z >>> 33)) * 0xff51afd7ed558ccdL;

        z = (z ^ (z >>> 33)) * 0xc4ceb9fe1a85ec53L;

        return z ^ (z >>> 33);

    }

    private static int mix32(long z) {

        z = (z ^ (z >>> 33)) * 0xff51afd7ed558ccdL;

        return (int)(((z ^ (z >>> 33)) * 0xc4ceb9fe1a85ec53L) >>> 32);

    }

    /**

     * Field used only during singleton initialization.

     * True when constructor completes.

     */

    boolean initialized;

    /** Constructor used only for static singleton */

    private ThreadLocalRandom() {

        initialized = true; // false during super() call

    }

    /** The common ThreadLocalRandom */

    static final ThreadLocalRandom instance = new ThreadLocalRandom();

    /**

     * Initialize Thread fields for the current thread.  Called only

     * when Thread.threadLocalRandomProbe is zero, indicating that a

     * thread local seed value needs to be generated. Note that even

     * though the initialization is purely thread-local, we need to

     * rely on (static) atomic generators to initialize the values.

     */

    static final void localInit() {

        int p = probeGenerator.addAndGet(PROBE_INCREMENT);

        int probe = (p == 0) ? 1 : p; // skip 0

        long seed = mix64(seeder.getAndAdd(SEEDER_INCREMENT));

        Thread t = Thread.currentThread();

        UNSAFE.putLong(t, SEED, seed);

        UNSAFE.putInt(t, PROBE, probe);

    }

    /**

     * Returns the current thread's {@code ThreadLocalRandom}.

     *

     * @return the current thread's {@code ThreadLocalRandom}

     */

    public static ThreadLocalRandom current() {

        if (UNSAFE.getInt(Thread.currentThread(), PROBE) == 0)

            localInit();

        return instance;

    }

    /**

     * Throws {@code UnsupportedOperationException}.  Setting seeds in

     * this generator is not supported.

     *

     * @throws UnsupportedOperationException always

     */

    public void setSeed(long seed) {

        // only allow call from super() constructor

        if (initialized)

            throw new UnsupportedOperationException();

    }

    final long nextSeed() {

        Thread t; long r; // read and update per-thread seed

        UNSAFE.putLong(t = Thread.currentThread(), SEED,

                       r = UNSAFE.getLong(t, SEED) + GAMMA);

        return r;

    }

    // We must define this, but never use it.

    protected int next(int bits) {

        return (int)(mix64(nextSeed()) >>> (64 - bits));

    }

    // IllegalArgumentException messages

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

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

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

    /**

     * The form of nextLong used by LongStream Spliterators.  If

     * origin is greater than bound, acts as unbounded form of

     * nextLong, else as bounded form.

     *

     * @param origin the least value, unless greater than bound

     * @param bound the upper bound (exclusive), must not equal origin

     * @return a pseudorandom value

     */

    final long internalNextLong(long origin, long bound) {

        long r = mix64(nextSeed());

        if (origin < bound) {

            long n = bound - origin, m = n - 1;

            if ((n & m) == 0L)  // power of two

                r = (r & m) + origin;

            else if (n > 0L) {  // reject over-represented candidates

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

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

                     u = mix64(nextSeed()) >>> 1) // retry

                    ;

                r += origin;

            }

            else {              // range not representable as long

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

                    r = mix64(nextSeed());

            }

        }

        return r;

    }

    /**

     * The form of nextInt used by IntStream Spliterators.

     * Exactly the same as long version, except for types.

     *

     * @param origin the least value, unless greater than bound

     * @param bound the upper bound (exclusive), must not equal origin

     * @return a pseudorandom value

     */

    final int internalNextInt(int origin, int bound) {

        int r = mix32(nextSeed());

        if (origin < bound) {

            int n = bound - origin, m = n - 1;

            if ((n & m) == 0)

                r = (r & m) + origin;

            else if (n > 0) {

                for (int u = r >>> 1;

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

                     u = mix32(nextSeed()) >>> 1)

                    ;

                r += origin;

            }

            else {

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

                    r = mix32(nextSeed());

            }

        }

        return r;

    }

    /**

     * The form of nextDouble used by DoubleStream Spliterators.

     *

     * @param origin the least value, unless greater than bound

     * @param bound the upper bound (exclusive), must not equal origin

     * @return a pseudorandom value

     */

    final double internalNextDouble(double origin, double bound) {

        double r = (nextLong() >>> 11) * DOUBLE_UNIT;

        if (origin < bound) {

            r = r * (bound - origin) + origin;

            if (r >= bound) // correct for rounding

                r = Double.longBitsToDouble(Double.doubleToLongBits(bound) - 1);

        }

        return r;

    }

    /**

     * Returns a pseudorandom {@code int} value.

     *

     * @return a pseudorandom {@code int} value

     */

    public int nextInt() {

        return mix32(nextSeed());

    }

    /**

     * Returns a pseudorandom {@code int} value between zero (inclusive)

     * and the specified bound (exclusive).

     *

     * @param bound the upper bound (exclusive).  Must be positive.

     * @return a pseudorandom {@code int} value between zero

     *         (inclusive) and the bound (exclusive)

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

     */

    public int nextInt(int bound) {

        if (bound <= 0)

            throw new IllegalArgumentException(BadBound);

        int r = mix32(nextSeed());

        int m = bound - 1;

        if ((bound & m) == 0) // power of two

            r &= m;

        else { // reject over-represented candidates

            for (int u = r >>> 1;

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

                 u = mix32(nextSeed()) >>> 1)

                ;

        }

        return r;

    }

    /**

     * Returns a pseudorandom {@code int} value between the specified

     * origin (inclusive) and the specified bound (exclusive).

     *

     * @param origin the least value returned

     * @param bound the upper bound (exclusive)

     * @return a pseudorandom {@code int} value between the origin

     *         (inclusive) and the bound (exclusive)

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

     *         or equal to {@code bound}

     */

    public int nextInt(int origin, int bound) {

        if (origin >= bound)

            throw new IllegalArgumentException(BadRange);

        return internalNextInt(origin, bound);

    }

    /**

     * Returns a pseudorandom {@code long} value.

     *

     * @return a pseudorandom {@code long} value

     */

    public long nextLong() {

        return mix64(nextSeed());

    }

    /**

     * Returns a pseudorandom {@code long} value between zero (inclusive)

     * and the specified bound (exclusive).

     *

     * @param bound the upper bound (exclusive).  Must be positive.

     * @return a pseudorandom {@code long} value between zero

     *         (inclusive) and the bound (exclusive)

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

     */

    public long nextLong(long bound) {

        if (bound <= 0)

            throw new IllegalArgumentException(BadBound);

        long r = mix64(nextSeed());

        long m = bound - 1;

        if ((bound & m) == 0L) // power of two

            r &= m;

        else { // reject over-represented candidates

            for (long u = r >>> 1;

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

                 u = mix64(nextSeed()) >>> 1)

                ;

        }

        return r;

    }

    /**

     * Returns a pseudorandom {@code long} value between the specified

     * origin (inclusive) and the specified bound (exclusive).

     *

     * @param origin the least value returned

     * @param bound the upper bound (exclusive)

     * @return a pseudorandom {@code long} value between the origin

     *         (inclusive) and the bound (exclusive)

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

     *         or equal to {@code bound}

     */

    public long nextLong(long origin, long bound) {

        if (origin >= bound)

            throw new IllegalArgumentException(BadRange);

        return internalNextLong(origin, bound);

    }

    /**

     * Returns a pseudorandom {@code double} value between zero

     * (inclusive) and one (exclusive).

     *

     * @return a pseudorandom {@code double} value between zero

     *         (inclusive) and one (exclusive)

     */

    public double nextDouble() {

        return (mix64(nextSeed()) >>> 11) * DOUBLE_UNIT;

    }

    /**

     * Returns a pseudorandom {@code double} value between 0.0

     * (inclusive) and the specified bound (exclusive).

     *

     * @param bound the upper bound (exclusive).  Must be positive.

     * @return a pseudorandom {@code double} value between zero

     *         (inclusive) and the bound (exclusive)

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

     */

    public double nextDouble(double bound) {

        if (!(bound > 0.0))

            throw new IllegalArgumentException(BadBound);

        double result = (mix64(nextSeed()) >>> 11) * DOUBLE_UNIT * bound;

        return (result < bound) ?  result : // correct for rounding

            Double.longBitsToDouble(Double.doubleToLongBits(bound) - 1);

    }

    /**

     * Returns a pseudorandom {@code double} value between the specified

     * origin (inclusive) and bound (exclusive).

     *

     * @param origin the least value returned

     * @param bound the upper bound (exclusive)