package stdlib;
/* ***********************************************************************
 *  Compilation:  javac StdRandom.java
 *  Execution:    java StdRandom
 *
 *  A library of static methods to generate pseudo-random numbers from
 *  different distributions (bernoulli, uniform, gaussian, discrete,
 *  and exponential). Also includes a method for shuffling an array.
 *
 *
 *  %  java StdRandom 5
 *  seed = 1316600602069
 *  59 16.81826  true 8.83954  0
 *  32 91.32098  true 9.11026  0
 *  35 10.11874  true 8.95396  3
 *  92 32.88401  true 8.87089  0
 *  72 92.55791  true 9.46241  0
 *
 *  % java StdRandom 5
 *  seed = 1316600616575
 *  96 60.17070  true 8.72821  0
 *  79 32.01607  true 8.58159  0
 *  81 59.49065  true 9.10423  1
 *  96 51.65818  true 9.02102  0
 *  99 17.55771  true 8.99762  0
 *
 *  % java StdRandom 5 1316600616575
 *  seed = 1316600616575
 *  96 60.17070  true 8.72821  0
 *  79 32.01607  true 8.58159  0
 *  81 59.49065  true 9.10423  1
 *  96 51.65818  true 9.02102  0
 *  99 17.55771  true 8.99762  0
 *
 *
 *  Remark
 *  ------
 *    - Relies on randomness of nextDouble() method in java.util.Random
 *      to generate pseudorandom numbers in [0, 1).
 *
 *    - This library allows you to set and get the pseudorandom number seed.
 *
 *    - See http://www.honeylocust.com/RngPack/ for an industrial
 *      strength random number generator in Java.
 *
 *************************************************************************/

import java.util.Random;

/**
 *  <i>Standard random</i>. This class provides methods for generating
 *  random number from various distributions.
 *  <p>
 *  For additional documentation, see <a href="http://introcs.cs.princeton.edu/22library">Section 2.2</a> of
 *  <i>Introduction to Programming in Java: An Interdisciplinary Approach</i> by Robert Sedgewick and Kevin Wayne.
 */
public final class StdRandom {

	private static Random random;    // pseudo-random number generator
	private static long seed;        // pseudo-random number generator seed

	// static initializer
	static {
		// this is how the seed was set in Java 1.4
		seed = System.currentTimeMillis();
		random = new Random(seed);
	}

	// don't instantiate
	private StdRandom() { }

	/**
	 * Set the seed of the psedurandom number generator.
	 */
	public static void setSeed(long s) {
		seed   = s;
		random = new Random(seed);
	}

	/**
	 * Get the seed of the psedurandom number generator.
	 */
	public static long getSeed() {
		return seed;
	}

	/**
	 * Return real number uniformly in [0, 1).
	 */
	public static double uniform() {
		return random.nextDouble();
	}

	/**
	 * Return an integer uniformly between 0 (inclusive) and N (exclusive).
	 */
	public static int uniform(int N) {
		return random.nextInt(N);
	}

	///////////////////////////////////////////////////////////////////////////
	//  STATIC METHODS BELOW RELY ON JAVA.UTIL.RANDOM ONLY INDIRECTLY VIA
	//  THE STATIC METHODS ABOVE.
	///////////////////////////////////////////////////////////////////////////

	/**
	 * Return real number uniformly in [0, 1).
	 */
	public static double random() {
		return uniform();
	}

	/**
	 * Return int uniformly in [a, b).
	 */
	public static int uniform(int a, int b) {
		return (int) (a + uniform() * (((double)b)-((double)a)));
	}

	/**
	 * Return real number uniformly in [a, b).
	 */
	public static double uniform(double a, double b) {
		return a + uniform() * (b-a);
	}

	/**
	 * Return a boolean, which is true with probability p, and false otherwise.
	 */
	public static boolean bernoulli(double p) {
		return uniform() < p;
	}

	/**
	 * Return a boolean, which is true with probability .5, and false otherwise.
	 */
	public static boolean bernoulli() {
		return bernoulli(0.5);
	}

	/**
	 * Return a real number with a standard Gaussian distribution.
	 */
	public static double gaussian() {
		// use the polar form of the Box-Muller transform
		double r, x, y;
		do {
			x = uniform(-1.0, 1.0);
			y = uniform(-1.0, 1.0);
			r = x*x + y*y;
		} while (r >= 1 || r == 0);
		return x * Math.sqrt(-2 * Math.log(r) / r);

		// Remark:  y * Math.sqrt(-2 * Math.log(r) / r)
		// is an independent random gaussian
	}

	/**
	 * Return a real number from a gaussian distribution with given mean and stddev
	 */
	public static double gaussian(double mean, double stddev) {
		return mean + stddev * gaussian();
	}

	/**
	 * Return an integer with a geometric distribution with mean 1/p.
	 */
	public static int geometric(double p) {
		// using algorithm given by Knuth
		return (int) Math.ceil(Math.log(uniform()) / Math.log(1.0 - p));
	}

