// 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
// int random0_1( )                     --> Uniform, 0 to 1
// int randomInt( int low, int high )   --> Uniform low..high
// long randomLong( long low, long high ) --> Uniform low..high
// 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 pseudorandom int, and change the
     * internal state. DOES NOT WORK.
     * @return the pseudorandom int.
     */
    public int randomIntWRONG( )
    {
        return state = ( A * state ) % M;
    }

    /**
     * Return a pseudorandom double in the open range 0..1
     * and change the internal state.
     * @return the pseudorandom double.
     */
    public double random0_1( )
    {
        return (double) randomInt( ) / 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 long 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 long.
     */
    public long randomLong( long low, long high )
    {
        long longVal =  ( (long) randomInt( ) << 31 ) + randomInt( );
        long longM =  ( (long) M << 31 ) + M;

        double partitionSize = (double) longM / ( high - low + 1 );
        return (long) ( longVal / partitionSize ) + low;
    }
    /**
     * 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;

        // Test program
    public static void main( String [ ] args )
    {
        Random r = new Random( 1 );

        for( int i = 0; i < 20; i++ )
            System.out.println( r.randomInt( ) );
    }
}