/*
 * Written by Doug and released to the public domain, as explained at
 * http://creativecommons.org/licenses/publicdomain
 */

import java.util.*;

/**
 * Static factory methods returning random number generators of
 * varying qualities and speeds.  All returned generators are
 * subclasses of {@link java.util.Random} and thus provide the same
 * API. 
 *
 * <p>Algorithms are adapted from those described by George Masaglia's
 * paper "Xorshift RNGs" and various followups by others.  Xorshift
 * random number generators are a class of generators with very good
 * performance for various quality targets. The precise algorithms
 * used by these generators are subject to change over time. For this
 * reason, the generators do not accept initial "seed" parameters that
 * would otherwise imply a guarantee that they produce the same
 * sequence with the same seed.
 *
 * <p> The xorShift1 generator is among the fastest simple random
 * number generators available. The xorShift4 generator is a bit
 * slower but passes common random number quality tests. The xorShift8
 * generator is slower still but passes a much larger suite of quality
 * tests.
 *
 * <p>The generators do <em>not</em> employ synchronization, so
 * should ordinarily be used only if access is otherwise confined
 * to a single thread.
 */
public class XorShiftRandomFactory {
    private XorShiftRandomFactory() {} // non-instantiable

    /**
     * Return a generator optimized for speed over quality, and with a
     * seed that is unlikely to be the same as used in any other
     * generator.  The generator has period no less than
     * (2<sup>32</sup>-1). This generator may be useful for example in
     * driving performance tests requiring irregular sequences of
     * values, but might not pass enough quality tests to be useful in
     * contexts requring statistical independence.
     */
    public static Random xorShift1() {
        return new XorShift1();
    }

    /**
     * Return a generator of medium quality and speed, and with a seed
     * that is unlikely to be the same as used in any other generator.
     * The generator uses among the fastest algorithms that pass the
     * "diehard" tests. 
     */
    public static Random xorShift4() {
        return new XorShift4();
    }

    /**
     * Return a generator of high quality, and with a seed that is
     * unlikely to be the same as used in any other generator.  The
     * generator uses among the fastest algorithms that pass both the
     * "diehard" and "crash" tests. 
     */
    public static Random xorShift8() {
        return new XorShift8();
    }

    /**
     * Basic one-seed xorshift update with params (1, 3, 10), which is
     * reported to work well by Richard P. Brent in "Note on
     * Marsaglia's Xorshift Random Number Generators".
     * 
     * @param s seed
     * @return xorshift of seed
     */
    static final int xs(int s) {
        s ^= s << 1; 
        s ^= s >>> 3; 
        return s ^ (s << 10);
    }

    /**
     * One-seed Marsaglia xorshift from "Xorshift RNGs" paper, page 4.
     */
    static final class XorShift1 extends Random implements java.io.Serializable {
        private int s0;
        XorShift1() { super(); }
        public void setSeed(long seed) {
            super.setSeed(seed);
            // ensure nonzero seed
            if ((s0 = (int)(seed & 0xffffffffL)) == 0 && 
                (s0 = (int)(seed >>> 32)) == 0)
                s0 = 1;
        }

        private final int update() {
            int s = s0; // performance tweak: manually inline xs function
            s ^= s << 1; 
            s ^= s >>> 3; 
            s0 = s ^= s << 10;
            return s;
        }

        protected final int next(int bits) {
            return update() >>> (32 - bits);
        }

        public final void nextBytes(byte[] bytes) {
            for (int i = 0; i < bytes.length; ++i)
                bytes[i] = (byte)(update() & 0xff);
        }

        public final int nextInt() {
            return update();
        }

        public final int nextInt(int n) {
            if (n <= 0)
                throw new IllegalArgumentException("n must be positive");
            for (;;) {
                int bits = update() >>> 1;
                int val = bits % n;
                if (bits - val + (n-1) >= 0)
                    return val;
            }
        }

        public final long nextLong() {
            return ((long)(update()) << 32) | ((long)(update()) & 0xffffffffL);
        }
        
        public final boolean nextBoolean() {
            return (update() & 1) != 0;
        }

        public final float nextFloat() {
            return (update() >>> 8) * (float)(1.0f / (1 << 24));
        }

        public final double nextDouble() {
            int a = update();
            return ((a >>> 1)  * (1.0 / (1 << 31)) +
                    ((a >>> 31) & 1) * (1.0 / (1L << 32)));
        }
    }