	/**
	 * Return an integer with a Poisson distribution with mean lambda.
	 */
	public static int poisson(double lambda) {
		// using algorithm given by Knuth
		// see http://en.wikipedia.org/wiki/Poisson_distribution
		int k = 0;
		double p = 1.0;
		double L = Math.exp(-lambda);
		do {
			k++;
			p *= uniform();
		} while (p >= L);
		return k-1;
	}

	/**
	 * Return a real number with a Pareto distribution with parameter alpha.
	 */
	public static double pareto(double alpha) {
		return Math.pow(1 - uniform(), -1.0/alpha) - 1.0;
	}

	/**
	 * Return a real number with a Cauchy distribution.
	 */
	public static double cauchy() {
		return Math.tan(Math.PI * (uniform() - 0.5));
	}

	/**
	 * Return a number from a discrete distribution: i with probability a[i].
	 * Precondition: array entries are nonnegative and their sum (very nearly) equals 1.0.
	 */
	public static int discrete(double[] a) {
		double EPSILON = 1E-14;
		double sum = 0.0;
		for (int i = 0; i < a.length; i++) {
			if (a[i] < 0.0) throw new IllegalArgumentException("array entry " + i + " is negative: " + a[i]);
			sum = sum + a[i];
		}
		if (sum > 1.0 + EPSILON || sum < 1.0 - EPSILON)
			throw new IllegalArgumentException("sum of array entries not equal to one: " + sum);

		// the for loop may not return a value when both r is (nearly) 1.0 and when the
		// cumulative sum is less than 1.0 (as a result of floating-point roundoff error)
		while (true) {
			double r = uniform();
			sum = 0.0;
			for (int i = 0; i < a.length; i++) {
				sum = sum + a[i];
				if (sum > r) return i;
			}
		}
	}

	/**
	 * Return a real number from an exponential distribution with rate lambda.
	 */
	public static double exp(double lambda) {
		return -Math.log(1 - uniform()) / lambda;
	}

	/**
	 * Rearrange the elements of an array in random order.
	 */
	public static void shuffle(Object[] a) {
		int N = a.length;
		for (int i = 0; i < N; i++) {
			int r = i + uniform(N-i);     // between i and N-1
			Object temp = a[i];
			a[i] = a[r];
			a[r] = temp;
		}
	}

	/**
	 * Rearrange the elements of a double array in random order.
	 */
	public static void shuffle(double[] a) {
		int N = a.length;
		for (int i = 0; i < N; i++) {
			int r = i + uniform(N-i);     // between i and N-1
			double temp = a[i];
			a[i] = a[r];
			a[r] = temp;
		}
	}

	/**
	 * Rearrange the elements of an int array in random order.
	 */
	public static void shuffle(int[] a) {
		int N = a.length;
		for (int i = 0; i < N; i++) {
			int r = i + uniform(N-i);     // between i and N-1
			int temp = a[i];
			a[i] = a[r];
			a[r] = temp;
		}
	}


	/**
	 * Rearrange the elements of the subarray a[lo..hi] in random order.
	 */
	public static void shuffle(Object[] a, int lo, int hi) {
		if (lo < 0 || lo > hi || hi >= a.length)
			throw new RuntimeException("Illegal subarray range");
		for (int i = lo; i <= hi; i++) {
			int r = i + uniform(hi-i+1);     // between i and hi
			Object temp = a[i];
			a[i] = a[r];
			a[r] = temp;
		}
	}

	/**
	 * Rearrange the elements of the subarray a[lo..hi] in random order.
	 */
	public static void shuffle(double[] a, int lo, int hi) {
		if (lo < 0 || lo > hi || hi >= a.length)
			throw new RuntimeException("Illegal subarray range");
		for (int i = lo; i <= hi; i++) {
			int r = i + uniform(hi-i+1);     // between i and hi
			double temp = a[i];
			a[i] = a[r];
			a[r] = temp;
		}
	}

	/**
	 * Rearrange the elements of the subarray a[lo..hi] in random order.
	 */
	public static void shuffle(int[] a, int lo, int hi) {
		if (lo < 0 || lo > hi || hi >= a.length)
			throw new RuntimeException("Illegal subarray range");
		for (int i = lo; i <= hi; i++) {
			int r = i + uniform(hi-i+1);     // between i and hi
			int temp = a[i];
			a[i] = a[r];
			a[r] = temp;
		}
	}

	/**
	 * Unit test.
	 */
	public static void main(String[] args) {
		int N = Integer.parseInt(args[0]);
		if (args.length == 2) StdRandom.setSeed(Long.parseLong(args[1]));
		double[] t = { .5, .3, .1, .1 };

		StdOut.println("seed = " + StdRandom.getSeed());
		for (int i = 0; i < N; i++) {
			StdOut.format("%2d "  , uniform(100));
			StdOut.format("%8.5f ", uniform(10.0, 99.0));
			StdOut.format("%5b "  , bernoulli(.5));
			StdOut.format("%7.5f ", gaussian(9.0, .2));
			StdOut.format("%2d "  , discrete(t));
			StdOut.println();
		}

		String[] a = "A B C D E F G".split(" ");
		for (String s : a)
			StdOut.print(s + " ");
		StdOut.println();
	}

}