package Supporting;

import java.util.Date;
import DataStructures.Sort;


// Random class
//
// CONSTRUCTION: with (a) no initializer or (b) an integer
//     that specifies the initial state of the generator
//
// ******************PUBLIC OPERATIONS*********************
//     Return a random number according to some distribution:
// int randomInt( )                     --> Uniform, 1 to 2^31-1
// double randomReal( )                 --> Uniform, 0..1
// int randomInt( int low, int high )   --> Uniform low..high
// int poisson( double expectedVal )    --> Poisson
// double negExp( double expectedVal )  --> Negative exponential
//     A related static method:
// void permute( Object [ ] a )         --> Randomly permutate

/**
 * Random number class, using a 31-bit
 * linear congruential generator.
 * Note that java.util contains a class Random,
 * so watch out for name conflicts.
 * @author Mark Allen Weiss
 */
public class Random
{
    private static final int A = 48271;
    private static final int M = 2147483647;
    private static final int Q = M / A;
    private static final int R = M % A;

    /**
     * Construct this Random object with
     * initial state obtained from system clock.
     */
    public Random( )
    {
        this( (int) ( System.currentTimeMillis( ) % Integer.MAX_VALUE ) );
    }

    /**
     * Construct this Random object with
     * specified initial state.
     * @param initialValue the initial state.
     */
    public Random( int initialValue )
    {
        if( initialValue < 0 )
            initialValue += M;

        state = initialValue;
        if( state == 0 )
            state = 1;
    }

    /**
     * Return a pseudorandom int, and change the
     * internal state.
     * @return the pseudorandom int.
     */
    public int randomInt( )
    {
        int tmpState = A * ( state % Q ) - R * ( state / Q );
        if( tmpState >= 0 )
            state = tmpState;
        else
            state = tmpState + M;

        return state;
    }

    /**
     * Return a double in the open range (0,1), and
     * change the internal state.
     * @return the pseudorandom double.
     */
    public double randomReal( )
    {
        return randomInt( ) / ( double ) M;
    }

    /**
     * Return an int in the closed range [low,high], and
     * change the internal state.
     * @param low the minimum value returned.
     * @param high the maximum value returned.
     * @return the pseudorandom int.
     */
    public int randomInt( int low, int high )
    {
        double partitionSize = (double) M / ( high - low + 1 );

        return (int) ( randomInt( ) / partitionSize ) + low;
    }

    /**
     * Return an int using a Poisson distribution, and
     * change the internal state.
     * @param expectedValue the mean of the distribution.
     * @return the pseudorandom int.
     */
    public int poisson( double expectedValue )
    {
        double limit = -expectedValue;
        double product = Math.log( randomReal( ) );
        int count;

        for( count = 0; product > limit; count++ )
            product += Math.log( randomReal( ) );

        return count;
    }

    /**
     * Return an double using a negative exponential
     * distribution, and change the internal state.
     * @param expectedValue the mean of the distribution.
     * @return the pseudorandom double.
     */
    public double negExp( double expectedValue )
    {
        return - expectedValue * Math.log( randomReal( ) );
    }

    /**
     * Randomly rearrange an array.
     * The random numbers used depend on the time and day.
     * @param a the array.
     */
    public static final void permute( Object [ ] a )
    {
        Random r = new Random( );

        for( int j = 1; j < a.length; j++ )
            Sort.swapReferences( a, j, r.randomInt( 0, j ) );
    }

    private int state;
}