    /**
     * Four-seed Marsaglia xorshift from "Xorshift RNGs" paper, page 5.
     */
    static final class XorShift4 extends Random implements java.io.Serializable {
        private int s0, s1, s2, s3;
        XorShift4() { super(); }
        public void setSeed(long seed) {
            super.setSeed(seed);
            // Use simple xorshift mixed with arbitrary seeds for s2-s3
            s0 = (int)(seed & 0xffffffffL);
            s1 = (int)(seed >>> 32);
            s2 = xs(s0) + -715159705;
            s3 = xs(s1) + 273326509;
            if (s3 == 0)
                s3 = 1; // ensure at least one nonzero
        }

        private  int update() {  
            int t = s0;
            t ^= t << 11;
            s0 = s1; 
            s1 = s2; 
            int w = s2 = s3;
            s3 = t = (t ^ (t >>> 8)) ^ (w ^ (w >>> 19));
            return t;
        }

        public  void nextBytes(byte[] bytes) {
            for (int i = 0; i < bytes.length; ++i)
                bytes[i] = (byte)(update() & 0xff);
        }

        public  int nextInt() {
            return update();
        }

        public  int nextInt(int n) {
            if (n <= 0)
                throw new IllegalArgumentException("n must be positive");
            for (;;) {
                int bits = update() >>> 1;
                int val = bits % n;
                if (bits - val + (n-1) >= 0)
                    return val;
            }
        }

        public  long nextLong() {
            return ((long)(update()) << 32) + update();
        }
        
        public  boolean nextBoolean() {
            return (update() & 1) != 0;
        }

        public  float nextFloat() {
            return (update() >>> 8) / ((float)(1 << 24));
        }

        public  double nextDouble() {
            int a = update();
            int b = update();
            return (((long)(a >>> 6) << 27) + (b >>> 5)) / (double)(1L << 53);
        }

    }

    
    /**
     * Eight-seed xorshift adapted from Panneton & L'Ecuyer "On the
     * Xorshift random number generators", figure 1.  This version
     * uses 8 distinct seeds rather than array, so requires manual
     * cycling but avoids array indexing overhead, which seems to be
     * the best tradeoff.
     */
    static final class XorShift8 extends Random implements java.io.Serializable {
        private int s0, s1, s2, s3, s4, s5, s6, s7;
        XorShift8() { super(); }
        public void setSeed(long seed) {
            super.setSeed(seed);
            // Use simple xorshift mixed with arbitrary seeds for s2-s7
            int a = s0 = (int)(seed & 0xffffffffL);
            int b = s1 = (int)(seed >>> 32);
            s2 = (a = xs(a)) + -715159705;
            s3 = (b = xs(b)) + 273326509;
            s4 = (a = xs(a)) + -1831433054;
            s5 = (b = xs(b)) + 0x61c88647;
            s6 = (a = xs(a)) + 362436069;
            s7 = (b = xs(b)) + 521288629;
            if (s7 == 0)
                s7 = 1; // ensure at least one nonzero
        }

        private  int update() {  
            int r = s7;
            r ^= r << 13;
            r ^= r <<  9;
            s7 = s6; 
            s6 = s5; 
            int v = s5 = s4;
            r ^= v ^ (v << 7);
            v = s4 = s3;
            r ^= v ^ (v >>> 3);
            s3 = s2; 
            v = s2 = s1;
            r ^= v ^ (v >>> 10);
            v = s1 = s0;
            v ^= v >>> 7;
            v ^= v << 24;
            s0 = r ^= v;
            return r;
        }

        public  void nextBytes(byte[] bytes) {
            for (int i = 0; i < bytes.length; ++i)
                bytes[i] = (byte)(update() & 0xff);
        }

        public  int nextInt() {
            return update();
        }

        public  int nextInt(int n) {
            if (n <= 0)
                throw new IllegalArgumentException("n must be positive");
            for (;;) {
                int bits = update() >>> 1;
                int val = bits % n;
                if (bits - val + (n-1) >= 0)
                    return val;
            }
        }

        public  long nextLong() {
            return ((long)(update()) << 32) + update();
        }
        
        public  boolean nextBoolean() {
            return (update() & 1) != 0;
        }

        public  float nextFloat() {
            return (update() >>> 8) / ((float)(1 << 24));
        }

        public  double nextDouble() {
            int a = update();
            int b = update();
            return (((long)(a >>> 6) << 27) + (b >>> 5)) / (double)(1L << 53);
        }
    }
}